Countdown: Difference between revisions
m
→{{header|11l}}: Void
m (→{{header|Prolog}}: Code alignement) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (5 intermediate revisions by 5 users not shown) | |||
Line 30:
The brute force algorithm is quite obvious. What is more interesting is to find some optimisation heuristics to reduce the number of calculations. For example, a rather interesting computational challenge is to calculate, as fast as possible, all existing solutions (that means 2'764'800 operations) for all possible games (with all the 13'243 combinations of six numbers out of twenty-four for all 898 possible targets between 101 and 999).
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V best = 0
V best_out = ‘’
V target = 952
V nbrs = [100, 75, 50, 25, 6, 3]
F sol(target, nbrs, out = ‘’) -> Void
I abs(target - :best) > abs(target - nbrs[0])
:best = nbrs[0]
:best_out = out
I target == nbrs[0]
print(out)
E I nbrs.len > 1
L(i1) 0 .< nbrs.len - 1
L(i2) i1 + 1 .< nbrs.len
V remains = nbrs[0 .< i1] [+] nbrs[i1 + 1 .< i2] [+] nbrs[i2 + 1 ..]
V (a, b) = (nbrs[i1], nbrs[i2])
I a > b
swap(&a, &b)
V res = b + a
V op = b‘ + ’a‘ = ’res‘ ; ’
sol(target, res [+] remains, out‘’op)
I b != a
res = b - a
op = b‘ - ’a‘ = ’res‘ ; ’
sol(target, res [+] remains, out‘’op)
I a != 1
res = b * a
op = b‘ * ’a‘ = ’res‘ ; ’
sol(target, res [+] remains, out‘’op)
I b % a == 0
res = Int(b / a)
op = b‘ / ’a‘ = ’res‘ ; ’
sol(target, res [+] remains, out‘’op)
sol(target, nbrs)
I best != target
print(‘Best solution ’String(best))
print(best_out)</syntaxhighlight>
{{out}}
<pre>
100 + 6 = 106 ; 106 * 75 = 7950 ; 7950 * 3 = 23850 ; 23850 - 50 = 23800 ; 23800 / 25 = 952 ;
100 + 6 = 106 ; 106 * 3 = 318 ; 318 * 75 = 23850 ; 23850 - 50 = 23800 ; 23800 / 25 = 952 ;
100 + 6 = 106 ; 75 * 3 = 225 ; 225 * 106 = 23850 ; 23850 - 50 = 23800 ; 23800 / 25 = 952 ;
100 + 3 = 103 ; 103 * 75 = 7725 ; 7725 * 6 = 46350 ; 46350 / 50 = 927 ; 927 + 25 = 952 ;
100 + 3 = 103 ; 103 * 6 = 618 ; 618 * 75 = 46350 ; 46350 / 50 = 927 ; 927 + 25 = 952 ;
100 + 3 = 103 ; 75 * 6 = 450 ; 450 * 103 = 46350 ; 46350 / 50 = 927 ; 927 + 25 = 952 ;
100 + 3 = 103 ; 75 * 6 = 450 ; 450 / 50 = 9 ; 103 * 9 = 927 ; 927 + 25 = 952 ;
75 * 6 = 450 ; 450 / 50 = 9 ; 100 + 3 = 103 ; 103 * 9 = 927 ; 927 + 25 = 952 ;
75 * 6 = 450 ; 100 + 3 = 103 ; 450 * 103 = 46350 ; 46350 / 50 = 927 ; 927 + 25 = 952 ;
75 * 6 = 450 ; 100 + 3 = 103 ; 450 / 50 = 9 ; 103 * 9 = 927 ; 927 + 25 = 952 ;
75 * 3 = 225 ; 100 + 6 = 106 ; 225 * 106 = 23850 ; 23850 - 50 = 23800 ; 23800 / 25 = 952 ;
</pre>
=={{header|J}}==
Line 118 ⟶ 175:
</pre>
=={{header|Nim}}==
Here is, with some minor modifications, a program I already wrote to solve this game. It gets the six values and the target value from the command line.
The program uses brute force, but no recursion, to find one of the best solutions.
<syntaxhighlight lang="Nim">import std/[os, strutils, tables]
type
Operator = enum opAdd = "+", opSub = "-", opMul = "×", opDiv = "/", opNone = ""
Operation = tuple[op1, op2: int; op: Operator; r: int]
func result(values: seq[int]; target: int): tuple[val: int; ops: seq[Operation]] =
type Results = Table[seq[int], seq[Operation]]
var results: Results
results[values] = @[]
var terminated = false
while not terminated:
terminated = true
var next: Results
for vals, ops in results:
var v1 = vals
for i1, val1 in vals:
v1.delete i1
var v2 = v1
for i2, val2 in v1:
v2.delete i2
for op in opAdd..opNone:
let newVal = case op
of opAdd: val1 + val2
of opSub: (if val1 > val2: val1 - val2 else: 0)
of opMul: val1 * val2
of opDiv: (if val1 mod val2 == 0: val1 div val2 else: 0)
of opNone: val1
if newVal > 0:
v2.add newVal
if v2.len > 1: terminated = false
let newOps = if op != opNone: ops & (val1, val2, op, newVal) else: ops
if v2 notin next or newOps.len < next[v2].len:
next[v2] = newOps
discard v2.pop
v2 = v1
v1 = vals
results = move next
var best = int.high
var bestOps: seq[Operation]
for vals, ops in results:
let val = vals[0]
if val == target: return (val, ops)
if abs(val - target) < abs(best - target):
best = val
bestOps = ops
result = (best, bestOps)
let params = commandLineParams()
if params.len != 7:
quit "Six values + the target value are expected.", QuitFailure
var values: seq[int]
for param in params:
var val: int
try:
val = parseInt(param)
if val <= 0:
raise newException(ValueError, "")
except ValueError:
quit "Wrong value: " & param, QuitFailure
values.add val
let target = values.pop()
let (val, ops) = result(values, target)
echo "Target value: ", target
echo "Nearest value computed: ", val
echo "Operations:"
for (op1, op2, op, r) in ops:
echo " ", op1, " ", op, " ", op2, " = ", r
</syntaxhighlight>
{{out}}
Using command <code>./countdown 3 6 25 50 75 100 952</code>, we get the following result:
<pre>Target value: 952
Nearest value computed: 952
Operations:
6 + 100 = 106
3 × 75 = 225
106 × 225 = 23850
23850 - 50 = 23800
23800 / 25 = 952
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl" line>
use v5.36;
use builtin 'indexed';
use experimental qw(builtin for_list);
sub countdown ($target, @numbers) {
return 0 if 1 == scalar(@numbers);
for my ($n0k,$n0v) (indexed @numbers) {
my @nums1 = @numbers;
splice(@nums1,$n0k,1);
for my($n1k,$n1v) (indexed @nums1) {
my @nums2 = @nums1;
splice(@nums2,$n1k,1);
my @numsNew;
if ($n1v >= $n0v) {
@numsNew = @nums2;
push @numsNew, my $res = $n1v + $n0v;
if ($res == $target or countdown($target, @numsNew)) {
say "$res = $n1v + $n0v" and return 1
}
if ($n0v != 1) {
@numsNew = @nums2;
push @numsNew, my $res = $n1v * $n0v;
if ($res == $target or countdown($target, @numsNew)) {
say "$res = $n1v * $n0v" and return 1
}
}
if ($n1v != $n0v) {
@numsNew = @nums2;
push @numsNew, my $res = $n1v - $n0v;
if ($res == $target or countdown($target, @numsNew)) {
say "$res = $n1v - $n0v" and return 1
}
}
if ($n0v != 1 and 0==($n1v%$n0v)) {
@numsNew = @nums2;
push @numsNew, my $res = int($n1v / $n0v);
if ($res == $target or countdown($target, @numsNew)) {
say "$res = $n1v / $n0v" and return 1
}
}
}
}
}
return 0
}
my @numbersList = ([3,6,25,50,75,100], [100,75,50,25,6,3], [8,4,4,6,8,9]);
my @targetList = <952 952 594>;
for my $i (0..2) {
my $numbers = $numbersList[$i];
say "Using : ", join ' ', @$numbers;
say "Target: ", my $target = $targetList[$i];
say "No exact solution found" unless countdown($target, @$numbers);
say '';
}
</syntaxhighlight>
{{out}}
<pre>
Using : 3 6 25 50 75 100
Target: 952
952 = 23800 / 25
23800 = 23850 - 50
23850 = 225 * 106
106 = 100 + 6
225 = 75 * 3
Using : 100 75 50 25 6 3
Target: 952
952 = 23800 / 25
23800 = 23850 - 50
23850 = 7950 * 3
7950 = 106 * 75
106 = 100 + 6
Using : 8 4 4 6 8 9
Target: 594
594 = 66 * 9
66 = 64 + 2
64 = 16 * 4
2 = 6 - 4
16 = 8 + 8
</pre>
=={{header|Phix}}==
Line 526 ⟶ 760:
218.0 ms
</pre>
=={{header|Raku}}==
{{trans|Wren}}
<syntaxhighlight lang="raku" line># 20221021 Raku programming solution
sub countdown ($target, @numbers) {
return False if @numbers.elems == 1;
for @numbers.kv -> \n0k,\n0v {
(my @nums1 = @numbers).splice(n0k,1);
for @nums1.kv -> \n1k,\n1v {
(my @nums2 = @nums1).splice(n1k,1);
if n1v >= n0v {
(my @numsNew = @nums2).append: my $res = n1v + n0v;
if ($res == $target or countdown($target, @numsNew)) {
say "$res = ",n1v,' + ',n0v andthen return True
}
if n0v != 1 {
(my @numsNew = @nums2).append: my $res = n1v * n0v;
if ($res == $target or countdown($target, @numsNew)) {
say "$res = ",n1v,' * ',n0v andthen return True
}
}
if n1v != n0v {
(my @numsNew = @nums2).append: my $res = n1v - n0v;
if ($res == $target or countdown($target, @numsNew)) {
say "$res = ",n1v,' - ',n0v andthen return True
}
}
if n0v != 1 and n1v %% n0v {
(my @numsNew = @nums2).append: my $res = n1v div n0v;
if ($res == $target or countdown($target, @numsNew)) {
say "$res = ",n1v,' / ',n0v andthen return True
}
}
}
}
}
return False
}
my @allNumbers = < 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 25 50 75 100 >;
my @numbersList = <3 6 25 50 75 100> , <100 75 50 25 6 3>,
<8 4 4 6 8 9> , @allNumbers.pick(6);
my @targetList = 952, 952, 594, (101..1000).pick;
for (0..^+@numbersList) -> \i {
say "Using : ", my @numbers = |@numbersList[i];
say "Target: ", my $target = @targetList[i];
say "No exact solution found" unless countdown $target, @numbers;
say()
}</syntaxhighlight>
{{out}}
<pre>Using : [3 6 25 50 75 100]
Target: 952
952 = 23800 / 25
23800 = 23850 - 50
23850 = 225 * 106
106 = 100 + 6
225 = 75 * 3
Using : [100 75 50 25 6 3]
Target: 952
952 = 23800 / 25
23800 = 23850 - 50
23850 = 7950 * 3
7950 = 106 * 75
106 = 100 + 6
Using : [8 4 4 6 8 9]
Target: 594
594 = 66 * 9
66 = 64 + 2
64 = 16 * 4
2 = 6 - 4
16 = 8 + 8
Using : [100 9 50 2 9 8]
Target: 599
599 = 590 + 9
590 = 59 * 10
10 = 8 + 2
59 = 109 - 50
109 = 100 + 9</pre>
=={{header|Rebol}}==
Line 629 ⟶ 946:
{{trans|Quorum}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||