Возможно, вы видели это в « Крепком орешке: с местью» … Этот вопрос основан на знаменитой головоломке с кувшинами на 3 и 5 литров, но с немного другим уклоном.
Подберите какой-нибудь код, который, если дать целое число от 1 до 100, даст вам самые быстрые инструкции отмерить в баке соответствующее количество литров воды из фонтана, используя 3-литровый кувшин и 5-литровый кувшин.
Там нет градаций ни на одном из кувшинов; фонтан изобилует водой, и предполагается, что бак опорожняется в начале каждого выполнения кода.
Вы не можете получить доступ к воде из резервуара, когда она попадет в резервуар.
Формат исполнения следующий:
Входные данные:
4
например.
Выход
Выведите каждый пронумерованный шаг, как показано на рисунке, а затем подсчитайте объемы кувшина на 5 л, кувшина на 3 л и бака. Формат Tally также показан ниже. Количество шагов также должно быть выведено в конце шагов.
1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into 3L jug
5L: 2, 3L: 3, T: 0
3) Empty 3L jug
5L: 2, 3L: 0, T: 0
4) Pour from 5L jug into 3L jug
5L: 0, 3L: 2, T: 0
5) Fill 5L jug
5L: 5, 3L: 2, T: 0
6) Pour from 5L jug into 3L jug
5L: 4, 3L: 3, T: 0
7) Pour from 5L jug into tank
5L: 0, 3L: 3, T: 4
Volume measured out in 7 turns
Пример 2
Входные данные: 8
Выход:
1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
3) Fill 3L jug
5L: 0, 3L: 3, T: 5
4) Pour from 3L jug into tank
5L: 0, 3L: 0, T: 8
Volume measured out in 4 turns
Условные обозначения
Fill xL jug
- заполняет соответствующий кувшин до фонтана от фонтанаEmpty xL jug
- выливает содержимое кувшина в фонтанPour from xL jug into yL jug
- Выливает содержимое кувшина xL в кувшин yLPour from xL jug into tank
- Выливает содержимое кувшина xL в бак
Самый короткий код выигрывает.
источник
Ответы:
Рубин,
407376365331324323Это становится трудно читать ...
Принимает участие в STDIN. Пример прогона для N = 10:
источник
T-SQL 2012:
14101302Еще одна причудливая попытка задать вопрос в SQL, но эта предложила приятную возможность поиграть с некоторыми из новых опций оконных функций в версии 2012. Кроме того, она использует рекурсивные CTE, которые могут быть не очень впечатляющими в большинстве языков программирования, но рекурсия в SQL это все равно что переключаться с коня и глючного на Ferrari.
Механизм в основе этого находится в строках 5-12, который использует рекурсивный CTE и оконную функцию для построения таблицы большинства чисел, необходимых для решения проблемы. Обратите особое внимание на тест для 3, 4, 6 или 9, который обеспечивает оптимальный подход к решению на 3 с от этих чисел и далее. (Технически, это ничья на 4 между подходом 3-1 и 2-2, но при таком подходе у меня появилось много персонажей.) Тогда легко присоединиться к таблице поиска оптимальных шагов для различных куски проблемы и использовать другую оконную функцию, чтобы правильно нумеровать шаги.
Если у вас нет MS SQL, поиграйте с ним в SQLFiddle.
Результаты для входа 42:
Редактировать:
Выиграл приличное улучшение
источник
Javascript: 481
Первая попытка игры в гольф, совет ценится
Он запутывается с некоторыми числами, потому что не проверяет, лучше ли разлить 3 или 5, например: 9 дает 9 ходов вместо 6, я мог бы исправить это позже
Вставьте его в консоль
От 553 до 481 благодаря @WallyWest
источник
n=["3L jug","5L jug","tank"];l=[0,0,0];t=[3,5,0];h=0;c=console;function e(d){l[d]=t[d];c.log(++h+") Fill "+n[d]);k()}function m(d,g){s=l[d];f=l[g];b=s+f>t[g];l[g]=b?t[g]:f+s;l[d]=b?s-(t[g]-f):0;c.log(++h+") Pour from "+n[d]+" into "+n[g]);k()}function k(){c.log("5L: "+l[1]+", 3L: "+l[0]+", T: "+l[2])}a=prompt();for(t[2]=a;4<a;)e(1),m(1,2),a-=5;2<a&&(e(0),m(0,2),a-=3);1<a&&(e(1),m(1,0),m(1,2),a=0);0<a&&(e(0),m(0,1),e(0),m(0,1),m(0,2));c.log("Volume measured out in "+h+" turns")
для 481 символа ...if
sЯва, 610
Я принял решение Сумедха и сыграл в гольф. Я хотел поместить это в комментарии, но моей репутации недостаточно :(. Это на 40% меньше, я думаю, что это должно быть по крайней мере разделено. Хотя все еще далеко от первого, хотя ...
Вот негольфированный:
NB: работает только при первом запуске. Перезапустите его, и результат будет неправильным (из-за глобальной переменной).
Следующая версия безопасна, но мы теряем 2 символа с 610 до 612:
Пример вывода для N = 69:
источник
Ява: 984
Вот код
Ввод из командной строки. например: Java X 4
источник
main(String[]s)
,int n=Integer.parseInt(s[0]),t=0,c=0;
,java.io.PrintStream q=System.out;
. Кроме того, может быть возможно написать первыйwhile
как один или два символа корочеfor
. Кроме того, вашиString
повторяются, вы можете попытаться сохранить повторяющиеся части в переменных или создать функции, которые строят их, используя только один префабString
.Python 2.7 - 437
Не самый короткий код, но я думаю, что это самый оптимальный способ решения этой проблемы.
Как я уже говорил в комментариях, самый оптимальный способ рассчитать это:
divmod(amount,5)
. Это даст вам один из 4,3,2,1 в качестве остатка.Что оставляет 1 или 2 в качестве остатка. Используйте оптимальное решение для любого из них, которое может быть заранее известно как:
Код:
И вывод на 4л за 7 шагов:
источник
Smalltalk (Smalltalk / X),
568 560516вход в п:
мальчик, это определенно самая запутанная программа, которую я когда-либо писал ...
Изменить: Некоторые другие Smalltalks могут не разрешать автоматически объявленные переменные рабочего пространства, и вам придется добавлять объявления. Также bindWith: может быть другим (expandWith: '<p>').
Пример вывода для n = 17:
источник
С
567609предыдущая недействительная версия:
и вот код дегольфеда:
источник
C (
480465 байт)Оптимальная версия (добавляет 10 байт)
Скорее всего, здесь будет больше игры в гольф - функции вывода убивали меня. Это должно дать оптимальное решение (наименьшее количество шагов). Подобно другому коду, он заполняет и опорожняет кувшины объемом 5 л, пока не опустится ниже 5, а затем переключится на кувшины объемом 3 л. Он проверяет 2 особых случая (6 и 9) и, если находит, переключается на кувшины 3 л. Инструкции по получению 1л и 2л жестко запрограммированы.
Более читаемая версия:
Редактирование:
Тестовый вывод для n = 11 (оптимальный вариант):
источник
T-SQL (2012):
794689580Вдохновлен ответом @ Jonathan-Van-Matre 's T-SQL в сочетании с алгоритмом @ Lego-Stormtroopr . Я хотел сделать это, потому что я наслаждался 99 бутылками пива .
Я пытался держать окно (
OVER
) как минимум в предпочтениях математических / bool-функций.SQLFiddle здесь .
Входные данные:
11
Человек читаемый:
источник
input = 8
input = 11
Python 3 (417 символов)
Разъяснения
Обратите внимание, что у нас есть 4 объекта, а именно: кувшин на 3 л, кувшин на 5 л, резервуар и подставка. Единственные операции, которые мы можем сделать, - это перемещать воду от объекта
a
к объектуb
. Это какая функцияo(a, b)
делает в моем коде, она перемещает воду и печатает ее и продолжает считать.Трюки
N=['3L jug','5L jug','tank',0]
, Здесь мне нужен последний элемент, чтобы избежатьIndexError
. Кроме того, его можно использовать как глобальную переменную подсчета без расширенногоglobal
ключевого слова. Например,N[3] += 1
Так как
0 <= a < 4, 0 <= b < 4
в функцииo(a, b)
мы можем кодировать(a, b)
в шестнадцатеричную цифру, используя(a << 2) | b
, и декодировать ее используяdivmod(x, 4)
. С помощью этого трюка все 5 решений (reminder=0, 1, 2, 3, 4
) могут быть закодированы в массив['','c1c12','d46','c2','d434d46']
, который немного короче, чем его первоначальная форма:A=[ (), ((3,0),(0,1),(3,0),(0,1),(0,2)), ((3,1),(1,0),(1,2)), ((3,0),(0,2)), ((3,1),(1,0),(0,3),(1,0),(3,1),(1,0),(1,2)) ]
Пример вывода (n = 17)
источник
COBOL (IBM Enterprise COBOL) 192 строки по 72 символа
Это подтверждение концепции для вопроса и начало для Golf-COBOL :-)
Вопрос требует самого быстрого. Итак, реализуем параллелизм. Даже один человек может сразу наполнить один кувшин объемом 3 л и один кувшин объемом 5 л.
Просто разделите ввод на восемь, оставив остаток. Сделайте несколько быстрых 5L / 3L наполнений до количества раз, сколько восемь подгонок, затем разберитесь с оставшимся количеством от одного до семи литров.
Самый интересный из оставшихся - на четыре литра. Делая это как один литр плюс три литра, выливает намного меньше воды, только 18 литров против 23 для других возможностей.
Кодекс (рабочий)
Это приводит к абсолютной загрузке диагностических сообщений для кода, запускаемого в неправильном месте, и нехватки необходимых точек останова.
Ни одна из диагностик не указывает на какое-либо влияние на объектный код. Таким образом, несмотря на то, что RC = 8 с перебоями, я знаю, что объект будет в порядке, поэтому связал его и запустил.
Вот выходы от одного до восьми литров. После этого все результаты могут быть интуитивно понятны. 17 и 100 включены в качестве примеров параллелизма.
Еще многое можно сделать, чтобы сжать программу в символах, прежде всего важен правильный вывод. Подсчет символов, когда они находятся на линиях фиксированной длины, это совсем другое дело.
Пример вывода:
источник