Codingteam's submission for ICFPC-2019
How to run this
You'll need the Scala build tool, sbt, and the Scala compiler. We used Scala 2.12.8.
To execute the solver on a particular problem, run this:
$ sbt "run --problem-file path/to/tasks/prob-103.desc"
To execute the solver on all problems in a directory, run this:
$ sbt "run --directory path/to/tasks/ --minutes 10 --cores 8"
--minutes
dictates a timeout after which the solver gives up on the problem
and moves on; defaults to 10 minutes. --cores
is how many tasks are solved
simultaneously; defaults to number of virtual processors in the machine.
The solutions (.sol files) will be stored right next to the tasks. If a solution
already exists, it will only be overwritten if we got a shorter one. (master
branch has the correct logic for this; earlier branches might compare existing
file's size to new solution's length, which doesn't work in presence of actions
with arguments, e.g. Shift or Attach).
What approaches are used
Code-wise, there is a single solver — src/main/scala/org/codingteam/icfpc2019/Solver.scala. However, it was tweaked and twisted with every new commit, and re-ran periodically to obtain new—but not always better—solutions. As a result, it's hard to point at a particular file and say "here's our implementation of idea X". Instead, we'll have to make do with some general, handy-wavy descriptions.
Obstacles are turned into collections of cells with AWT. We literally paint them on a virtual canvas and read back the pixels that each correspond to a cell.
Most of the solutions were generated by our greedy solver, that tries to maximize the number of wrapped cells. To achieve that, it evaluates movements in all four directions and turning either left or right. To choose between alternatives with the same number of wrapped cells, the solver uses Lee wavefront algorithm to find the closest unwrapped cell, and moves to that. Ties between those are broken by specifics of Scala's list sorting.
The rest of the solutions were generated by A*-degraded-into-DFS. Its cost function is a tuple:
( wrapped_cell_count + number_of_boosters_used_so_far * 50
, - distance_to_closest_unwrapped_cell
, - solution_length )
Those tuples are compared lexicographically—by their first component, with ties broken by the second component, with ties in that broken by the third component. The priority queue in A* returns the element with the largest value of the tuple.
To give this DFS some intelligence, we game the node generation a bit. The solver always considers moves in all four directions, but only considers turns if they wrap new cells. Moreover, it looks one turn ahead after enabling the drill or attaching some wheels, to make A* see the delayed gratification of those actions.
Teleports, drills, wheels—the solver tries them all on every turn, but most of these tries don't bring any benefit, and disappear into the depths of the priority queue. Same goes for extra manipulators, which are attached to every possible extremity at every turn.
We also tried to generate random solutions, but abandoned the idea when we saw that the results are measured in megabytes. Hat tip to that smart programmer who wrote the evaluation server—we didn't get any crashes, our solutions simply weren't evaluated. Nice work!
Thanks for a nice contest! Not all of us appreciated the mining challenge, but oh well; that's still days well spent.
With our best regards, Codingteam (in no particular order):
- Akon32
- Portnov Ilya
- Alexander Batischev (report (in Russian))
- Friedrich von Never (report (in Russian))
- Hagane