Happy New Year!
January 1, 2013
We will be following a post on Wolfram’s Blog that describes a solution to the problem. The basic idea is to generate all 59 = 1953125 possible combinations of numbers interspersed with operators, evaluate them, and report the ones that are equal to 2013. We will use the expression evaluator from a previous exercise.
Wolfram begins by defining the numbers and operators:
(define nums (list "10" "9" "8" "7" "6" "5" "4" "3" "2" "1"))
(define ops (list "" "+" "-" "*" "/"))
A built-in function of Mathematica computes all the possible combinations of nine copies of the five operators:
(define (tuples xs n)
(let loop ((n (- n 1)) (zs (map list xs)))
(if (zero? n) zs
(loop (- n 1)
(mappend (lambda (z)
(map (lambda (x) (cons x z)) xs))
zs)))))
Then another built-in function of Mathematica “riffles” the numbers and operators together, like riffling two decks of cards to intermingle them:
(define (riffle xs ys)
(let loop ((xs xs) (ys ys) (zs (list)))
(if (null? xs)
(reverse (append (reverse ys) zs))
(loop ys (cdr xs) (cons (car xs) zs)))))
Then another function joins the pieces together to form a string; the Mathematica function is StringJoin, but since we already have a function of that name in the Standard Prelude, we call our function catenate:
(define (catenate ss) (apply string (mappend string->list ss)))
Putting it together, we generate the list of 1953125 combinations of operators, riffle each one with the ten numbers, catenate them into the expr variable, evaluate each one, and collect those that are equal to 2013:
(define (happy-new-year n))
(let loop ((xs (tuples ops 9)) (zs (list)))
(if (null? xs) zs
(let ((expr (catenate (riffle nums (car xs)))))
(loop (cdr xs) (if (= (evaluate expr) n) (cons expr zs) zs)))))
All that is left is to print the survivors:
> (for-each
(lambda (x) (display x) (newline))
(happy-new-year 2013))
109-8*7+654*3-2/1
109-8*7+654*3-2*1
10*9*8*7/6/5*4*3-2-1
10*98/7*6/5*4*3-2-1
We used mappend from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/ov1mQQsc.
Happy 2013 to you all. Here a version in Python.
from __future__ import division from itertools import product ops = ["", "+", "-", "*","/"] nums = [str(i) for i in range(10, 0, -1)] def riffle(a, b): ita, itb = iter(a), iter(b) while 1: yield ita.next() yield itb.next() for op in product(ops, repeat=9): ev = "".join(riffle(nums, op)) if eval(ev) == 2013: print evWith Python 3 /, I suppose it’s just luck that some floating point approximation does not hide a proper solution :) Anyway, here’s a denser Python expression.
from itertools import product, chain, repeat print(*(e for e in map(lambda rest : '10' + ''.join(rest).replace('|', ''), product(*chain(*zip(repeat('|+-*/'), '987654321')))) if eval(e) == 2013), sep = '\n')(defun combine (nums) (cond ((null nums) '("")) ((null (cdr nums)) nums) (t (loop for rest in (combine (cdr nums)) nconc (loop for op in '("" "+" "-" "*" "/") collect (concatenate 'string (car nums) op rest)))))) (progn (assert (equal (combine '("1")) '("1"))) (assert (equal (combine '("2" "1")) '("21" "2+1" "2-1" "2*1" "2/1"))) (assert (equal (combine '("3" "2" "1")) '("321" "3+21" "3-21" "3*21" "3/21" "32+1" "3+2+1" "3-2+1" "3*2+1" "3/2+1" "32-1" "3+2-1" "3-2-1" "3*2-1" "3/2-1" "32*1" "3+2*1" "3-2*1" "3*2*1" "3/2*1" "32/1" "3+2/1" "3-2/1" "3*2/1" "3/2/1")))) (ql:quickload :infix) (loop for iexpr in (combine '("10" "9" "8" "7" "6" "5" "4" "3" "2" "1")) for expr = (infix:string->prefix iexpr) for n = (eval expr) when (= n 2013) do (print iexpr)) "10*98/7*6/5*4*3-2-1" "10*9*8*7/6/5*4*3-2-1" "109-8*7+654*3-2*1" "109-8*7+654*3-2/1"[…] Pages: 1 2 […]
Here’s my take (in Racket):
Happy New Year
As I tend to do, I somewhat over-engineered the solution, allowing for any arbitrary list of numbers (which could actually be expanded to any datatype) and any arbitrary binary infix operators, including precedence. All of that made it a bit slower than it could have been, but it still manages to churn through the roughly 2 million possibilities for this problem in about 20 seconds (I’m using ~ for concatenation):
> (solve '(10 9 8 7 6 5 4 3 2 1) `(((~ ,(lambda (x y) (string->number (string-append (number->string x) (number->string y)))))) ((* ,*) (/ ,/)) ((+ ,+) (- ,-))) 2013) (10 ~ 9 - 8 * 7 + 6 ~ 5 ~ 4 * 3 - 2 * 1) (10 ~ 9 - 8 * 7 + 6 ~ 5 ~ 4 * 3 - 2 / 1) (10 * 9 ~ 8 / 7 * 6 / 5 * 4 * 3 - 2 - 1) (10 * 9 * 8 * 7 / 6 / 5 * 4 * 3 - 2 - 1)In Ruby…
require 'mathn' countdown = 10.downto(1).map {|n| n.to_s} ['', '+', '-', '*', '/'].repeated_permutation(9) do |perm| str = countdown.zip(perm).join puts str if eval(str) == 2013 end PS C:\Users\dave\Documents\dev\ruby> ruby .\countdown_2013.rb 109-8*7+654*3-2*1 109-8*7+654*3-2/1 10*98/7*6/5*4*3-2-1 10*9*8*7/6/5*4*3-2-1It should probably be noted that all five allowable operators may appear 0 or more times in each one of the four expressions. Your first example demonstrates that fact (and that there are 9 required binary operations to occur), but it wasn’t immediately obvious to me
a prefix version
python with recursion
[…] The task: […]
In python