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]]
- 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
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]].
- na przykład
Obowiązują standardowe metody IO, a standardowe luki są zakazane
To jest kod golfowy, więc wygrywa najkrótsza odpowiedź w bajtach
źródło
[(12,12),(6,11),(3,10),(2,5)]
Na wejście(2,5)
?Odpowiedzi:
JavaScript (ES6),
1119083 bajtówWypróbuj online!
Skomentował
źródło
Haskell,
7069 bajtówWypróbuj online!
Prosty BFS. Śledzi kroki na liście list par.
źródło
Python 3 ,
907472 bajty-2 bajty dzięki Dennisowi .
Wypróbuj online!
Pobiera dane wejściowe jako listę singletonów .
Bez golfa
źródło
Pyth, 41 bajtów
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 lambdaL
) do wykonania jednego z ruchów i stosujemy go zarówno do przodu, jak i do tyłu.źródło
Galaretka , 20 bajtów
Wypróbuj online!
źródło
[[2,5]]
)05AB1E ,
252220 bajtówPobiera 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.
Wypróbuj online!
Wyjaśnienie
źródło
Siatkówka , 72 bajty
Wypróbuj online! Tylko dwa przypadki testowe z powodu ograniczeń jednostkowej arytmetyki. Wyjaśnienie:
Konwertuj na unary.
Chociaż dane wejściowe nie zawierają pary identycznych liczb ...
... dopasuj ostatnią parę w każdej linii ...
... 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.
Trzymaj linię z pasującą parą.
Konwertuj z powrotem na dziesiętne.
8988-bajtowa wersja arytmetyczna bez znaku dziesiętnego (działa również z 0):Wypróbuj online!
źródło
MATL , 24 bajty
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
źródło
Stax ,
2926 bajtówUruchom 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.
źródło
Haskell , 95 bajtów
Wypróbuj online! Wyjścia w odwrotnej kolejności, np .
h(2,5)
Zyski[(12,12),(6,11),(3,10),(2,5)]
.źródło
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ę.Wypróbuj online!
Ścisłe wejście:
Dane wejściowe to na przykład dwie liczby
2 5
Czerwony , 214 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło