#!/usr/bin/perl
use strict;

sub permute_init {
    my ($digits) = shift;
    return([ [[], $digits] ]);
}

sub permute_next {
    my ($state) = shift;
    my ($left, $right);
    my ($newleft, $newright);
    my ($val, $item, $i, $done);
        
    $item = pop(@$state);
        
    if (defined($item)) {
        
         ($left, $right) = @$item;
                 
         while (! $done) {
                 
            if (scalar(@$right) > 0) {
                        
                foreach $i (0 .. (scalar(@$right) - 1)) {
                    $newright = [];
                    $newleft = [];
                    @$newright = @$right;
                    @$newleft = @$left;
                    push(@$newleft,
                         splice(@$newright, $i, 1));
                    unshift(@$state,
                         [$newleft, $newright]);
                                                 
                }
             }
             if (scalar(@$left) > 0) {
                 $val = join('', @$left);
                 $done = 1;
             } else {
                 $item = pop(@$state);
                 ($left, $right) = @$item;
             }
          }
      }
      return($state, $val);
          
}

sub main {
    my ($state1, $state2, $val1, $val2);
    my ($digits, $result, $count, $tries);
    my ($tmp, $diff, $len, $bests, $bestdiff);
        
    $digits = [9, 2, 3, 8, 6];
    $result = 5029;

    $| = 1;
    $tries = 0; $bestdiff = 99999;
    $len = scalar(@$digits);
        
    $state1 = &permute_init($digits);
        
    ($state1, $val1) = &permute_next($state1);
    while (defined($val1)) {
        
        $state2 = &permute_init($digits);
                
        ($state2, $val2) = &permute_next($state2);
        while (defined($val2)){
                
            $tmp = $val1 - $val2 - $result;
            $tmp = -$tmp if $tmp < 0;
                        
            if ($tmp == $bestdiff){
                $count++;
                push(@$bests, [$val1, $val2]);
            } elsif ($tmp < $bestdiff){
                $count = 1; 
                                
                $bests = [[$val1, $val2]];
                $bestdiff = $tmp;
                                
            }
                        
            $tries++;
            ($state2, $val2) = &permute_next($state2);
         }
         ($state1, $val1) = &permute_next($state1);
                 
    }
        
print("$tries different possibilities were tested.\n");
print("There are $count answers that are off by $bestdiff\n");

    foreach $tmp (@$bests) {
        ($val1, $val2) = @$tmp;
         printf "%${len}d - %${len}d = %${len}d\n",
                 $val1, $val2, $val1 - $val2;
    }
}

&main