Code Golf:倒数游戏

Question

挑战

这是一项任务,灵感来自着名的英国电视游戏节目Countdown.即使不了解游戏,挑战也应该非常明确,但随时可以要求澄清.

如果你想看到这款游戏的动态片段,请查看此YouTube视频片段.它拥有1997年美妙的已故理查德怀特利.

您将获得6个数字,从集{1,2,3,4,5,6,8,9,10,25,50,75,100}中随机选择,以及100到999之间的随机目标数.目的是使用六个给定的数字和四个常用的算术运算(加法,减法,乘法,除法;遍及有理数)来生成目标 - 或尽可能接近任一侧.每个数字最多只能使用一次,而每个算术运算符可以使用任意次数(包括零).请注意,使用多少个数并不重要.

编写一个函数,它接受目标数和6个数字的集合(可以表示为列表/集合/数组/序列),并以任何标准数字符号(例如中缀,前缀,后缀)返回解决方案.该函数必须始终将最接近的结果返回给目标,并且必须在标准PC上运行最多1分钟.请注意,在存在多个解决方案的情况下,任何单个解决方案就足够了.

例子:

• {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;偏2)

规则

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

说,我可能不会简单地用最短的代码接受答案.我还将关注代码的优雅和算法的时间复杂度!

我的解决方案

当我找到空闲时间时,我正在尝试使用F#解决方案 - 当我有东西时会将它发布在这里!

---

格式

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

语言

字符数:???

完全混淆的功能:

(code here)

清除(理想评论)功能:

(code here)

关于算法/聪明的快捷方式的任何注释.

---

Answer 1

蟒蛇

字符数: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]

你可以这样称呼它:

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

在旧PC上给出的示例大约需要半分钟.

这是评论版:

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]

它通过详尽列举所有可能性来工作.它有点聪明,如果有两个具有相同值的表达式使用相同的输入数字,它会丢弃其中一个.它在考虑新组合方面也很聪明,使用M中的索引快速修剪共享输入数字的所有潜在组合.

Answer 2

哈斯克尔

字符数:361 350 338 322

完全混淆的功能:

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))

功能清晰:

-- | 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

关于算法/聪明的快捷方式的任何注释:

• 在golf'd版本,z将列表中的单子,而不是Maybe为ops做.
• 虽然这里的算法是强力的,但由于Haskell的懒惰,它在小而固定的线性空间中运行.我编写了精彩的@ keith-randall算法,但它大约在同一时间运行并在Haskell中占用了1.5G的内存.
• reduce 多次生成一些答案,以便轻松包含较少术语的解决方案.
• 在高尔夫版本中,y部分地根据其自身来定义.
• 结果用Rational值计算.Golf'd代码将缩短17个字符,如果计算得更快,则更快Double.
• 注意该函数如何onRemainder影响pick和之间的结构相似性pick2.

高尔夫版驱动程序:

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