The Snail in the Well

Question

Background

There's a common riddle that goes something like this:

A snail is at the bottom of a 30 foot well. Every day the snail is able to climb up 3 feet. At night when they sleep, they slide back down 2 feet. How many days does it take for the snail to get out of the well?

The intuitive answer is

30 days, because the snail climbs at 1 foot per day for 30 days to reach the top,

but actually the answer is

28 days, because once the snail is 27 feet in the air (after 27 days), they will simply climb the remaining 3 feet to the top on the 28th day.

Challenge

This challenge generalizes this riddle. Given three positive integers as input, representing the total height, the climb height, and the fall height, return the number of days it will take to climb out of the well.

If the snail cannot climb out of the well, you may return 0, return a falsy value, or throw an exception. You may also write code that will halt if and only if a solution exists.

If you wish, you may take the fall height as a negative integer.

Test Cases

(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) -> None
(81, 14, 14) -> None

Scoring

This is code-golf, so the shortest answer in each language wins.

Answer 1

Gray Snail, 1206 bytes for numeric I/O, 149 bytes for unary I/O

For fun. Composition of first program:

• 451 bytes, converting number into dots
• 121 bytes, core function (a separated version is written below)
• 634 bytes, converting dots into number

Take numeric input and output. Input is A, B, C respectively. Compared to other (near) O(1) answer, the code has a complexity of O(n). But for large number, it may eat up your memory first.

Hang if no solution is found.

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]

f is a (maybe) recursive function to convert integers into dots. Argument is saved in [p] and output in [o].

U is a function testing S1>=S2, storing parameter in B, A while saving A-B into A.

Code starting from D is a stub converting dots into numbers.

The underlying principle is the same with my C answer (ripping off falsy output for impossible solutions).

Standalone version, 149 156 157 167 170 230 bytes, only support unary I/O

Input needs to be dots, e.g. .......... for 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]

U calculates A=A-B, and jumps to D when A<=0. Otherwise $ assigns A+C to A and call U.

Hang if no solution is found.

Tricks: abuse the "compiler"'s ability to interpret empty string. You can rip off conditions in GOTO statement to make unconditioned jumps and the same trick works for POP.

Remark: I may golf it more by 3 bytes but by doing so, mine and WheatWizard's answer would have the exact same logic. The result is probably the shortest GraySnail solution and I'm trying to prove it.

Answer 2

Note: the byte count is being questioned by Martin Ender in the comments. It seems there is no clear consensus about what to do with named, recursive lambda expressions in C# answers. So I have asked a question in Meta about it.

C# (.NET Core), 32 31 bytes

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

Try it online!

A recursive approach. If the snail cannot escape, it ends with the following message: Process is terminating due to StackOverflowException.

• 1 byte saved thanks to LiefdeWen!

Answer 3

GRAY SNAIL, 219 206 169 167 159 156 146 bytes (unary 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].

I think I can golf this down a bit.

Answer 4

JavaScript (ES6), 31 28 27 bytes

Saved a few bytes thanks to @Arnauld

I hadn't realized we could fail with an exception. Pretty sure this is optimal:

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

Assign to a variable with e.g. f=, then call like f(climb)(fall)(height). Throws InternalError: too much recursion if the climb is impossible.

---

JavaScript (ES6), 38 bytes

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

A recursive function that returns the number of days, or NaN for never.

Test cases

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

Answer 5

Excel, 51 46 bytes

-1 byte thanks to @Scarabee.

-4 because INT(x) = FLOOR(x,1)

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

Input taken from Cells A1, B1 and C1 respectively. Returns FALSE for invalid scenarios.

Answer 6

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

Only on 32-bit GCC and all optimizaitons turned off.

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

Return 0 when solution is impossible. A modified version of original recursive solution.

Inspired by @Jonah J solution and @CarlosAlejo C# solution.

I'll update the expanded version later (after I finish my Grey Snail answer).

Answer 7

Java (OpenJDK 8), 35 bytes

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

Try it online!

Math wins!

Credits

• -1 byte thanks to Kevin Cruijssen

Answer 8

Python 2, 37 bytes

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

Try it online!

Finally got my recursive version below my standard calculation (I was passing a count to my function instead of adding one before calling it).

Python 2, 43 46 bytes

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

Try it online!

Shaved 3 bytes by trading "__ and 1" for "__>0".

Using boolean trickery, essentially executes:

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)

Answer 9

Perl 5, 37 bytes

35 bytes code +2 for -pa.

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

Try it online!

Answer 10

R, 43 bytes

Borrowing from other answers:

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

Gives error if no solution.

Answer 11

Haskell, 30 29 27 bytes

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

Try it online!

Shorter than the existing Haskell answer. Perhaps someone else can beat me.

This uses a recursive approach to solving the problem. Each recursion is essentially a day of movement for the snail. If the distance left to the end is less than the distance still required we end our recursion.

Answer 12

J, 25 bytes

First a nice solution, which is a cheat, since it assumes that "anything other than a positive integer result" equals "None":

>.>:%/2-/\

explanation

• 2-/\ use windows of length 2 across our 3 item input, placing a minus sign between each one, which for the input 30 3 2, eg, returns 27 1
• %/ put a division symbol between each element of the list, in our case the list has only two items, so it means "divide 27 by 1"
• >: increment by 1
• >. take the ceiling

official solution

Here is the official solution that converts negatives and infinity to 0, which part i was not able to find a satisfyingly terse solution for:

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

TIO

Answer 13

PHP>=7.1, 60 bytes

prints 0 for no escape

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

PHP Sandbox Online

PHP>=7.1, 67 bytes

prints nothing for no escape

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

PHP Sandbox Online

Answer 14

PowerShell, 95 94 bytes

$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}

Try it online!

Answer 15

Mathematica, 47 40 39 bytes

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

-7 bytes from @KeyuGan

Answer 16

Ruby, 49 47 bytes

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

Throws exception if snail can't climb out

Try it online!

Answer 17

Batch, 66 bytes

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

The second last test case printed nothing, and the last test case actually crashed CMD.EXE...

Answer 18

05AB1E, 19 bytes

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

Explanation:

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

For invalid values, this may return any value less than 1. However, in 05AB1E, only 1 is truthy so this meets the requirement that the output for an invalid value should be falsy.

Try it online!

Answer 19

PHP, 60 bytes

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

prints N for None. Run with -r.

Answer 20

05AB1E, 12 bytes

.×ηO<²›1k2÷>

Try it online!

Prints 0 if impossible.

Input format:

[climb, -fall]
height

Answer 21

Japt, 12 bytes

@UµV-W §W}aÄ

Test it online!

Outputs undefined for never, after possibly freezing your browser for a while, so please be careful.

I'm not convinced this is optimal. oWV-W l works on all but the last three cases...

Answer 22

Python v2 & v3, 44 Bytes

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

^Infinite recursion (error) for None case.

Answer 23

HP-15C Programmable Calculator, 26 Bytes

The three numbers are loaded into the stack in order before running the program. The fall height is entered as a negative number. If the snail cannot climb out of the well, the result is either a negative number or error #0 (zero divide error).

Op codes in hex:

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

Instruction meanings:

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

You can try the program with this HP-15C simulator.

Answer 24

Common Lisp, 49 bytes

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

Try it online!

Recursive function, stack overflow if no solution found.

Answer 25

QBIC, 31 23 bytes

Just noticed the requirements changed. This version doesn't check if the snail will ever reach the top of the well.

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

The explanation below, for the original version that does check if a solution exists, covers all relevant parts of this code too.

---

Original, 31 byte answer:

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

Explanation

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

Try it online! (OK, not really: this is a translation of QBIC to QBasic code run in repl.it 's (somewhat lacking) QBasic enviroment)

Answer 26

Excel VBA, 47 Bytes

Anonymous VBE immediate window function that takes input in from the range [A1:C1] from the ActiveSheet object outputs to the VBE immediate window

This primarily Excel formula based solution appears to be smaller than any purely VBA solution that I can come up with :(

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

Answer 27

Haskell, 47 55 bytes (48 if tuple required)

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

tuple variation

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

Explanation

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

Answer 28

Python 3, 41 Bytes

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

Error for Never

Outgolf @veganaiZe

Answer 29

APL (Dyalog), 13 bytes

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

Try it online!

---

Errors on division by zero if the snail cannot climb out of the well.

Answer 30

C# (.NET Core), 37 bytes

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

Non-recursive lambda. Uses formula found here. Could be shortened by 6 bytes if "any negative result" is a valid way to return failure; currently returns 0 instead.