# -*- mode: cperl6; -*- # 2011 Perl 6 Coding Contest # Edgar GonzÃ lez i Pellicer use v6; use Grooves; use Heap; # Piece movement string sub piece-movement-str(Piece \$p, Int \$offset) { return "{\$p.groove}[{(\$p.start .. \$p.end).join} -> " ~ "{((\$p.start .. \$p.end) <<+>> \$offset).join}]"; } # State class State { has @.movements; has \$.board; } # A* search # If the heuristic is optimistic, the solution found has minimal cost # (i.e., number of movements) sub a-star(Board \$start) { # Is it final? return if \$start.is-final; # State heap my \$states = MinHeap.new; # Insert the starting one \$states.push(\$start.heuristic-cost, State.new(board => \$start)); # Visited my %visited = \$start => 1; # Not empty? while !\$states.empty { # Get the state with the lowest cost so far my \$cur = \$states.top.value; \$states.pop; # For each piece and movement for \$cur.board.pieces -> \$p { for \$cur.board.piece-movements(\$p) -> \$m { # Make the move my \$new-board = \$cur.board.move-piece(\$p, \$m); # Is it resulting board already visited? my \$hash = \$new-board.hash-str; if !%visited{\$hash} { # Mark it %visited{\$hash} = 1; # New movement list my @new-movements = \$cur.movements; @new-movements.push(piece-movement-str(\$p, \$m)); # Is it final? return @new-movements if \$new-board.is-final; # New state my \$new-state = State.new(movements => @new-movements, board => \$new-board); # Insert it into the heap \$states.push(@new-movements.elems + \$new-board.heuristic-cost, \$new-state); } } } } # Nothing found die "No solution."; } # Main multi sub MAIN() { # Read the starting board my Board \$start = read-board(\$*IN); # Solve it my @movements = a-star(\$start); .say for @movements; # Exception CATCH { # Show exception message .say; # Don't rethrow default {} } } # Call main # @maybe This should be done automatically? MAIN(|@*ARGS);