Jump to content

Countdown

From Rosetta Code
Countdown is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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).


11l

Translation of: Python
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)
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 ; 

FreeBASIC

Translation of: Wren
Function countdown(target As Integer, numbers() As Integer) As Boolean
    Dim As Integer i, k, j, l, m
    If Ubound(numbers) = 0 Then Return False
    For i = 0 To Ubound(numbers)
        Dim nums1(Ubound(numbers) - 1) As Integer
        For k = 0 To Ubound(numbers) - 1
            nums1(k) = Iif(k < i, numbers(k), numbers(k + 1))
        Next k
        For j = 0 To Ubound(nums1)
            Dim nums2(Ubound(nums1) - 1) As Integer
            For l = 0 To Ubound(nums1) - 1
                nums2(l) = Iif(l < j, nums1(l), nums1(l + 1))
            Next l
            If nums1(j) >= numbers(i) Then
                Dim res As Integer = nums1(j) + numbers(i)
                Dim numsNew(Ubound(nums2) + 1) As Integer
                For m = 0 To Ubound(nums2)
                    numsNew(m) = nums2(m)
                Next m
                numsNew(Ubound(numsNew)) = res
                If res = target Orelse countdown(target, numsNew()) Then
                    Print res; " ="; nums1(j); " +"; numbers(i)
                    Return True
                End If
                If numbers(i) <> 1 Then
                    res = nums1(j) * numbers(i)
                    For m = 0 To Ubound(nums2)
                        numsNew(m) = nums2(m)
                    Next m
                    numsNew(Ubound(numsNew)) = res
                    If res = target Orelse countdown(target, numsNew()) Then
                        Print res; " ="; nums1(j); " *"; numbers(i)
                        Return True
                    End If
                End If
                If nums1(j) <> numbers(i) Then
                    res = nums1(j) - numbers(i)
                    For m = 0 To Ubound(nums2)
                        numsNew(m) = nums2(m)
                    Next m
                    numsNew(Ubound(numsNew)) = res
                    If res = target Or countdown(target, numsNew()) Then
                        Print res; " ="; nums1(j); " -"; numbers(i)
                        Return True
                    End If
                End If
                If numbers(i) <> 1 Andalso nums1(j) Mod numbers(i) = 0 Then
                    res = nums1(j) \ numbers(i)
                    For m = 0 To Ubound(nums2)
                        numsNew(m) = nums2(m)
                    Next m
                    numsNew(Ubound(numsNew)) = res
                    If res = target Orelse countdown(target, numsNew()) Then
                        Print res; " ="; nums1(j); " /"; numbers(i)
                        Return True
                    End If
                End If
            End If
        Next j
    Next i
    Return False
End Function

Dim allNumbers(23) As Integer = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100}
Dim numbersList(3, 5) As Integer = {{3, 6, 25, 50, 75, 100}, {100, 75, 50, 25, 6, 3}, {8, 4, 4, 6, 8, 9}}
Dim targetList(3) As Integer = {952, 952, 594}

Randomize Timer
Dim As Integer i, j
For i = 0 To 5
    numbersList(3, i) = allNumbers(Int(Rnd * Ubound(allNumbers)))
Next i
targetList(3) = Int(Rnd * 900) + 101

For i = 0 To 3
    Print "Using : [";
    Dim currentNumbers(5) As Integer
    For j = 0 To 5
        currentNumbers(j) = numbersList(i, j)
        Print currentNumbers(j); ",";
    Next j
    Print Chr(8); " ]"
    Print "Target:"; targetList(i)
    Dim start As Double = Timer
    Dim done As Boolean = countdown(targetList(i), currentNumbers())
    Print "Took"; Int((Timer - start) * 1000); " ms"
    If Not done Then Print "No exact solution found"
    Print
Next i

Sleep
Output:
Using : [ 3, 6, 25, 50, 75, 100 ]
Target: 952
 952 = 23800 / 25
 23800 = 23850 - 50
 23850 = 225 * 106
 106 = 100 + 6
 225 = 75 * 3
Took 56 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
Took 110 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 6 ms

Using : [ 8, 75, 5, 8, 6, 75 ]
Target: 512
 512 = 64 * 8
 64 = 75 - 11
 11 = 6 + 5
 83 = 75 + 8
Took 5 ms

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

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.

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
Output:

Using command ./countdown 3 6 25 50 75 100 952, we get the following result:

Target value: 952
Nearest value computed: 952
Operations:
  6 + 100 = 106
  3 × 75 = 225
  106 × 225 = 23850
  23850 - 50 = 23800
  23800 / 25 = 952

Perl

Translation of: Raku
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 '';
}
Output:
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

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

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.
Output:
100+6=106
106*75=7950
7950*3=23850
23850-50=23800
23800/25=952

yes

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(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."
    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    
                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
Output:
952 = 23800 / 25
23800 = 23850 - 50
23850 = 225 * 106
225 = 3 * 75
106 = 6 + 100
218.0 ms

Raku

Translation of: Wren
# 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() 
}
Output:
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

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]
Output:
75*3=225
100+6=106
225*106=23850
23850-50=23800
23800/25=952
false

Scala

Translation of: Python
Library: Scala

My son made this translation for me.

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)
}
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 ; 

Wren

Translation of: Quorum
Library: Wren-fmt
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
                    }
                }
                if (n1 != n0) {
                    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
                    }
                }
                if (n0 != 1 && n1 % n0 == 0) {
                    res = (n1/n0).truncate
                    numsNew = nums2.toList
                    numsNew.add(res)
                    if (res == target || countdown.call(target, numsNew)) {
                        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(targetList[i], numbersList[i])
    System.print("Took %(((System.clock - start) * 1000).round) ms")
    if (!done) System.print("No exact solution found")
    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 = 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
Took 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
Cookies help us deliver our services. By using our services, you agree to our use of cookies.