Team Unagi's repository for ICFPC 2019
Brief directions for judges to build/run the solution
Requirements
Solving tasks
cd wata
cargo run --release task.desc "" > task.sol # Buying nothing
cargo run --release task.desc "CC" > task.sol # Buying CC
Solving puzzles
cd puzzle
cargo run task.cond task.desc
Deciding what to buy
cd knapsack
cargo run --bin main knapsack-in.txt 748091 > knapsack-out.txt
Each line of knapsack-in.txt
should contain problem ID, buy string, solution ID, and time, which are separated by commas. For example:
prob-002,,29259,381
prob-002,B,50721,356
prob-002,C,59200,224
prob-002,CB,51232,226
prob-003,,34881,210
prob-003,B,52255,210
prob-003,C,47656,128
prob-003,CB,52766,128
...
It outputs selected solutions to be submitted to stdout.
Description of the solution approach
Solving tasks
- A single-worker solution is constructed by the left-hand rule (https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower). See
chokudai/src/lib.rs
.
- An initial sequence is prepared, which collects boosters and replicates workers. It uses greedy algorithms and dynamic programming. See
common/src/{bootstrap.rs, bootstrap_clone.rs}
.
- Given them, multi-worker solution is created by splitting the single-worker solution and concatenating to the initial sequence. See
wata/src/main.rs
.
- Local refinement is applied to the solution. It tries to improve the solution by removing some parts of the solution and reconstructing actions to perform the same things with shorter steps. It uses depth-first and breadth-first searches. See
common/src/local_optimization.rs
.
Solving puzzles
- Our puzzle solvers heavily relies on narrow paths for satisfying point constraints.
- It then adjusts the area and number of vertices to satisfy the area and vertices constraings.
- See
puzzle/src/*.rs
.
Deciding what to buy
Feedback about the contest
- The conditions of mining puzzles seem too loose, even at last rounds. Top teams could solve all mining puzzles and performance of puzzle solvers did not matter. In additoin, there was little incentive to create interesting and/or hard tasks for mining puzzles.
Self-nomination for judges’ prize
Our mining puzzle solver creates beautiful tasks. Please see 83.png. It illustrates our task that is officially selected for block 83.