DZIGA

CityGraph

Store the junctions and streets of a City as an adjacency matrix for easy traversal and lookup. Given a 'City', produce a adj_matrix adjacency matrix dictionary with {endpointA : {endpointB : Street}} as key-value pairs. Also hashes all Junction objects in the city by id (and vice versa) for easy lookup.

Fields

• matrix::Dict{Int,Dict{Int,Street}} a dictionary of dictionaries where the first key is the starting junction and the ending junction, which maps to theStreet` value.
• ids_to_junctions::Dict{Int,Junction} a dictionary of Junctions by junction id
• junctions_to_ids::Dict{Junction,Int} a dictionary of junction ids by Junction

best_first_search(visited::Dict{Int,Int}, city_graph::CityGraph, city::City) ::Vector{Int}

Implements best-first search with a special heuristic function. Returns an itinerary for a single car.

get_best_move(time_elapsed, visited, city, city_graph, current_junction, candidates) ::Pair{Int,Street}

Returns the best move given a set of candidates. Uses a heuristic that rewards previously-unvisited streets.

get_junction_score(junction, street, city_graph, visited, total_duration, time_elapsed) ::Number

Implementation of the heuristic function f(x) that rewards previously-unvisited streets and penalizes time-consuming streets, as described more fully in the final writeup. Returns the heuristic score of input junction.

get_upper_bound(city::City) ::Int

Return the greatest possible distance you can traverse for the given City by summing the longest streets first. The summing concludes once the total duration of the streets exceeds the total duration of the simulation * total number of cars in the City.

greedy_bst(city::City) ::Int

Uses a best-first search to greedily generate a plan that covers the greatest possible distance you can traverse for the given City across all City.nb_cars.

greedy_planner(city::City) ::Int

DZGIA's state of the art planner for the HashCode 2014 challenge. Returns a Solution that greedily covers the greatest possible distance you can traverse for the given City. Calls greedy_bst.