`#!/usr/bin/perl
use strict;
use warnings;
while (<DATA>) {
chomp;
my $level = $_;
my @work = {board => $level, hits => 9};
my $avail_hits = possible_hits($level);
my %stat;
while (@work) {
my $item = pop @work;
my ($board, $hits) = @{$item}{qw/board hits/};
$hits--;
for my $pos (possible_hits($board)) {
my $new_board = play_board($board, $pos);
# No need to continue if we have won
if (game_won($new_board)) {
$stat{$hits}++;
next;
}
# Not able to continue if we have lost
if (! $hits) {
$stat{lost}++;
next;
}
# We need to continue
push @work, {board => $new_board, hits => $hits};
}
}
print join(',',
$level,
$avail_hits,
($stat{lost} || 0),
map {join(':', (9 - $_), ($stat{$_} || 0))} reverse 0 .. 8
), "\n";
}
sub game_won {
my ($board) = @_;
return $board =~ /^0{30}$/;
}
sub possible_hits {
my ($board) = @_;
my @possible;
for (0 .. length($board) - 1) {
push @possible, $_ if substr($board, $_, 1) ne '0';
}
return wantarray ? @possible : scalar @possible;
}
sub play_board {
my ($board, $pos) = @_;
hit(\$board, $pos);
return $board;
}
sub hit {
my ($board, $pos) = @_;
# Ran off the edge of the board
return if $pos < 0 || substr($$board, $pos, 1) eq '0'; # not sure
+2nd instance can ever happen
my $val = substr($$board, $pos, 1);
$val--;
substr($$board, $pos, 1, $val);
if (! $val) {
hit($board, n_neighbor($board, $pos));
hit($board, s_neighbor($board, $pos));
hit($board, e_neighbor($board, $pos));
hit($board, w_neighbor($board, $pos));
}
}
sub n_neighbor {
my ($board, $pos) = @_;
while (1) {
$pos -= 5;
last if $pos < 0;
return $pos if substr($$board, $pos, 1) ne '0';
}
return -1;
}
sub s_neighbor {
my ($board, $pos) = @_;
while (1) {
$pos += 5;
last if $pos > 29;
return $pos if substr($$board, $pos, 1) ne '0';
}
return -1;
}
sub e_neighbor {
my ($board, $pos) = @_;
my $min_val = int($pos / 5) * 5;
while (1) {
$pos -= 1;
last if $pos < $min_val;
return $pos if substr($$board, $pos, 1) ne '0';
}
return -1;
}
sub w_neighbor {
my ($board, $pos) = @_;
my $max_val = (int($pos / 5) * 5) + 4;
while (1) {
$pos += 1;
last if $pos > $max_val;
return $pos if substr($$board, $pos, 1) ne '0';
}
return -1;
}
__DATA__
101010000010101000000000010101
000000000000100000000000000000
211000000000000000000000000000
432114010304403414114124232323
`

It takes too long to figure out all the ways to play a game. I am thinking I need to lower the number of possible moves and limit how much time can be spent playing a single game. What do you think?