Countdown: Difference between revisions
m
→{{header|11l}}: Void
(Back to initial Quorum solution without compiler memory allocation bug during recursive calls on lists or array data structures) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (14 intermediate revisions by 6 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 255 ⟶ 489:
</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}}==
Line 322 ⟶ 680:
number start = datetime:GetEpochTime()
List<integer> numbers
numbers:Add(3)
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."
Line 351 ⟶ 709:
integer res = 0
List<integer> numbersNew
numbersNew = cast(List<integer>, numbers2:Copy())
numbersNew:Add(res)
if res = target or Solution(target, numbersNew)
output res + " = " + n1 + "
return true
end
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
Line 396 ⟶ 758:
225 = 3 * 75
106 = 6 + 100
</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>
=={{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 { |
if (numbers.count == 1) return false
for (n0 in numbers) {
Line 418 ⟶ 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 491 ⟶ 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 505 ⟶ 1,026:
23800 = 23850 - 50
23850 = 225 * 106
106 =
225 =
Took
Using : [100, 75, 50, 25, 6, 3]
Line 513 ⟶ 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>
| |||