Код Гольф: игра с обратным отсчетом

Question

Вызов

Вот задача, вдохновленная известным британским телевизионным игровым шоу Countdown. Задача должна быть достаточно ясной даже без знания игры, но не стесняйтесь просить разъяснений.

И если вы хотите увидеть клип этой игры в действии, посмотрите этот клип на YouTube. Это показывает прекрасный покойный Ричард Уайтли в 1997 году.

Вам дается 6 номеров, выбранных случайным образом из набора {1, 2, 3, 4, 5, 6, 8, 9, 10, 25, 50, 75, 100}, и случайное число от 100 до 999. Цель состоит в том, чтобы использовать шесть заданных чисел и четыре общие арифметические операции (сложение, вычитание, умножение, деление; по всем рациональным числам), чтобы сгенерировать цель - или как можно ближе к любой из сторон. Каждое число может использоваться только один раз, в то время как каждый арифметический оператор может использоваться любое количество раз (включая ноль). Обратите внимание, что не имеет значения, сколько чисел используется.

Напишите функцию, которая берет целевой номер и набор из 6 чисел (может быть представлен как список / коллекция / массив / последовательность) и возвращает решение в любой стандартной числовой записи (например, инфикс, префикс, постфикс). Функция всегда должна возвращать целевой объект как можно ближе к результату и должна выполняться не более 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)

правила

Помимо упомянутых в постановке задачи, никаких дальнейших ограничений нет. Вы можете написать функцию на любом стандартном языке (стандартный ввод / вывод не требуется). Цель, как всегда, состоит в том, чтобы решить задачу с наименьшим количеством символов кода.

Сказав это, я не могу просто принять ответ с самым коротким кодом. Я также буду смотреть на элегантность кода и временную сложность алгоритма!

Мое решение

Я пытаюсь найти решение F#, когда найду свободное время - опубликую его здесь, когда у меня будет что-нибудь!

---

Формат

Пожалуйста, опубликуйте все ответы в следующем формате для удобства сравнения:

язык

Количество символов:???

Полностью запутанная функция:

(code here)

Четкая (идеально прокомментированная) функция:

(code here)

Любые замечания по алгоритму / умные ярлыки, которые он принимает.

---

Answer 1

Haskell

Количество символов: 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

Любые замечания по алгоритму / умные ярлыки, которые он принимает:

• В версии для гольфа z возвращает в список монаду, а не Maybe как ops делает.
• Хотя алгоритм здесь грубый, он работает в маленьком фиксированном линейном пространстве из-за лени Хаскелла. Я написал замечательный алгоритм @keith-randall, но он запустился примерно в то же время и занял 1,5 ГБ памяти в Haskell.
• reduce генерирует несколько ответов несколько раз, чтобы легко включать решения с меньшим количеством терминов.
• В версии для гольфа y определяется частично с точки зрения самого себя.
• Результаты рассчитываются с Rational ценности. Гольф-код будет на 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

Answer 2

питон

Количество символов: 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)

Занимает примерно полминуты на приведенных примерах на старом ПК.

Вот прокомментированная версия:

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]

Это работает через исчерпывающий перечень всех возможностей. Немного разумно, если два выражения с одинаковым значением, использующие одинаковые входные числа, отбрасывают одно из них. Он также умен в том, как он рассматривает новые комбинации, используя индекс в М для быстрого сокращения всех потенциальных комбинаций, которые разделяют входные числа.

Answer 3

Ruby 1.9.2

Количество символов: 404

Я сдаюсь пока, это работает, пока есть точный ответ. Если нет, то перечисление всех возможностей занимает слишком много времени.

Полностью запутанный

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

декодированный

Coming soon

Тестовый скрипт

#!/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) основан на этом: Нахождение всех комбинаций правильных скобок

Answer 4

Ruby 1.9.2 вторая попытка

Количество символов: 492 440 (426)

Снова возникает проблема с неточным ответом. На этот раз это достаточно быстро, но по некоторым причинам ближе всего к 824 - 819 вместо 826.

Я решил поместить это в новый ответ, так как он использует метод, совершенно отличный от моей последней попытки.

Удаление итогового результата (поскольку это не требуется спецификацией) составляет -14 символов.

Полностью запутанный

def r d,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 f t,n;[0,2].each{|a|Array===t[a] ?f(t[a],n): t[a]=n.pop}end
def d t;Float===t ?t:d(t[0]).send(t[1],d(t[2]))end
def o c;Float===c ?c.round: "(#{o c[0]}#{c[1]}#{o c[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|f t,n.dup;h[d t]=o t}}
puts h[k=h.keys.min_by{|i|(l-i).abs}]+"=#{k.round}"

декодированный

Coming soon

Тестовый скрипт

#!/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 операторов. Затем он проходит и вставляет все перестановки входных чисел в листья этих деревьев. Наконец, он просто перебирает эти возможные уравнения, сохраняя их в хеш с результатом в качестве индекса. Тогда достаточно просто выбрать наиболее близкое значение к требуемому ответу из хеша и отобразить его.