Головоломка на 3 и 5 литров

14

Возможно, вы видели это в « Крепком орешке: с местью» … Этот вопрос основан на знаменитой головоломке с кувшинами на 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

Условные обозначения

  1. Fill xL jug - заполняет соответствующий кувшин до фонтана от фонтана
  2. Empty xL jug - выливает содержимое кувшина в фонтан
  3. Pour from xL jug into yL jug - Выливает содержимое кувшина xL в кувшин yL
  4. Pour from xL jug into tank - Выливает содержимое кувшина xL в бак

Самый короткий код выигрывает.

Уолли Уэст
источник
возможный дубликат проблемы Water-Bucket
Говард
4
@ Ховард, старый вопрос плохо задан (не имеет критериев выигрыша) и был заброшен, поэтому я думаю, что этот вопрос лучше и его не следует закрывать.
Виктор Стафуса
Назовите меня сумасшедшим, но не будет ли оптимальным решением 1. Добавить как можно больше 5 л, 2. Добавить 3 л, если необходимо, 3. Добавить уже растворенную часть 2 л или 1 л, если необходимо?
1
@LegoStormtroopr Когда все сводится, правда. Но я ожидаю, что это будет соответствующим образом.
WallyWest
3
@LegoStormtroopr Я тоже так думал, но не 6 и 9 контрпримеры?
Пол Престиж

Ответы:

6

Рубин, 407 376 365 331 324 323

Это становится трудно читать ...

x=y=n=d=0
g=gets.to_i
"#{[43435,102,t=45,t,12,t,12,t,t][g+~d]||12}".chars{|c|n+=1
puts [eval(["x-=t=[3-y,x].min;y+=t"+t=";'Pour from 5L jug into 3L jug'","x=5;'Fill 5L jug'","d+=x;x=0"+t.sub(/3.+/,"tank'")][c.ord%3].tr t='35xy',c<?3?t:'53yx'),"5L: #{x}, 3L: #{y}, T: #{d}"]}while g>d
$><<"Volume measured out in #{n} turns"

Принимает участие в STDIN. Пример прогона для N = 10:

Fill 5L jug
5L: 5, 3L: 0, T: 0
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
Fill 5L jug
5L: 5, 3L: 0, T: 5
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
Volume measured out in 4 turns
Пол Престиж
источник
2
«Это становится трудно читать ...» - Чувак, разве в этом нет смысла играть в гольф? ;)
WallyWest
4
@WallWest Нет. У нас есть тег [обфускация] для них! Мое скромное мнение было бы таковым из двух решений Codegolf одинаковой длины, наиболее читаемым было бы лучшим.
Мистер Листер
@MrLister Справедливо, но иногда запутывание - единственный способ достичь желаемой усадки ...
WallyWest
5

T-SQL 2012: 1410 1302

Еще одна причудливая попытка задать вопрос в SQL, но эта предложила приятную возможность поиграть с некоторыми из новых опций оконных функций в версии 2012. Кроме того, она использует рекурсивные CTE, которые могут быть не очень впечатляющими в большинстве языков программирования, но рекурсия в SQL это все равно что переключаться с коня и глючного на Ferrari.

Механизм в основе этого находится в строках 5-12, который использует рекурсивный CTE и оконную функцию для построения таблицы большинства чисел, необходимых для решения проблемы. Обратите особое внимание на тест для 3, 4, 6 или 9, который обеспечивает оптимальный подход к решению на 3 с от этих чисел и далее. (Технически, это ничья на 4 между подходом 3-1 и 2-2, но при таком подходе у меня появилось много персонажей.) Тогда легко присоединиться к таблице поиска оптимальных шагов для различных куски проблемы и использовать другую оконную функцию, чтобы правильно нумеровать шаги.

Если у вас нет MS SQL, поиграйте с ним в SQLFiddle.

DECLARE @i INT=42,@l VARCHAR(9)='L jug ',@k VARCHAR(99)='into tank
5L: 0, 3L: 0, T: ',@o VARCHAR(99)='
5L: 5, 3L: 0, T: ',@n CHAR(1)='
',@5 VARCHAR(99)=') Pour from 5',@3 VARCHAR(99)=') Pour from 3'
;WITH t AS (SELECT @i i,(@i-@i%5)%5 j
UNION ALL
SELECT i-5,(i-i%5)%5+5 FROM t WHERE i>=5 AND i NOT IN(6,9)
UNION ALL
SELECT i-3,3FROM t WHERE i in(3,4,6,9)
UNION ALL
SELECT i-i,i FROM t WHERE i<3 AND i>0)
SELECT t.i,t.j,v.s,ROW_NUMBER()OVER(PARTITION BY t.j ORDER BY t.i DESC)x,SUM(t.j)OVER(ORDER BY t.i DESC ROWS UNBOUNDED PRECEDING)y INTO #q FROM(VALUES(1,5),(2,3),(3,2),(5,2))v(i,s) JOIN t ON t.j = v.i
SELECT z.b FROM(SELECT ROW_NUMBER()OVER(ORDER BY q.i DESC,w.s)a,CAST(ROW_NUMBER()OVER(ORDER BY q.i DESC,w.s)AS VARCHAR)+w.v+CAST(y-CASE WHEN q.s!=w.s THEN q.j ELSE 0 END AS VARCHAR)b
FROM(VALUES(5,1,') Fill 5'+@l+@o),(5,2,@5+@l+@k),(3,1,') Fill 3'+@l+@n+'5L: 0, 3L: 3, T: '),(3,2,@3+@l+@k),(2,1,') Fill 5'+@l+@o),(2,2,@5+@l+' into 3'+@l+@n+'5L: 2, 3L: 3, T: '),(2,3,@5+@l+@k),(1,1,') Fill 3'+@l+@n+'5L: 0, 3L: 3, T: '),(1,2,@3+@l+'into 5'+@l+@n+'5L: 3, 3L: 0, T: '),(1,3,') Fill 3'+@l+@n+'5L: 3, 3L: 3, T: '),(1,4,@3+@l+'into 5'+@l+@n+'5L: 5, 3L: 1, T: '),(1,5,@3+@l+'into tank'+@o))w(i,s,v)JOIN #q q ON w.i=q.j
UNION
SELECT 99,'Volume measured out in '+CAST(COUNT(*)AS VARCHAR)+' turns'
FROM #q)z

Результаты для входа 42:

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 5L jug 
5L: 5, 3L: 0, T: 5
4) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10 
5) Fill 5L jug 
5L: 5, 3L: 0, T: 10 
6) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 15 
7) Fill 5L jug 
5L: 5, 3L: 0, T: 15 
8) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 20 
9) Fill 5L jug 
5L: 5, 3L: 0, T: 20 
10) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 25 
11) Fill 5L jug 
5L: 5, 3L: 0, T: 25 
12) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 30 
13) Fill 5L jug 
5L: 5, 3L: 0, T: 30 
14) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 35 
15) Fill 5L jug 
5L: 5, 3L: 0, T: 35 
16) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 40 
17) Fill 5L jug 
5L: 5, 3L: 0, T: 40 
18) Pour from 5L jug  into 3L jug 
5L: 2, 3L: 3, T: 40 
19) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 42 
Volume measured out in 9 turns 

Редактировать:

Выиграл приличное улучшение

  • устранение ненужных +5 в первом ряду CTE и предложение WHERE, в котором это необходимо
  • встроенные таблицы VALUES, сохраняющие дорогостоящие операторы DECLARE
  • помня конвертировать двухбайтовые CRLF-файлы Windows в стиль Unix на этот раз.
Джонатан Ван Матре
источник
+1 за храбрость, чувак ... Очень впечатляет и спасибо за скриптовую ссылку MS SQL!
WallyWest
1
Хаха, спасибо мужчина! Я действительно полагал, что этот может быть выигрышным, когда я начал и имел рекурсивный основной запрос. Но даже при обширном гольфе, многословность добавления всего необходимого текста обречена на мое окончательное решение. :)
Джонатан Ван Матр
Если бы я мог получить «самую креативную» награду, вы бы ее получили ...
WallyWest
+1 за то, что сделал меня лол. T-SQL - это, конечно, странный клуб, в котором можно носить сумку для игры в гольф.
Коминтерн
5

Javascript: 481

Первая попытка игры в гольф, совет ценится

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

Он запутывается с некоторыми числами, потому что не проверяет, лучше ли разлить 3 или 5, например: 9 дает 9 ходов вместо 6, я мог бы исправить это позже

Вставьте его в консоль

От 553 до 481 благодаря @WallyWest

Сэм
источник
1
Вы можете попробовать: 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 символа ...
WallyWest
@WallWest спасибо, не думал об использовании логических операторов вместо ifs
Сэм
3

Ява, 610

class X{int n,c=0,t=0;public void static main(String[]a){n=Integer.parseInt(a[0]);String s,b,f,k,m,u;b="5L";s="3L";k="tank";u="Fill %s jug\n5L: %d, 3L: %d, T: %d";m="\nPour from %s jug into %s\n5L: %d, 3L: %d, T: %d";f=u+m;for(;n>4;)z(f,2,5,b,5,0,t,b,k,0,0,t+=5);while(n!=0){if(n==1)z(f+f+m,5,1,s,0,3,t,s,b,3,0,t,s,3,3,t,s,b,5,1,t,s,k,5,0,t+1);if(n==3)z(f,2,3,s,0,3,t,s,k,0,0,t+3);z(f+m,3,2,b,5,0,t,b,s,2,3,t,b,k,0,3,t+=2);if(n==2)z("Empty 3L jug\n5L: 0, 3L: 0,T: %d",1,0,t)}z("Volume measured out in %d turns",0,0,c)}void z(String s,int o,int w,Object...a){c+=o;n-=w;System.out.println(String.format(s,a))}}

Я принял решение Сумедха и сыграл в гольф. Я хотел поместить это в комментарии, но моей репутации недостаточно :(. Это на 40% меньше, я думаю, что это должно быть по крайней мере разделено. Хотя все еще далеко от первого, хотя ...

Вот негольфированный:

    class X{
    int n,c=0,t=0;
    public void static main(String[] a){
        n=Integer.parseInt(a[0]);
        String s,b,f,k,m,u;
        b="5L";
        s="3L";
        k="tank";
        u="Fill %s jug\n5L: %d, 3L: %d, T: %d";
        m="\nPour from %s jug into %s\n5L: %d, 3L: %d, T: %d";
        f=u+m;
        for(;n>4;)z(f,2,5,b,5,0,t,b,k,0,0,t+=5);
        while(n!=0)
        {
            if(n==1)z(f+f+m,5,1,s,0,3,t,s,b,3,0,t,s,3,3,t,s,b,5,1,t,s,k,5,0,t+1);
            if(n==3)z(f,2,3,s,0,3,t,s,k,0,0,t+3); 
            z(f+m,3,2,b,5,0,t,b,s,2,3,t,b,k,0,3,t+=2);
            if(n==2)z("Empty 3L jug\n5L: 0, 3L: 0,T: %d",1,0,t);
        }
        z("Volume measured out in %d turns",0,0,c);
    }
    void z(String s,int o, int w,Object... a){
        c+=o;
        n-=w;
        System.out.println(String.format(s,a));
    }
}

NB: работает только при первом запуске. Перезапустите его, и результат будет неправильным (из-за глобальной переменной).

Следующая версия безопасна, но мы теряем 2 символа с 610 до 612:

    class X{
    int n,c,t;
    public void static main(String[] a){
        n=Integer.parseInt(a[0]);
        String s,b,f,k,m,u;
        t=c=0;
        b="5L";
        s="3L";
        k="tank";
        u="Fill %s jug\n5L: %d, 3L: %d, T: %d";
        m="\nPour from %s jug into %s\n5L: %d, 3L: %d, T: %d";
        f=u+m;
        for(;n>4;)z(f,2,5,b,5,0,t,b,k,0,0,t+=5);
        while(n!=0)
        {
            if(n==1)z(f+f+m,5,1,s,0,3,t,s,b,3,0,t,s,3,3,t,s,b,5,1,t,s,k,5,0,t+1);
            if(n==3)z(f,2,3,s,0,3,t,s,k,0,0,t+3); 
            z(f+m,3,2,b,5,0,t,b,s,2,3,t,b,k,0,3,t+=2);
            if(n==2)z("Empty 3L jug\n5L: 0, 3L: 0,T: %d",1,0,t);
        }
        z("Volume measured out in %d turns",0,0,c);
    }
    void z(String s,int o, int w,Object... a){
        c+=o;
        n-=w;
        System.out.println(String.format(s,a));
    }
}

Пример вывода для N = 69:

Fill 5L jug
5L: 5, 3L: 0, T: 0
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
Fill 5L jug
5L: 5, 3L: 0, T: 5
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
Fill 5L jug
5L: 5, 3L: 0, T: 10
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 15
Fill 5L jug
5L: 5, 3L: 0, T: 15
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 20
Fill 5L jug
5L: 5, 3L: 0, T: 20
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 25
Fill 5L jug
5L: 5, 3L: 0, T: 25
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 30
Fill 5L jug
5L: 5, 3L: 0, T: 30
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 35
Fill 5L jug
5L: 5, 3L: 0, T: 35
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 40
Fill 5L jug
5L: 5, 3L: 0, T: 40
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 45
Fill 5L jug
5L: 5, 3L: 0, T: 45
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 50
Fill 5L jug
5L: 5, 3L: 0, T: 50
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 55
Fill 5L jug
5L: 5, 3L: 0, T: 55
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 60
Fill 5L jug
5L: 5, 3L: 0, T: 60
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 65
Fill 5L jug
5L: 5, 3L: 0, T: 65
Pour from 5L jug into 3L
5L: 2, 3L: 3, T: 65
Pour from 5L jug into tank
5L: 0, 3L: 3, T: 67
Empty 3L jug
5L: 0, 3L: 0,T: 67
Fill 5L jug
5L: 5, 3L: 0, T: 67
Pour from 5L jug into 3L
5L: 2, 3L: 3, T: 67
Pour from 5L jug into tank
5L: 0, 3L: 3, T: 69
Volume measured out in 33 turns
Narmer
источник
2

Ява: 984

Вот код

class X{public static void main(String[] s){int n=Integer.parseInt(s[0]);int t=0;int c=0;while(n>4){n-=5;System.out.println("Fill 5L jug\n5L: 5, 3L: 0, T: "+t+"\nPour from 5L jug into tank\n5L: 0, 3L: 0, T: "+(t+5));t+=5;c+=2;}while(n!=0){switch(n){case 1:System.out.println("Fill 3L jug\n5L: 0, 3L: 3, T: "+t+"\nPour from 3L jug into 5L jug\n5L: 3, 3L: 0, T: "+t+"\nFill 3L jug\n5L: 3, 3L: 3, T: "+t+"\nPour from 3L jug into 5L jug\n5L: 5, 3L: 1, T: "+t+"\nPour from 3L jug into tank\n5L: 5, 3L: 0, T: "+(t+1));n=0;c+=5;break;case 3:System.out.println("Fill 3L jug\n5L: 0, 3L: 3, T: "+t+"\nPour from 3L jug into tank\n5L: 0, 3L: 0, T: "+(t+3));n=0;c+=2;break;default:System.out.println("Fill 5L jug\n5L: 5, 3L: 0, T: "+t+"\nPour from 5L jug into 3L jug\n5L: 2, 3L: 3, T: "+t+"\nPour from 5L jug into tank\n5L: 0, 3L: 0, T: "+(t+2));n-=2;c+=3;t+=2;if(n==2){System.out.println("Empty 3L jug\n5L: 0, 3L: 0,T: "+t);c++;}break;}}System.out.println("Volume measured out in "+c+" turns");}}

Ввод из командной строки. например: Java X 4

Sumedh
источник
Я не могу комментировать в другом месте, поэтому я комментирую здесь. @Lego Stormtroopr, есть альтернативное оптимальное решение, где для оставшегося 4 л вы можете сделать то же самое, что и для 2 л (3 шага), затем опорожнить 3-литровый кувшин, а затем повторить для оставшихся 2 л, тем самым завершив его за 7 шагов .... это то же самое для вашего решения, где 4L делится на: 3L в бак (2 шага) и 5-шаговый метод для оставшегося 1L.
Сумед
@ Chron, ваш код работает для значений N, где N% 5 равно 1 или 4? Я не понимаю, рубин, поэтому я не мог проверить это сам ...
Сумед
здесь, например, следует взглянуть на N = 11: ideone.com/3ZDuOS Вы можете нажать правку в верхнем левом углу и изменить STDIN на другие значения, если хотите проверить.
Пол Престиж
Вау, у вас есть более оптимальное решение, чем у меня ... как вы решаете, когда прекратить 5L и использовать вместо этого 3L? Я имею в виду, что если вход 81, то вы получите до 75 л, используя 5 л, а затем используйте 3 л. если ip равен 89, то 5 л используется до 80 л, а остальные 3 л.
Сумед
Сохранить некоторые символы: main(String[]s), int n=Integer.parseInt(s[0]),t=0,c=0;, java.io.PrintStream q=System.out;. Кроме того, может быть возможно написать первый whileкак один или два символа короче for. Кроме того, ваши Stringповторяются, вы можете попытаться сохранить повторяющиеся части в переменных или создать функции, которые строят их, используя только один префаб String.
Виктор Стафуса
2

Python 2.7 - 437

Не самый короткий код, но я думаю, что это самый оптимальный способ решения этой проблемы.

Как я уже говорил в комментариях, самый оптимальный способ рассчитать это:

  1. Возьмите как можно больше кусков по 5 л divmod(amount,5). Это даст вам один из 4,3,2,1 в качестве остатка.
  2. Возьмите 3 (если возможно) от остатка.
  3. Что оставляет 1 или 2 в качестве остатка. Используйте оптимальное решение для любого из них, которое может быть заранее известно как:

    1. 1 л, 5 ступеней: 3 л -> 5 л, 3 л -> 5 л, оставляя 1 л в 3 л, 3 л (удерживая 1 л) -> бак
    2. 2 л, 3 ступени: 5 л -> 3 л, листья 2 л в 5 л, 5 л (удерживание 2 л) -> бак

Код:

j,T="%dL jug","tank"
A="\n5L: %d, 3L: %d, T: %d"
F,P="Fill "+j+A,"Pour from "+j+" into %s"+A
f,r=divmod(input(),5)
o,t=f*5,[]
for i in range(f):o+=[F%(5,5,0,5*i),P%(5,T,0,0,5*i+5)]
if r>2:o+=[F%(3,0,3,t),P%(3,T,0,0,t+3)];r-=3;t+=3
if r==2:o+=[F%(5,5,0,t),P%(5,j%3,2,3,t),P%(5,T,0,3,t+2)]
if r==1:o+=[F%(3,0,3,t),P%(3,j%5,3,0,t),F%(3,3,3,t),P%(3,j%5,5,1,t),P%(3,T,5,0,t+1)]
print"\n".join(o),'\n',"Volume measured out in %d turns"%len(o)

И вывод на 4л за 7 шагов:

Fill 3L jug
5L: 0, 3L: 3, T: 0
Pour from 3L jug into tank
5L: 0, 3L: 0, T: 3
Fill 3L jug
5L: 0, 3L: 3, T: 3
Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 3
Fill 3L jug
5L: 3, 3L: 3, T: 3
Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 3
Pour from 3L jug into tank
5L: 5, 3L: 0, T: 4
Volume measured out in 7 turns

источник
Вы назначаете int для o, а затем пытаетесь добавить список. Я думаю, что вы хотели назначить o, t = [], f * 5 в строке 5.
psion5mx
1
Потеряйте операторы for, range и if, и вы можете уменьшить его до 399 на одной строке: j, T = "% dL jug", "tank"; A = "\ n5L:% d, 3L:% d, T :% d "; F, P =" Заполнить "+ j + A," Вылить из "+ j +" в% s "+ A; f, r = divmod (input (), 5); t, o = f * 5, []; о = [F% (5,5,0,5 * я), Р% (5, Т, 0,0,5 * I + 5)] * е + [F% (3,0, 3, т), Р% (3, Т, 0,0, T + 3)] * (г> 2) + [F% (5,5,0, т), Р% (5, J% 3, 2,3, т), Р% (5, Т, 0,3, T + 2)] * (г == 2) + [F% (3,0,3, т), Р% (3, J % 5,3,0, т), F% (3,3,3, т), Р% (3, J% 5,5,1, т), Р% (3, Т, 5,0, т +1)] * (r в [1,4]); выведите «\ n» .join (o), «\ nОбъем измеряется в% d оборотов»% len (o)
psion5mx
1
Впечатляющие манипуляции ... @ psion5mx Я не думал, что такое программирование возможно на Python? Нет диапазона, рекурсии или если заявления?
WallyWest
Сила списков. Умножение списка на целое число заменяет «циклы». Умножение на логическое значение заменяет «если».
psion5mx
Кроме того - мне удалось сократить его до одного пробела (вне кавычек), но я мог устранить все пробелы за счет символа, заменив (r в [1,4]) на (r% 5in [1,4] ) в таком случае.
psion5mx
2

Smalltalk (Smalltalk / X), 568 560 516

вход в п:

    T:=j:=J:=c:=0.m:={'Pour from'.' into'.' 3L jug'.' 5L jug'.[j:=j+3.'Fill'].[J:=J+5.'Fill'].[t:=j.j:=0.''].[t:=J.J:=0.''].[r:=j min:5-J.j:=j-r.J:=J+r.''].[r:=J min:3-j.J:=J-r.j:=j+r.''].[T:=T+t.' into tank'].[c:=c+1.'\5L: %1 3L: %2 T: %3\'bindWith:J with:j with:T].['Volume measured out in %1 turns'bindWith:c]}.[n>=0]whileTrue:[s:=n.n:=0.(s caseOf:{0->[n:=-1.'<'].1->'42;02813;42;02813;062:;'.2->'53;03912;073:;'.3->'42;062:;'.4->[n:=1.'42;062:;']}otherwise:[n:=s-5.'53;073:;'])do:[:c|(m at:c-$/)value withCRs print]]

мальчик, это определенно самая запутанная программа, которую я когда-либо писал ...

Изменить: Некоторые другие Smalltalks могут не разрешать автоматически объявленные переменные рабочего пространства, и вам придется добавлять объявления. Также bindWith: может быть другим (expandWith: '<p>').

Пример вывода для n = 17:

Fill 5L jug 
5L: 5, 3L: 0, T: 0
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
Fill 5L jug 
5L: 5, 3L: 0, T: 5
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
Fill 5L jug 
5L: 5, 3L: 0, T: 10
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 15
Fill 5L jug 
5L: 5, 3L: 0, T: 15
Pour from 5L jug into 3L jug 
5L: 2, 3L: 3, T: 15
Pour from 5L jug into tank
5L: 0, 3L: 3, T: 17
Volume measured out in 9 turns
blabla999
источник
2

С 567 609

#define r printf
#define l r("5L: %d, 3L: %d, T: %d\n", a, b, T);
#define j(x,y,z,w) r("%d) "#x" %dL jug\n", i++, y),z=w,l
#define e j(Empty,3,b,0)
#define f j(Fill,5,a,5)
#define g j(Fill,3,b,3)
#define o(x,y,z,w) r("%d) Pour from %dL jug into "x"\n", i++, y,z),w;l
#define t(x,y) T+=x,o("tank",y,0,x=0)
#define p(x) o("%dL jug",5,3,(a-=x,b+=x))
int N,T,i;q(x){int a=0,b=0;switch(x){case 5:f t(a,5) break;case 3:g t(b,3) break;case 1:case 2:case 4:f if(x-2){e p(2)f p(1)if(x-4){e p(3)}}t(a,5)}N-=x;}main(){T=0,i=1,scanf("%d",&N);while(N>5)q((N-6)&&(N-9)?5:3);q(N);r("Volume measured out in %d turns",i-1);}

предыдущая недействительная версия:

#define r printf
#define l r("5L: %d, 3L: %d, T: %d\n", a, b, T);
#define j(x,y,z,w) r("%d) "#x" %dL jug\n", i++, y),z=w,l
#define e j(Empty,3,b,0)
#define f j(Fill,5,a,5)
#define g j(Fill,3,b,3)
#define o(x,y,z,w) r("%d) Pour from %dL jug into "x"\n", i++, y,z),w;l
#define t o("tank",5,0,a=0)
#define p(x) o("%dL jug",5,3,(a-=x,b+=x))
int N,T,i;q(x){int a=0,b=0;switch(x){case 5:f t break;case 3:g t break;case 1:case 2:case 4:f if(x-2){e p(2)f p(1)if(x-4){e p(3)}}t}N-=x;}main(){T=0,i=1,scanf("%d",&N);while(N>5)q(5);q(N);r("Volume measured out in %d turns",i-1);}

и вот код дегольфеда:

#define r printf
#define l r("5L: %d, 3L: %d, T: %d\n", a, b, T);
#define j(x,y,z,w) r("%d) "#x" %dL jug\n", i++, y),z=w,l
#define e j(Empty,3,b,0)
#define f j(Fill,5,a,5)
#define g j(Fill,3,b,3)
#define o(x,y,z,w) r("%d) Pour from %dL jug into "x"\n", i++, y,z),w;l
#define t o("tank",5,0,a=0)
#define p(x) o("%dL jug",5,3,(a-=x,b+=x))
int N,T,i;
q(x)
{
    int a=0,b=0;
    switch(x)
    {
        case 5:
            f
            t 
            break;
        case 3:
            g
            t
            break;
        case 1:
        case 2:
        case 4:
            f
            if(x-2)
            {
                e
                p(2)
                f
                p(1)
                if(x-4)
                {
                    e
                    p(3)
                }
            }
            t
    }
    N-=x;
}
main()
{
    T=0,i=1,scanf("%d",&N);
    while(N&gt;
    5)q(5);
    q(N);
    r("Volume measured out in %d turns",i-1);
}
VX
источник
Это не дает оптимального решения для 9 (8 ходов, должно быть 6 - заполните и опорожните 3L 3 раза).
Коминтерн
Также не работает вообще для ввода 1.
Коминтерн
Не работает на 1? Жаль ... Но
достойное
да, есть некоторые ошибки, и решение не всегда оптимально. но он составляет 1 л за 8 шагов ...
VX
Пара советов по гольфу - Вы можете сэкономить 6 байтов, заменив int N, T, i; с N, T, i, a, b; и int a = 0, b = 0; с = b = 0; Вы также получите 3 байта, добавив (к вашему определению PRINTF Я думаю , что самый большой прирост будет сокращение оператора коммутатора на вложенной тройным , хотя -. Заявления случае и перерыв действительно складывают.
Коминтерн
2

C ( 480 465 байт)

#define P printf(
#define O(x) P"%d) Pour from %dL jug into "x"\n"
#define S P"5L: %d, 3L: %d, T: %d\n",F,H,g);}
F,H,s,g,x;l(j){P"%d) Fill %dL jug\n",++s,j);St(j,o,m){O("%dL jug"),++s,j,(j^5)?5:3);Se(j,i){O("tank"),++s,j);Smain(){scanf("%d",&x);while(x>4){x-=5;l(F=5);g+=5;e(5,F=0);}while(x>2){x-=3;l(H=3);g+=3;e(3,H=0);}(x^2)?(x^1)?0:(l(H=3),t(3,H=0,F=3),l(H=3),t(3,H=1,F=5),g++,e(3,H=0)):(l(F=5),t(5,F=2,H=3),g+=2,e(5,F=0));P"Volume measured out in %d turns",s);}

Оптимальная версия (добавляет 10 байт)

#define P printf(
#define O(x) P"%d) Pour from %dL jug into "x"\n"
#define S P"5L: %d, 3L: %d, T: %d\n",F,H,g);}
F,H,s,g,x;l(j){P"%d) Fill %dL jug\n",++s,j);St(j,o,m){O("%dL jug"),++s,j,(j^5)?5:3);Se(j,i){O("tank"),++s,j);Smain(){scanf("%d",&x);while(x>4&&x^6&&x^9){x-=5;l(F=5);g+=5;e(5,F=0);}while(x>2){x-=3;l(H=3);g+=3;e(3,H=0);}(x^2)?(x^1)?0:(l(H=3),t(3,H=0,F=3),l(H=3),t(3,H=1,F=5),g++,e(3,H=0)):(l(F=5),t(5,F=2,H=3),g+=2,e(5,F=0));P"Volume measured out in %d turns",s);}

Скорее всего, здесь будет больше игры в гольф - функции вывода убивали меня. Это должно дать оптимальное решение (наименьшее количество шагов). Подобно другому коду, он заполняет и опорожняет кувшины объемом 5 л, пока не опустится ниже 5, а затем переключится на кувшины объемом 3 л. Он проверяет 2 особых случая (6 и 9) и, если находит, переключается на кувшины 3 л. Инструкции по получению 1л и 2л жестко запрограммированы.

Более читаемая версия:

#define P printf(
#define O(x) P"%d) Pour from %dL jug into "x"\n"
#define S P"5L: %d, 3L: %d, T: %d\n",F,H,g);}
F,H,s,g,x;
l(j)
{
    P"%d) Fill %dL jug\n",++s,j);S

t(j,o,m)
{
    O("%dL jug"),++s,j,(j^5)?5:3);S

e(j,i)
{
    O("tank"),++s,j);S

main()
{
    scanf("%d",&x);
    //while(x>4&&x^6&&x^9)     <--optimal version
    while(x>4)
    {
        x-=5;l(F=5);g+=5;e(5,F=0);
    }
    while(x>2)
    {
        x-=3;l(H=3);g+=3;e(3,H=0);
    }
    (x^2)?
        (x^1)?  
            0
             :
            (l(H=3),t(3,H=0,F=3),l(H=3),t(3,H=1,F=5),g++,e(3,H=0))
             :(l(F=5),t(5,F=2,H=3),g+=2,e(5,F=0));
    P"Volume measured out in %d turns",s);
}

Редактирование:

  • Удалено 10 байтов, которые дали оптимальную производительность для оцененной версии на основе разъяснения ОП.
  • Побрей 5 байтов, преобразовав функцию в определение.

Тестовый вывод для n = 11 (оптимальный вариант):

11
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
5) Fill 3L jug
5L: 0, 3L: 3, T: 8
6) Pour from 3L jug into tank
5L: 0, 3L: 0, T: 11
Volume measured out in 6 turns
Коминтерн
источник
Почему вы не считаете 11 как особый случай? Что ты делаешь для 14? Одна пятая, три тройка (8) будет бить две пятерки и составлять остальные четыре литра (чего нельзя сделать за четыре хода).
Билл Вуджер
11 и 14 включают особые случаи. После того, как вы вычли первые 5L, они оставляют 6 и 9 соответственно, и они обрабатываются особыми случаями. 9 - наибольшее число, которое можно сделать за меньшее количество шагов, используя только кувшин 3 л. Ввод 14 дает 8 ступенчатое решение, выход для 11 выше.
Коминтерн
2

T-SQL (2012): 794 689 580

Вдохновлен ответом @ Jonathan-Van-Matre 's T-SQL в сочетании с алгоритмом @ Lego-Stormtroopr . Я хотел сделать это, потому что я наслаждался 99 бутылками пива .

Я пытался держать окно (OVER ) как минимум в предпочтениях математических / bool-функций.

SQLFiddle здесь .

WITH n AS(SELECT 11 n UNION ALL SELECT n-IIF(n>4,5,3)FROM n WHERE n>2)SELECT n, a,LEN(a)L,i=IDENTITY(INT,1,1),'L jug'j INTO #t FROM n JOIN(VALUES(3303),(33900),(5550),(55900),(2550),(259323),(25903),(1303),(139530),(1333),(139551),(13950))x(a)ON RIGHT(LEFT(12335,n),1)=LEFT(a,1)ORDER BY n DESC SELECT LTRIM(i)+') '+REPLACE(IIF(L=4,'Fill ','Pour ')+RIGHT(a/100,L-3),9,j+' into ')+IIF(L=5,'tank',j)  +'
5L: '+LTRIM((A%100)/10)+', 3L: '+LTRIM(A%10)+', T: '+LTRIM(SUM(IIF(L=5,LEFT(a,1),0))OVER(ORDER BY i))FROM #t UNION SELECT 'Volume measured out in ' +LTRIM(MAX(i))+' turns'FROM #t

Входные данные: 11

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 5L jug
5L: 5, 3L: 0, T: 5
4) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
5) Fill 3L jug
5L: 0, 3L: 3, T: 10
6) Pour from 3L jug into
5L jug 5L: 0, 3L: 3, T: 10
7) Fill 3L jug
5L: 3, 3L: 3, T: 10
8) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 10
9) Pour from 3L jug into tank
5L: 5, 3L: 0, T: 11
Volume measured out in 9 turns

Человек читаемый:

WITH n AS(
  SELECT 11 n
    UNION ALL
  SELECT n-IIF(n>4,5,3)
  FROM n
  WHERE n>2
)
SELECT n, a,LEN(a) L, i = IDENTITY(INT,1,1), 'L jug'j
INTO #t
FROM n
JOIN(VALUES
     (3303),(33900),
     (5550),(55900),
     (2550),(259323),(25903),
     (1303),(139530),(1333),(139551),(13950)
    )x(a)
ON RIGHT(LEFT(12335,n),1) = LEFT(a,1)
ORDER BY n DESC

 SELECT LTRIM(i)+') '
  + REPLACE(IIF(L=4,'Fill ','Pour ')
  + RIGHT(a/100,L-3),9,j+' into ')+IIF(L=5,'tank',j)
  +'
5L: ' + LTRIM((A%100)/10) + ', 3L: ' + LTRIM(A%10) + ', T: '
  + LTRIM(SUM(IIF(L=5,LEFT(a,1),0))OVER(ORDER BY i)) FROM #t
UNION ALL
 SELECT 'Volume measured out in ' +LTRIM(MAX(i))+' turns'FROM #t
 DROP TABLE #t
comfortablydrei
источник
У вас есть пример вывода?
Билл Вуджер,
@BillWoodger добавлен выход дляinput = 8
comfortablydrei
Благодарю. 8 довольно легко. Один к 11 дает хороший толчок к коду :-) Я голосую, так что не возвращайся и не говори мне, что это не работает.
Билл Вуджер,
@ Билл Спасибо. Изменено наinput = 11
комфортноDrei
@comforblydrei Удивительные вещи с использованием T-SQL ... Взяв страницу из книги Джонатона ...
WallyWest
1

Python 3 (417 символов)

P=print
D=divmod
N=['3L jug','5L jug','tank',0]
M=999
R=[0,0,0,M]
F=[3,5,M,M]
def o(a,b):k=a==3;P(['Pour from %s into %s','Empty %s','Fill %s'][k*2+(b==3)]%[(N[a],N[b]),(N[b])][k]);d=min(R[a],F[b]-R[b]);R[a]-=d;R[b]+=d;P('5L:',R[1],'3L:',R[0],'T:',R[2]);N[3]+=1
k,r=D(int(input()),5)
for i in'0'*k:o(3,1);o(1,2)
for x in['','c1c12','d46','c2','d434d46'][r]:o(*D(int(x,16),4))
P('Volume measured out in',N[3],'turns')

Разъяснения

Обратите внимание, что у нас есть 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)

17
Fill 5L jug
5L: 5 3L: 0 T: 0
Pour from 5L jug into tank
5L: 0 3L: 0 T: 5
Fill 5L jug
5L: 5 3L: 0 T: 5
Pour from 5L jug into tank
5L: 0 3L: 0 T: 10
Fill 5L jug
5L: 5 3L: 0 T: 10
Pour from 5L jug into tank
5L: 0 3L: 0 T: 15
Fill 5L jug
5L: 5 3L: 0 T: 15
Pour from 5L jug into 3L jug
5L: 2 3L: 3 T: 15
Pour from 5L jug into tank
5L: 0 3L: 3 T: 17
Volume measured out in 9 turns
луч
источник
1

COBOL (IBM Enterprise COBOL) 192 строки по 72 символа

Это подтверждение концепции для вопроса и начало для Golf-COBOL :-)

Вопрос требует самого быстрого. Итак, реализуем параллелизм. Даже один человек может сразу наполнить один кувшин объемом 3 л и один кувшин объемом 5 л.

Просто разделите ввод на восемь, оставив остаток. Сделайте несколько быстрых 5L / 3L наполнений до количества раз, сколько восемь подгонок, затем разберитесь с оставшимся количеством от одного до семи литров.

Самый интересный из оставшихся - на четыре литра. Делая это как один литр плюс три литра, выливает намного меньше воды, только 18 литров против 23 для других возможностей.

Кодекс (рабочий)

   ID DIVISION
   PROGRAM-ID
   DATA DIVISION
   WORKING-STORAGE SECTION
   1.
   88 g1 VALUE ' '.
   2  PIC X
   88 H VALUE 'F'.
   88 I VALUE 'E'.
   88 J VALUE 'T'.
   2 PIC X
   88 K VALUE 'F'.
   88 L VALUE 'E'.
   88 M VALUE 'T'.
   1 R
   2 A1 PIC 999
   2 B PIC 99
   2 C PIC 9
   1 E
   2 e2 PIC X(120) VALUE "  ) Fill both jugs"
   2 e3 PIC X(120)
   88 O VALUE "5L: 0, 3L: 0, T: 000".
   2 e4 PIC X(120) VALUE "  ) Empty both jugs"
   2 e5 PIC X(120)
   2 e1 occurs 32 depending on p pic x(240)
   2 e6 pic x(99)
   1 F PIC 999 VALUE 0
   1 P PIC 99 VALUE 0
   1 P1 PIC 99
   PROCEDURE DIVISION
   ACCEPT A1
   DIVIDE A1 BY 8 GIVING B REMAINDER C
   set o to true
   move e3 to e5
   move 5 to e3(5:1)
   move 3 to e3(12:1)
   PERFORM D1 B TIMES
   EVALUATE C
   WHEN 1
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 2
   MOVE ZERO TO R
   SET H TO TRUE
   PERFORM N
   SET J TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   WHEN 3
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 4
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 5
   MOVE ZERO TO R
   SET H TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   WHEN 6
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 7
   MOVE ZERO TO R
   SET H TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   SET H TO TRUE
   PERFORM N
   SET J TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   END-EVALUATE
   string "Volume measured out in " delimited size P " turns"
   delimited size into e6
   if  e6(24:1) = 0
   move e6(25:) to e6 (24:)
   end-if
   move p to p1
   perform d2 p times
   DISPLAY E(481:)
   GOBACK
   D1
   ADD 1 TO P
   MOVE P TO E(1:2)
   move e2 to e1(p)
   move e3 to e1(p)(121:)
   ADD 1 TO P
   MOVE P TO E(241:2)
   ADD 8 TO F
   MOVE F TO E(378:3)
   move e4 to e1(p)
   move e5 to e1(p)(121:)
   MOVE F TO E(138:3)
   N
   ADD 1 TO P
   SET O TO TRUE
   EVALUATE TRUE
   WHEN K

   MOVE 3 TO B
   string p delimited size ") Fill 3L jug" delimited by size
   into e1(p)
   WHEN M
   COMPUTE C = C + B
   IF  C > 5
   COMPUTE B = C - 5
   MOVE 5 TO C
   ELSE
   MOVE 0 TO B
   END-IF
   string  P delimited size ") Pour from 3L jug into 5L jug"
   delimited size into e1(p)
   WHEN L
   ADD B TO F
   MOVE 0 TO B
   string  P delimited size ") Empty 3L jug into tank"
   delimited size into e1(p)
   END-EVALUATE
   EVALUATE TRUE
   WHEN H
   MOVE 5 TO C
   string  P delimited size ") Fill 5L jug"
   delimited size into e1(p)
   WHEN J
   COMPUTE B = C + B
   IF  B > 3
   COMPUTE C = B - 3
   MOVE 3 TO B
   ELSE
   MOVE 0 TO C
   END-IF
   string  P delimited size ") Pour from 5L jug into 3L jug"
   delimited size into e1(p)
   WHEN I
   ADD C TO F
   MOVE 0 TO C
   string  P delimited size ") Empty 5L jug into tank"
   delimited size into e1(p)
   END-EVALUATE
   string  "5L: " delimited size
       C delimited size ", 3L: " delimited size B(2:)
   ", T: " delimited size F delimited size
   into e1(p)(121:)
   SET g1 TO TRUE
   d2
   perform d3 2 times
   if  e1(p1)(1:1) = 0
   move e1(p1)(2:) to e1(p1)(1:120)
   end-if
   subtract 1 from p1
   d3
   if  e1(p1)(138:1) = 0
   move e1(p1)(139:) to e1(p1)(138:)
   end-if

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

Ни одна из диагностик не указывает на какое-либо влияние на объектный код. Таким образом, несмотря на то, что RC = 8 с перебоями, я знаю, что объект будет в порядке, поэтому связал его и запустил.

Вот выходы от одного до восьми литров. После этого все результаты могут быть интуитивно понятны. 17 и 100 включены в качестве примеров параллелизма.

Еще многое можно сделать, чтобы сжать программу в символах, прежде всего важен правильный вывод. Подсчет символов, когда они находятся на линиях фиксированной длины, это совсем другое дело.

Пример вывода:

1) Fill 3L jug                 
5L: 0, 3L: 3, T: 0             
2) Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 0             
3) Fill 3L jug                 
5L: 3, 3L: 3, T: 0             
4) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 0             
5) Empty 3L jug into tank      
5L: 5, 3L: 0, T: 1             
Volume measured out in 5 turns 

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 5L jug into tank      
5L: 0, 3L: 3, T: 2             
Volume measured out in 3 turns

1) Fill 3L jug                 
5L: 0, 3L: 3, T: 0             
2) Empty 3L jug into tank      
5L: 0, 3L: 0, T: 3             
Volume measured out in 2 turns 

1) Fill 3L jug                 
5L: 0, 3L: 3, T: 0             
2) Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 0             
3) Fill 3L jug                 
5L: 3, 3L: 3, T: 0             
4) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 0             
5) Empty 3L jug into tank      
5L: 5, 3L: 0, T: 1             
6) Fill 3L jug                 
5L: 5, 3L: 3, T: 1             
7) Empty 3L jug into tank      
5L: 5, 3L: 0, T: 4             
Volume measured out in 7 turns 

1) Fill 5L jug                
5L: 5, 3L: 0, T: 0            
2) Empty 5L jug into tank     
5L: 0, 3L: 0, T: 5            
Volume measured out in 2 turns

1) Fill 3L jug                 
5L: 0, 3L: 3, T: 0             
2) Empty 3L jug into tank      
5L: 0, 3L: 0, T: 3             
3) Fill 3L jug                 
5L: 0, 3L: 3, T: 3             
4) Empty 3L jug into tank      
5L: 0, 3L: 0, T: 6             
Volume measured out in 4 turns 

1) Fill 5L jug                  
5L: 5, 3L: 0, T: 0              
2) Empty 5L jug into tank       
5L: 0, 3L: 0, T: 5              
3) Fill 5L jug                  
5L: 5, 3L: 0, T: 5              
4) Pour from 5L jug into 3L jug 
5L: 2, 3L: 3, T: 5              
5) Empty 5L jug into tank       
5L: 0, 3L: 3, T: 7              
Volume measured out in 5 turns 



1) Fill both jugs               
5L: 5, 3L: 3, T: 0              
2) Empty both jugs              
5L: 0, 3L: 0, T: 8              
Volume measured out in 2 turns  

1) Fill both jugs               
5L: 5, 3L: 3, T: 0              
2) Empty both jugs              
5L: 0, 3L: 0, T: 8              
3) Fill both jugs               
5L: 5, 3L: 3, T: 8              
4) Empty both jugs              
5L: 0, 3L: 0, T: 16             
5) Fill 3L jug                  
5L: 0, 3L: 3, T: 16             
6) Pour from 3L jug into 5L jug 
5L: 3, 3L: 0, T: 16             
7) Fill 3L jug                  
5L: 3, 3L: 3, T: 16             
8) Pour from 3L jug into 5L jug 
5L: 5, 3L: 1, T: 16             
9) Empty 3L jug into tank       
5L: 5, 3L: 0, T: 17             
Volume measured out in 9 turns  



1) Fill both jugs  
5L: 5, 3L: 3, T: 0 
2) Empty both jugs 
5L: 0, 3L: 0, T: 8 
3) Fill both jugs  
5L: 5, 3L: 3, T: 8 
4) Empty both jugs 
5L: 0, 3L: 0, T: 16
5) Fill both jugs  
5L: 5, 3L: 3, T: 16
6) Empty both jugs 
5L: 0, 3L: 0, T: 24
7) Fill both jugs  
5L: 5, 3L: 3, T: 24
8) Empty both jugs 
5L: 0, 3L: 0, T: 32
9) Fill both jugs  
5L: 5, 3L: 3, T: 32
10) Empty both jugs
5L: 0, 3L: 0, T: 40
11) Fill both jugs 
5L: 5, 3L: 3, T: 40
12) Empty both jugs
5L: 0, 3L: 0, T: 48
13) Fill both jugs 
5L: 5, 3L: 3, T: 48
14) Empty both jugs
5L: 0, 3L: 0, T: 56
15) Fill both jugs 
5L: 5, 3L: 3, T: 56
16) Empty both jugs
5L: 0, 3L: 0, T: 64
17) Fill both jugs 
5L: 5, 3L: 3, T: 64
18) Empty both jugs
5L: 0, 3L: 0, T: 72
19) Fill both jugs               
5L: 5, 3L: 3, T: 72              
20) Empty both jugs              
5L: 0, 3L: 0, T: 80              
21) Fill both jugs               
5L: 5, 3L: 3, T: 80              
22) Empty both jugs              
5L: 0, 3L: 0, T: 88              
23) Fill both jugs               
5L: 5, 3L: 3, T: 88              
24) Empty both jugs              
5L: 0, 3L: 0, T: 96              
25) Fill 3L jug                  
5L: 0, 3L: 3, T: 96              
26) Pour from 3L jug into 5L jug 
5L: 3, 3L: 0, T: 96              
27) Fill 3L jug                  
5L: 3, 3L: 3, T: 96              
28) Pour from 3L jug into 5L jug 
5L: 5, 3L: 1, T: 96              
29) Empty 3L jug into tank       
5L: 5, 3L: 0, T: 97              
30) Fill 3L jug                  
5L: 5, 3L: 3, T: 97              
31) Empty 3L jug into tank       
5L: 5, 3L: 0, T: 100             
Volume measured out in 31 turns 
Билл Вуджер
источник
Восхитительный подход, @BillWoodger; Я, однако, не установил команду «заполнить оба кувшина» в доступных инструкциях ... замечательная работа и поддержка а) использования COBOL, б) следования по самому быстрому маршруту метода .
WallyWest
1
@WallWest Спасибо. Если я думаю, что бизнес-спецификацию можно улучшить, я всегда так делаю :-). Мне также не нужно было «пусто в фонтан», поэтому два новых и два не использовались - двойной провал!
Билл Вуджер