Countdown
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.
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
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).
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 ;
using System;
using System.Collections.Generic;
using System.Linq;
public sealed class Countdown
{
public static void Main(string[] args)
{
List<int> allNumbers = new List<int>
{
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100
};
Random random = new Random();
allNumbers = allNumbers.OrderBy(x => random.Next()).ToList();
List<List<int>> numberLists = new List<List<int>>
{
new List<int> { 3, 6, 25, 50, 75, 100 },
new List<int> { 100, 75, 50, 25, 6, 3 },
new List<int> { 8, 4, 4, 6, 8, 9 },
allNumbers.Take(6).ToList()
};
List<int> targetList = new List<int> { 952, 952, 594, random.Next(101, 1000) };
for (int i = 0; i < targetList.Count; i++)
{
Console.WriteLine($"Using : [{string.Join(", ", numberLists[i])}]");
Console.WriteLine($"Target: {targetList[i]}");
bool done = CountdownSolver(numberLists[i], targetList[i]);
if (!done)
{
Console.WriteLine("No solution found");
}
Console.WriteLine();
}
}
private static bool CountdownSolver(List<int> numbers, int target)
{
if (numbers.Count <= 1)
{
return false;
}
foreach (int n0 in numbers)
{
List<int> numbers1 = new List<int>(numbers);
numbers1.Remove(n0);
foreach (int n1 in numbers1)
{
List<int> numbers2 = new List<int>(numbers1);
numbers2.Remove(n1);
if (n1 >= n0)
{
int result = n1 + n0;
List<int> numbersNext = new List<int>(numbers2) { result };
if (result == target || CountdownSolver(numbersNext, target))
{
Console.WriteLine($"{result} = {n1} + {n0}");
return true;
}
if (n0 != 1)
{
result = n1 * n0;
numbersNext = new List<int>(numbers2) { result };
if (result == target || CountdownSolver(numbersNext, target))
{
Console.WriteLine($"{result} = {n1} * {n0}");
return true;
}
}
if (n1 != n0)
{
result = n1 - n0;
numbersNext = new List<int>(numbers2) { result };
if (result == target || CountdownSolver(numbersNext, target))
{
Console.WriteLine($"{result} = {n1} - {n0}");
return true;
}
}
if (n0 != 1 && n1 % n0 == 0)
{
result = n1 / n0;
numbersNext = new List<int>(numbers2) { result };
if (result == target || CountdownSolver(numbersNext, target))
{
Console.WriteLine($"{result} = {n1} / {n0}");
return true;
}
}
}
}
}
return false;
}
}
- 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 : [8, 5, 2, 8, 10, 9] Target: 902 902 = 451 * 2 451 = 450 + 1 450 = 50 * 9 50 = 10 * 5 1 = 8 / 8
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
void shuffle(std::vector<int>& array) {
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(array.begin(), array.end(), g);
}
bool countdown(std::vector<int> numbers, int target) {
if (numbers.size() <= 1) {
return false;
}
for (size_t i = 0; i < numbers.size(); i++) {
int n0 = numbers[i];
std::vector<int> numbers1;
for (size_t k = 0; k < numbers.size(); k++) {
if (k != i) {
numbers1.push_back(numbers[k]);
}
}
for (size_t j = 0; j < numbers1.size(); j++) {
int n1 = numbers1[j];
std::vector<int> numbers2;
for (size_t k = 0; k < numbers1.size(); k++) {
if (k != j) {
numbers2.push_back(numbers1[k]);
}
}
if (n1 >= n0) {
// Addition
int result = n1 + n0;
std::vector<int> numbersNext = numbers2;
numbersNext.push_back(result);
if (result == target || countdown(numbersNext, target)) {
std::cout << result << " = " << n1 << " + " << n0 << std::endl;
return true;
}
// Multiplication
if (n0 != 1) {
result = n1 * n0;
numbersNext = numbers2;
numbersNext.push_back(result);
if (result == target || countdown(numbersNext, target)) {
std::cout << result << " = " << n1 << " * " << n0 << std::endl;
return true;
}
}
// Subtraction
if (n1 != n0) {
result = n1 - n0;
numbersNext = numbers2;
numbersNext.push_back(result);
if (result == target || countdown(numbersNext, target)) {
std::cout << result << " = " << n1 << " - " << n0 << std::endl;
return true;
}
}
// Division
if (n0 != 1 && n1 % n0 == 0) {
result = n1 / n0;
numbersNext = numbers2;
numbersNext.push_back(result);
if (result == target || countdown(numbersNext, target)) {
std::cout << result << " = " << n1 << " / " << n0 << std::endl;
return true;
}
}
}
}
}
return false;
}
int main() {
std::vector<int> 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
};
shuffle(allNumbers);
std::vector<std::vector<int>> numberLists = {
{3, 6, 25, 50, 75, 100},
{100, 75, 50, 25, 6, 3},
{8, 4, 4, 6, 8, 9},
{allNumbers.begin(), allNumbers.begin() + 6}
};
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(101, 999);
std::vector<int> targetList = {952, 952, 594, dis(gen)};
for (size_t i = 0; i < targetList.size(); i++) {
std::cout << "Using : [";
for (size_t j = 0; j < numberLists[i].size(); j++) {
std::cout << numberLists[i][j];
if (j < numberLists[i].size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
std::cout << "Target: " << targetList[i] << std::endl;
bool done = countdown(numberLists[i], targetList[i]);
if (!done) {
std::cout << "No solution found" << std::endl;
}
std::cout << std::endl;
}
return 0;
}
- 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 : [75, 100, 6, 9, 7, 3] Target: 501 501 = 167 * 3 167 = 182 - 15 182 = 175 + 7 15 = 9 + 6 175 = 100 + 75
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
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
allNumbers := []int{
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100,
}
// Shuffle the slice
rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(allNumbers), func(i, j int) {
allNumbers[i], allNumbers[j] = allNumbers[j], allNumbers[i]
})
numberLists := [][]int{
{3, 6, 25, 50, 75, 100},
{100, 75, 50, 25, 6, 3},
{8, 4, 4, 6, 8, 9},
allNumbers[:6],
}
targetList := []int{952, 952, 594, rand.Intn(899) + 101}
for i := 0; i < len(targetList); i++ {
fmt.Printf("Using : %v\n", numberLists[i])
fmt.Printf("Target: %d\n", targetList[i])
done := countdown(numberLists[i], targetList[i])
if !done {
fmt.Println("No solution found")
}
fmt.Println()
}
}
func countdown(numbers []int, target int) bool {
if len(numbers) <= 1 {
return false
}
for i, n0 := range numbers {
numbers1 := make([]int, 0, len(numbers)-1)
numbers1 = append(numbers1, numbers[:i]...)
numbers1 = append(numbers1, numbers[i+1:]...)
for j, n1 := range numbers1 {
numbers2 := make([]int, 0, len(numbers1)-1)
numbers2 = append(numbers2, numbers1[:j]...)
numbers2 = append(numbers2, numbers1[j+1:]...)
if n1 >= n0 {
// Addition
result := n1 + n0
numbersNext := make([]int, len(numbers2)+1)
copy(numbersNext, numbers2)
numbersNext[len(numbers2)] = result
if result == target || countdown(numbersNext, target) {
fmt.Printf("%d = %d + %d\n", result, n1, n0)
return true
}
// Multiplication
if n0 != 1 {
result = n1 * n0
numbersNext = make([]int, len(numbers2)+1)
copy(numbersNext, numbers2)
numbersNext[len(numbers2)] = result
if result == target || countdown(numbersNext, target) {
fmt.Printf("%d = %d * %d\n", result, n1, n0)
return true
}
}
// Subtraction
if n1 != n0 {
result = n1 - n0
numbersNext = make([]int, len(numbers2)+1)
copy(numbersNext, numbers2)
numbersNext[len(numbers2)] = result
if result == target || countdown(numbersNext, target) {
fmt.Printf("%d = %d - %d\n", result, n1, n0)
return true
}
}
// Division
if n0 != 1 && n1%n0 == 0 {
result = n1 / n0
numbersNext = make([]int, len(numbers2)+1)
copy(numbersNext, numbers2)
numbersNext[len(numbers2)] = result
if result == target || countdown(numbersNext, target) {
fmt.Printf("%d = %d / %d\n", result, n1, n0)
return true
}
}
}
}
}
return false
}
- 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 : [3 4 7 1 2 6] Target: 289 289 = 287 + 2 287 = 41 * 7 41 = 42 - 1 42 = 7 * 6 7 = 4 + 3
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)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
public final class Countdown {
public static void main(String[] args) {
List<Integer> allNumbers = new ArrayList<Integer>(List.of(
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100 ));
ThreadLocalRandom random = ThreadLocalRandom.current();
Collections.shuffle(allNumbers);
List<List<Integer>> numberLists = List.of(
List.of( 3, 6, 25, 50, 75, 100 ),
List.of( 100, 75, 50, 25, 6, 3 ),
List.of( 8, 4, 4, 6, 8, 9 ),
allNumbers.subList(0, 6)
);
List<Integer> targetList = List.of( 952, 952, 594, random.nextInt(101, 1000) );
for ( int i = 0; i < targetList.size(); i++ ) {
System.out.println("Using : " + numberLists.get(i));
System.out.println("Target: " + targetList.get(i));
final boolean done = countdown(numberLists.get(i), targetList.get(i));
if ( ! done ) {
System.out.println("No solution found");
}
System.out.println();
}
}
private static boolean countdown(List<Integer> numbers, int target) {
if ( numbers.size() <= 1 ) {
return false;
}
for ( int n0 : numbers ) {
List<Integer> numbers1 = new ArrayList<Integer>(numbers);
numbers1.remove(Integer.valueOf(n0));
for ( int n1 : numbers1 ) {
List<Integer> numbers2 = new ArrayList<Integer>(numbers1);
numbers2.remove(Integer.valueOf(n1));
if ( n1 >= n0 ) {
int result = n1 + n0;
List<Integer> numbersNext = new ArrayList<Integer>(numbers2);
numbersNext.addLast(result);
if ( result == target || countdown(numbersNext, target) ) {
System.out.println(result + " = " + n1 + " + " + n0);
return true;
}
if ( n0 != 1 ) {
result = n1 * n0;
numbersNext = new ArrayList<Integer>(numbers2);
numbersNext.addLast(result);
if ( result == target || countdown(numbersNext, target) ) {
System.out.println(result + " = " + n1 + " * " + n0);
return true;
}
}
if ( n1 != n0 ) {
result = n1 - n0;
numbersNext = new ArrayList<Integer>(numbers2);
numbersNext.addLast(result);
if ( result == target || countdown(numbersNext, target) ) {
System.out.println(result + " = " + n1 + " - " + n0);
return true;
}
}
if ( n0 != 1 && n1 % n0 == 0 ) {
result = n1 / n0;
numbersNext = new ArrayList<Integer>(numbers2);
numbersNext.addLast(result);
if ( result == target || countdown(numbersNext, target) ) {
System.out.println(result + " = " + n1 + " / " + n0);
return true;
}
}
}
}
}
return false;
}
}
- 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 : [3, 8, 8, 6, 10, 3] Target: 920 920 = 92 * 10 92 = 84 + 8 84 = 14 * 6 14 = 11 + 3 11 = 8 + 3
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
function countdown(numbers, target) {
if (numbers.length <= 1) {
return false;
}
for (let n0 of numbers) {
const numbers1 = numbers.filter(n => n !== n0);
for (let n1 of numbers1) {
const numbers2 = numbers1.filter(n => n !== n1);
if (n1 >= n0) {
let result = n1 + n0;
let numbersNext = [...numbers2, result];
if (result === target || countdown(numbersNext, target)) {
console.log(`${result} = ${n1} + ${n0}`);
return true;
}
if (n0 !== 1) {
result = n1 * n0;
numbersNext = [...numbers2, result];
if (result === target || countdown(numbersNext, target)) {
console.log(`${result} = ${n1} * ${n0}`);
return true;
}
}
if (n1 !== n0) {
result = n1 - n0;
numbersNext = [...numbers2, result];
if (result === target || countdown(numbersNext, target)) {
console.log(`${result} = ${n1} - ${n0}`);
return true;
}
}
if (n0 !== 1 && n1 % n0 === 0) {
result = Math.floor(n1 / n0);
numbersNext = [...numbers2, result];
if (result === target || countdown(numbersNext, target)) {
console.log(`${result} = ${n1} / ${n0}`);
return true;
}
}
}
}
}
return false;
}
function main() {
const 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
];
shuffle(allNumbers);
const numberLists = [
[3, 6, 25, 50, 75, 100],
[100, 75, 50, 25, 6, 3],
[8, 4, 4, 6, 8, 9],
allNumbers.slice(0, 6)
];
const targetList = [952, 952, 594, Math.floor(Math.random() * 899) + 101];
for (let i = 0; i < targetList.length; i++) {
console.log("Using : " + JSON.stringify(numberLists[i]));
console.log("Target: " + targetList[i]);
const done = countdown(numberLists[i], targetList[i]);
if (!done) {
console.log("No solution found");
}
console.log();
}
}
main();
- 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 No solution found Using : [7,8,3,25,10,6] Target: 893 893 = 918 - 25 918 = 153 * 6 153 = 150 + 3 150 = 15 * 10 15 = 8 + 7
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
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
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
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)
0.906
/* 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
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 ;
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
# 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 [
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
use rand::seq::SliceRandom;
use rand::thread_rng;
use rand::Rng;
fn main() {
let mut all_numbers = vec![
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100
];
let mut rng = thread_rng();
all_numbers.shuffle(&mut rng);
let number_lists = vec![
vec![3, 6, 25, 50, 75, 100],
vec![100, 75, 50, 25, 6, 3],
vec![8, 4, 4, 6, 8, 9],
all_numbers[0..6].to_vec(),
];
let target_list = vec![952, 952, 594, rng.gen_range(101..1000)];
for i in 0..target_list.len() {
println!("Using : {:?}", number_lists[i]);
println!("Target: {}", target_list[i]);
let done = countdown(&number_lists[i], target_list[i]);
if !done {
println!("No solution found");
}
println!();
}
}
fn countdown(numbers: &[i32], target: i32) -> bool {
if numbers.len() <= 1 {
return false;
}
for (i, &n0) in numbers.iter().enumerate() {
let mut numbers1 = Vec::new();
numbers1.extend_from_slice(&numbers[..i]);
numbers1.extend_from_slice(&numbers[i + 1..]);
for (j, &n1) in numbers1.iter().enumerate() {
let mut numbers2 = Vec::new();
numbers2.extend_from_slice(&numbers1[..j]);
numbers2.extend_from_slice(&numbers1[j + 1..]);
if n1 >= n0 {
// Addition
let result = n1 + n0;
let mut numbers_next = numbers2.clone();
numbers_next.push(result);
if result == target || countdown(&numbers_next, target) {
println!("{} = {} + {}", result, n1, n0);
return true;
}
// Multiplication
if n0 != 1 {
let result = n1 * n0;
let mut numbers_next = numbers2.clone();
numbers_next.push(result);
if result == target || countdown(&numbers_next, target) {
println!("{} = {} * {}", result, n1, n0);
return true;
}
}
// Subtraction
if n1 != n0 {
let result = n1 - n0;
let mut numbers_next = numbers2.clone();
numbers_next.push(result);
if result == target || countdown(&numbers_next, target) {
println!("{} = {} - {}", result, n1, n0);
return true;
}
}
// Division
if n0 != 1 && n1 % n0 == 0 {
let result = n1 / n0;
let mut numbers_next = numbers2.clone();
numbers_next.push(result);
if result == target || countdown(&numbers_next, target) {
println!("{} = {} / {}", result, n1, n0);
return true;
}
}
}
}
}
false
}
- 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 : [75, 3, 2, 7, 25, 50] Target: 480 480 = 1250 - 770 770 = 77 * 10 1250 = 50 * 25 77 = 75 + 2 10 = 7 + 3
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 ;
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
import "std/random.zc"
import "std/vec.zc"
let rng: Random;
fn shuffle(a: int*, len: usize) {
for let i: usize = len - 1; i >= 1; --i {
let j = rng.next_int_range(0, (int)i);
if j != i {
let t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
fn countdown(numbers: Vec<int>, target: int) -> bool {
if numbers.length() <= 1 { return false; }
for i in 0..numbers.length() {
let n0 = numbers.get(i);
let numbers1 = Vec<int>::new();
for k in 0..numbers.length() {
if k != i { numbers1 << numbers.get(k); }
}
for j in 0..numbers1.length() {
let n1 = numbers1.get(j);
let numbers2 = Vec<int>::new();
for k in 0..numbers1.length() {
if k != j { numbers2 << numbers1.get(k); }
}
if n1 >= n0 {
// Addition.
let result = n1 + n0;
let numbers_new = numbers2.clone();
numbers_new << result;
if result == target || countdown(numbers_new, target) {
println "{result} = {n1} + {n0}";
return true;
}
// Multiplication.
if n0 != 1 {
result = n1 * n0;
let numbers_next = numbers2.clone();
numbers_next << result;
if result == target || countdown(numbers_next, target) {
println "{result} = {n1} * {n0}";
return true;
}
}
// Subtraction.
if n1 != n0 {
result = n1 - n0;
let numbers_next = numbers2.clone();
numbers_next << result;
if result == target || countdown(numbers_next, target) {
println "{result} = {n1} - {n0}";
return true;
}
}
// Division.
if n0 != 1 && !(n1 % n0) {
result = n1 / n0;
let numbers_next = numbers2.clone();
numbers_next << result;
if result == target || countdown(numbers_next, target) {
println "{result} = {n1} / {n0}";
return true;
}
}
}
}
}
return false;
}
fn main() {
rng = Random::new();
let all_numbers = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100];
shuffle(all_numbers, all_numbers.len);
let a1 = [3, 6, 25, 50, 75, 100];
let a2 = [100, 75, 50, 25, 6, 3]; // see if there's much difference if we reverse a1
let a3 = [8, 4, 4, 6, 8, 9];
let a4: int[6];
for i in 0..6 { a4[i] = all_numbers[i]; }
let aa: int*[4] = [a1, a2, a3, a4];
let target_list = [952, 952, 594, rng.next_int_range(101, 999)];
for i in 0..4 {
let v = Vec<int>::new();
print "Using : [";
for j in 0..6 {
print "{aa[i][j]}, ";
v << aa[i][j];
}
println "\b\b]";
println "Target: {target_list[i]}";
let done = countdown(v, target_list[i]);
if !done { println "No exact solution found."; }
println "";
}
}
- Output:
Note that 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 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 : [9, 4, 3, 100, 2, 25] Target: 243 243 = 218 + 25 218 = 436 / 2 436 = 109 * 4 109 = 100 + 9
const std = @import("std");
const Writer = std.Io.Writer;
const Op = enum { add, mul, sub, div };
fn printSlice(stdout: *Writer, slice: []const u32) !void {
try stdout.writeAll("Using : [");
for (slice, 0..) |item, i| {
if (i > 0) try stdout.writeAll(", ");
try stdout.print("{d}", .{item});
}
try stdout.writeAll("]\n");
}
fn apply(op: Op, a: u32, b: u32) ?u32 {
return switch (op) {
.add => a + b,
.mul => if (b != 1) a * b else null,
.sub => if (a != b) a - b else null,
.div => if (b != 1 and a % b == 0) @divExact(a, b) else null,
};
}
fn opChar(op: Op) u8 {
return switch (op) {
.add => '+',
.mul => '*',
.sub => '-',
.div => '/',
};
}
fn countdown(stdout: *Writer, numbers: []u32, target: u32) !?void {
if (numbers.len <= 1) return null;
const ops = [_]Op{ .add, .mul, .sub, .div };
for (0..numbers.len) |i| {
for (i + 1..numbers.len) |j| {
const hi = @max(numbers[i], numbers[j]);
const lo = @min(numbers[i], numbers[j]);
// Build reduced list: remove i and j, compact the rest
var buf: [24]u32 = undefined;
var len: usize = 0;
for (0..numbers.len) |k| {
if (k != i and k != j) {
buf[len] = numbers[k];
len += 1;
}
}
for (ops) |op| {
if (apply(op, hi, lo)) |result| {
buf[len] = result;
if (result == target or try countdown(stdout, buf[0 .. len + 1], target) != null) {
try stdout.print("{d} = {d} {c} {d}\n", .{ result, hi, opChar(op), lo });
return {};
}
}
}
}
}
return null;
}
pub fn main(init: std.process.Init) !void {
const io = init.io;
var all_numbers = [_]u32{ 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 random_source = std.Random.IoSource{ .io = io };
const random = random_source.interface();
random.shuffle(u32, &all_numbers);
const number_lists = [_][]const u32{
&[_]u32{ 3, 6, 25, 50, 75, 100 },
&[_]u32{ 100, 75, 50, 25, 6, 3 },
&[_]u32{ 8, 4, 4, 6, 8, 9 },
all_numbers[0..6],
};
const target_list = [_]u32{ 952, 952, 594, random.intRangeAtMost(u32, 101, 999) };
var stdout_writer = std.Io.File.stdout().writer(io, &.{});
const stdout = &stdout_writer.interface;
const start = std.Io.Clock.awake.now(io);
for (number_lists, target_list) |numbers, target| {
try printSlice(stdout, numbers);
try stdout.print("Target: {d}\n", .{target});
var buf: [24]u32 = undefined;
@memcpy(buf[0..numbers.len], numbers);
if (try countdown(stdout, buf[0..numbers.len], target) == null) {
try stdout.writeAll("No solution found\n");
}
try stdout.writeAll("\n");
}
const elapsed = start.untilNow(io, .awake);
std.debug.print("Took {} ms\n", .{elapsed.toMilliseconds()});
}
- 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 = 225 * 106 225 = 75 * 3 106 = 100 + 6 Using : [8, 4, 4, 6, 8, 9] Target: 594 594 = 54 * 11 11 = 8 + 3 54 = 9 * 6 3 = 12 / 4 12 = 8 + 4 Using : [4, 5, 2, 9, 10, 4] Target: 972 972 = 162 * 6 162 = 18 * 9 6 = 10 - 4 18 = 9 * 2 9 = 5 + 4 Took 5 ms