Happy New Year!

January 1, 2013

As we begin the new year, we note that 109-8*7+654*3-2/1 = 2013. There are three other combinations of the numbers 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, in order, combined with the five operators NIL, +, -, * and / that also evaluate to 2013.

Your task is to write a program that finds all four expressions that evaluate to 2013. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
11 Comments »

11 Responses to “Happy New Year!”

  1. Paul said
    January 1, 2013 at 10:00 AM

    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 ev
  2. Jussi Piitulainen said
    January 1, 2013 at 12:25 PM

    With 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')
  3. Pascal Bourguignon said
    January 1, 2013 at 1:11 PM 
    (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"
  5. jpverkamp said
    January 2, 2013 at 10:26 PM

    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)
  6. David said
    January 3, 2013 at 5:29 PM

    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-1
  7. ardnew said
    January 3, 2013 at 8:19 PM

    It 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

  9. Joe A said
    January 6, 2013 at 6:39 PM

    python with recursion

    def fun_2013(cur=10,expr=''):
	expr += str(cur)

	if cur == 1:
		if eval(expr) == 2013:
			print expr
		return;

	fun_2013 (cur-1, expr)
	fun_2013 (cur-1, expr + "+")
	fun_2013 (cur-1, expr + "-")
	fun_2013 (cur-1, expr + "/")
	fun_2013 (cur-1, expr + "*")

Leave a comment