Фон

Есть общая загадка, которая выглядит примерно так:

Улитка находится на дне 30-футового колодца. Каждый день улитка может подняться на 3 фута. Ночью, когда они спят, они спускаются вниз на 2 фута. Сколько дней нужно улитке, чтобы выбраться из колодца?

Интуитивный ответ

30 дней, потому что улитка поднимается на 1 фут в день в течение 30 дней, чтобы достичь вершины,

но на самом деле ответ

28 дней, потому что как только улитка поднимется в воздух на 27 футов (после 27 дней), они просто поднимутся на оставшиеся 3 фута к вершине на 28-й день.

Вызов

Эта проблема обобщает эту загадку. Учитывая три положительных целых числа в качестве входных данных, представляющих общую высоту, высоту набора высоты и высоту падения, возвращает количество дней, которое потребуется, чтобы выбраться из скважины.

Если улитка не может выбраться из колодца, вы можете вернуть 0, вернуть ложное значение или сгенерировать исключение. Вы также можете написать код, который будет останавливаться тогда и только тогда, когда существует решение.

Если вы хотите, вы можете принять высоту падения как отрицательное целое число.

Тестовые случаи

(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) -> Нет
(81, 14, 14) -> Нет

счет

Это код-гольф , поэтому выигрывает самый короткий ответ на каждом языке.

Grey Snail , 1206 байтов для числового ввода / вывода, 149 байтов для одинарного ввода / вывода

Ради забавы. Состав первой программы:

• 451 байт, преобразование числа в точки
• 121 байт, основная функция (отдельная версия написана ниже)
• 634 байта, преобразование точек в число

Возьмите числовой ввод и вывод. Вход A, B, Cсоответственно. По сравнению с другим (близким) O(1)ответом, код имеет сложность O(n). Но для большого количества это может съесть Вашу память сначала.

Повесьте, если решение не найдено.

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(возможно) рекурсивная функция для преобразования целых чисел в точки Аргумент сохраняется в [p]и выводится в [o].

Uявляется функцией тестирования S1>=S2, сохраняющей параметр B, Aпри сохранении A-Bв A.

Код, начиная с Dзаглушки, превращает точки в числа.

Основополагающий принцип такой же, как и в моем ответе C (срывая ложные данные для невозможных решений).

Автономная версия, 149 156 157 167 170 230 байты, поддерживают только унарный ввод / вывод

Ввод должен быть точками, например, ..........для 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рассчитывает A=A-Bи переходит к Dкогда A<=0. В противном случае $назначается A+Cдля Aи вызова U.

Повесьте, если решение не найдено.

Трюки: злоупотребляйте способностью "компилятора" интерпретировать пустую строку. Вы можете срывать условия в GOTOзаявлении, чтобы сделать безусловные прыжки, и тот же трюк работает для POP.

Замечание: я могу сыграть в гольф больше на 3 байта, но при этом мой и WheatWizard ответ будут иметь точно такую ​​же логику. В результате, вероятно, самое короткое решение GraySnail, и я пытаюсь доказать это.

Примечание: количество байтов ставится под сомнение Мартином Эндером в комментариях. Кажется, нет единого мнения о том, что делать с именованными рекурсивными лямбда-выражениями в ответах на C #. Так что я задал вопрос в Мете об этом.

C # (.NET Core) , 32 31 байт

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

Попробуйте онлайн!

Рекурсивный подход. Если улитка не может сбежать, она заканчивается следующим сообщением:Process is terminating due to StackOverflowException.

• 1 байт сохранен благодаря LiefdeWen!

GREY SNAIL, 219 206 169 167 159 156 146 байт (одинарный 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].

Я думаю, что могу немного поиграть в гольф.

JavaScript (ES6), 31 28 27 байт

Сохранено несколько байтов благодаря @Arnauld

Я не понял, что мы можем потерпеть неудачу за исключением. Уверен, что это оптимально:

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

Присвойте переменную, например f=, затем вызовите like f(climb)(fall)(height). Броски, InternalError: too much recursionесли подняться невозможно.

JavaScript (ES6), 38 байт

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

Рекурсивная функция, которая возвращает количество дней или NaNникогда.

Контрольные примеры

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 байт

-1 байт благодаря @ Скараби .

-4 потому что INT (x) = FLOOR (x, 1)

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

Ввод взят из ячеек A1, B1 и C1 соответственно. Возвращает FALSEдля недействительных сценариев.

C (gcc), 39 43 44 46 47 58 60 байтов

Только на 32-битном GCC и все оптимизации отключены.

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

Вернуть 0, когда решение невозможно. Модифицированная версия оригинального рекурсивного решения.

Вдохновлен решениями @Jonah J и @CarlosAlejo C #.

Я обновлю расширенную версию позже (после того, как я закончу свой ответ Grey Snail).

Java (OpenJDK 8) , 35 байт

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

Попробуйте онлайн!

Математика побеждает!

кредиты

• -1 байт благодаря Кевину Круйссену

Python 2 , 37 байт

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

Попробуйте онлайн!

Наконец, моя рекурсивная версия оказалась ниже моего стандартного вычисления (я передавал счет своей функции вместо того, чтобы добавить ее перед вызовом).

Python 2 , 4346 байтов

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

Попробуйте онлайн!

Побрил 3 байта, торгуя «__ и 1» для «__> 0».

Используя булеву хитрость, по существу выполняет:

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 байта

Заимствование из других ответов:

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

Выдает ошибку, если нет решения.

J, 25 байт

Сначала хорошее решение, которое является читом, так как оно предполагает, что «что-либо кроме положительного целочисленного результата» равно «None»:

>.>:%/2-/\

объяснение

• 2-/\используйте окна длиной 2 на нашем 3 элементном вводе, помещая знак минус между каждым, что для ввода 30 3 2, например, возвращает27 1
• %/ поместите символ деления между каждым элементом списка, в нашем случае список состоит только из двух элементов, поэтому он означает «делить 27 на 1»
• >: увеличение на 1
• >. взять потолок

официальное решение

Вот официальное решение, которое преобразует негативы и бесконечность в 0, и я не смог найти достаточно краткого решения для этого:

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

TIO

Perl 5 , 37 байт

35 байт код +2 для -pa.

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

Попробуйте онлайн!

PHP> = 7.1, 60 байт

печатает 0 для выхода

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

PHP Sandbox Online

PHP> = 7,1, 67 байт

ничего не печатает без побега

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

PHP Sandbox Online

Mathematica, 47 40 39 байт

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

-7 байтов от @KeyuGan

Рубин , 49 47 байт

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

Выдает исключение, если улитка не может выбраться

Попробуйте онлайн!

Пакетный, 66 байт

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

Второй последний контрольный пример ничего не печатал, а последний контрольный пример фактически потерпел крах CMD.EXE...

05AB1E , 19 байтов

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

Объяснение:

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

Для недопустимых значений это может возвращать любое значение меньше 1. Однако в 05AB1E только 1 является правдивым, поэтому это соответствует требованию, что вывод для недопустимого значения должен быть ложным.

Попробуйте онлайн!

PHP, 60 байт

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

печатает Nдля None. Беги с -r.

05AB1E , 12 байтов

.×ηO<²›1k2÷>

Попробуйте онлайн!

Печатает, 0если невозможно.

Формат ввода:

[climb, -fall]
height

Japt , 12 байт

@UµV-W §W}aÄ

Проверьте это онлайн!

Выходы undefinedникогда, после возможного зависания вашего браузера на некоторое время, поэтому, пожалуйста, будьте осторожны.

Я не уверен, что это оптимально. oWV-W lработает на всех, кроме последних трех случаев ...

Haskell , 30 29 байт

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

Попробуйте онлайн!

Короче, чем существующий ответ на Haskell. Возможно, кто-то еще может победить меня.

Это использует рекурсивный подход к решению проблемы. Каждая рекурсия по сути является днем ​​движения для улитки. Если оставшееся до конца расстояние меньше требуемого, мы заканчиваем нашу рекурсию.

QBIC , 31 23 байта

Просто заметил, что требования изменились. Эта версия не проверяет, достигнет ли когда-нибудь улитка вершины колодца.

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

Приведенное ниже объяснение для исходной версии, которая проверяет, существует ли решение, охватывает также все соответствующие части этого кода.

Оригинал, 31 байтовый ответ:

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

объяснение

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

Попробуйте онлайн! (Хорошо, не совсем: это перевод QBIC в код QBasic, запускаемый в repl.it (в некоторой степени отсутствует) среда QBasic)

Excel VBA, 47 байт

Функция анонимного непосредственного окна VBE, которая принимает входные данные из диапазона [A1:C1]от ActiveSheetвыходных данных объекта до непосредственного окна VBE

Это решение, основанное на формулах Excel, кажется меньше, чем любое чисто VBA-решение, которое я могу придумать :(

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

Haskell, 47 55 байт (48, если требуется кортеж)

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

вариация кортежа

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

объяснение

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 байт

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

Ошибка для Никогда

Outgolf @veganaiZe

APL (Dyalog) , 13 байт

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

Попробуйте онлайн!

Ошибки при делении на ноль, если улитка не может выбраться из колодца.

C # (.NET Core) , 37 байт

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

Нерекурсивная лямбда. Использует формулу, найденную здесь . Может быть сокращено на 6 байт, если «любой отрицательный результат» является допустимым способом возврата ошибки; в настоящее время возвращает 0 вместо.

Python v2 & v3, 44 байта

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

^ Бесконечная рекурсия (ошибка) для None case.

Программируемый калькулятор HP-15C, 26 байт

Три числа загружаются в стек по порядку перед запуском программы. Высота падения вводится как отрицательное число. Если улитка не может вылезти из колодца, результатом будет либо отрицательное число, либо ошибка № 0 (ошибка деления на ноль).

Коды операций в шестнадцатеричном формате:

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

Инструкция значения:

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

Вы можете попробовать программу с этим симулятором HP-15C .

Common Lisp, 49 байт

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

Попробуйте онлайн!

Рекурсивная функция, переполнение стека, если решение не найдено.

PowerShell , 95 94 байта

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

Попробуйте онлайн!