Countdown
- Task
Given six numbers randomly selected from the list [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100], calculate using only positive integers and four operations [+, -, *, /] a random number between 101 and 999.
Example:
Using: [3, 6, 25, 50, 75, 100]
Target: 952
Solution:
- 100 + 6 = 106
- 75 * 3 = 225
- 106 * 225 = 23850
- 23850 - 50 = 23800
- 23800 / 25 = 952
- Origins
This is originally a 1972 French television game show. The game consists of randomly selecting six of the twenty-four numbers, from a list of: twenty "small numbers" (two each from 1 to 10), and four "large numbers" of 25, 50, 75 and 100. A random target number between 101 and 999 is generated. The players have 30 seconds to work out a sequence of calculations with the numbers whose final result is as close as possible to the target number. Only the four basic operations: addition, subtraction, multiplication and division can be used to create new numbers and not all six numbers are required. A number can only be used once. Division can only be done if the result has no remainder (fractions are not allowed) and only positive integers can be obtained at any stage of the calculation. (More info on the original game).
- Extra challenge
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).
J
Brute force implementation:
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
}}
Examples:
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)
Julia
Brute force with a somewhat narrowed search space.
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
- Output:
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
Phix
Here's one I already had, cleaned up a bit:
-- -- demo/Countdown.exw -- -- solves the numbers game from countdown. -- with javascript_semantics constant n = 6, ops = "+-*/" enum ADD, SUB, MUL, DIV sequence chosen = repeat(0,n), -- original numbers <-> partial sums expression = repeat(0,n), -- the operations tried so far solution -- (a/best snapshot of expression) int len, -- n+1 means no solution yet found maxlev, -- recursion limit (5, drops as solns found) near, -- nearest answer (in solution) out by this lenn, -- length of "" "" target procedure countdown(int level=1) -- -- 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. -- for i=1 to n do integer sti = chosen[i] -- speedwise/save if sti!=0 then for j=1 to n do integer stj = chosen[j] -- "" if i!=j and stj!=0 then for operation=ADD to DIV do if (operation<DIV or mod(sti,stj)=0) and (operation<MUL or stj!=1) and (sti>=stj) then -- worth doing... integer ci = sti switch operation do case ADD: ci += stj case SUB: ci -= stj case MUL: ci *= stj case DIV: ci /= stj end switch chosen[i] = ci chosen[j] = 0 /* store operands and operator */ expression[level] = {sti,ops[operation],stj,ci} -- check for solution if ci==target then if level<len then /* solution is shortest so far - store it */ len = level maxlev = level-1 near = 0 solution = deep_copy(expression) end if else --store closest? integer offby = abs(target-ci) if offby<near then near = offby lenn = level solution = deep_copy(expression) end if -- if not at required level, recurse if level<maxlev then countdown(level+1) end if end if -- undo chosen[i] = sti chosen[j] = stj end if end for end if end for end if end for end procedure procedure test(sequence list, int dest) len = n+1 maxlev = 5 near = dest target = dest chosen = deep_copy(list) countdown() /* process solution into printable form */ string off = "exact" if len=n+1 then off = sprintf("off by %d",near) len = lenn end if string soln = join(apply(true,sprintf,{{"%d%c%d=%d"},solution[1..len]}),", ") printf(1,"Target %d from %18v: %s (%s)\n",{dest,list,soln,off}) end procedure atom t0 = time() test({75,50,25,100,8,2},737) test({3,6,25,50,75,100},952) test({100,75,50,25,6,3},952) test({50,100,4,2,2,4},203) test({25,4,9,2,3,10},465) test({9,8,10,5,9,7},241) test({3,7,6,2,1,7},824) test({75,50,25,100,8,2},125) test({8,4,4,6,8,9},594) test({2,4,9,10,3,5},363) --test(shuffle(tagset(10)&tagset(10)&tagstart(25,4,25))[1..6],100+rand(899)) ?time()-t0 {} = wait_key()
- Output:
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
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)
- Output:
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 ;
Quorum
use Libraries.Containers.List
use Libraries.Containers.Iterator
use Libraries.System.DateTime
action Main
DateTime datetime
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)
if not Solution(952,numbers)
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 = 0
List<integer> numbersNew
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
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 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
if n1 >= n0 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 // it1
end // it0
end // if numbers:GetSize() > 1
return false
end
- Output:
952 = 23800 / 25 23800 = 23850 - 50 23850 = 225 * 106 225 = 3 * 75 106 = 6 + 100 311.0 ms
Wren
This is based on the original Quorum algorithm as it's more or less the approach I'd have used anyway.
The latest algorithm is not working properly as numbers are being used twice (50 in the first example).
A bit slow but not too bad for Wren :)
import "random" for Random
import "./fmt" for Fmt
var countdown // recursive function
countdown = Fn.new { |numbers, target|
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)
var res = n0 + n1
var numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(numsNew, target)) {
Fmt.print("$d = $d + $d", res, n0, n1)
return true
}
res = n0 * n1
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(numsNew, target)) {
Fmt.print("$d = $d * $d", res, n0, n1)
return true
}
if (n0 > n1) {
res = n0 - n1
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(numsNew, target)) {
Fmt.print("$d = $d - $d", res, n0, n1)
return true
}
} else if (n1 > n0) {
res = n1 - n0
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(numsNew, target)) {
Fmt.print("$d = $d - $d", res, n1, n0)
return true
}
}
if (n0 > n1) {
if (n0 % n1 == 0) {
res = n0 / n1
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(numsNew, target)) {
Fmt.print("$d = $d / $d", res, n0, n1)
return true
}
}
} else {
if (n1 % n0 == 0) {
res = n1 / n0
numsNew = nums2.toList
numsNew.add(res)
if (res == target || countdown.call(numsNew, target)) {
Fmt.print("$d = $d / $d", res, n1, n0)
return true
}
}
}
}
}
return false
}
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(numbersList[i], targetList[i])
System.print("Took %(((System.clock - start) * 1000).round) ms")
if (!done) System.print("No solution exists")
System.print()
}
- Output:
Sample output (as the fourth example is random):
Using : [3, 6, 25, 50, 75, 100] Target: 952 952 = 23800 / 25 23800 = 23850 - 50 23850 = 225 * 106 106 = 6 + 100 225 = 3 * 75 Took 1525 ms Using : [100, 75, 50, 25, 6, 3] Target: 952 952 = 23800 / 25 23800 = 23850 - 50 23850 = 106 * 225 225 = 75 * 3 106 = 100 + 6 Took 1522 ms Using : [8, 4, 4, 6, 8, 9] Target: 594 594 = 54 * 11 11 = 8 + 3 54 = 6 * 9 3 = 12 / 4 12 = 8 + 4 Took 27 ms Using : [2, 4, 9, 10, 3, 5] Target: 363 363 = 3 + 360 360 = 9 * 40 40 = 10 + 30 30 = 5 * 6 6 = 2 + 4 Took 107 ms