Countdown: Difference between revisions
m
→{{header|11l}}: Void
m (→{{header|J}}: discard duplicate solutions) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (20 intermediate revisions by 8 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 69 ⟶ 126:
#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}}==
Line 203 ⟶ 487:
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>
Line 210 ⟶ 675:
use Libraries.Containers.Iterator
use Libraries.System.DateTime
action Main
DateTime datetime
number start = datetime:GetEpochTime()
List<integer> numbers
numbers:Add(6)
numbers:Add(25)
if not
output "No exact solution found."
end
number stop = datetime:GetEpochTime()
output stop-start + " ms"
end
action Solution(integer target, List<integer> numbers) returns boolean
if numbers:GetSize() > 1
// All couple of numbers
Iterator<integer> it0 = numbers:GetIterator()
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 =
List<integer> numbersNew
if n1
numbersNew:Add(res)
if res =
return true
end
res = n1 * n0
if res = target or Solution(target,
output res + " = " +
return true
end
end
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 =
</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}}==
<syntaxhighlight lang="rebol">
REBOL [
Title: "CountDown"
Date: 1-May-2008
]
target: 952
list: [ 3 6 25 50 75 100 ]
op: [+ - * /]
ad: func[x y][x + y]
sb: func[x y][x - y]
ml: func[x y][if error? try [return x * y][0]]
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>
Line 320 ⟶ 946:
{{trans|Quorum}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "random" for Random
import "./fmt" for Fmt
var countdown // recursive function
countdown = Fn.new { |
if (numbers.count == 1) return false
for (n0 in numbers) {
Line 337 ⟶ 958:
var nums2 = nums1.toList
nums2.remove(n1)
var
var numsNew = nums2.
numsNew.add(res)
if (res == target || countdown.call(
Fmt.print("$d = $d
return true
}
res = n1
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(
Fmt.print("$d = $d
return true
}
}
res = n1 - n0
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(
Fmt.print("$d = $d
return true
}
}
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(
Fmt.print("$d = $d / $d", res, n1, n0)
return true
Line 410 ⟶ 1,012:
System.print("Target: %(targetList[i])")
var start = System.clock
var done = countdown.call(
System.print("Took %(((System.clock - start) * 1000).round) ms")
if (!done) System.print("No exact solution
System.print()
}</syntaxhighlight>
Line 424 ⟶ 1,026:
23800 = 23850 - 50
23850 = 225 * 106
106 =
225 =
Took
Using : [100, 75, 50, 25, 6, 3]
Line 432 ⟶ 1,034:
952 = 23800 / 25
23800 = 23850 - 50
23850 =
106 = 100 + 6
Took
Using : [8, 4, 4, 6, 8, 9]
Target: 594
594 =
Took
Using : [
Target:
Took
</pre>
| |||