#!/usr/bin/perl -wT

use strict;
use warnings;

use POSIX;
use CGI;

use constant PILES => 3;
use constant DEFAULT_SIZE => 7;

sub position($$$)
{
    my $card = shift;
    my $deck = shift;
    my $size = shift;
    
    my ($pile, $slot, $position);
    
    foreach my $j (0..PILES)
    {
        foreach my $i (0..($size-1))
        {
            if( $deck->[$i + $j*$size] == $card )
            {
                $pile = $j + 1;
                $slot = $i + 1;
                $position = 1 + $i + $j*$size;

                return( ($pile, $slot, $position) );
            }
        }
    }
}

sub piles($$;$)
{
    my $pile = shift;
    my $size = shift;
    my $indx = shift;

    die "Bad pile index $pile" if( $pile < 0 || $pile >= PILES ); 
    die "Bad index $indx" if( defined($indx) && ($indx < 0 || $indx >= $size) );

    if( defined($indx) )
    {
        return( $pile*$size + $indx );
    }
    else
    {
        return( ($pile * $size)..(($pile+1)*$size - 1) );
    }
}

sub run_trick($$$)
{
    my $query = shift;
    my $card  = shift;
    my $size  = shift;

    my @deck = 1..(PILES * $size);
    my @tmp;

    my $middle = ($card >= $size+1  &&  $card <= 2*$size) ? -1 : 0;       # my card always put in second pile
    my ($lastpile,$lastslot,$lastpos) = (0,0,0);

    my @summary = ($query->th({-align=>'right'}, ['Step', 'Pile', 'Position in Pile', 'Position in Deck'] ), );

    my $step = 0;
    my ($pile, $slot, $position) = print_deck( $query, $step, $card, \@deck, $size );

    push @summary, $query->td( {-align=>'right'}, [$step, $pile, $slot, $position] );

    my $maxsteps = $size + 2;

    while( $step < $maxsteps )
    {
        #
        # Sort
        #

        foreach my $i (0..(PILES-1))
        {
            if( grep {$_ == $card} @deck[piles($i,$size)] )
            {
                @tmp = @deck;

                if( PILES == 3 )
                {
                    @deck = (@tmp[piles(($i + 2) % PILES, $size)], @tmp[piles($i,$size)], @tmp[piles(($i + 1) % PILES, $size)]);
                }
                else
                {
                    die "Number of piles not equal 3 not yet supported";
                }

                if( $i == 1 )
                {
                    ++$middle;
                }
                else
                {
                    $middle = 0;
                }

                last;
            }
        }

        last if( $pile == 2 && $lastpile == 2 && $position == $lastpos );
        ($lastpile,$lastslot,$lastpos) = ($pile, $slot, $position) if( $step > 0 );

        #last if( $middle >= 2 );

        #
        # Deal
        #

        @tmp = @deck;

        foreach my $i (reverse(0..($size-1)))
        {
            $deck[piles(0, $size, $i)] = shift(@tmp);
            $deck[piles(1, $size, $i)] = shift(@tmp);
            $deck[piles(2, $size, $i)] = shift(@tmp);
        }

        ($pile, $slot, $position) = print_deck( $query, ++$step, $card, \@deck, $size );
        push @summary, $query->td( {-align=>'right'}, [$step, $pile, $slot, $position] );
    }

    if( $step >= $maxsteps )
    {
        $query->print( $query->span( {-style=>'font-size: large;'}, "Whoa! This just keeps going, and I'm getting tired. Help!\n", $query->br,
                                     "Is there a way that I can figure out your card in this version of the trick?\n" ) );
        $query->print( $query->br, $query->br, $query->span( {-style=>'font-size: large;'}, "Here's what we have so far:\n" ) );
        $query->print( $query->table( {-cellspacing=>12}, $query->Tr( [@summary] ) ), "\n" );
        $query->print( $query->br, "\n" );
        $query->print( $query->span( {-style=>'font-size: large;'}, "Do you see a pattern? Do you think you can make this version of the trick work?\n", $query->br,
                                     "Can you find a way to help me figure out your card? Have my magic powers vanished?\n" ) );
        $query->print( $query->hr, $query->br, "\n" );

        return( undef );
    }
    else
    {
        $query->print( $query->span( {-style=>'font-size: large;'}, "Here's a summary of where your card was at each step (1 = Top):", "\n" ) );
        $query->print( $query->table( {-cellspacing=>12}, $query->Tr( [@summary] ) ), "\n" );
        $query->print( $query->br, "\n" );
        $query->print( $query->hr, $query->br, "\n" );

        $query->print( $query->span( {-style=>'font-size: large;'}, $query->a( {name=>'magic'},"Using my magic powers, I know that your card is: " ),
                                $query->table({-border=>0,-cellpadding=>4,-style=>'display: inline;'},
                                              $query->Tr($query->td({-bgcolor=>'#CCCCCC',-align=>'center'},
                                                      $query->span( {-style=>'color: red; font-size: large; font-weight: bold;'}, ($card < 10) ? "&nbsp;$card&nbsp;" : $card ) ))), "."),
                       $query->br, $query->br, "\n" );
        $query->print( $query->span( {-style=>'font-size: large;'}, "How did I know? I promise I didn't peek. It's just magic ... well, OK, there is a trick to it.\n" ),
                       $query->br, $query->br,
                       $query->span( {-style=>'font-size: large;'}, "Can you explain how I knew which card was yours? How did I, the magician, know when to stop the trick?\n" ),
                       $query->br, $query->hr, "\n" );
        

        return( ($step, position($card, \@deck, $size)) );
    }
}
    

sub print_deck($$$$$)
{
    my $query = shift;
    my $step = shift;
    my $card = shift;
    my $deck = shift;
    my $size = shift;
    
    my @ordinals = ("oops", "on", "the second card from the", "the third card from the", "the fourth card from the", "the fifth card from the", "the sixth card from the", "the seventh card from the", "the eighth card from the", "the ninth card from the", "the tenth card from the", "the eleventh card drom the", );

    my @entries = ( $query->th( {-align=>'center'}, [map {"Pile $_"} 1..PILES] ), );

    my ($pile, $slot, $position) = position( $card, $deck, $size );

    my @cdeck = map { $query->table({-border=>1,-cellpadding=>4}, $query->Tr($query->td({-align=>'center'},($_ < 10) ? "&nbsp;$_&nbsp;" : $_))) } @$deck;
    $cdeck[$position - 1] = $query->table({-border=>1,-cellpadding=>4}, $query->Tr($query->td({-bgcolor=>'#CCCCCC',-align=>'center'},
                             $query->span( {-style=>'color: red; font-size: large; font-weight: bold;'}, ($card < 10) ? "&nbsp;$card&nbsp;" : $card ) )));

    if( $step > 0 )
    {
        $query->print( $query->span( {-style=>'font-size: large;'}, "After step $step ...\n" ) );
    }
    else
    {
        $query->print( $query->span( {-style=>'font-size: large;'}, "At the start ...\n" ) );
    }

    my $ordinal;

    if( $slot > 0 && $slot <= 11 )
    {
        $ordinal = $ordinals[$slot];
    }
    elsif( $slot > 11 )
    {
        $ordinal = ($slot % 10 == 1) ? "${slot}st" : (($slot % 10 == 2) ? "${slot}nd" : (($slot % 10 == 3) ? "${slot}rd" : "${slot}th"));
    }
    else
    {
        die "Improper slot ($slot)";
    }

    $query->print( $query->span( {-style=>'font-size: large;'},
                                 sprintf( "your card is %s top of pile %d, and ", $ordinal, $pile ), $query->br,
                                 sprintf( "when the piles are stacked, your card is number %d, counting from the top of the deck\n<BR>",  $position ) ) );
                             

    if( PILES == 3 )
    {
        foreach my $i (0..($size-1))
        {
            push @entries, $query->td( {-align=>'right'}, [$cdeck[piles(0,$size, $i)], $cdeck[piles(1,$size, $i)], $cdeck[piles(2,$size, $i)]] );
        }
    }
    else
    {
        die "Number of piles not equal 3 not yet supported";
    }

    $query->print( $query->table( {-cellspacing=>12,-cellpadding=>4}, $query->Tr( [@entries] ) ), "\n" );
    $query->print( $query->hr, $query->br, "\n" );

    return( ($pile, $slot, $position) );
}

#
# Main routine
#

my $query = new CGI;

my $size;

my $scratch = $query->param('size');

if( defined $scratch )
{
    $scratch =~ /\A(\d+)\Z/  || die "Improper size specified";

    $size = $1;

    die "That many cards will tire me out!\n" if( $size > 100 );
    die "We need more cards than that to make it a challenge." if( $size < 2 );
}
else
{
    $size = DEFAULT_SIZE;
}

$query->print( $query->header, "\n" );
$query->print( $query->start_html, "\n" );

if( $query->param( 'change' ) )
{
    $query->delete( 'card' );
}

if( $query->param( 'card' ) )
{
    my $scratch;

    $scratch = $query->param('size');

    if( defined $scratch )
    {
        $scratch =~ /\A(\d+)\Z/  || die "Improper size specified";

        $size = $1;

        die "That many cards will tire me out!\n" if( $size > 100 );
    }
        
    $scratch = $query->param( 'card' );
    $scratch =~ /(\d+)/  || die "Improper card specified\n";
    my $card = $1;

    die "Your card must between 1 and " . (PILES * $size) . "\n" if( $card < 1 || $card > PILES * $size );

    $query->print( $query->span( {-style=>'font-size: large;'}, "Here's how the trick goes. I stack the three piles with the pile you chose in the middle." ),
                   $query->br, "\n" );
    $query->print( $query->span( {-style=>'font-size: large;'}, "Then I deal out three piles again. I show you each pile and you tell which pile your card is in."),
                   $query->br, "\n" );
    $query->print( $query->span( {-style=>'font-size: large;'}, "I stack the three piles again like before and keep going until my magic powers tell me to stop."),
                   $query->br, $query->br, "\n" );
    $query->print( $query->span( {-style=>'font-size: large;'}, "Now I'll do the trick and show you the piles every step of the way."),
                    $query->br,
                   $query->span( {-style=>'font-size: large;'}, "Your card will be shown in ", $query->span({-style=>"color: red; background-color: #CCCCCC;"}, "red" ), ", but I am not peeking!\n"),
                   $query->br, $query->br, "\n" );
    $query->print( $query->span( {-style=>'font-size: large;'}, "Scroll down to see how it all works. You will find my magical guess at the ", $query->a( {href=>$query->self_url() . '#magic' }, "end" ), ".\n" ), 
                   $query->br, $query->hr, "\n" );


    run_trick( $query, $card, $size );

    $query->delete( 'card' );
    $query->print( $query->start_form('POST', $query->url()), "\n" );
    $query->print( $query->submit( -name=>'reset', -value=>'Pick another card' ), "\n" );
    $query->print( $query->hidden( 'size', $size ), "\n" );
    $query->print( $query->end_form, "\n" );
}
else
{
    $query->print( $query->span( {-style=>'font-size: large;'}, "I have a magic trick to show you. Do you want to see it?", $query->br, $query->br, "I, the magician, have put " . (PILES*$size) . " cards into 3 piles of " . $size . " cards each. The cards are numbered from 1 to " . (PILES*$size) . ".", $query->br, $query->br, "You, the volunteer, pick one of the cards in one of the piles. Don't show it to me. (And don't worry, I won't peek.)", $query->br, $query->br, "When you have picked your card, push the button below that says 'Do the trick now'." ),
                   $query->br,  $query->br, "\n" );

    $query->print( $query->start_form('POST', $query->url()), "\n" );
    
    my @entries = ( $query->th({-align=>'right'},[map {"Pile $_"} 1..PILES]),  );
    my @h = map { $query->table({-border=>1,-cellpadding=>4}, $query->Tr($query->td({-align=>'center'}, $_))) } $query->radio_group( -name=>'card', -values=>[1..(PILES * $size)], -default=>'-' );

    if( PILES == 3 )
    {
        foreach my $k (0..($size-1))
        {
            push @entries, $query->td( {-align=>'right'}, [@h[($k,$k+$size,$k+2*$size)]] );
        }
    }
    else
    {
        die "Number of piles not equal 3 not yet supported";
    }        
    

    $query->print( $query->table( {-cellspacing=>12}, $query->Tr( [@entries] ) ), "\n", $query->br, "\n" );
    $query->print( $query->submit( -name=>'run', -value=>'Do the trick now' ), "\n" );
    $query->print( $query->br, $query->br, "\n" );
    $query->print( $query->span( {-style=>'font-size: large;'}, "When you have played with the trick using 7 cards per pile, try making a new trick by changing the pile size.\n"), $query->br, "\n" );
    $query->print( $query->span( {-style=>'font-size: large;'}, "Fill in a new pile size here: ", $query->textfield(-name=>'size', -default=>$size, -size=>2, -maxlength=>3), " then press this button ", $query->submit( -name=>'change', -value=>'Change the trick' ), " to set up new piles.\n"), $query->br, $query->br, "\n" );
    $query->print( $query->span( {-style=>'font-size: large;'}, "Try some odd numbers and some even numbers. Be sure to run the trick many times with each pile size ",
$query->br, "to discover if you can make the trick work. If it's a magic trick, it should work every time.\n"), $query->br, $query->br, "\n" );
    $query->print( $query->end_form, "\n" );
}

$query->print( $query->end_html, "\n" );