Trayendo un par de enteros a la igualdad

51

Esto se inspiró en un problema matemático que vi en algún lugar de Internet pero no recuerdo dónde (ACTUALIZACIÓN: El problema original se encontró en el subreddit de acertijos matemáticos con una prueba siempre que sea posible, consulte también esta publicación de Math SE ), solicitando una prueba si el siguiente proceso es posible para cualquier par arbitrario de enteros (por lo que recuerdo, fue posible para cualquier par dado):

Dado un par de enteros, j y k, duplique uno de ellos y agregue uno al otro, dando como resultado un par de enteros nuevos, es decir, (j, k) -> (j + 1, k * 2) o (j * 2, k + 1). Luego repita este proceso con esos enteros, con el objetivo de que el par de enteros sea igual.

Estos ejemplos dados no son necesariamente óptimos, pero muestran cómo se puede realizar este proceso en cualquier número entero, positivo, negativo o cero:

(2, 5) -> (3, 10) -> (6, 11) -> (12, 12)

(5, 6) -> (6, 12) -> (7, 24) -> (14, 25) -> (28, 26) -> (56, 27) -> (112, 28) -> (113, 56) -> (226, 57) -> (227, 114) -> (228, 228)

(0, 2) -> (1, 4) -> (2, 5) -> (3, 10) -> (6, 11) -> (12, 12)

(-4, 0) -> (-3, 0) -> (-2, 0) -> (-1, 0) -> (0, 0)

(3, -1) -> (6, 0) -> (12, 1) -> (13, 2) -> (14, 4) -> (15, 8) -> (16, 16)

(-4, -3) -> (-8, -2) -> (-16, -1) -> (-32, 0) -> (-31, 0) -> ... -> (0, 0)

Desafío

Cree un programa que tenga dos enteros, muestre la lista de pasos necesarios para igualar esos enteros incrementando repetidamente uno y duplicando el otro

Especificaciones

  • La solución no tiene que ser óptima, pero debe resolverse en un número finito de pasos para cualquier par arbitrario
  • La entrada debe ser dos enteros

  • La salida puede ser cualquier salida razonable que denote claramente los enteros resultantes de cada paso, por ejemplo:

    • una cadena con dos delimitadores distintos (cualquier símbolo, espacio en blanco, etc.), uno para cada número entero en un par y otro para cada par
      • por ejemplo, entrada j, k: 2, 5 -> salida: 3,10; 6,11; 12,12
    • una lista de listas de enteros
      • por ejemplo, entrada j, k: 2, 5 -> salida: [[3, 10], [6, 11], [12, 12]]
  • Si la entrada es un par de números iguales, puede generar cualquier cosa siempre que sea coherente con otras respuestas no triviales

    • por ejemplo
      • si la entrada [2, 5] tiene salida [[3, 10], [6, 11], [12, 12]], que no incluye el par de entrada, entonces la entrada [4, 4] no debería generar nada.
      • si la entrada [2, 5] tiene salida [[2, 5], [3, 10], [6, 11], [12, 12]], que incluye el par de entrada, entonces la entrada [4, 4] debería salida [[4, 4]].
  • Se aplican métodos IO estándar y se prohíben las lagunas estándar

  • Este es el código de golf, por lo que la respuesta más corta en bytes gana

JMigst
fuente
13
Este es un buen primer desafío, por cierto. Bienvenido a PPCG!
Arnauld
@Arnauld ¡Gracias! También gracias por señalar el error, hice todos los ejemplos a mano y realmente debería implementar una solución yo primero
JMigst
¿Puede la salida estar en reversa? Por ejemplo, [(12,12),(6,11),(3,10),(2,5)]para la entrada (2,5)?
Laikoni
1
@Laikoni Teniendo en cuenta que todos los pasos necesarios aún se emiten, creo que está bien
JMigst
1
Agregué esto al OEIS como A304027 . La pareja (34,23) parece ser especialmente difícil.
Peter Kagey

Respuestas:

10

JavaScript (ES6), 111 90 83 bytes

f=(a,b,p=q=[],u=[...p,[a,b]])=>a-b?f(...(q=[[a*2,b+1,u],[a+1,b*2,u],...q]).pop()):u

Pruébalo en línea!

Comentado

f = (                       // f = recursive function taking:
  a, b,                     //   (a, b) = input integers
  p =                       //   p[] = current path
  q = [],                   //   q[] = queue
  u = [...p, [a, b]]        //   u[] = updated path with [a, b] appended to it
) =>                        //
  a - b ?                   // if a is not yet equal to b:
    f(...                   //   recursive call, using spread syntax:
      (q = [                //     prepend the next 2 possible moves in the queue:
        [a * 2, b + 1, u],  //       a * 2, b + 1
        [a + 1, b * 2, u],  //       a + 1, b * 2
        ...q                //
      ]).pop()              //     use the move on the top of the queue
    )                       //   end of recursive call
  :                         // else:
    u                       //   success: return the (updated) path
Arnauld
fuente
9

Haskell, 70 69 bytes

f(w@((i,j):_):r)|i==j=w|1<2=f$r++[(i+1,j*2):w,(i*2,j+1):w]
g x=f[[x]]

Pruébalo en línea!

Un simple BFS. Realiza un seguimiento de los pasos en una lista de la lista de pares.

g x=f[[x]]                -- start with a single list where the only
                          -- step is the starting pair
f (w@((i,j):_):r) =       -- let w be the first list of steps
                          --     (i,j) the last pair of the first list of steps
                                       ('last' as in last operated on. As we store
                                        the steps in reverse order it's the
                                        first element in the list)
                          --     r all other lists of steps
   i==j=w                 -- if i==j stop and return the first list
   1<2= f                 -- else make a recursive call
          r++             -- where the new input list is r followed by
                          -- the first list extended one time by
          [(i+1,j*2):w,         (i+1,j*2) and one time by
             (i*2,j+1):w]       (i*2,j+1)
nimi
fuente
7

Python 3 , 90 74 72 bytes

-2 bytes gracias a Dennis .

def f(a,*x):j,k=a[0];return(j==k)*a or f(*x,[(2*j,k+1)]+a,[(j+1,2*k)]+a)

Pruébalo en línea!

Toma la entrada como una lista singleton .


Sin golf

def f(a,*x):              # function taking at least one argument
                          # a is the first argument, all other are stored in x
  j, k = a[0]             # get the newest values of the current path
  return (j==k)*a         # if j is equal to k return the current path
                  or      # else ...
   f(                     # continue ...
     *x,                  # with the remaining paths ...
     [(2*j,k+1)]+a        # and split the current path ...
     [(j+1,2*k)]+a        # in two new ones
    ) 
ovs
fuente
4

Pyth, 41 bytes

J]]QL,hhb*2ebWt{KehJ=J+tJm+hJ]d,yK_y_K)hJ

Pruébalo aquí

Explicación

Esta es una búsqueda bastante amplia y sencilla. Mantenga una cola de posibles secuencias ( J), y hasta que obtengamos un par coincidente, tome la siguiente secuencia, pegue cada uno de los movimientos posibles y colóquelos al final de la cola.
En aras de la brevedad, definimos una función y(utilizando la expresión lambda L) para realizar uno de los movimientos y aplicarla tanto hacia adelante como hacia atrás.

Mnemotécnico
fuente
4

Jalea , 20 bytes

ḃ2d2;@+*¥\
0çṪEɗ1#Ḣç

Pruébalo en línea!

Dennis
fuente
(nota: esto toma una lista singleton de una lista de 2 elementos, por ejemplo [[2,5]])
usuario202729
4

05AB1E , 25 22 20 bytes

Toma una lista doblemente anidada como entrada y genera una lista irregular con cada paso en una profundidad de nido.

[ć¤Ë#¤xs>R‚ø`R‚s¸sâ«

Pruébalo en línea!

Explicación

[                      # start a loop
 ć                     # extract the first element of the current list (current path)
  ¤Ë#                  # break if all elements in the head are equal
     ¤xs>              # duplicate one copy of the head and increment another
         R             # reverse the incremented copy
          ‚ø           # zip them together
            `R‚        # reverse the tail of the zipped list
               s¸sâ    # cartesian product with the rest of the current path
                   «   # append to the list of all current paths
Emigna
fuente
4

Retina , 72 bytes

\d+
*
/\b(_+),\1\b/^+%`(_+),(_+)$
$&;_$&$2¶$=;$1$&_
G`\b(_+),\1\b
_+
$.&

Pruébalo en línea! Solo dos casos de prueba debido a las limitaciones de la aritmética unaria. Explicación:

\d+
*

Convierte a unario.

/\b(_+),\1\b/^+

Si bien la entrada no contiene un par de números idénticos ...

%`(_+),(_+)%

... coincide con el último par en cada línea ...

$&;_$&$2¶$=;$1$&_

... y convierta la línea en dos líneas, una sufijada con el primer número incrementado y la segunda duplicada, la otra sufijada con el primer número duplicado y la segunda incrementada.

G`\b(_+),\1\b

Mantenga la línea con el par correspondiente.

_+
$.&

Convertir de nuevo a decimal. 89 Versión aritmética decimal sin signo de 88 bytes (también funciona con 0):

/\b(\d+),\1\b/^+%`(\d+),(\d+)$
$&;$.(_$1*),$.(2*$2*)¶$=;$.(2*$1*),$.(_$2*
G`\b(\d+),\1\b

Pruébalo en línea!

Neil
fuente
4

MATL , 24 bytes

`vxG1r/q:"tt1rEk(+]td0=~

El tiempo de ejecución es aleatorio, pero es finito con probabilidad 1.

El código es muy ineficiente. Las entradas que requieren más de 4 o 5 pasos tienen una gran probabilidad de tiempo de espera en el intérprete en línea.

Pruébalo en línea!

Explicación

`         % Do...while
  vx      %   Concatenate stack and delete. This clears the stack from contents
          %   of previous iterations   
  G       %   Push input
  1       %   Push 1
  r       %   Push random number uniformly distributed on (0,1)
  /       %   Divide
  q       %   Subtract 1. The result is a random number, t, that has nonzero
          %   probability of being arbitrarily large. Specifically, t is in
          %   the interval (0,1) with probability 1/2; in (1,2) with probability
          %   1/6; ... in (k,k+1) with probability 1/((k+1)*(k+2).
  :       %   Range [1 2 ... floor(t)]
  "       %   For each (that is: do thw following floor(t) times)
    tt    %     Duplicate twice
    1     %     Push 1
    rEk   %     Random number in (0,1), times 2, round down. This produces a 
          %     number i that equals 0 or 1 with probability 1/2
    (     %     Write 1 at entry i. So if the top of the stack is [a b], this
          %     transforms it into either [1 b] or [a 1]
    +     %     Add, element-wise. This gives either [a+1 2*b] or [2*a b+1] 
  ]       %   End for each
  td      %   Duplicate, consecutive difference between the two entries
  0=~     %   Is it not zero? If so, the do...while loop continues with a new
          %   iteration. Normally the code 0=~ could be omitted, because a
          %   nonzero consecutive difference is truthy. But for large t the
          %   numbers a, b may have gone to infinity, and then the consecutive
          %   difference gives NaN
          % End do...while (implicit). Display (implicit)
Luis Mendo
fuente
3

Stax , 29 26 bytes

ä⌠|Tô&cm♂NV↓↔╗╣¢♠╜╒█¡Φ≈ñY@

Ejecutar y depurarlo

Es una primera búsqueda amplia. Parece razonablemente rápido.

Se necesita un par de enteros doblemente envueltos. La salida es una lista de valores separados por espacios. Cada dos valores representa un par en el camino hacia la solución.

recursivo
fuente
2

Haskell , 95 bytes

g s|a:_<-[a|a@((x,y):_)<-s,x==y]=a
g s=g$do a@((x,y):_)<-s;[(x*2,y+1):a,(x+1,y*2):a]
h t=g[[t]]

Pruébalo en línea! Salidas en orden inverso, por ejemplo, h(2,5)rendimientos [(12,12),(6,11),(3,10),(2,5)].

Laikoni
fuente
2

Rojo , 142 bytes

Toma la entrada como un bloque doblemente anidado del par de enteros en el formato de Red(2, 5) ->2x5

Devuelve el resultado como una lista de pares rojos , por ejemplo 2x5 3x10 6x11 12x12. Incluye el par inicial.

func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]do replace/all{%+ 1x0 * 1x2
%* 2x1 + 0x1}"%""append/only a append copy d l "]f a]

Pruébalo en línea!

Entrada estricta:

La entrada es dos números, por ejemplo 2 5

Rojo , 214 bytes

func[a b][g: func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]append/only a append copy d l + 1x0 * 1x2
append/only a append copy d l * 2x1 + 0x1]g a]c: copy[]insert/only c reduce[do rejoin[a 'x b]]g c]

Pruébalo en línea!

Explicación:

f: func[a b][                 
g: func[c][                                   ; recursive helper function
  a: copy[]                                   ; an empty block
  foreach d c[                                ; for each block of the input 
    l: last d                                 ; take the last pair
    if l/1 = l/2[return d]                    ; if the numbers are equal, return the block 
    append/only a append copy d l + 1x0 * 1x2 ; in place of each block append two blocks
    append/only a append copy d l * 2x1 + 0x1 ; (j+1, k*2) and (j*2, k+1)
  ]                                           ; using Red's arithmetic on pairs
  g a                                         ; calls the function anew
]
c: copy[]insert/only c reduce[do rejoin[a 'x b]]; prepares a nested block from the input
g c                                           ; calls the recursive function 
]
Galen Ivanov
fuente