#!/usr/bin/perl -w
########################
#
#   Place the digits 1 through 9 in the *'s such that
#
#       */** + */** + */** = 1 
#
#   (From Technology Review's puzzle corner, Oct 2001)
#
#  The approach here is just a brute force recursive search on 
#  all permutations of 1..9, using the CPAN Algorithm::FastPermute
#  to loop over the permutations.
#
#  - Jim Mahoney
#########################
use strict;
use Time::HiRes qw( time );
use Algorithm::FastPermute qw( permute );

our $count = 0; # how many combinations were examined? (global variable)

# Tell a web browser what to do with this programs output.
print "Content-type: text/plain\n\n";

# Talk to the nice people out there.
print " Looking for digits 1..9 to solve */** + */** + */** = 1 \n\n";

# Save the current time so we can see how long this takes to run.
my $startTime = time();

# And perform the calculation.
my @p = 1..9;
permute { display(@p) if sum(@p) == 1 } @p;

my $endTime = time();
my $timeString = sprintf("%.3g", $endTime-$startTime );

print "
 Done.  Elapsed time = $timeString seconds.
 Number of permutations examined = $count 
";

# -- subroutines -----------------------------------

sub sum {
  my @n = @_;
  $count++;      # Increment global number of permutations examined.
  return fraction(@n[0..2]) + fraction(@n[3..5]) + fraction(@n[6..8]);
}

sub fraction {
  my ($a,$b,$c) = @_;
  return $a/( 10*$b + $c );
}

sub display {
  print " $_[0]/$_[1]$_[2] + $_[3]/$_[4]$_[5] + $_[6]/$_[7]$_[8] = 1 \n";
}