No solo un rompecabezas de cuatro patas

11

En esta variante del rompecabezas de Cuatro patas, debe usar hasta x x's(y ningún otro número) y un conjunto definido de operaciones para llegar a cada número del 0 al 100. Si x = 4puede usar hasta cuatro 4sy esta pregunta se convierte en los cuatro cuatro clásicos. rompecabezas (excepto que puede usar hasta cuatro 4s en lugar de tener que usar exactamente cuatro de ellos). Asumimos 1 < x <= 9.

En esta versión, solo se permiten los siguientes operadores:

  • Suma ( +), Resta ( -), Multiplicación ( *), División ( /). Tenga en cuenta que esta es una división real, por lo que 5/2 = 2.5.
  • Exponenciación (por ejemplo, 4 ^ 4) ya que esto no implicaría símbolos adicionales si se escribe normalmente a mano.
  • Puedes hacer nuevos enteros concatenando xs. Por ejemplo, puedes hacer los enteros 4, 44, 444, 4444.

También puede usar paréntesis para agrupar números simplemente para controlar el orden de evaluación de los operadores. Por ejemplo, no puede combinar paréntesis con concatenación como en (4/4)(4/4) = (1)(1) = 11.

No se pueden usar otros símbolos y se aplica el orden estándar de operaciones.

Su programa debería generar, dada una xdentro del rango definido y una solución nintermedia 0e 100inclusiva, para esa entrada si existe. De lo contrario, su código debe generar algo para indicar que no existe tal solución.

Debe poder ejecutar su envío hasta su finalización en su máquina para cualquier valor de entrada de xy nen el rango permitido. Este es el código de golf, por lo que gana la solución más corta.

Esta vieja pregunta relacionada utiliza más operadores (y solo 4) y, por lo tanto, todos los números del 0 al 100 son solucionables, lo que no será cierto para este desafío.

Entrada y salida

Su código toma dos enteros xy ncomo entrada y debe generar una solución (o una indicación de que no hay solución) en cualquier formato legible por humanos que considere conveniente. La entrada 4 6significaría "Usando hasta cuatro 4s, haga el número 6" por ejemplo. Entonces, si la entrada es 4 6la salida podría ser (4+4)/4+4.

Anush
fuente
1
Referencia útil
brindis de ingeniero
2
¿Se pueden combinar los padres con la concatenación? ej. `(4/4) (4/4) = (1) (1) = 11?
Trauma digital
1
Agregar paréntesis (y no permitir paréntesis + concatenación) hace que esto sea mucho más difícil
Draconis
2
Agregando el operador de exponenciación y un bucle externo sobre la cantidad de veces que se usa el dígito, no IMO agregue nada no trivial sobre codegolf.stackexchange.com/q/82884/194
Peter Taylor
2
@PeterTaylor Los paréntesis parecen marcar una gran diferencia. Votaría para reabrir si pudiera.
felipa

Respuestas:

4

Python 3 , 265 bytes

def f(x,n):
 for e in g(x,x-(x>7)):
  try:
   if eval(e)==n:return e
  except:1
g=lambda x,d:{str(x)*-~i for i in range(d)}|{s%(a,b)for a in g(x,d-1)for b in g(x,d-a.count(str(x)))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}if d else{}

Pruébalo en línea!

Funciona para todos los números en la referencia vinculada por Engineer Toast.

Se ejecuta hasta x=8el tio, x=9toma un par de minutos en mi máquina.


La función gdevuelve un conjunto de todas las combinaciones con un máximo xde x's. fluego los recorre y devuelve el primero que evalúa el número n.

El número de valores posibles que encontré para cada uno xson:

x  possible numbers
------
2  5
3  17
4  35
5  56
6  83
7  101
8  101
9  101

Todos los números anteriores se pueden generar a partir de (a+b), (a-b), (a+b), a*b, a/b, (a/b), y a^b. a+by a-bno le des más números.

a^b también se usa solo una vez, ya que de lo contrario se crean grandes cantidades (esto también se verifica en el documento de referencia anterior)


Una versión alternativa que cortocircuita tan pronto como encuentra una solución (no tan golfizada):

Esto es mucho más rápido ya que x=7..9se pueden crear todos los números.

Python 3 , 338 289 bytes

def f(x,n,d=-1):
 d=[d,x][d<0];X=str(x);r=set()
 for E in{X*-~i for i in range(d)}|{s%(a,b)for a in[0]*d and f(x,n,d-1)for b in f(x,n,d-a.count(X))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}:
  try:e=eval(E)
  except:e=-1
  if e==n:exit(E)
  r|={E}
 return r

Pruébalo en línea!

TFeld
fuente
Esta es una muy buena respuesta! Pensé que siempre usabas exactamente (en lugar de hasta) x xs (por ejemplo, (4/4**(4-4))para 4), pero resulta que ese no es el caso.
Anush
exit(e)es más corto quereturn e
mbomb007