algorithm - regresivas - minuto para ganar cronometro

Código de golf: número de cuenta atrás del juego

Question

Reto

Aquí está la tarea, inspirada en el conocido juego de televisión británico Countdown . El desafío debe ser bastante claro incluso sin conocimiento del juego, pero no dude en pedir aclaraciones.

Y si te apetece ver un video de este juego en acción, echa un vistazo a este clip de YouTube . Cuenta con el maravilloso Richard Whitely en 1997.

Le dan 6 números, elegidos al azar del conjunto {1, 2, 3, 4, 5, 6, 8, 9, 10, 25, 50, 75, 100}, y un número objetivo aleatorio entre 100 y 999. El objetivo es usar los seis números dados y las cuatro operaciones aritméticas comunes (suma, resta, multiplicación, división, en todos los números racionales) para generar el objetivo, o lo más cerca posible de cada lado. Cada número solo se puede utilizar una vez como máximo, mientras que cada operador aritmético se puede usar cualquier número de veces (incluido el cero). Tenga en cuenta que no importa cuántos números se usen.

Escriba una función que tome el número objetivo y el conjunto de 6 números (puede representarse como lista / colección / matriz / secuencia) y devuelve la solución en cualquier notación numérica estándar (por ejemplo, infijo, prefijo, postfijo). La función siempre debe devolver el resultado más cercano posible al objetivo , y debe ejecutarse como máximo 1 minuto en una PC estándar. Tenga en cuenta que, en caso de que exista más de una solución, cualquier solución individual es suficiente.

Ejemplos:

• {50, 100, 4, 2, 2, 4}, objetivo 203
  por ejemplo, 100 * 2 + 2 + (4/4) (exacto)
  ej. (100 + 50) * 4 * 2 / (4 + 2) (exacto)

• {25, 4, 9, 2, 3, 10}, objetivo 465
  ej. (25 + 10 - 4) * (9 * 2 - 3) (exacto)

• {9, 8, 10, 5, 9, 7}, objetivo 241
  ej. ((10 + 9) * 9 * 7) + 8) / 5 (exacto)

• {3, 7, 6, 2, 1, 7}, objetivo 824
  ej. ((7 * 3) - 1) * 6 - 2) * 7 (= 826; desactivado por 2)

Reglas

Aparte de lo mencionado en la declaración del problema, no hay más restricciones. Puede escribir la función en cualquier idioma estándar (la E / S estándar no es necesaria). El objetivo, como siempre, es resolver la tarea con el menor número de caracteres de código.

Diciendo eso, no puedo simplemente aceptar la respuesta con el código más corto. ¡También miraré la elegancia del código y la complejidad del tiempo del algoritmo!

Mi solución

Estoy intentando una solución F # cuando encuentro el tiempo libre. ¡Lo publicaré aquí cuando tenga algo!

Formato

Por favor, publique todas las respuestas en el siguiente formato para facilitar la comparación:

Idioma

Número de caracteres: ???

Función completamente ofuscada:

(code here)

Función clara (idealmente comentada):

(code here)

Cualquier nota sobre el algoritmo / atajos inteligentes que se necesita.

Answer 1

Ruby 1.9.2

Número de caracteres: 404

Me rindo por el momento, funciona mientras haya una respuesta exacta. Si no es así, lleva mucho tiempo enumerar todas las posibilidades.

Totalmente ofuscado

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

Descifrado

Coming soon

Script de prueba

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

Salida

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

Detalles

La función utilizada para generar los pares de corchetes ( b ) se basa en esta: encontrar todas las combinaciones de corchetes bien formados

Answer 2

Ruby 1.9.2 segundo intento

Número de caracteres: 492 440 (426)

De nuevo, hay un problema con la respuesta no exacta. Esta vez, esto es bastante rápido pero, por alguna razón, lo más cerca que llega a 824 es 819 en lugar de 826.

Decidí poner esto en una nueva respuesta ya que está usando un método muy diferente a mi último intento.

La eliminación del total de la salida (ya que no es requerida por la especificación) es de -14 caracteres.

Totalmente ofuscado

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

Descifrado

Coming soon

Script de prueba

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

Salida

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

Detalles

Esto construye el conjunto de árboles ternarios que representan todas las combinaciones posibles de 5 operadores. Luego pasa e inserta todas las permutaciones de los números ingresados ​​en las hojas de estos árboles. Finalmente, simplemente itera a través de estas posibles ecuaciones almacenándolas en un hash con el resultado como índice. Entonces es bastante fácil elegir el valor más cercano a la respuesta requerida del hash y mostrarlo.

Answer 3

Haskell

Número de caracteres: 361 350 338 322

Función completamente ofuscada:

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

Función clara:

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

Cualquier nota sobre el algoritmo / atajos inteligentes que se necesita:

• En la versión de golf, z vuelve en la lista de la mónada, en lugar de Maybe como ops .
• Mientras que el algoritmo aquí es la fuerza bruta, opera en un espacio pequeño, fijo y lineal debido a la pereza de Haskell. Codifiqué el maravilloso algoritmo de @ keith-randall, pero funcionó aproximadamente al mismo tiempo y tomó más de 1.5G de memoria en Haskell.
• reduce genera algunas respuestas varias veces, para incluir fácilmente soluciones con menos términos.
• En la versión de golf, y se define parcialmente en términos de sí mismo.
• Los resultados se calculan con valores Rational . El código de Golf sería de 17 caracteres más corto y más rápido si se calcula con Double .
• Observe cómo la función en onRemainder cuenta la similitud estructural entre pick y pick2 .

Controlador para la versión de golf:

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]

Ejecutar, con el tiempo (aún por debajo de un minuto por resultado):

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

Pitón

Número de caracteres: 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]

puedes llamarlo así:

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

Toma aproximadamente medio minuto en los ejemplos dados en una PC antigua.

Aquí está la versión comentada:

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]

Funciona mediante una enumeración exhaustiva de todas las posibilidades. Es un poco inteligente en el sentido de que si hay dos expresiones con el mismo valor que usan los mismos números de entrada, descarta una de ellas. También es inteligente en cuanto a cómo considera nuevas combinaciones, usando el índice en M para reducir rápidamente todas las combinaciones potenciales que comparten números de entrada.