Code Golf: Countdown Number Game

Question

Python

Number of characters: 548 482 425 421 416 413 408

from operator import *
n=len
def C(N,T):
 R=range(1<<n(N));M=[{}for i in R];p=1
 for i in range(n(N)):M[1<<i][1.*N[i]]="%d"%N[i]
 while p:
  p=0
  for i in R:
   for j in R:
    m=M[i|j];l=n(m)
    if not i&j:m.update((f(x,y),"("+s+o+t+")")for(y,t)in M[j].items()if y for(x,s)in M[i].items() for(o,f)in zip('+-*/',(add,sub,mul,div)))
    p|=l<n(m)
 return min((abs(x-T),e)for t in M for(x,e)in t.items())[1]

you can call it like this:

>>> print C([50, 100, 4, 2, 2, 4], 203)
((((4+2)*(2+100))/4)+50)

Takes about half a minute on the given examples on an oldish PC.

Here's the commented version:

def countdown(N,T):
  # M is a map: (bitmask of used input numbers -> (expression value -> expression text))                  
  M=[{} for i in range(1<<len(N))]

  # initialize M with single-number expressions                                                           
  for i in range(len(N)):
    M[1<<i][1.0*N[i]] = "%d" % N[i]

  # allowed operators                                                                                     
  ops = (("+",lambda x,y:x+y),("-",lambda x,y:x-y),("*",lambda x,y:x*y),("/",lambda x,y:x/y))

  # enumerate all expressions                                                                             
  n=0
  while 1:

    # test to see if we're done (last iteration didn't change anything)                                   
    c=0
    for x in M: c +=len(x)
    if c==n: break
    n=c

    # loop over all values we have so far, indexed by bitmask of used input numbers                       
    for i in range(len(M)):
      for j in range(len(M)):
        if i & j: continue    # skip if both expressions used the same input number                       
        for (x,s) in M[i].items():
          for (y,t) in M[j].items():
            if y: # avoid /0 (and +0,-0,*0 while we're at it)                                             
              for (o,f) in ops:
                M[i|j][f(x,y)]="(%s%s%s)"%(s,o,t)

  # pick best expression                                                                                  
  L=[]
  for t in M:
    for(x,e) in t.items():
      L+=[(abs(x-T),e)]
  L.sort();return L[0][1]

It works through exhaustive enumeration of all possibilities. It is a bit smart in that if there are two expressions with the same value that use the same input numbers, it discards one of them. It is also smart in how it considers new combinations, using the index into M to prune quickly all the potential combinations that share input numbers.

Haskell

Number of characters: 361 350 338 322

Fully obfuscated function:

m=map
f=toRational
a%w=m(\(b,v)->(b,a:v))w
p[]=[];p(a:w)=(a,w):a%p w
q[]=[];q(a:w)=[((a,b),v)|(b,v)<-p w]++a%q w
z(o,p)(a,w)(b,v)=[(a`o`b,'(':w++p:v++")")|b/=0]
y=m z(zip[(-),(/),(+),(*)]"-/+*")++m flip(take 2 y)
r w=do{((a,b),v)<-q w;o<-y;c<-o a b;c:r(c:v)}
c t=snd.minimum.m(\a->(abs(fst a-f t),a)).r.m(\a->(f a,show a))

Clear function:

-- | add an element on to the front of the remainder list
onRemainder :: a -> [(b,[a])] -> [(b,[a])]
a`onRemainder`w = map (\(b,as)->(b,a:as)) w

-- | all ways to pick one item from a list, returns item and remainder of list
pick :: [a] -> [(a,[a])]
pick [] = []
pick (a:as) = (a,as) : a `onRemainder` (pick as)

-- | all ways to pick two items from a list, returns items and remainder of list
pick2 :: [a] -> [((a,a),[a])]
pick2 [] = []
pick2 (a:as) = [((a,b),cs) | (b,cs) <- pick as] ++ a `onRemainder` (pick2 as)    

-- | a value, and how it was computed
type Item = (Rational, String)

-- | a specification of a binary operation
type OpSpec = (Rational -> Rational -> Rational, String)

-- | a binary operation on Items
type Op = Item -> Item -> Maybe Item

-- | turn an OpSpec into a operation
-- applies the operator to the values, and builds up an expression string
-- in this context there is no point to doing +0, -0, *0, or /0
combine :: OpSpec -> Op
combine (op,os) (ar,as) (br,bs)
    | br == 0   = Nothing
    | otherwise = Just (ar`op`br,"("++as++os++bs++")")

-- | the operators we can use
ops :: [Op]
ops = map combine [ ((+),"+"), ((-), "-"), ((*), "*"), ((/), "/") ]
        ++ map (flip . combine) [((-), "-"), ((/), "/")]

-- | recursive reduction of a list of items to a list of all possible values
-- includes values that don't use all the items, includes multiple copies of
-- some results          
reduce :: [Item] -> [Item]
reduce is = do
    ((a,b),js) <- pick2 is
    op <- ops
    c <- maybe [] (:[]) $ op a b
    c : reduce (c : js)

-- | convert a list of real numbers to a list of items
items :: (Real a, Show a) => [a] -> [Item]
items = map (\a -> (toRational a, show a))

-- | return the first reduction of a list of real numbers closest to some target
countDown:: (Real a, Show a) => a -> [a] -> Item
countDown t is = snd $ minimum $ map dist $ reduce $ items is
    where dist is = (abs . subtract t' . fst $ is, is)
          t' = toRational t

Any notes on the algorithm/clever shortcuts it takes:

• In the golf'd version, z returns in the list monad, rather than Maybe as ops does.
• While the algorithm here is brute force, it operates in small, fixed, linear space due to Haskell's laziness. I coded the wonderful @keith-randall algorithm, but it ran in about the same time and took over 1.5G of memory in Haskell.
• reduce generates some answers multiple times, in order to easily include solutions with fewer terms.
• In the golf'd version, y is defined partially in terms of itself.
• Results are computed with Rational values. Golf'd code would be 17 characters shorter, and faster if computed with Double.
• Notice how the function onRemainder factors out the structural similarity between pick and pick2.

Driver for golf'd version:

main = do
    print $ c 203 [50, 100, 4, 2, 2, 4]
    print $ c 465 [25, 4, 9, 2, 3, 10]
    print $ c 241 [9, 8, 10, 5, 9, 7]
    print $ c 824 [3, 7, 6, 2, 1, 7]

Run, with timing (still under one minute per result):

[1076] : time ./Countdown
(203 % 1,"(((((2*4)-2)/100)+4)*50)")
(465 % 1,"(((((10-4)*25)+2)*3)+9)")
(241 % 1,"(((((10*9)/5)+8)*9)+7)")
(826 % 1,"(((((3*7)-1)*6)-2)*7)")

real    2m24.213s
user    2m22.063s
sys     0m 0.913s

Ruby 1.9.2

Number of characters: 404

I give up for now, it works as long as there is an exact answer. If there isn't it takes way too long to enumerate all possibilities.

Fully Obfuscated

def b a,o,c,p,r
o+c==2*p ?r<<a :o<p ?b(a+['('],o+1,c,p,r):0;c<o ?b(a+[')'],o,c+1,p,r):0
end
w=a=%w{+ - * /}
4.times{w=w.product a}
b [],0,0,3,g=[]
*n,l=$<.read.split.map(&:to_f)
h={}
catch(0){w.product(g).each{|c,f|k=f.zip(c.flatten).each{|o|o.reverse! if o[0]=='('};n.permutation{|m|h[x=eval(d=m.zip(k)*'')]=d;throw 0 if x==l}}}
c=h[k=h.keys.min_by{|i|(i-l).abs}]
puts c.gsub(/(\d*)\.\d*/,'\1')+"=#{k}"

Decoded

Coming soon

Test script

#!/usr/bin/env ruby
[
  [[50,100,4,2,2,4],203],
  [[25,4,9,2,3,10],465],
  [[9,8,10,5,9,7],241],
  [[3,7,6,2,1,7],824]
].each do |b|
  start = Time.now
  puts "{[#{b[0]*', '}] #{b[1]}}  gives #{`echo "#{b[0]*' '} #{b[1]}" | ruby count-golf.rb`.strip} in #{Time.now-start}"
end

Output

→ ./test.rb
{[50, 100, 4, 2, 2, 4] 203}  gives 100+(4+(50-(2)/4)*2)=203.0 in 3.968534736
{[25, 4, 9, 2, 3, 10] 465}  gives 2+(3+(25+(9)*10)*4)=465.0 in 1.430715549
{[9, 8, 10, 5, 9, 7] 241}  gives 5+(9+(8)+10)*9-(7)=241.0 in 1.20045702
{[3, 7, 6, 2, 1, 7] 824}  gives 7*(6*(7*(3)-1)-2)=826.0 in 193.040054095

Details

The function used for generating the bracket pairs (b) is based off this one: Finding all combinations of well-formed brackets