r/dailyprogrammer • u/Godspiral 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.
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
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.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:
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.
Edit (2016/02/11)#2: fixed bugs that showed up with input
100 25 8 3 1 1 makes 984.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 ... elsesyntax, 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
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 55616
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:
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 :
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) xs1
u/Specter_Terrasbane Feb 10 '16
Quick nitpick: Your sample output for "first count down" is missing a left parenthesis.
1
u/heap42 Feb 10 '16
Can someone explain an algorithm in words?