24 game/Solve: Difference between revisions
Content added Content deleted
Underscore (talk | contribs) (Added Haskell.) |
(added perl implementation) |
||
Line 148: | Line 148: | ||
*<code>Permutations[Array[v, n]]</code> returns <math>n!</math> permutations. |
*<code>Permutations[Array[v, n]]</code> returns <math>n!</math> permutations. |
||
Therefore, the size of the working set is <math>64 \cdot n!\, C_{n-1} = 64 \cdot (n-1)!!!! = 64 \frac{(2n-2)!}{(n-1)!}</math>, where <math>n!!!!</math> is the [[wp:quadruple factorial|quadruple factorial]]. It goes without saying that this number increases very fast. For this game, the total is 7680 elements. For higher numbers of inputs, it is {7 680, 107 520, 1 935 360, 42 577 920, 1 107 025 920, ...}. |
Therefore, the size of the working set is <math>64 \cdot n!\, C_{n-1} = 64 \cdot (n-1)!!!! = 64 \frac{(2n-2)!}{(n-1)!}</math>, where <math>n!!!!</math> is the [[wp:quadruple factorial|quadruple factorial]]. It goes without saying that this number increases very fast. For this game, the total is 7680 elements. For higher numbers of inputs, it is {7 680, 107 520, 1 935 360, 42 577 920, 1 107 025 920, ...}. |
||
=={{header|Perl}}== |
|||
Will generate all possible solutions of any given four numbers according to the rules of the [[24 game]]. |
|||
Note: the <code>permute</code> function was taken from [http://faq.perl.org/perlfaq4.html#How_do_I_permute_N_e here] |
|||
<lang Perl># Fischer-Krause ordered permutation generator |
|||
# http://faq.perl.org/perlfaq4.html#How_do_I_permute_N_e |
|||
sub permute (&@) { |
|||
my $code = shift; |
|||
my @idx = 0..$#_; |
|||
while ( $code->(@_[@idx]) ) { |
|||
my $p = $#idx; |
|||
--$p while $idx[$p-1] > $idx[$p]; |
|||
my $q = $p or return; |
|||
push @idx, reverse splice @idx, $p; |
|||
++$q while $idx[$p-1] > $idx[$q]; |
|||
@idx[$p-1,$q]=@idx[$q,$p-1]; |
|||
} |
|||
} |
|||
@formats = ( |
|||
'((%d %s %d) %s %d) %s %d', |
|||
'(%d %s (%d %s %d)) %s %d', |
|||
'(%d %s %d) %s (%d %s %d)', |
|||
'%d %s ((%d %s %d) %s %d)', |
|||
'%d %s (%d %s (%d %s %d))', |
|||
); |
|||
# generate all possible combinations of operators |
|||
@op = qw( + - * / ); |
|||
@operators = map{ $a=$_; map{ $b=$_; map{ "$a $b $_" }@op }@op }@op; |
|||
while(1) |
|||
{ |
|||
print "Enter four integers or 'q' to exit: "; |
|||
chomp($ent = <>); |
|||
last if $ent eq 'q'; |
|||
if($ent !~ m/^[1-9] [1-9] [1-9] [1-9]$/){ print "invalid input\n"; next } |
|||
@n = split / /,$ent; |
|||
permute { push @numbers,join ' ',@_ }@n; |
|||
for(@formats) |
|||
{ |
|||
$format = $_; |
|||
for(@numbers) |
|||
{ |
|||
@n = split; |
|||
for(@operators) |
|||
{ |
|||
@o = split; |
|||
$str = sprintf $format,$n[0],$o[0],$n[1],$o[1],$n[2],$o[2],$n[3]; |
|||
$r = eval($str); |
|||
print "$str\n" if $r == 24; |
|||
} |
|||
} |
|||
} |
|||
}</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |