代码高尔夫:倒计数游戏

挑战

英国着名电视游戏节目“ 倒计时”的启发,这是一项任务。 即使没有任何关于游戏的知识,挑战应该是非常清楚的,但是可以随时要求澄清。

如果你想看看这个游戏的剪辑,看看这个YouTube剪辑 。 它在1997年以奇妙的理查德·怀特利为特色。

给你6个数字,从集合{1,2,3,4,5,6,8,9,10,25,50,75,100}中随机select,以及100和999之间的随机目标数字。其目的是使用六个给定的数字和四个常用的算术运算(加,减,乘,除;全部有理数)来生成目标 – 或尽可能接近两侧。 每个数字最多只能使用一次,而每个算术运算符可以使用任意次数(包括零)。请注意,使用多less个数字并不重要。

编写一个采用目标编号和6个数字组(可以表示为list / collection / array / sequence)的函数,并以任何标准数字符号(例如中缀,前缀,后缀)返回解。 该function必须始终将最接近可能的结果返回给目标 ,并且必须在标准PC上最多运行1分钟。 请注意,在存在多个解决scheme的情况下,任何单个解决scheme都是足够的。

例子:

  • {50,100,4,2,2,4},目标203
    例如100 * 2 + 2 +(4/4) (确切)
    例如(100 + 50)* 4 * 2 /(4 + 2) (确切的)

  • {25,4,9,2,3,10},目标465
    例如(25 + 10 – 4)*(9 * 2 – 3) (确切)

  • {9,8,10,5,9,7},目标241
    例如((10 + 9)* 9 * 7)+8)/ 5 (确切)

  • {3,7,6,2,1,7},目标824
    例如((7 * 3)-1)* 6-2 )* 7 (= 826;closures2)

规则

除了问题陈述中提到的,没有进一步的限制。 您可以使用任何标准语言编写函数(不需要标准I / O)。 一如既往的目标是解决代码字符数最less的任务。

说到这一点,我可能不会简单地用最短的代码来接受答案。 我也将看到代码的优雅和algorithm的时间复杂性!

我的解决scheme

当我find空闲时间的时候,我尝试了一个F#的解决scheme – 当我有东西的时候会在这里发布它!


格式

请以下列格式发布所有答案,以便于比较:

语言

字符数:???

完全混淆function:

(code here) 

清除(理想评论)function:

 (code here) 

任何有关algorithm/巧妙的快捷方式的笔记。


哈斯克尔

字符数: 361 350 338 322

完全混淆function:

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

清除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 ab 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 

任何有关algorithm/聪明快捷键的注释:

  • 在golf'd版本中, z返回列表monad,而不是像ops符那样。
  • 虽然这里的algorithm是蛮力,但由于Haskell的懒惰,它在小的,固定的线性空间中运行。 我编写了精彩的@ keith-randallalgorithm,但它几乎在同一时间运行,并在Haskell中占用了1.5G的内存。
  • reduce多次生成一些答案,以便轻松地包含更less的条款的解决scheme。
  • 在高尔夫版本中, y是部分根据自身定义的。
  • 结果是使用Rational值进行计算的。 高尔夫的代码将缩短17个字符,如果使用Double计算,则代码更快。
  • 注意onRemainder函数是如何计算pickpick2之间的结构相似性的。

高尔夫版本的驱动程序:

 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] 

运行时间(每个结果还不到一分钟):

 [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 

python

字符数: 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(xT),e)for t in M for(x,e)in t.items())[1] 

你可以这样称呼它:

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

在老式电脑上给出的例子大概半分钟。

这是注释版本:

 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:xy),("*",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(xT),e)] L.sort();return L[0][1] 

它通过详尽列举所有的可能性。 如果有两个相同值的expression式使用相同的input数字,它会丢掉其中的一个。 它在考虑新组合时也很聪明,使用M中的索引来快速修剪所有共享input数字的潜在组合。

Ruby 1.9.2

字符数:404

我现在放弃,只要有确切的答案,它就会工作。 如果没有,列举所有可能性需要太长的时间。

完全混淆

 def ba,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|(il).abs}] puts c.gsub(/(\d*)\.\d*/,'\1')+"=#{k}" 

解码

 Coming soon 

testing脚本

 #!/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 

产量

 → ./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 

细节

用于生成支架对( b )的函数基于下面的函数: find格式正确的括号的所有组合

Ruby 1.9.2第二次尝试

字符数: 492 440(426)

再一次有一个问题与非确切的答案。 这一次很容易,但由于某种原因,最接近824的是819,而不是826。

我决定把它放在一个新的答案,因为它使用了一个非常不同的方法来我最后的尝试。

删除输出的总数(按规范不要求)是-14个字符。

完全混淆

 def rd,c;d>4?[0]:(k=c.pop;a=[];r(d+1,c).each{|b|a<<[b,k,nil];a<<[nil,k,b]};a)end def ft,n;[0,2].each{|a|Array===t[a] ?f(t[a],n): t[a]=n.pop}end def dt;Float===t ?t:d(t[0]).send(t[1],d(t[2]))end def oc;Float===c ?c.round: "(#{oc[0]}#{c[1]}#{oc[2]})"end w=a=%w{+ - * /} 4.times{w=w.product a} *n,l=$<.each(' ').map(&:to_f) h={} w.each{|y|r(0,y.flatten).each{|t|ft,n.dup;h[dt]=ot}} puts h[k=h.keys.min_by{|i|(li).abs}]+"=#{k.round}" 

解码

 Coming soon 

testing脚本

 #!/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 

产量

 → ./test.rb {[50, 100, 4, 2, 2, 4] 203} gives ((4-((2-(2*4))/100))*50)=203 in 1.089726252 {[25, 4, 9, 2, 3, 10] 465} gives ((10*(((3+2)*9)+4))-25)=465 in 1.039455671 {[9, 8, 10, 5, 9, 7] 241} gives (7+(((9/(5/10))+8)*9))=241 in 1.045774539 {[3, 7, 6, 2, 1, 7] 824} gives ((((7-(1/2))*6)*7)*3)=819 in 1.012330419 

细节

这构成了代表5个运算符的所有可能组合的三元树集合。 然后它通过input数字的所有排列插入这些树的叶子。 最后,它只是将这些可能的方程迭代存储到散列中,结果作为索引。 然后很容易就可以从哈希中select最接近所需答案的值并显示它。