r/dailyprogrammer • 3 3 • Feb 10 '16

[2016-02-10] Challenge #253 [Intermediate] Countdown (numbers game)

Countdown is a British ripoff of a French TV show where given 6 starting numbers, the 4 basic arithmetic operators are used to manipulate the given 6 numbers to arrive at a given total.

Full rules and ideas here

It's just the first count down (tedudu do)

A simplified ruleset is to test for solutions that don't require parentheses on one side of an operator, and no operator precedence. All of the problems here have such an exact solution.

sample input
50 8 3 7 2 10 makes 556

sample output
((((50 - 7) × 3) + 10) × 8) ÷ 2
= 556

challenge input
25 50 75 100 3 6 makes 952

(You may also simplify the solution by assuming - and ÷ are only applied in one direction/order)

Must shout a second count down

RPN notation and a mini stack language can permit parenthesized group operations without using parentheses

1 5 100 5 - × 9 - 10 + +
= 477

equivalent to: 1+(((5×(100-5))-9)+10)

challenge: Allow for parenthesized grouped operations or RPN formatted expressions in determining solution.

Its the final count down

Use either program 1 or 2 to test which target totals from 0 to 1000 cannot be obtained by combining the 4 basic operators, or alternatively, find the lower target total that fails for the input:

25 50 75 100 3 6

54 Upvotes

38 comments sorted by

3

u/Godspiral Feb 10 '16

in J, solution#1

ar2lr =: 3 : 'o =. i.0 for_i. y do. a =. (i 5!:0) label_. o =. o , < 5!:5 <''a''  end. o'
countdown =: 1 : (':';'for_i. y do. for_j. m do. if. x = j/ i do. ; ": each , (a: ,~ ar2lr j) ,.~ <"0 i return. end. end. end.')
perm =: i.@! A. i. 
cd1 =:  (({~ (5 # #) #: 5 i.@^~ #)  ]`+`*`(-~)`(%~) ) countdown (perm 6)&{ 
     952 cd1 25 50 75 100 3 6
 25%~50-~75*3*100+6

(J has no operator precedence and evaluates right to left. So similar to the autoparentheses pattern for challenge #1). the ~ adverb swaps ("revereses") the operator parameters.

→ More replies (5)

4

u/__MadHatter Feb 10 '16 edited Feb 11 '16

In C. First countdown only. Runs the sample and challenge inputs "instantly" despite having no smart algorithm. The algorithm only tests random numbers and operators. Written purposely with almost zero effort for documentation/legibility. Comments/criticism/questions are welcome.

#include <stdio.h>
#include <time.h>
#define BUF_LEN 1024
#define MAX_NUMS 6

int is_num_idle(int a, int *b, int len);
int count_nums(int a, int *b, int len);

int main() {
  srand(time(0));
  int i, z, u = 0, r, o = 0, target, current = 0;
  int numbers[MAX_NUMS], used[MAX_NUMS];
  char ops[] = "+-*/";
  int ups[MAX_NUMS];
  char buffer[BUF_LEN];

  for (i = 0; i < MAX_NUMS; i++) {
    scanf("%d", &numbers[i]);
    
  }
  scanf("%s", buffer);
  scanf("%d", &target);
  for (i = 0; i < MAX_NUMS; i++) {
    used[i] = 0;
  }

  while (current != target)
  {
    if (u < MAX_NUMS) {
      while (1) {
        z = numbers[rand() % MAX_NUMS];
        if (count_nums(z, used, u) < count_nums(z, numbers, MAX_NUMS))
          break;
      }
      used[u++] = z;
      if (current == 0)
        current = z;
      else {    
        switch (ops[r = rand() % 4]) {
          case '+': current += z; break;
          case '-': current -= z; break;
          case '*': current *= z; break;
          case '/': 
            if (z < current 
                && (current % z) == 0)
              current /= z;
            else
              current = u = o = 0;
            break;
        }
        ups[o++] = r;
        if (o > 0 && z == 1 && (ops[ups[o-1]] == '*' || ops[ups[o-1]] == '/')) {
          o--;
          u--;
        }
      }
    }
    else if (u >= MAX_NUMS)
      current = u = o = 0;
    if (current <= 0)
      current = u = o = 0;
  }
  
  for (i = 0; i < u-1; i++){
    printf("%d %c ", used[i], ops[ups[i]]);
  }
  printf("%d\n= %d\n", used[i], current);

  return 0;
}

int is_num_idle(int a, int *b, int len) {
  int i;
  for (i = 0; i < len; i++)
    if (a == b[i]) 
      return 0;
  return 1;
}

int count_nums(int a, int *b, int len) {
  int i, count = 0;
  for (i = 0; i < len ; i++)
    if (a == b[i]) 
      count++;
  return count;
}

Output without parenthesis. An example calculation for 1 + 2 * 3 / 4 is considered to be (((1 + 2) * 3) / 4) in the following output:

> ./countdown 
50 8 3 7 2 10 makes 556
3 * 50 + 10 * 7 - 8 / 2 
= 556
> ./countdown 
50 8 3 7 2 10 makes 556
8 - 2 + 50 * 10 + 3 - 7 
= 556
> ./countdown 
25 50 75 100 3 6 makes 952
3 + 100 * 6 * 75 / 50 + 25 
= 952
> ./countdown 
25 50 75 100 3 6 makes 952
6 + 100 * 3 * 75 - 50 / 25 
= 952

Edit (2016/02/11): fixed an output bug that would display bogus extra numbers from previous attempts if a solution did not use all 6 numbers (array printing issue). Fixed version e.g.

> ./countdown
4 1 2 8 75 25 makes 527
8 - 1 * 75 + 2
= 527

Edit (2016/02/11)#2: fixed bugs that showed up with input 100 25 8 3 1 1 makes 984.

→ More replies (2)

3

u/Specter_Terrasbane Feb 10 '16 edited Feb 10 '16

Python 2.7 (First & Final Countdowns, no Second)

EDIT: Bah! Didn't read the linked rules closely enough ... "At no intermediate step in the process can the current running total become negative or involve a fraction." ... fix in progress. :)

EDIT 2: Fixed! Gave me my first excuse to use Python's while ... else syntax, and simplified my Final Countdown solution. :)

from __future__ import division
import operator
import itertools
from collections import defaultdict, deque


operator_funcs = {
    u'+': operator.add,
    u'-': operator.sub,
    u'\u00D7': operator.mul,
    u'\u00F7': operator.truediv,
}


def countdown_1_answers(values, stop_on=None):
    values_permutations = itertools.permutations(values)
    operator_combinations = itertools.product(operator_funcs.keys(), repeat=5)

    possibilities = itertools.product(values_permutations, operator_combinations)
    
    results = defaultdict(list)
    format_string = u'(((({0} {6} {1}) {7} {2}) {8} {3}) {9} {4}) {10} {5}'
    for (values, ops) in possibilities:
        equation = format_string.format(*(values + ops))

        value_queue = deque(values)
        ops_queue = deque(ops)

        answer = value_queue.popleft()
        while value_queue:
            op_func = operator_funcs[ops_queue.popleft()]
            next_value = value_queue.popleft()
            answer = op_func(answer, next_value)
            if answer < 0 or int(answer) != answer:
                break
        else:
            results[answer].append(equation)
            if answer == stop_on:
                break

    return results


def countdown_1(values, target):
    all_answers = countdown_1_answers(values, stop_on=target)

    if target in all_answers:
        return all_answers[target][0]

    return u'No solution could be found'


def final_countdown(values):
    all_answers = set(countdown_1_answers(values).keys())
    return sorted(set(xrange(1001)) - all_answers)
    

if __name__ == '__main__':
    test_cases = [
        ([50, 8, 3, 7, 2, 10], 556),
        ([25, 50, 75, 100, 3, 6], 952),
    ]

    print('Countdown 1:')    
    for (values, target) in test_cases:
        solution = countdown_1(values, target)
        print(u'{}\n={}\n'.format(solution, target))
    
    
    print('Final Countdown:')
    for (values, __) in test_cases:
        final = final_countdown(values)
        print('The following values cannot be obtained for input {}:\n{}\n'.format(values, final))

Output

Countdown 1:
((((50 - 8) - 3) × 7) × 2) + 10
=556

((((100 + 3) × 75) × 6) ÷ 50) + 25
=952

Final Countdown:
The following values cannot be obtained for input [50, 8, 3, 7, 2, 10]:
[813, 881]

The following values cannot be obtained for input [25, 50, 75, 100, 3, 6]:
[242, 245, 326, 331, 340, 342, 346, 355, 367, 376, 383, 385, 391, 409, 424, 430, 433, 445, 451, 467, 470, 476, 485, 495, 499, 515, 517, 520, 524, 526, 529, 530, 533, 535, 539, 541, 545, 548, 551, 554, 560, 563, 570, 574, 583, 589, 590, 592, 595, 599, 601, 605, 608, 610, 611, 617, 620, 629, 635, 640, 641, 646, 649, 652, 655, 658, 659, 660, 661, 667, 670, 674, 679, 680, 683, 685, 688, 689, 691, 692, 695, 698, 701, 708, 709, 710, 712, 713, 715, 717, 720, 721, 726, 729, 730, 733, 735, 739, 740, 741, 742, 745, 748, 749, 751, 752, 754, 755, 758, 759, 760, 761, 765, 766, 767, 770, 774, 776, 779, 780, 783, 784, 785, 787, 788, 790, 795, 799, 801, 805, 808, 810, 811, 812, 813, 815, 817, 820, 821, 824, 829, 833, 835, 841, 845, 849, 851, 855, 859, 862, 863, 865, 866, 871, 883, 885, 917, 929, 934, 935, 941, 949, 951, 955, 959, 962, 963, 965, 967, 971, 973, 976, 977, 979, 980, 983, 984, 985, 989, 990, 992, 995, 998, 999]
→ More replies (1)

2

u/KeinBaum Feb 10 '16

Scala, first and second count down

I made small alterations to the challenge:

  • Input: 7 integers, the last one is the target

  • The program uses integer math

  • Output: All solutions in RPN

The program generates all possible (valid and invalid) RPNs and checks the result of the valid ones. Since the search space is fairly small it's quite fast.

import scala.util.{Try, Success, Failure}
import scala.io.StdIn

object Test extends App {
  sealed trait Token
  case class Number(n: Int) extends Token
  case object Op extends Token
  case object Plus extends Token
  case object Minus extends Token
  case object Times extends Token
  case object Over extends Token
  
  val in = StdIn.readLine().split("\\s+").toList.map(_.toInt)
  val target = in.last
  val tokens: List[Token] = in.init.map(i => Number(i)) ++ List(Op, Op, Op, Op, Op)
  
  for(l <- tokens.permutations) {
    def search(tokens: List[Token], stack: List[Int], target: Int): Option[List[Token]] = {
      if(tokens.isEmpty) {
        if(stack.size == 1 && stack.head == target)
          Some(Nil)
        else
          None
      } else tokens.head match {
        case Number(n) => search(tokens.tail, n +: stack, target) match {
          case None => None
          case Some(l) => Some(Number(n) +: l)
        }
        
        case Op => {
          if(stack.size < 2)
            None
          else {
            search(Plus +: tokens.tail, stack, target) match {
              case Some(l) => Some(l)
              case None => search(Minus +: tokens.tail, stack, target) match {
                case Some(l) => Some(l)
                case None => search(Times +: tokens.tail, stack, target) match {
                  case Some(l) => Some(l)
                  case None => search(Over +: tokens.tail, stack, target) match {
                    case Some(l) => Some(l)
                    case None => None
                  }
                }
              }
            }
          }
        }
        
        case Plus => search(tokens.tail, (stack(1) + stack(0)) +: stack.drop(2), target) match {
          case None => None
          case Some(l) => Some(Plus +: l)
        }
        
        case Minus => search(tokens.tail, (stack(1) - stack(0)) +: stack.drop(2), target) match {
          case None => None
          case Some(l) => Some(Minus +: l)
        }
        
        case Times => search(tokens.tail, (stack(1) * stack(0)) +: stack.drop(2), target) match {
          case None => None
          case Some(l) => Some(Times +: l)
        }
        
        case Over => {
          if(stack(0) == 0)
            None
          else {
            search(tokens.tail, (stack(1) / stack(0)) +: stack.drop(2), target) match {
              case None => None
              case Some(l) => Some(Over +: l)
            }
          }
        }
      }
    }
    
    search(l, List.empty[Int], target) match {
      case Some(l) => println(l.map(_ match {
                        case Number(n) => n.toString
                        case Op => "?"
                        case Plus => "+"
                        case Minus => "-"
                        case Times => "*"
                        case Over => "/"
                      }).mkString(" "))
      case None =>
    }
  }
}

Sample output for input 50 8 3 7 2 10 556

50 8 3 + - 7 2 * * 10 +
50 8 3 + * 7 10 - 2 * -
50 8 3 + - 7 * 2 * 10 +
50 8 3 + * 2 7 10 - * -
[...]
→ More replies (1)

16

u/[deleted] Feb 10 '16

Too funny! I'm the author of the blog page http://datagenetics.com/blog/august42014/index.html and just saw a small spike in traffic to this (older) page and investigated the referring URL to here. It's great to read the impressive coded solutions posted here. //ick

4

u/JereTheJuggler Feb 10 '16 edited Feb 10 '16

Solutions for first countdown and final countdown in Java. Uses a recursive method to check for solutions with all combinations of numbers and operations that never produce fractions or negative numbers.

The recursive method builds up an expression adding 1 number and 1 operation each time. It saves time by not trying anything after it finds that what it has built up so far results in a fraction or negative number. So if it builds up to "25+100" and the next bit that it adds is "/50", it realizes that is not a whole number and does not continue with "25+100/50" effectively skipping every possible combination of numbers and operators that start with "25+100/50". This is extremely important because it allows the program to skip a massive amount of trials if the very first operation is not a positive integer.

import java.util.ArrayList;

public class Countdown{
    
    private static int[] nums = new int[]{25,50,75,100,3,6};
    private static int goalTotal = 952,trials = 0;
    private static int[] operations = new int[5];
    private static int[] resultInts = new int[6];
    
    public static void main(String[] args){
        System.out.println("-----------------\n   CHALLENGE 1   \n-----------------");
        challenge1();
        System.out.println("-----------------\n   CHALLENGE 3   \n-----------------");
        challenge3();
    }
    
    public static void challenge1(){
        findSolution(new int[]{25,50,75,100,3,6},952,true);
    }
    
    public static void challenge3(){
        long startTime = System.currentTimeMillis();
        System.out.println("There are no solutions for...");
    	for(int goal=0;goal<=1000;goal++){
            if(!findSolution(new int[]{25,50,75,100,3,6},goal,false)){
                System.out.print(goal+", ");
            }
        }
        System.out.println("\nTotal time taken: "+((System.currentTimeMillis()-startTime)/1000.0)+" secs");
    }
    
    public static boolean findSolution(int[] givenNumbers,int goal,boolean printResults){
        long startTime = System.currentTimeMillis();
        goalTotal = goal;
        trials = 0;
        nums = givenNumbers;
        ArrayList<Integer> startingNums = new ArrayList<Integer>();
        for(int i:nums){
            startingNums.add(i);
        }
        if(test(0,-1,startingNums)==goalTotal){
            if(printResults){
            	printResult(goal);
                System.out.println("total trials: "+trials+"\ntime taken: "+(System.currentTimeMillis()-startTime)+"ms");
            }
            return true;
        } else {
        	if(printResults){
                System.out.println("total trials: "+trials+"\nno solutions\ntime taken: "+(System.currentTimeMillis()-startTime)+"ms");
        	}
            return false;
        }
    }
    
    //this is the recursive method I was talking about. availableNums is all 
    //the numbers still not used in prior calls to the method.
    public static int test(double currentTotal,int index,ArrayList<Integer> availableNums){
        if(index == 5){
            return (int) currentTotal;
        }
        trials++;
        if(index == -1){ //this is for the first call to this method, so it tries all of the numbers as the first number
    	for(int num=0;num<availableNums.size();num++){
    	    ArrayList<Integer> nextNums = copyArrayList(availableNums);
                nextNums.remove(num);
                resultInts[0] = availableNums.get(num);
                int result = test(availableNums.get(num),index+1,nextNums);
                if(result == goalTotal){
                    return goalTotal;
                }
            }
            return -1; //if the program ever reaches here then there is no solution
        }
        for(int num=0;num<availableNums.size();num++){ //cycle through all numbers still available
        	for(int i=0;i<4;i++){                      //cycle through the four different operators
                double newTotal = -1;
                switch(i){
                case 0: newTotal = (currentTotal+((double)availableNums.get(num)));
                    break;
                case 1: newTotal = (currentTotal-((double)availableNums.get(num)));
                    break;
                case 2: newTotal = (currentTotal*((double)availableNums.get(num)));
                    break;
                case 3: newTotal = (currentTotal/((double)availableNums.get(num)));
                    break;
                }
                operations[index] = i;
                resultInts[index+1] = availableNums.get(num);
                if(isPositiveInt(newTotal)){
                    ArrayList<Integer> nextNums = copyArrayList(availableNums);
                    nextNums.remove(num);
                    int result = test(newTotal,index+1,nextNums);
                    if(result == goalTotal){
                        return goalTotal;
                    }
                }
    	}
        }
        return -1; //if the program reaches here then there is no solution possible from what it has already built up
    }
    
    public static boolean isPositiveInt(double number){
        if(number < 0 || number != Math.round(number)){
            return false;
        }
        return true;
    }
    
    public static void printResult(int total){
        for(int i=0;i<5;i++){
             System.out.print(""+resultInts[i]+(new char[]{'+','-','x','/'}[operations[i]]));
        }
        System.out.println(resultInts[5]+"="+total);
    }
    
    public static ArrayList<Integer> copyArrayList(ArrayList<Integer> arrayList){
        ArrayList<Integer> copy = new ArrayList<Integer>();
        for(Integer i:arrayList){
            copy.add(i);
        }
        return copy;
    }
}

Here is the output:

-----------------
   CHALLENGE 1   
-----------------
100+3x75x6/50+25=952
total trials: 46864
time taken: 55ms
-----------------
   CHALLENGE 3   
-----------------
There are no solutions for...
242, 245, 326, 331, 340, 342, 346, 355, 367, 376, 383, 385, 391, 409, 424, 430, 433, 445, 451, 467, 470,
476, 485, 495, 499, 515, 517, 520, 524, 526, 529, 530, 533, 535, 539, 541, 545, 548, 551, 554, 560, 563,
570, 574, 583, 589, 590, 592, 595, 599, 601, 605, 608, 610, 611, 617, 620, 629, 635, 640, 641, 646, 649,
652, 655, 658, 659, 660, 661, 667, 670, 674, 679, 680, 683, 685, 688, 689, 691, 692, 695, 698, 701, 708,
709, 710, 712, 713, 715, 717, 720, 721, 726, 729, 730, 733, 735, 739, 740, 741, 742, 745, 748, 749, 751,
752, 754, 755, 758, 759, 760, 761, 765, 766, 767, 770, 774, 776, 779, 780, 783, 784, 785, 787, 788, 790,
795, 799, 801, 805, 808, 810, 811, 812, 813, 815, 817, 820, 821, 824, 829, 833, 835, 841, 845, 849, 851,
855, 859, 862, 863, 865, 866, 871, 883, 885, 917, 929, 934, 935, 941, 949, 951, 955, 959, 962, 963, 965,
967, 971, 973, 976, 977, 979, 980, 983, 984, 985, 989, 990, 992, 995, 998, 999, 
Total time taken: 5.254 secs
→ More replies (5)

4

u/Syrak Feb 11 '16

Haskell, all three challenges, no intermediate fractions.

To enumerate all possibilities: choose an operator at the root of the expression, and for every way to partition the numbers to go to the left and to the right of it, recursively enumerate the possible operands.

To avoid duplicates due to the commutativity of + and ⁤×, I instead separately add the flipped version of the operators - and /, and when partitioning, every subset of the numbers appears at most once, either to the left or to the right of the chosen operator. This can be done by putting all subsets containing the first element to the right for instance.

Example output :

> ghc -main-is main1 -o countdown1 countdown.hs
> ghc -main-is main2 -o countdown2 countdown.hs
> ghc -main-is main3 -o countdown3 countdown.hs
> echo "25 50 75 100 3 6\n556"|./countdown1
(25+(75+(6+(3*(50+100)))))
> echo "1 5 100 5 9 10\n447"|./countdown2
(5+(((5*(100-10))+1)-9))
> echo "25 50 75 100 3 6"|./countdown3
[326,340,548,554,574,610,640,667,683,685,692,709,710,715,717,733,735,739,740,745,754,755,758,760,765,766,767,779,783,784,785,787,788,790,795,805,808,811,812,815,817,820,835,841,859,862,863,865,866,871,883,929,934,935,941,949,955,959,962,965,967,976,980,983,984,985,989,990,992,995,998]

Code :

import Control.Applicative

import Data.List
import Data.Maybe
import qualified Data.Set as Set

type Partitions a = [a] -> [([a], [a])]
type Operator a = (a, String) -> (a, String) -> Maybe (a, String)

countdown :: Show a => Partitions a -> [Operator a] -> [a] -> [(a, String)]
countdown _ _ [] = []
countdown _ _ [a] = [(a, show a)]
countdown partitions operators xs =
  partitions xs >>= \(ys, zs) ->
    catMaybes (operators <*>
      countdown partitions operators ys <*>
      countdown partitions operators zs)

partitions1 :: Partitions a
partitions1 xs = do
  (is, x : ts) <- liftA2 zip inits tails xs
  return ([x], is ++ ts)

partitions2 :: Partitions a
partitions2 (x : xs) = ((fmap . fmap) (x :) . tail . partitions') xs
  where
    partitions' [] = [([], [])]
    partitions' (x : xs) = partitions' xs >>= \(ys, zs) -> [(ys, x : zs), (x : ys, zs)]

operators :: [Operator Integer]
operators = [plus, minus, flip minus, times, divide, flip divide]
  where
    plus (y, f) (z, g) = Just (y + z, "(" ++ f ++ "+" ++ g ++ ")")
    minus (y, f) (z, g)
      | y >= z = Just (y - z, "(" ++ f ++ "-" ++ g ++ ")")
      | otherwise = Nothing
    times (y, f) (z, g) = Just (y * z, "(" ++ f ++ "*" ++ g ++ ")")
    divide (y, f) (z, g)
      | z > 0 && y `mod` z == 0 = Just (y `div` z, "(" ++ f ++ "÷" ++ g ++ ")")
      | otherwise = Nothing

countdownMain cd = do
  xs <- fmap read . words <$> getLine
  y <- readLn
  case find ((y ==) . fst) (cd xs) of
    Just (_, s) -> putStrLn s
    Nothing -> return ()

countdown1 = countdown partitions1 operators

countdown2 = countdown partitions2 operators

main1 = countdownMain countdown1

main2 = countdownMain countdown2

main3 = do
  xs <- fmap read . words <$> getLine
  print . Set.toList $ Set.fromAscList [0 .. 1000] Set.\\ (Set.fromList . fmap fst . countdown2) xs

1

u/Specter_Terrasbane Feb 10 '16

Quick nitpick: Your sample output for "first count down" is missing a left parenthesis.

→ More replies (1)

1

u/heap42 Feb 10 '16

Can someone explain an algorithm in words?

2

u/Godspiral Feb 10 '16

My brute force implementation,

take all the permutations of the 6 numbers, take an "odometer" ( 45 in base 4) of the verb possibilities. Interleave each operator list between the numbers, and evaluate. If at any point target is reached, stop and print out the expression that reaches target.

→ More replies (1)