Zostało to zainspirowane problemem matematycznym, który widziałem gdzieś w Internecie, ale nie pamiętam gdzie (AKTUALIZACJA: Oryginalny problem został znaleziony na łamach zagadek matematycznych z dowodami, pod warunkiem, że jest to możliwe, zobacz także ten post Math SE ), prosząc o dowód, czy możliwy jest następujący proces dla dowolnej dowolnej liczby całkowitej (z tego co pamiętam, było możliwe dla dowolnej pary):

Biorąc pod uwagę parę liczb całkowitych, j i k, należy podwoić jedną z nich i dodać jedną do drugiej, co daje parę nowych liczb całkowitych, tj. (J, k) -> (j + 1, k * 2) lub (j * 2, k + 1). Następnie powtórz ten proces z liczbami całkowitymi, aby para liczb całkowitych była równa.

Podane przykłady niekoniecznie są optymalne, ale pokazują, jak można wykonać ten proces na liczbach całkowitych, dodatnich, ujemnych lub zerowych:

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

Wyzwanie

Utwórz program, który podał dwie liczby całkowite, wyświetla listę kroków wymaganych do wyrównania tych liczb całkowitych poprzez wielokrotne zwiększanie jednego i podwajanie drugiego

Dane techniczne

• Rozwiązanie nie musi być optymalne, ale musi zostać rozwiązane w skończonej liczbie kroków dla dowolnej dowolnej pary

• Dane wejściowe muszą być dwiema liczbami całkowitymi

• Wyjściem może być każdy rozsądny wynik, który wyraźnie oznacza wynikowe liczby całkowite każdego kroku, na przykład:

  • ciąg z dwoma wyraźnymi ogranicznikami (dowolny symbol, biała spacja itp.), po jednym dla każdej liczby całkowitej w parze i po jednym dla każdej pary
    • np. wejście j, k: 2, 5 -> wyjście: 3,10; 6,11; 12,12
  • lista list liczb całkowitych
    • np. wejście j, k: 2, 5 -> wyjście: [[3, 10], [6, 11], [12, 12]]

• Jeśli dane wejściowe to para równych liczb, możesz wypisać cokolwiek, o ile jest to zgodne z innymi nietrywialnymi odpowiedziami

  • na przykład
    • jeśli wejście [2, 5] ma wyjście [[3, 10], [6, 11], [12, 12]], które nie obejmuje pary wejść, wówczas wejście [4, 4] nie powinno nic wypisywać.
    • jeśli wejście [2, 5] ma wyjście [[2, 5], [3, 10], [6, 11], [12, 12]], które obejmuje parę wejściową, wówczas wejście [4, 4] powinno wyjście [[4, 4]].

• Obowiązują standardowe metody IO, a standardowe luki są zakazane

• To jest kod golfowy, więc wygrywa najkrótsza odpowiedź w bajtach

JavaScript (ES6), 111 90 83 bajtów

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

Wypróbuj online!

Skomentował

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

Haskell, 70 69 bajtów

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

Wypróbuj online!

Prosty BFS. Śledzi kroki na liście list par.

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)

Python 3 , 90 74 72 bajty

-2 bajty dzięki Dennisowi .

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)

Wypróbuj online!

Pobiera dane wejściowe jako listę singletonów .

Bez golfa

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
    ) 

Pyth, 41 bajtów

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

Wypróbuj tutaj

Wyjaśnienie

Jest to dość proste wyszukiwanie na szerokość. Zachowaj kolejkę możliwych sekwencji ( J) i dopóki nie otrzymamy pasującej pary, weź kolejną sekwencję, przyklej każdy z możliwych ruchów i umieść je na końcu kolejki.
Ze względu na zwięzłość definiujemy funkcję y(używając wyrażenia lambda L) do wykonania jednego z ruchów i stosujemy go zarówno do przodu, jak i do tyłu.

Galaretka , 20 bajtów

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

Wypróbuj online!

05AB1E , 25 22 20 bajtów

Pobiera na wejściu podwójnie zagnieżdżoną listę i wysyła listę postrzępionych z każdym krokiem na jednej głębokości zagnieżdżenia.

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

Wypróbuj online!

Wyjaśnienie

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

Siatkówka , 72 bajty

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

Wypróbuj online! Tylko dwa przypadki testowe z powodu ograniczeń jednostkowej arytmetyki. Wyjaśnienie:

\d+
*

Konwertuj na unary.

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

Chociaż dane wejściowe nie zawierają pary identycznych liczb ...

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

... dopasuj ostatnią parę w każdej linii ...

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

... i zamień linię na dwie linie, jedna z przyrostkiem z pierwszą liczbą zwiększoną, a druga z podwojoną, druga z przyrostkiem z pierwszą liczbą podwójną, a druga z przyrostem.

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

Trzymaj linię z pasującą parą.

_+
$.&

Konwertuj z powrotem na dziesiętne. 89 88-bajtowa wersja arytmetyczna bez znaku dziesiętnego (działa również z 0):

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

Wypróbuj online!

MATL , 24 bajty

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

Czas działania jest losowy, ale jest skończony z prawdopodobieństwem 1.

Kod jest bardzo nieefektywny. Dane wejściowe wymagające więcej niż 4 lub 5 kroków mają duże prawdopodobieństwo przekroczenia limitu czasu w tłumaczu online.

Wypróbuj online!

Wyjaśnienie

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

Stax , 29 26 bajtów

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

Uruchom i debuguj

To pierwsze wyszukiwanie szerokości. Wydaje się dość szybki.

Wymaga podwójnie zapakowanej tablicy liczb całkowitych. Dane wyjściowe to rozdzielona spacjami lista wartości. Co dwie wartości reprezentują jedną parę na ścieżce do rozwiązania.

Haskell , 95 bajtów

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

Wypróbuj online! Wyjścia w odwrotnej kolejności, np . h(2,5)Zyski [(12,12),(6,11),(3,10),(2,5)].

Czerwony , 142 bajty

Traktuje dane wejściowe jako podwójnie zagnieżdżony blok pary liczb całkowitych w kolorze czerwonym formacie(2, 5) ->2x5

Zwraca wynik na przykład jako listę czerwonych par 2x5 3x10 6x11 12x12. Obejmuje początkową parę.

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]

Wypróbuj online!

Ścisłe wejście:

Dane wejściowe to na przykład dwie liczby 2 5

Czerwony , 214 bajtów

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]

Wypróbuj online!

Wyjaśnienie:

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 
]