# -*- 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);