tło

Istnieje wspólna zagadka, która przebiega mniej więcej tak:

Ślimak znajduje się na dnie studni o długości 30 stóp. Każdego dnia ślimak może wspinać się na 3 stopy. W nocy, kiedy śpią, zsuwają się z powrotem o 2 stopy. Ile dni zajmuje ślimakowi wydostanie się ze studni?

Intuicyjna odpowiedź brzmi

30 dni, ponieważ ślimak wspina się 1 stopę dziennie przez 30 dni, aby dotrzeć na szczyt,

ale tak naprawdę odpowiedź brzmi

28 dni, ponieważ gdy ślimak znajdzie się 27 stóp w powietrzu (po 27 dniach), po prostu wspina się na pozostałe 3 stopy na szczyt 28 dnia.

Wyzwanie

To wyzwanie uogólnia tę zagadkę. Biorąc pod uwagę trzy dodatnie liczby całkowite jako dane wejściowe, reprezentujące całkowitą wysokość, wysokość wspinaczki i wysokość upadku, zwróć liczbę dni potrzebnych do wyjścia ze studni.

Jeśli ślimak nie może wydostać się ze studni, możesz zwrócić 0, zwrócić wartość fałszowania lub zgłosić wyjątek. Możesz także napisać kod, który zatrzyma się tylko wtedy, gdy istnieje rozwiązanie.

Jeśli chcesz, możesz przyjąć wysokość upadku jako ujemną liczbę całkowitą.

Przypadki testowe

(30, 3, 2) -> 28
(84, 17, 15) -> 35
(79, 15, 9) -> 12
(29, 17, 4) -> 2
(13, 18, 8) -> 1
(5, 5, 10) -> 1
(7, 7, 7) -> 1
(69, 3, 8) -> Brak
(81, 14, 14) -> Brak

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w każdym języku.

Grey Snail , 1206 bajtów na numeryczne operacje we / wy, 149 bajtów na jednoargumentowe operacje we / wy

Dla zabawy. Skład pierwszego programu:

• 451 bajtów, konwertując liczbę na kropki
• 121 bajtów, podstawowa funkcja (oddzielna wersja jest napisana poniżej)
• 634 bajty, konwertując kropki na liczby

Weź numeryczne dane wejściowe i wyjściowe. Wejście jest A, B, Codpowiednio. W porównaniu do innych (bliskich) O(1)odpowiedzi, kod ma złożoność O(n). Ale w przypadku dużej liczby może to pochłonąć pamięć.

Zawieś, jeśli nie zostanie znalezione rozwiązanie.

INPUT p
POP Z r .!
f
POP Z o .
q
POP Z p [p]
GOTO [Z]
0
POP Z n .
GOTO w
1
POP Z n ..
GOTO w
2
POP Z n ...
GOTO w
3
POP Z n ....
GOTO w
4
POP Z n .....
GOTO w
5
POP Z n ......
GOTO w
6
POP Z n .......
GOTO w
7
POP Z n ........
GOTO w
8
POP Z n .........
GOTO w
9
POP Z n ..........
GOTO w
w
POP Z o .[o][o][o][o][o][o][o][o][o][o][n]
GOTO [r] [p] 
GOTO q
!
POP Z A .[o]
INPUT p
POP Z r .@
GOTO f
@
POP Z B .[o]
INPUT p
POP Z r .#
GOTO f
#
POP Z C .[o]
POP H N .[B]
U
POP Z A [A]
POP Z B [B]
GOTO D [A] 
GOTO $ [B] 
GOTO U
$
POP Z A .[A][C]
POP Z H ..[H]
POP Z B .[N]
GOTO U
D
POP Z r .
POP Z M .
POP Z N ...........
POP Z z .[N]
POP Z V .[H]
+
GOTO l[V] [H] 
POP Z H [H]
POP Z z [z]
GOTO ( [z] 
GOTO +
(
GOTO ) [H] 
POP Z z .[N]
POP Z M ..[M]
POP Z V .[H]
GOTO +
)
POP Z r .0[r]
POP Z M ..[M]
POP Z H .[M]
POP Z M .
POP Z V .[H]
POP Z z .[N]
GOTO +
l
POP Z r .0[r]
GOTO -
l.
POP Z r .1[r]
GOTO -
l..
POP Z r .2[r]
GOTO -
l...
POP Z r .3[r]
GOTO -
l....
POP Z r .4[r]
GOTO -
l.....
POP Z r .5[r]
GOTO -
l......
POP Z r .6[r]
GOTO -
l.......
POP Z r .7[r]
GOTO -
l........
POP Z r .8[r]
GOTO -
l.........
POP Z r .9[r]
GOTO -
-
GOTO / [M] 
POP Z H .[M]
POP Z M .
POP Z V .[H]
POP Z z .[N]
GOTO +
/
OUTPUT [r]

fjest (być może) funkcją rekurencyjną przekształcającą liczby całkowite w kropki. Argument jest zapisywany [p]i wyprowadzany w [o].

Uto funkcja testująca S1>=S2, przechowująca parametr B, Apodczas zapisywania A-Bdo A.

Kod zaczynający się od Djest kodem pośredniczącym przekształcającym kropki w liczby.

Podstawowa zasada jest taka sama w przypadku mojej odpowiedzi w języku C (odrywanie wyników fałszywych dla niemożliwych rozwiązań).

Wersja autonomiczna, 149 156 157 167 170 230 bajty, obsługują tylko jednoargumentowe operacje we / wy

Dane wejściowe muszą być kropkami, np . ..........Dla 10.

INPUT A
INPUT B
INPUT C
POP N H .
GOTO U
$
POP N A .[A][C]
POP Z H ..[H]
U
POP Z A [A]
POP Z N ..[N]
GOTO D [A] 
GOTO $ .[B] [N]
GOTO U
D
OUTPUT .[H]

Uoblicza A=A-Bi przeskakuje do Dkiedy A<=0. W przeciwnym razie $przypisuje A+Csię Ai dzwoni U.

Zawieś, jeśli nie zostanie znalezione rozwiązanie.

Sztuczki: nadużywaj zdolności „kompilatora” do interpretowania pustego łańcucha. Możesz zerwać warunki w GOTOinstrukcji, aby wykonać bezwarunkowe skoki i ta sama sztuczka działa POP.

Uwaga: Mogę grać w golfa bardziej o 3 bajty, ale robiąc to, moja i WheatWizard miałyby dokładnie taką samą logikę. Wynikiem jest prawdopodobnie najkrótsze rozwiązanie GraySnail i próbuję to udowodnić.

Uwaga: liczba bajtów jest kwestionowana przez Martina Endera w komentarzach. Wydaje się, że nie ma wyraźnego konsensusu co do tego, co zrobić z nazwanymi, rekurencyjnymi wyrażeniami lambda w odpowiedziach w języku C #. Zadałem więc na ten temat pytanie w Meta .

C # (.NET Core) , 32 31 bajtów

f=(a,b,c)=>a>b?1+f(a-b+c,b,c):1

Wypróbuj online!

Podejście rekurencyjne. Jeśli ślimak nie może uciec, kończy się następującym komunikatem:Process is terminating due to StackOverflowException.

• 1 bajt zapisany dzięki LiefdeWen!

SZARY ŚLIMAK, 219 206 169 167 159 156 146 bajtów (jednoargumentowy IO)

INPUT a
INPUT u
INPUT d
POP U c 
GOTO 1
3
POP f a [a][d]
POP U c ..[c]
1
GOTO 2 [a] 
GOTO 3 [U] [u]
POP f U ..[U]
POP f a [a]
GOTO 1
2
OUTPUT [c].

Myślę, że mogę trochę pograć w golfa.

JavaScript (ES6), 31 28 27 bajtów

Zaoszczędź kilka bajtów dzięki @Arnauld

Nie zdawałem sobie sprawy, że możemy zawieść z wyjątkiem. Jestem pewien, że jest to optymalne:

u=>d=>g=h=>h>u?1+g(h-u+d):1

Przypisz do zmiennej za pomocą np. f=Następnie wywołaj like f(climb)(fall)(height). Rzuca, InternalError: too much recursionjeśli wspinaczka jest niemożliwa.

JavaScript (ES6), 38 bajtów

f=(h,u,d=0)=>h>u?u>0?1+f(h-u,u-d):+f:1

Funkcja rekurencyjna, która zwraca liczbę dni lub NaNnigdy.

Przypadki testowe

let f=(h,u,d=0)=>h>u?u>0?1+f(h-u,u-d):+f:1;

[
  [30,  3,  2],
  [84, 17, 15],
  [79, 15,  9],
  [29, 17,  4],
  [13, 18,  8],
  [ 5,  5, 10],
  [ 7,  7,  7],
  [69,  3,  8],
  [81, 14, 14]
].map(x => console.log(x + '', '->', f.apply(null, x)))

Excel, 51 46 bajtów

-1 bajt dzięki @ Scarabee .

-4, ponieważ INT (x) = FLOOR (x, 1)

=IF(B1<A1,IF(C1<B1,-INT((B1-A1)/(B1-C1)-1)),1)

Dane wejściowe pobrane odpowiednio z komórek A1, B1 i C1. Zwraca FALSEza nieprawidłowe scenariusze.

C (gcc), 39 43 44 46 47 58 60 bajty

Tylko w 32-bitowym GCC i wszystkie optymalizacje wyłączone.

f(a,b,c){a=a>b?b>c?1+f(a-b+c,b,c):0:1;}

Zwróć 0, gdy rozwiązanie jest niemożliwe. Zmodyfikowana wersja oryginalnego rozwiązania rekurencyjnego.

Zainspirowany rozwiązaniem @Jonah J i rozwiązaniem @CarlosAlejo C #.

Zaktualizuję rozszerzoną wersję później (po skończeniu mojej odpowiedzi Grey Snail).

Java (OpenJDK 8) , 35 bajtów

(a,b,c)->b<a?c<b?(a+~c)/(b-c)+1:0:1

Wypróbuj online!

Matematyka wygrywa!

Kredyty

• -1 bajt dzięki Kevin Cruijssen

Python 2 , 37 bajtów

f=lambda x,y,z:x-y<1or 1+f(x-y+z,y,z)

Wypróbuj online!

W końcu moja wersja rekurencyjna spadła poniżej mojego standardowego obliczenia (przekazałem licznik do mojej funkcji zamiast dodawać jedną przed jej wywołaniem).

Python 2 , 4346 bajty

#43 bytes
lambda x,y,z:y/x>0 or[1-(x-y)/(z-y),0][z/y]
#46 bytes
lambda x,y,z:y/x and 1or[1-(x-y)/(z-y),0][z/y]

Wypróbuj online!

Ogolono 3 bajty, zamieniając „__ i 1” na „__> 0”.

Za pomocą sztuczek logicznych zasadniczo wykonuje:

if floor(y/x) > 0:
    return True # == 1
elif floor(z/y) == 1:
    return 0
elif floor(z/y) == 0:
    return 1-floor((x-y)/(z-y))
    # Python 2 implicitly treats integer division as floor division
    # equivalent: 1 + math.ceil((y-x)/(z-y))
    # because: -floor(-x) == ceil(x)

R, 43 bajty

Pożyczanie od innych odpowiedzi:

g=function(a,b,c)`if`(b<a,1+g(a-b+c,b,c),1)

Podaje błąd, jeśli nie ma rozwiązania.

J, 25 bajtów

Najpierw fajne rozwiązanie, które jest oszustwem, ponieważ zakłada, że ​​„cokolwiek innego niż dodatnia liczba całkowita” równa się „Brak”:

>.>:%/2-/\

wyjaśnienie

• 2-/\użyj okien o długości 2 w całym naszym 3 wejściowym elemencie, umieszczając między nimi znak minus, który na 30 3 2przykład zwraca27 1
• %/ umieść symbol podziału między każdym elementem listy, w naszym przypadku lista zawiera tylko dwa elementy, więc oznacza to „podziel 27 przez 1”
• >: przyrost o 1
• >. weź sufit

oficjalne rozwiązanie

Oto oficjalne rozwiązanie, które konwertuje negatywy i nieskończoność na 0, dla której części nie byłem w stanie znaleźć zadowalająco zwięzłego rozwiązania dla:

0:`[@.(>&0*<&_)>.>:%/2-/\

TIO

Perl 5 , 37 bajtów

Kod 35 bajtów +2 dla -pa .

$i-=$F[2]while++$\,($i+=$F[1])<$_}{

Wypróbuj online!

PHP> = 7,1, 60 bajtów

drukuje 0 dla braku ucieczki

[,$h,$u,$d]=$argv;echo$h>$u?$u>$d?ceil(($h-$d)/($u-$d)):0:1;

PHP Sandbox Online

PHP> = 7,1, 67 bajtów

nie drukuje niczego bez ucieczki

for([,$h,$u,$d]=$argv;($u>$d?:$h<=$u)&&0<$h+$t*$d-$u*++$t;);echo$t;

PHP Sandbox Online

Mathematica, 47 40 39 bajtów

If[#==#2,1,⌈(#-#3)/(#2-#3)⌉~Max~0]&

-7 bajtów z @KeyuGan

Rubinowy , 49 47 bajtów

->h,a,b{h-a<1?1:(1.0*(h-a)/[a-b,0].max+1).ceil}

Zgłasza wyjątek, jeśli ślimak nie może się wydostać

Wypróbuj online!

Partia, 66 bajtów

@set/an=%4+1,a=%1-%2+%3
@if %1 gtr %2 %0 %a% %2 %3 %n%
@echo %n%

Drugi ostatni przypadek testowy nic nie wydrukował, a ostatni przypadek testowy faktycznie się zawiesił CMD.EXE...

05AB1E , 19 bajtów

0[¼²+D¹<›i¾q}³-D1‹#

Wyjaśnienie:

0                   Initialise stack with 0
 [                  while(true)
  ¼                   increment the counter variable
   ²+                 add the second input to the top of the stack
     D¹<›i            if it is greater than or equal to the first input
          ¾             push the counter variable
           q            terminate the program
             }        end if
              ³-      subtract the third input from the top of the stack
                D     duplicate top of stack
                 1‹   if it is less than 1
                   #  break the loop

W przypadku niepoprawnych wartości może to zwracać dowolną wartość mniejszą niż 1. Jednak w 05AB1E tylko 1 jest prawdą, więc spełnia to wymaganie, aby wyjście dla niepoprawnej wartości było fałszem.

Wypróbuj online!

PHP, 60 bajtów

[,$h,$v,$d]=$argv;echo$h>$v?$v>$d?ceil(($h-$d)/($v-$d)):N:1;

wydruki Ndla None. Uruchom z -r.

05AB1E , 12 bajtów

.×ηO<²›1k2÷>

Wypróbuj online!

Wydruki 0 jeśli jest to niemożliwe.

Format wejściowy:

[climb, -fall]
height

Japt , 12 bajtów

@UµV-W §W}aÄ

Przetestuj online!

Wyjścia undefined nigdy, po ewentualnym zawieszeniu przeglądarki na jakiś czas, więc bądź ostrożny.

Nie jestem przekonany, że jest to optymalne. oWV-W ldziała na wszystkich oprócz trzech ostatnich przypadków ...

Haskell , 30 29 bajtów

(b!c)a=1+sum[(b!c)$a+c-b|a>b]

Wypróbuj online!

Krótszy niż istniejąca odpowiedź Haskella. Być może ktoś inny może mnie pokonać.

Wykorzystuje to podejście rekurencyjne do rozwiązania problemu. Każda rekurencja jest zasadniczo dniem ruchu ślimaka. Jeśli pozostała odległość do końca jest mniejsza niż odległość, która jest jeszcze wymagana, kończymy naszą rekurencję.

QBIC , 31 23 bajtów

Właśnie zauważyłem, że wymagania się zmieniły. Ta wersja nie sprawdza, czy ślimak kiedykolwiek osiągnie szczyt studni.

≈:-:>0|q=q+1┘a=a-b+:]?q

Wyjaśnienie poniżej, dotyczące oryginalnej wersji, która sprawdza, czy istnieje rozwiązanie, obejmuje również wszystkie odpowiednie części tego kodu.

Oryginalna, 31-bajtowa odpowiedź:

~:>:|≈:-a>0|q=q+1┘c=c-a+b]?q\?0

Wyjaśnienie

~           IF
 :          cmd line arg 'a'  (the increment of our snail)
  >         is greater than
   :        cmd line arg 'b'  (the decrement, or daily drop)
    |       THEN
≈           WHILE
 :          cmd line arg 'c'  (the height of the well)
  -a        minus the increment (we count down the hieght-to-go)
    >0|     is greater than 0 (ie while we haven't reached the top yet)
q=q+1       Add a day to q (day counter, starts at 1)
┘           (syntactic linebreak)
c=c-a+b     Do the raise-and-drop on the height-to-go
]           WEND
?q          PRINT q (the number of days)
\?0         ELSE (incrementer <= decrementer) print 0 (no solution)

Wypróbuj online! (OK, niezupełnie: jest to tłumaczenie kodu QBIC na kod QBasic uruchamiany w środowisku repl.it (nieco brakuje) QBasic)

Excel VBA, 47 bajtów

Anonimowa funkcja bezpośredniego okna VBE, która pobiera dane wejściowe z zakresu [A1:C1]odActiveSheet wyjściowych obiektów do bezpośredniego okna VBE

To przede wszystkim rozwiązanie oparte na formule Excel wydaje się być mniejsze niż każde rozwiązanie oparte wyłącznie na VBA, które mogę wymyślić :(

?[If(B1>C1,-Int((B1-A1)/(B1-C1)-1),Int(A1=B1))]

Haskell, 47 55 bajtów (48, jeśli wymagana jest krotka)

f d c s|d<=c=1|c<s= -1|d>c||c<s=1+(f(d-c+s)c s)

wariacja krotki

f(d,c,s)|d<=c=1|c<s= -1|d>c||c<s=1+(f(d-c+s)c s)

Wyjaśnienie

f d c s       function that does all the heavy lifting =)
              d - depth
              c - climb per day
              s - slide per night

 |d<=c=1             recursion terminator. 1 day of climbing 
 |c<s= -1            possibility check. top can't be reached
 |otherwise=1+(f(d-c+s)c s)  1 day plus the rest of the distance

Python 3, 41 bajtów

f=lambda a,b,c:int(b>=a)or 1+f(a-b+c,b,c)

Błąd dla Nigdy

Outgolf @veganaiZe

APL (Dyalog) , 13 bajtów

(⌈+÷⊢)/0⌈2-/⊢

Wypróbuj online!

Błędy przy dzieleniu przez zero, jeśli ślimak nie może wydostać się ze studni.

C # (.NET Core) , 37 bajtów

(h,c,f)=>h>c?f<c?1+(h-f-1)/(c-f):0:1;

Nierekurencyjna lambda. Wykorzystuje wzór znaleziony tutaj . Można skrócić o 6 bajtów, jeśli „jakikolwiek wynik ujemny” jest prawidłowym sposobem na zwrócenie błędu; obecnie zwraca 0 zamiast tego.

Python v2 i v3, 44 bajtów

f=lambda x,y,z:1+f(x-(y-z),y,z)if x>y else 1

^ Nieskończona rekurencja (błąd) dla przypadku Brak.

Programowalny kalkulator HP-15C, 26 bajtów

Trzy liczby są ładowane do stosu w kolejności przed uruchomieniem programu. Wysokość upadku jest wprowadzana jako liczba ujemna. Jeśli ślimak nie może wydostać się ze studni, wynikiem jest albo liczba ujemna, albo błąd nr 0 (błąd podziału zerowego).

Kody operacyjne szesnastkowe:

C5 C1 B4 C5 FB 74 1A C4 FA B4 C5 FD C1 C1 A3 70 C6 F0 B4 FA EB F1 FA B2 0A F1

Znaczenie instrukcji:

x↔y 
ENTER
g R⬆
x↔y 
− 
g TEST x≤0 
GTO A
R⬇
+ 
g R⬆
x↔y 
÷ 
ENTER
ENTER
f FRAC
TEST x≠0 
EEX 
0 
g R⬆
+ 
g INT 
1 
+ 
g RTN 
f LBL A
1

Możesz wypróbować program za pomocą tego symulatora HP-15C .

Common Lisp, 49 bajtów

(defun f(a b c)(if(> a b)(1+(f(+(- a b)c)b c))1))

Wypróbuj online!

Funkcja rekurencyjna, przepełnienie stosu, jeśli nie znaleziono rozwiązania.

PowerShell , 95 94 bajtów

$g=$args[0]
$c=$args[1]
$f=$args[2]
$p=0
$d=0
1..$g|%{$d+=1;$p+=$c;if($p-ge$g){$d;exit}$p-=$f}

Wypróbuj online!