On Friday, January 18, 2002, user who wrote:
uw> 4 numbers (all from 1-9) are given, make a formula(include +-*/()) for
uw> result 24. ex:
uw> 4, 2, 7, 5
uw> (4-2)*(7+5) = 24
uw> shortest/quickest solution?
Some months ago Ton and me happened to be golfing a very similar
problem. The task was to read n+1 numbers from the command line and
make a formula of the first n (using +-*/()) that computes to the last
number. If no formula exists for that target number, the number
closest to the target that can be reached has to be printed. All
source numbers can be used at most once.
This is the code we came up with:
%{$~*=2}=($t=$_)x2for$~=s''map{eval{$p>$;or$;%$p||8346while($;
,$Q)=each%$_}while($p,$P)=each%{$_&~$a?b:$a-$_}}a/(++$a<$~)..$
~until$$t'/s/\d/(*2x=\\(22a{2x=2;$&2p}||="(2Q$&2P)")),/g,@ARGV
;y|2-9|$*-0|;eval;$j=$t+($;=$|---$;)until$$j;print$$j,"=$j$/"
$ perl numberquiz.pl 2 4 5 7 24
((7+5)*2)=24
$ perl numberquiz.pl 2 4 8 19
((8*2)+4)=20
If anyone wants to try decrypting it, it uses some dynamic
programming style of approach:
For each subset A of the source numbers
For each 2 smaller subsets B,C that combine to A
Numbers reachable with A :=
[num. reachable with B] [+-*/] [num. rechable with C]
The numbers reachable via B and C are guaranteed to be
calculated before they are accessed because the subsets are
walked in a bottom up fashion.
The script can be modified to not stop early when the target number is
found without all source numbers being used. That way, solutions that
use all source numbers should be preferred, but if there is no
solution that uses all the numbers, a different one will be printed.
To get this behaviour, s'until$$t'while a' in the above code (though
this is probably not optimally short).
- Karsten
