高尔夫代码:倒计时数字游戏 [英] Code Golf: Countdown Number Game

问题描述

这是任务，它受到英国著名电视游戏节目《倒计时》的启发.即使没有任何游戏知识，挑战也应该很清楚，但请随时澄清.

Here is the task, inspired by the well-known British TV game show Countdown. The challenge should be pretty clear even without any knowledge of the game, but feel free to ask for clarifications.

如果您希望看到该游戏的片段，请查看此YouTube片段.它以1997年出色的已故理查德·怀特利(Richard Whitely)为例.

And if you fancy seeing a clip of this game in action, check out this YouTube clip. It features the wonderful late Richard Whitely in 1997.

您将获得6个数字，这些数字是从{1、2、3、4、5、6、8、9、10、25、50、75、100}中随机选择的，并且目标数字介于100和999.目标是使用六个给定的数字和四个常见的算术运算(加法，减法，乘法，除法；遍及有理数)来生成目标-或尽可能靠近任一侧.每个数字最多只能使用一次，而每个算术运算符可以使用任意次(包括零次).请注意，使用多少个数字都没有关系.

You are given 6 numbers, chosen at random from the set {1, 2, 3, 4, 5, 6, 8, 9, 10, 25, 50, 75, 100}, and a random target number between 100 and 999. The aim is to use the six given numbers and the four common arithmetic operations (addition, subtraction, multiplication, division; all over the rational numbers) to generate the target - or as close as possible either side. Each number may only be used once at most, while each arithmetic operator may be used any number of times (including zero.) Note that it does not matter how many numbers are used.

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

Write a function that takes the target number and set of 6 numbers (can be represented as list/collection/array/sequence) and returns the solution in any standard numerical notation (e.g. infix, prefix, postfix). The function must always return the closest-possible result to the target, and must run in at most 1 minute on a standard PC. Note that in the case where more than one solution exists, any single solution is sufficient.

示例:

• {50，100，4，2，2，4}，目标203
  例如100 * 2 + 2 +(4/4)<精确>(精确)
  例如(100 + 50)* 4 * 2/(4 + 2)(完全)

• {50, 100, 4, 2, 2, 4}, target 203
  e.g. 100 * 2 + 2 + (4 / 4) (exact)
  e.g. (100 + 50) * 4 * 2 / (4 + 2) (exact)

{25，4，9，2，3，10}，目标465
例如(25 + 10-4)*(9 * 2-3)(精确)

{25, 4, 9, 2, 3, 10}, target 465
e.g. (25 + 10 - 4) * (9 * 2 - 3) (exact)

{9，8，10，5，9，7}，目标241
例如((10 + 9)* 9 * 7)+ 8)/5 (完全)

{9, 8, 10, 5, 9, 7}, target 241
e.g. ((10 + 9) * 9 * 7) + 8) / 5 (exact)

{3，7，6，2，1，1，7}，目标824
例如((7 * 3)-1)* 6-2)* 7 (= 826;减2)

{3, 7, 6, 2, 1, 7}, target 824
e.g. ((7 * 3) - 1) * 6 - 2) * 7 (= 826; off by 2)

除问题说明中所述外，没有其他限制.您可以用任何标准语言编写该功能(不需要标准I/O).一如既往的目标是用最少的代码字符数来解决任务.

Other than mentioned in the problem statement, there are no further restrictions. You may write the function in any standard language (standard I/O is not necessary). The aim as always is to solve the task with the smallest number of characters of code.

这样说，我可能不会简单地接受代码最短的答案.我还将关注代码的优美性和算法的时间复杂性！

Saying that, I may not simply accept the answer with the shortest code. I'll also be looking at elegance of the code and time complexity of the algorithm!

找到空闲时间后，我正在尝试F#解决方案-当我有空时将其张贴在这里！

I'm attempting an F# solution when I find the free time - will post it here when I have something!

为了便于比较，请以以下格式发布所有答案:

Please post all answers in the following format for the purpose of easy comparison:

语言

字符数:???

完全模糊的功能:

(code here)

清除(理想状态)功能:

Clear (ideally commented) function:

(code here)

关于使用的算法/智能快捷键的任何注释.

Any notes on the algorithm/clever shortcuts it takes.

---

推荐答案

Haskell

字符数: 361 350 338 322

Haskell

Number of characters: 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

关于需要使用的算法/智能快捷键的任何注释:

Any notes on the algorithm/clever shortcuts it takes:

• 在高尔夫球版中，z返回单子列表，而不是像ops那样返回Maybe.
• 尽管这里的算法是蛮力的，但由于Haskell的惰性，它在较小的，固定的线性空间中运行.我编写了很棒的@ keith-randall算法，但它同时运行，并在Haskell中接管了1.5G的内存.
• reduce会多次生成一些答案，以便轻松包含术语更少的解决方案.
• 在golf'd版本中，y是部分根据自身定义的.
• 结果是使用Rational值计算的. Golf'd代码将短17个字符，而如果使用Double计算，则将更快.
• 请注意，函数onRemainder是如何排除pick和pick2之间的结构相似性的.

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

高尔夫版驱动程序:

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

这篇关于高尔夫代码:倒计时数字游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！