#!/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
[download]