Help me finish the last part of my application? He solves any Countdown Numbers game on Channel 4 by roughly forcing every possible equation.

Question

For those who are not familiar with the game. You are given 8 numbers, and you need to achieve the goal using +, -, / and *.

So, if the goal is 254, and your game numbers are 2, 50, 5, 2, 1, you will correctly answer the question by indicating 5 * 50 = 250. Then 2 + 2 - four. Add this to get 254.

Some game videos are here:

Video 1 Video 2

Basically, I roughly force the game to use, generating all perms of all sizes for numbers and all character Persians and use a basic calculator to calculate the solution.

However, it contains a drawback, because all decisions are solved as follows: (((((1 + 1) * 2) * 3) * 4). He does not rearrange the brackets and causes me a headache.

Therefore, I can not solve every equation. For example, given

Target 16 and numbers 1,1,1,1,1,1,1,1,1 it fails if it should do (1 + 1 + 1 + 1) * (1 + 1 + 1 + 1) = 16.

I would love it if someone could finish it ... in any language.

This is what I wrote so far:

#!/usr/bin/env perl use strict; use warnings; use Algorithm::Permute; # GAME PARAMETERS TO FILL IN my $target = 751; my @numbers = ( '2', '4', '7', '9', '1', '6', '50', '25' ); my $num_numbers = scalar(@numbers); my @symbols = (); foreach my $n (@numbers) { push(@symbols, ('+', '-', '/', '*')); } my $num_symbols = scalar(@symbols); print "Symbol table: " . join(", ", @symbols); my $lst = []; my $symb_lst = []; my $perms = ''; my @perm = (); my $symb_perms = ''; my @symb_perm; my $print_mark = 0; my $progress = 0; my $total_perms = 0; my @closest_numbers; my @closest_symb; my $distance = 999999; sub calculate { my @oprms = @{ $_[0] }; my @ooperators = @{ $_[1] }; my @prms = @oprms; my @operators = @ooperators; #print "PERMS: " . join(", ", @prms) . ", OPERATORS: " . join(", ", @operators); my $total = pop(@prms); foreach my $operator (@operators) { my $x = pop(@prms); if ($operator eq '+') { $total += $x; } if ($operator eq '-') { $total -= $x; } if ($operator eq '*') { $total *= $x; } if ($operator eq '/') { $total /= $x; } } #print "Total: $total\n"; if ($total == $target) { #print "ABLE TO ACCURATELY SOLVE WITH THIS ALGORITHM:\n"; #print "PERMS: " . join(", ", @oprms) . ", OPERATORS: " . join(", ", @ooperators) . ", TOTAL=$total\n"; sum_print(\@oprms, \@ooperators, $total, 0); exit(0); } my $own_distance = ($target - $total); if ($own_distance < 0) { $own_distance *= -1; } if ($own_distance < $distance) { #print "found a new solution - only $own_distance from target $target\n"; #print "PERMS: " . join(", ", @oprms) . ", OPERATORS: " . join(", ", @ooperators) . ", TOTAL=$total\n"; sum_print(\@oprms, \@ooperators, $total, $own_distance); @closest_numbers = @oprms; @closest_symb = @ooperators; $distance = $own_distance; } $progress++; if (($progress % $print_mark) == 0) { print "Tested $progress permutations. " . (($progress / $total_perms) * 100) . "%\n"; } } sub factorial { my $f = shift; $f == 0 ? 1 : $f*factorial($f-1); } sub sum_print { my @prms = @{ $_[0] }; my @operators = @{ $_[1] }; my $total = $_[2]; my $distance = $_[3]; my $tmp = ''; my $op_len = scalar(@operators); print "BEST SOLUTION SO FAR: "; for (my $x = 0; $x < $op_len; $x++) { print "("; } $tmp = pop(@prms); print "$tmp"; foreach my $operator (@operators) { $tmp = pop(@prms); print " $operator $tmp)"; } if ($distance == 0) { print " = $total\n"; } else { print " = $total (distance from target $target is $distance)\n"; } } # look for straight match foreach my $number (@numbers) { if ($number == $target) { print "matched!\n"; } } for (my $x = 1; $x < (($num_numbers*2)-1); $x++) { $total_perms += factorial($x); } print "Total number of permutations: $total_perms\n"; $print_mark = $total_perms / 100; if ($print_mark == 0) { $print_mark = $total_perms; } for (my $num_size=2; $num_size <= $num_numbers; $num_size++) { $lst = \@numbers; $perms = new Algorithm::Permute($lst, $num_size); print "Perms of size: $num_size.\n"; # print matching symb permutations $symb_lst = \@symbols; $symb_perms = new Algorithm::Permute($symb_lst, $num_size-1); while (@perm = $perms->next) { while (@symb_perm = $symb_perms->next) { calculate(\@perm, \@symb_perm); } $symb_perms = new Algorithm::Permute($symb_lst, $num_size-1); } } print "exhausted solutions"; print "CLOSEST I CAN GET: $distance\n"; sum_print(\@closest_numbers, \@closest_symb, $target-$distance, $distance); exit(0); 

Here is an example output:

 [15:53: /mnt/mydocuments/git_working_dir/countdown_solver$] perl countdown_solver.pl Symbol table: +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *, +, -, /, *Total number of permutations: 93928268313 Perms of size: 2. BEST SOLUTION SO FAR: (2 + 4) = 6 (distance from target 751 is 745) BEST SOLUTION SO FAR: (2 * 4) = 8 (distance from target 751 is 743) BEST SOLUTION SO FAR: (4 + 7) = 11 (distance from target 751 is 740) BEST SOLUTION SO FAR: (4 * 7) = 28 (distance from target 751 is 723) BEST SOLUTION SO FAR: (4 * 9) = 36 (distance from target 751 is 715) BEST SOLUTION SO FAR: (7 * 9) = 63 (distance from target 751 is 688) BEST SOLUTION SO FAR: (4 * 50) = 200 (distance from target 751 is 551) BEST SOLUTION SO FAR: (7 * 50) = 350 (distance from target 751 is 401) BEST SOLUTION SO FAR: (9 * 50) = 450 (distance from target 751 is 301) Perms of size: 3. BEST SOLUTION SO FAR: ((4 + 7) * 50) = 550 (distance from target 751 is 201) BEST SOLUTION SO FAR: ((2 * 7) * 50) = 700 (distance from target 751 is 51) BEST SOLUTION SO FAR: ((7 + 9) * 50) = 800 (distance from target 751 is 49) BEST SOLUTION SO FAR: ((9 + 6) * 50) = 750 (distance from target 751 is 1) Perms of size: 4. BEST SOLUTION SO FAR: (((9 + 6) * 50) + 1) = 751 

Answer 1

Here is the Java applet ( source ) and the Javascript version.

Answer 2

The suggestion to use a reversible designation of varnish is excellent.

If you have N = 5 numbers, the pattern

 {num} {num} {ops} {num} {ops} {num} {ops} {num} {ops} 

Anywhere can be from zero to N operations, although the total number will be N-1. You just need to try different placements for numbers and options.

The solution (((1+1)+1)+1)*(((1+1)+1)+1)=16 will be found when trying

 1 1 + 1 + 1 + 1 1 + 1 + 1 + * 

Update . Perhaps this is not so good, as the search above may take 433,701,273,600 attempts. The number was obtained using the following:

 use strict; use warnings; { my %cache = ( 0 => 1 ); sub fact { my ($n) = @_; $cache{$n} ||= fact($n-1) * $n } } { my %cache; sub C { my ($n,$r) = @_; return $cache{"$n,$r"} ||= do { my $i = $n; my $j = $n-$r; my $c = 1; $c *= $i--/$j-- while $j; $c }; } } my @nums = (1,1,1,1,1,1,1,1); my $Nn = 0+@nums ; # Number of numbers. my $No = $Nn-1; # Number of operators. my $max_tries = do { my $num_orderings = fact($Nn); { my %counts; ++$counts{$_} for @nums; $num_orderings /= fact($_) for values(%counts); } my $op_orderings = 4 ** $No; my $op_placements = 1; $op_placements *= C($No, $_) for 1..$No-1; $num_orderings * $op_orderings * $op_placements }; printf "At most %.f tries needed\n", $max_tries;