Rosetta Code

Countdown: Difference between revisions

Page Discussion

Countdown (view source)

Revision as of 08:47, 7 May 2024

52,309 bytes added ,  16 days ago
m
→‎{{header|11l}}: Void
(→‎{{header|Quorum}}: Replace french variables names with english variables names)
 
(28 intermediate revisions by 9 users not shown)
Line 28:
;Extra challenge:
 
The brute force algorithm is quite obvious. What is more interesting areis theto 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 12013'867'208243 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}}==
Brute force implementation:
<syntaxhighlight lang=J>deck=: (25*1+i.4),2#1+i.10
deal=: 6&((?#){])@deck
targ=: 101+?@899
Pi=: ,~((#:I.@,)</~)i.
Va=: {{
ok=. I#~(= 1>.>.)u&".&>/y{~|:I=. Pi N=.#y
(N-1){."1 (y{~ok-."1~i.N),.<@(u expr)"1 ok{y
}}
Pa=: {{ if. 1<#;:y do. '(',y,')' else. y end. }}
expr=: {{ (Pa A),(;u`''),Pa B['A B'=.y }}
arith=: [:; <@(+Va, -Va, *Va, %Va,(-Va, %Va)@|.)"1
all=: {{ A#~x=".@>A=.~.,arith^:5 ":each y}}
 
task=: {{
echo 'terms: ',":c=. /:~ deal ''
echo 'target: ',":t=. targ ''
echo '#solutions: ',":#a=. t all c
echo 'for example: ',;{.a
}}</syntaxhighlight>
 
Examples:
<syntaxhighlight lang=J> task''
terms: 2 3 3 6 9 50
target: 476
#solutions: 77
for example: (9*(3+50))-(6-(2+3))
task''
terms: 1 4 6 7 8 9
target: 657
#solutions: 75
for example: 9*(8+((1+4)*(6+7)))
task''
terms: 4 7 8 9 10 10
target: 300
#solutions: 495
for example: (10+(9*10))*((4+7)-8)</syntaxhighlight>
 
=={{header|Julia}}==
Brute force with a somewhat narrowed search space.
<syntaxhighlight lang="julia">using Combinatorics
 
const max_pick = 6
const fulllist = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100]
const oplist = [+, +, +, +, +, +, -, -, -, -, -, -, *, *, *, *, *, *, ÷, ÷, ÷, ÷, ÷, ÷]
 
 
function single_countdown_game(ilist, target)
candidates = [(0, "")]
for i in 1:max_pick, arr in permutations(ilist, i), ops in multiset_permutations(oplist, length(arr) - 1)
candidate = arr[1]
if !isempty(ops)
for (j, op) in pairs(ops)
((op == ÷) && candidate % arr[j + 1] != 0) && @goto nextops
candidate = op(candidate, arr[j + 1])
end
end
if abs(candidate - target) <= abs(candidates[1][1] - target)
if abs(candidate - target) < abs(candidates[1][1] - target)
empty!(candidates)
end
sops = push!(map(string, ops), "")
push!(candidates, (candidate, prod(" $(arr[i]); $(sops[i])" for i in eachindex(arr))))
end
@label nextops
end
return unique(candidates)
end
 
for (terms, target) in [([2, 3, 3, 6, 9, 50], 476), ([1, 4, 6, 7, 8, 9], 657), ([4, 7, 8, 9, 10, 10], 300)]
sols = single_countdown_game(terms, target)
println("$(length(sols)) solutions for terms $terms, target $target.")
println(" Example: $(sols[1][2])= $(sols[1][1])\n")
end
</syntaxhighlight>{{out}}
<pre>
24 solutions for terms [2, 3, 3, 6, 9, 50], target 476.
Example: 3; + 50; * 9; + 2; - 3; = 476
 
42 solutions for terms [1, 4, 6, 7, 8, 9], target 657.
Example: 4; + 6; * 8; - 7; * 9; = 657
 
223 solutions for terms [4, 7, 8, 9, 10, 10], target 300.
Example: 7; - 4; * 10; * 10; = 300
</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}}==
Here's one I already had, cleaned up a bit:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo/Countdown.exw
--
-- solves the numbers game from countdown.
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">ops</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"+-*/"</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">ADD</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">SUB</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">MUL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">DIV</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- original numbers &lt;-&gt; partial sums</span>
<span style="color: #000000;">expression</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- the operations tried so far</span>
<span style="color: #000000;">solution</span> <span style="color: #000080;font-style:italic;">-- (a/best snapshot of expression)</span>
<span style="color: #004080;">int</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- n+1 means no solution yet found</span>
<span style="color: #000000;">maxlev</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- recursion limit (5, drops as solns found)</span>
<span style="color: #000000;">near</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- nearest answer (in solution) out by this</span>
<span style="color: #000000;">lenn</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- length of "" ""</span>
<span style="color: #000000;">target</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">countdown</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--
-- Recursive search - takes two numbers, performs an op (storing result), checks
-- for target value, and calls itself. All solutions are stored, to find shortest,
-- so that, for example, 100+1 is chosen instead of 100+(75/25)-1-1.
-- Optimizations are made to ensure commutative operations are only performed one
-- way round, division is only performed when no remainder, and */1 are skipped.
--</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">sti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- speedwise/save</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sti</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">stj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- ""</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">j</span> <span style="color: #008080;">and</span> <span style="color: #000000;">stj</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">operation</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ADD</span> <span style="color: #008080;">to</span> <span style="color: #000000;">DIV</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">operation</span><span style="color: #0000FF;"><</span><span style="color: #000000;">DIV</span> <span style="color: #008080;">or</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sti</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stj</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">operation</span><span style="color: #0000FF;"><</span><span style="color: #000000;">MUL</span> <span style="color: #008080;">or</span> <span style="color: #000000;">stj</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">sti</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">stj</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- worth doing...</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sti</span>
<span style="color: #008080;">switch</span> <span style="color: #000000;">operation</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">ADD</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">stj</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">SUB</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">stj</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">MUL</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">stj</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">DIV</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">stj</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ci</span>
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000080;font-style:italic;">/* store operands and operator */</span>
<span style="color: #000000;">expression</span><span style="color: #0000FF;">[</span><span style="color: #000000;">level</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">sti</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ops</span><span style="color: #0000FF;">[</span><span style="color: #000000;">operation</span><span style="color: #0000FF;">],</span><span style="color: #000000;">stj</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ci</span><span style="color: #0000FF;">}</span>
<span style="color: #000080;font-style:italic;">-- check for solution</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ci</span><span style="color: #0000FF;">==</span><span style="color: #000000;">target</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;"><</span><span style="color: #000000;">len</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">/* solution is shortest so far - store it */</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">level</span>
<span style="color: #000000;">maxlev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">near</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">solution</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expression</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000080;font-style:italic;">--store closest?</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">offby</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">target</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ci</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">offby</span><span style="color: #0000FF;"><</span><span style="color: #000000;">near</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">near</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">offby</span>
<span style="color: #000000;">lenn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">level</span>
<span style="color: #000000;">solution</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expression</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- if not at required level, recurse</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;"><</span><span style="color: #000000;">maxlev</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">countdown</span><span style="color: #0000FF;">(</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- undo</span>
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sti</span>
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stj</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">list</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">int</span> <span style="color: #000000;">dest</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">maxlev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">5</span>
<span style="color: #000000;">near</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dest</span>
<span style="color: #000000;">target</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dest</span>
<span style="color: #000000;">chosen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">countdown</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">/* process solution into printable form */</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">off</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"exact"</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">off</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"off by %d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">near</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lenn</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">soln</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%d%c%d=%d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">solution</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">len</span><span style="color: #0000FF;">]}),</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Target %d from %18v: %s (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">dest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">list</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">,</span><span style="color: #000000;">off</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">75</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span><span style="color: #000000;">737</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">75</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">},</span><span style="color: #000000;">952</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">75</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span><span style="color: #000000;">952</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span><span style="color: #000000;">203</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span><span style="color: #000000;">465</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span><span style="color: #000000;">241</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span><span style="color: #000000;">824</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">75</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span><span style="color: #000000;">125</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">},</span><span style="color: #000000;">594</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">({</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span><span style="color: #000000;">363</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--test(shuffle(tagset(10)&tagset(10)&tagstart(25,4,25))[1..6],100+rand(899))</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Target 737 from {75,50,25,100,8,2}: 75/25=3, 50-3=47, 100-2=98, 98*8=784, 784-47=737 (exact)
Target 952 from {3,6,25,50,75,100}: 75*3=225, 100+6=106, 225*106=23850, 23850-50=23800, 23800/25=952 (exact)
Target 952 from {100,75,50,25,6,3}: 100+6=106, 106*75=7950, 7950*3=23850, 23850-50=23800, 23800/25=952 (exact)
Target 203 from {50,100,4,2,2,4}: 50*4=200, 200+4=204, 2/2=1, 204-1=203 (exact)
Target 465 from {25,4,9,2,3,10}: 25-10=15, 9*3=27, 27+4=31, 31*15=465 (exact)
Target 241 from {9,8,10,5,9,7}: 9+9=18, 8+5=13, 18*13=234, 234+7=241 (exact)
Target 824 from {3,7,6,2,1,7}: 7+3=10, 10*6=60, 60-1=59, 59*2=118, 118*7=826 (off by 2)
Target 125 from {75,50,25,100,8,2}: 75+50=125 (exact)
Target 594 from {8,4,4,6,8,9}: 8*8=64, 64-4=60, 60+6=66, 66*9=594 (exact)
Target 363 from {2,4,9,10,3,5}: 9*4=36, 36*10=360, 360+3=363 (exact)
1.797
</pre>
 
=={{header|Prolog}}==
<syntaxhighlight lang="prolog">
/* given numbers & target */
 
n(100,1). n(75,2). n(50,3). n(25,4). n(6,5). n(3,6).
ok(Res) :- Res = 952.
 
/* four operations with strictly positive integers and N1 >= N2 */
 
r(N1,N2,Res,'+') :- Res is N1 + N2.
r(N1,N2,Res,'-') :- N1 > N2, Res is N1 - N2.
r(N1,N2,Res,'*') :- N2 > 1, Res is N1 * N2.
r(N1,N2,Res,'/') :- N2 > 1, 0 is N1 mod N2, Res is N1 div N2.
 
/* concatenation */
concaten([],L,L).
concaten([H|L1],L2,[H|L3]) :- concaten(L1,L2,L3).
 
/* four operations & print solution management */
 
ra(N1,N2,Res,Lout1,Lout2,NewLout) :-
concaten(Lout1,Lout2,Lout),
N1 >= N2,
r(N1,N2,Res,Ope),
concaten(Lout,[N1,Ope,N2,Res|[]],NewLout).
 
/* print result */
 
lout([]) :- nl.
lout([N1,Ope,N2,Res|Queue]) :-
out(N1,Ope,N2,Res),
lout(Queue).
out(N1,Ope,N2,Res) :-
write(N1), write(Ope), write(N2), write('='), write(Res), nl.
 
/* combine two last numbers & result control */
 
c(N1,N2,Lout1,Lout2) :-
ra(N1,N2,Res,Lout1,Lout2,NewLout),
ok(Res),
lout(NewLout).
 
/* unique list */
 
uniqueList([]).
uniqueList([H|T]) :- \+(member(H,T)), uniqueList(T).
 
/* all possible arrangements */
 
c1 :-
n(Nb,_), /* a */
ok(Nb),
write(Nb).
 
c2 :-
n(N1,I1), n(N2,I2), /* (ab) */
I1\=I2,
c(N1,N2,[],[]).
 
c3 :-
n(N1,I1), n(N2,I2), n(N3,I3),
I1\=I2, I1\=I3, I2\=I3,
ra(N1, N2, Res1,[], [], Lout1), /* (ab) c */
c(Res1,N3, Lout1,[]).
 
c4 :-
n(N1,I1), n(N2,I2), n(N3,I3), n(N4,I4),
uniqueList([I1,I2,I3,I4]),
ra(N1, N2, Res1,[], [], Lout1), /* (ab) (cd) */
(( ra(N3, N4, Res2,[], [], Lout2),
c(Res1,Res2, Lout1,Lout2)); /* ((ab) c) d */
( ra(Res1,N3, Res2,Lout1,[], Lout2),
c(Res2,N4, Lout2,[]))).
 
c5 :-
n(N1,I1), n(N2,I2), n(N3,I3), n(N4,I4), n(N5,I5),
uniqueList([I1,I2,I3,I4,I5]),
ra(N1, N2, Res1,[], [], Lout1), /* ((ab) (cd)) e */
(( ra(N3, N4, Res2,[], [], Lout2),
ra(Res1,Res2,Res3,Lout1,Lout2,Lout3),
c(Res3,N5, Lout3,[])); /* ((ab) c) (de) */
( ra(Res1,N3, Res2,Lout1,[], Lout2),
ra(N4, N5, Res3,[], [], Lout3),
c(Res2,Res3, Lout2,Lout3)); /* (((ab) c) d) e */
( ra(Res1,N3, Res2,Lout1,[], Lout2),
ra(Res2,N4, Res3,Lout2,[], Lout3),
c(Res3,N5, Lout3,[]))).
 
c6 :-
n(N1,I1), n(N2,I2), n(N3,I3), n(N4,I4), n(N5,I5), n(N6,I6),
uniqueList([I1,I2,I3,I4,I5,I6]),
ra(N1, N2, Res1,[], [], Lout1), /* ((ab) (cd)) (ef) */
(( ra(N3, N4, Res2,[], [], Lout2),
ra(Res1,Res2,Res3,Lout1,Lout2,Lout3),
ra(N5, N6, Res4,[], [], Lout4),
c(Res3,Res4, Lout3,Lout4)); /* ((ab) c) ((de) f) */
( ra(Res1,N3, Res2,Lout1,[], Lout2),
ra(N4, N5, Res3,[], [], Lout3),
ra(Res3,N6, Res4,Lout3,[], Lout4),
c(Res2,Res4, Lout2,Lout4)); /* (((ab) c) d) (ef) */
( ra(Res1,N3, Res2,Lout1,[], Lout2),
ra(Res2,N4, Res3,Lout2,[], Lout3),
ra(N5, N6, Res4,[], [], Lout4),
c(Res3,Res4, Lout3,Lout4)); /* ((((ab) c) d) e) f */
( ra(Res1,N3, Res2,Lout1,[], Lout2),
ra(Res2,N4, Res3,Lout2,[], Lout3),
ra(Res3,N5, Res4,Lout3,[], Lout4),
c(Res4,N6, Lout4,[]))).
 
/* solution */
 
solution :- c1 ; c2 ; c3 ; c4 ; c5 ; c6.
</syntaxhighlight>
{{out}}
<pre>
100+6=106
106*75=7950
7950*3=23850
23850-50=23800
23800/25=952
 
yes
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">
best = 0
best_out = ""
target = 952
nbrs = [100, 75, 50, 25, 6, 3]
def sol(target, nbrs, out=""):
global best, best_out
if abs(target - best) > abs(target - nbrs[0]):
best = nbrs[0]
best_out = out
if target == nbrs[0]:
print(out)
elif len(nbrs) > 1:
for i1 in range(0, len(nbrs)-1):
for i2 in range(i1+1, len(nbrs)):
remains = nbrs[:i1] + nbrs[i1+1:i2] + nbrs[i2+1:]
a, b = nbrs[i1], nbrs[i2]
if a > b: a, b = b, a
res = b + a
op = str(b) + " + " + str(a) + " = " + str(res) + " ; "
sol(target, [res] + remains, out + op)
if b != a:
res = b - a
op = str(b) + " - " + str(a) + " = " + str(res) + " ; "
sol(target, [res] + remains, out + op)
if a != 1:
res = b * a
op = str(b) + " * " + str(a) + " = " + str(res) + " ; "
sol(target, [res] + remains, out + op)
if b % a == 0:
res = int(b / a)
op = str(b) + " / " + str(a) + " = " + str(res) + " ; "
sol(target, [res] + remains, out + op)
 
sol(target, nbrs)
if best != target:
print("Best solution " + str(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|Quorum}}==
Line 41 ⟶ 680:
number start = datetime:GetEpochTime()
List<integer> numbers
numbers:Add(100)
numbers:Add(75)
numbers:Add(50)
numbers:Add(25)
numbers:Add(6)
numbers:Add(3)
Solution(952,numbers:Add(6)
numbers:Add(25)
numbers:Add(50)
numbers:Add(75)
numbers:Add(100)
if not Solution(952,numbers)
output "No exact solution found."
end
number stop = datetime:GetEpochTime()
output stop-start + " ms"
Line 53 ⟶ 694:
 
action Solution(integer target, List<integer> numbers) returns boolean
if numbers:GetSize() > 1
// All couple of numbers
if numbers:GetSize() = 1
Iterator<integer> it0 = numbers:GetIterator()
return false
end repeat while it0:HasNext()
integer n0 = it0:Next()
List<integer> numbers1 = cast(List<integer>, numbers:Copy())
numbers1:Remove(n0)
Iterator<integer> it1 = numbers1:GetIterator()
repeat while it1:HasNext()
integer n1 = it1:Next()
List<integer> numbers2 = cast(List<integer>, numbers1:Copy())
numbers2:Remove(n1)
// All four operations
integer res = 0
List<integer> numbersNew
if n1 >= n0 // Both case are generated
res = n1 + n0
numbersNew = cast(List<integer>, numbers2:Copy())
numbersNew:Add(res)
if res = target or Solution(target, numbersNew)
output res + " = " + n1 + " + " + n0
return true
end
if n0 not= 1
res = n1 * n0
numbersNew = cast(List<integer>, numbers2:Copy())
numbersNew:Add(res)
if res = target or Solution(target, numbersNew)
output res + " = " + n1 + " * " + n0
return true
end
end
if n1 not= n0
res = n1 - n0
numbersNew = cast(List<integer>, numbers2:Copy())
numbersNew:Add(res)
if res = target or Solution(target, numbersNew)
output res + " = " + n1 + " - " + n0
return true
end
end
if n0 not= 1 and n1 mod n0 = 0
res = n1 / n0
numbersNew = cast(List<integer>, numbers2:Copy())
numbersNew:Add(res)
if res = target or Solution(target, numbersNew)
output res + " = " + n1 + " / " + n0
return true
end
end
end // n1 >= n0
end // it1
end // it0
end // if numbers:GetSize() > 1
return false
end
</syntaxhighlight>
{{out}}
<pre>
952 = 23800 / 25
23800 = 23850 - 50
23850 = 225 * 106
225 = 3 * 75
106 = 6 + 100
218.0 ms
</pre>
 
=={{header|Raku}}==
Iterator<integer> it0 = numbers:GetIterator()
{{trans|Wren}}
repeat while it0:HasNext()
<syntaxhighlight lang="raku" line># 20221021 Raku programming solution
 
sub countdown ($target, @numbers) {
integer n0 = it0:Next()
return False if @numbers.elems == 1;
List<integer> numbers1 = cast(List<integer>, numbers:Copy())
for @numbers.kv -> \n0k,\n0v {
numbers1:Remove(n0)
(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 >;
Iterator<integer> it1 = numbers1:GetIterator()
my @numbersList = <3 6 25 50 75 100> , <100 75 50 25 6 3>,
repeat while it1:HasNext()
<8 4 4 6 8 9> , @allNumbers.pick(6);
my @targetList = 952, 952, 594, (101..1000).pick;
 
for (0..^+@numbersList) -> \i {
integer n1 = it1:Next()
say "Using : ", my @numbers = |@numbersList[i];
List<integer> numbers2 = cast(List<integer>, numbers1:Copy())
say "Target: ", my $target = @targetList[i];
numbers2:Remove(n1)
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]
integer res = 0
Target: 952
List<integer> numbersNew
952 = 23800 / 25
23800 = 23850 - 50
23850 = 7950 * 3
7950 = 106 * 75
106 = 100 + 6
 
Using : [8 4 4 6 8 9]
res = n0 + n1
Target: 594
numbersNew = cast(List<integer>, numbers2:Copy())
594 = 66 * 9
numbersNew:Add(res)
66 = 64 + 2
if res = target or Solution(target, numbersNew)
64 = 16 * 4
output res + " = " + n0 + " + " + n1
2 = 6 - 4
return true
16 = 8 + 8
end
 
Using : [100 9 50 2 9 8]
res = n0 * n1
Target: 599
numbersNew = cast(List<integer>, numbers2:Copy())
599 = 590 + 9
numbersNew:Add(res)
590 = 59 * 10
if res = target or Solution(target, numbersNew)
10 = 8 + 2
output res + " = " + n0 + " * " + n1
59 = 109 - 50
return true
109 = 100 + 9</pre>
end
 
=={{header|Rebol}}==
if n0 > n1
<syntaxhighlight lang="rebol">
res = n0 - n1
REBOL [
numbersNew = cast(List<integer>, numbers2:Copy())
Title: "CountDown"
numbersNew:Add(res)
Date: 1-May-2008
if res = target or Solution(target, numbersNew)
]
output res + " = " + n0 + " - " + n1
return true
end
elseif n1 > n0
res = n1 - n0
numbersNew = cast(List<integer>, numbers2:Copy())
numbersNew:Add(res)
if res = target or Solution(target, numbersNew)
output res + " = " + n1 + " - " + n0
return true
end
end
 
target: 952
if n0 > n1
list: [ 3 6 25 50 75 100 ]
if n0 mod n1 = 0
 
res = n0 / n1
op: [+ - * /]
numbersNew = cast(List<integer>, numbers2:Copy())
ad: func[x y][x + y]
numbersNew:Add(res)
sb: func[x y][x - y]
if res = target or Solution(target, numbersNew)
ml: func[x y][if error? try [return x * y][0]]
output res + " = " + n0 + " / " + n1
dv: func[x y][either (x // y) = 0 [x / y][0]]
calculs: func[x y][make block! [(ad x y) (sb x y) (ml x y) (dv x y)]]
nwlist: func[list j i res][sort append head remove at head remove at copy list j i res]
 
sol: function[list size][ol][
for i 1 (size - 1) 1 [
for j (i + 1) size 1 [
ol: reduce calculs list/:j list/:i
for k 1 4 1 [
if any [(ol/:k = target) all [(ol/:k <> 0) (size > 1) (s: sol (nwlist list j i ol/:k) (size - 1))]] [
return rejoin [list/:j op/:k list/:i "=" ol/:k newline s]
] ] ] ]
return false
]
 
print rejoin [ceb list length? list]
</syntaxhighlight>
{{out}}
<pre>
75*3=225
100+6=106
225*106=23850
23850-50=23800
23800/25=952
false
</pre>
 
=={{header|Scala}}==
{{trans|Python}}
{{libheader|Scala}}
[https://github.com/OlivierBlanvillain My son] made this translation for me.
<syntaxhighlight lang="scala">
var best = 0
var best_out = ""
val target = 952
val nbrs = List(100, 75, 50, 25, 6, 3)
 
def sol(target: Int, xs: List[Int], out: String): Unit = {
if ((target - best).abs > (target - xs.head).abs) {
best = xs.head
best_out = out
}
if (target == xs.head)
println(out)
else
0 until (xs.size-1) foreach { i1 =>
(i1+1) until xs.size foreach { i2 =>
val remains = xs.patch(i2, Nil, 1).patch(i1, Nil, 1)
val (n1, n2) = (xs(i1), xs(i2))
val (a, b) = (n1 min n2, n1 max n2)
def loop(res: Int, op: Char) =
sol(target, res :: remains, s"$out$b $op $a = $res ; ")
loop(b + a, '+')
if (b != a)
loop(b - a, '-')
if (a != 1) {
loop(b * a, '*')
if (b % a == 0)
loop(b / a, '/')
}
}
}
}
 
sol(target, nbrs, "")
if (best != target) {
println("Best solution " + best)
println(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|Wren}}==
{{trans|Quorum}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "random" for Random
import "./fmt" for Fmt
 
var countdown // recursive function
countdown = Fn.new { |target, numbers|
if (numbers.count == 1) return false
for (n0 in numbers) {
var nums1 = numbers.toList
nums1.remove(n0)
for (n1 in nums1) {
var nums2 = nums1.toList
nums2.remove(n1)
if (n1 >= n0) {
var res = n1 + n0
var numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(target, numsNew)) {
Fmt.print("$d = $d + $d", res, n1, n0)
return true
}
if (n0 != 1) {
res = n1 * n0
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(target, numsNew)) {
Fmt.print("$d = $d * $d", res, n1, n0)
return true
end}
end}
else if (n1 != n0) {
if n1 mod n0 res = 0n1 - n0
resnumsNew = n1 / n0nums2.toList
numbersNew = castnumsNew.add(List<integer>, numbers2:Copy()res)
numbersNew:Addif (res == target || countdown.call(target, numsNew)) {
if res Fmt.print("$d = target$d or- Solution(target$d", res, n1, numbersNewn0)
output res + " = " + n1 + " / " + n0
return true
end}
end}
end if (n0 != 1 && n1 % n0 == 0) {
res = (n1/n0).truncate
end
numsNew = nums2.toList
end
numsNew.add(res)
if (res == target || countdown.call(target, numsNew)) {
Fmt.print("$d = $d / $d", res, n1, n0)
return true
}
}
}
}
}
return false
}
end
 
</syntaxhighlight>
var 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]
var rand = Random.new()
var numbersList = [
[3, 6, 25, 50, 75, 100],
[100, 75, 50, 25, 6, 3], // see if there's much difference if we reverse the first example
[8, 4, 4, 6, 8, 9],
rand.sample(allNumbers, 6)
]
var targetList = [952, 952, 594, rand.int(101, 1000)]
for (i in 0...numbersList.count) {
System.print("Using : %(numbersList[i])")
System.print("Target: %(targetList[i])")
var start = System.clock
var done = countdown.call(targetList[i], numbersList[i])
System.print("Took %(((System.clock - start) * 1000).round) ms")
if (!done) System.print("No exact solution found")
System.print()
}</syntaxhighlight>
 
{{out}}
Sample output (as the fourth example is random):
<pre>
Using : [3, 6, 25, 50, 75, 100]
Target: 952
952 = 23800 / 25
23800 = 23850 - 50
23850 = 106225 * 225106
106 = 100 + 6
225 = 75 * 3
Took 173 ms
 
Using : [100, 75, 50, 25, 6, 3]
Target: 952
952 = 23800 / 25
23800 = 23850 - 50
23850 = 7950 * 3
7950 = 106 * 75
106 = 100 + 6
456.0Took 378 ms
 
Using : [8, 4, 4, 6, 8, 9]
Target: 594
594 = 66 * 9
66 = 64 + 2
64 = 16 * 4
2 = 6 - 4
16 = 8 + 8
Took 2 ms
 
Using : [7, 2, 1, 8, 5, 3]
Target: 436
436 = 109 * 4
109 = 112 - 3
4 = 5 - 1
112 = 56 * 2
56 = 8 * 7
Took 11 ms
</pre>
Alextretyak
1,480

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/331272...364307"