Countdown

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 are the optimisation heuristics to reduce the number of calculations. For example, a rather interesting computational challenge is to calculate all possible games (with all the 120'867'208 combinations of six numbers out of twenty-four for all possible targets between 101 and 999).

Quorum

use Libraries.Containers.List
use Libraries.Containers.Iterator
use Libraries.System.DateTime

action Main
    DateTime datetime
    number start = datetime:GetEpochTime() 
    List<integer> tirage
    tirage:Add(100)
    tirage:Add(75)
    tirage:Add(50)
    tirage:Add(25)
    tirage:Add(6)
    tirage:Add(3)
    Solution(952,tirage)
    number stop = datetime:GetEpochTime() 
    output stop-start + " ms"
end

action Solution(integer cible, List<integer> tirage) returns boolean
    
    if tirage:GetSize() = 1
        return false
    end    

    Iterator<integer> it0 = tirage:GetIterator()
    repeat while it0:HasNext()

        integer n0 = it0:Next()
        List<integer> tirage1 = cast(List<integer>, tirage:Copy())   
        tirage1:Remove(n0)

        Iterator<integer> it1 = tirage1:GetIterator()
        repeat while it1:HasNext()

            integer n1 = it1:Next()
            List<integer> tirage2 = cast(List<integer>, tirage1:Copy())
            tirage2:Remove(n1)

            integer res = 0
            List<integer> tirageNew

            res = n0 + n1
            tirageNew = cast(List<integer>, tirage2:Copy())
            tirageNew:Add(res)
            if res = cible or Solution(cible, tirageNew)
                output res + " = " + n0 + " + " + n1
                return true
            end

            res = n0 * n1
            tirageNew = cast(List<integer>, tirage2:Copy())
            tirageNew:Add(res)
            if res = cible or Solution(cible, tirageNew)
                output res + " = " + n0 + " * " + n1
                return true
            end

            if n0 > n1
                res = n0 - n1
                tirageNew = cast(List<integer>, tirage2:Copy())
                tirageNew:Add(res)
                if res = cible or Solution(cible, tirageNew)
                    output res + " = " + n0 + " - " + n1
                    return true
                end
            elseif n1 > n0
                res = n1 - n0
                tirageNew = cast(List<integer>, tirage2:Copy())
                tirageNew:Add(res)
                if res = cible or Solution(cible, tirageNew)
                    output res + " = " + n1 + " - " + n0
                    return true
                end
            end

            if n0 > n1 
                if n0 mod n1 = 0
                    res = n0 / n1
                    tirageNew = cast(List<integer>, tirage2:Copy())
                    tirageNew:Add(res)
                    if res = cible or Solution(cible, tirageNew)
                        output res + " = " + n0 + " / " + n1
                        return true
                    end
                end
            else
                if n1 mod n0 = 0
                    res = n1 / n0
                    tirageNew = cast(List<integer>, tirage2:Copy())
                    tirageNew:Add(res)
                    if res = cible or Solution(cible, tirageNew)
                        output res + " = " + n1 + " / " + n0
                        return true
                    end
                end
            end
        end
    end
    return false
end

Output:

952 = 23800 / 25
23800 = 23850 - 50
23850 = 106 * 225
225 = 75 * 3
106 = 100 + 6
456.0 ms