#!/usr/bin/perl

use strict;
use warnings;

package Jug;

use Moose;

use List::Util qw( min );

has water    => ( is => 'ro', isa => 'Int', default  => 0, );
has capacity => ( is => 'ro', isa => 'Int', required => 1, );

sub clone {
    my $self = shift;
    return __PACKAGE__->new( water => $self->water,
        capacity => $self->capacity );
}

sub fill {
    my $self = shift;

    my $used = $self->capacity - $self->water;
    $self->{water} = $self->capacity;

    return $used;
}

sub empty { shift->{water} = 0 }

sub _add {
    my ( $self, $water ) = @_;

    my $space = $self->capacity - $self->water;
    my $used = min $space, $water;
    $self->{water} += $used;

    return $used;
}

sub add_from {
    my ( $self, $other_jug ) = @_;

    die 'bad jug' unless $other_jug->isa(__PACKAGE__);
    $other_jug->{water} -= $self->_add( $other_jug->water );

    return 0;
}

__PACKAGE__->meta->make_immutable;

package main;

use List::Util qw( first );

$ARGV[0]++;
my @paths = (
    [
        {
            desc => 'starting state',
            jugs => [ map { Jug->new( capacity => $_ ) } @ARGV ],
            used => 0,
        }
    ]
);
$paths[0][0]{target}   = shift @{ $paths[0][0]{jugs} };
$paths[0][0]{strstate} = string_state( $paths[0][0] );
my %seen_states = ( $paths[0][0]{strstate} => 1 );

sub solution {
    return first {
        $_->[-1]->{target}->water == $_->[-1]->{target}->capacity - 1;
    }
    @paths;
}

while ( !solution() ) {

#    @paths = sort { $a->[-1]->{used} <=> $b->[-1]->{used} } @paths;
    my $p          = shift @paths;
    my $last_state = $p->[-1];
    foreach my $next_state ( grep { !$seen_states{ $_->{strstate} }++ }
                                  next_states($last_state) ) {
        push @paths, [ @{$p}, $next_state ];
    }
}

my @solution = @{ solution() };
my $step     = 0;
foreach my $state (@solution) {
    my $strstate = $state->{strstate};
    $strstate =~ s{\A(\d+)/\d+}{$1/T};

    printf "%03d. [ %s ] %s\n", $step++, $strstate, $state->{desc};
}

printf "USED %d units in %d steps\n", $solution[-1]->{used}, $#solution;

exit;

sub string_state {
    my $state = shift;
    return join q{ }, map { $_->water . '/' . $_->capacity } $state->{target},
        @{ $state->{jugs} };
}

sub new_state {
    my ( $state, $desc ) = @_;

    return {
        jugs   => [ map { $_->clone } @{ $state->{jugs} } ],
        target => $state->{target}->clone,
        used   => $state->{used},
        desc   => $desc
    };
}

sub next_states {
    my $state = shift;

    my @out;

    foreach my $jug_index ( 0 .. $#{ $state->{jugs} } ) {
        my $jug = $state->{jugs}->[$jug_index];

        if ( $jug->water < $jug->capacity ) {
            my $next = new_state( $state, "fill jug $jug_index" );
            $next->{used} += $next->{jugs}->[$jug_index]->fill();
            push @out, $next;
        }

        if ( $jug->water > 0 ) {
            my $next;

            foreach my $other_index ( 0 .. $#{ $state->{jugs} } ) {
                next if $other_index == $jug_index;

                $next = new_state( $state,
                    "pour jug $jug_index into jug $other_index" );
                my $other = $next->{jugs}->[$other_index];
                $other->add_from( $next->{jugs}->[$jug_index] );
                push @out, $next;
            }

            $next = new_state( $state, "pour jug $jug_index into target" );
            $next->{target}->add_from( $next->{jugs}->[$jug_index] );
            push @out, $next;

            $next = new_state( $state, "empty jug $jug_index" );
            $next->{jugs}->[$jug_index]->empty();
            push @out, $next;
        }
    }

    $_->{strstate} = string_state($_) for @out;

    return @out;
}