Vous avez peut-être vu celui-ci dans Die Hard: With a Vengeance ... Cette question est basée sur le célèbre Jug Puzzle de 3 et 5 litres, mais avec une inclinaison légèrement différente.

Montez un code qui, lorsqu'il est donné un entier entre 1 et 100, vous fournira les instructions les plus rapides pour mesurer dans un réservoir, le nombre correspondant de litres d'eau d'une fontaine, en utilisant un pot de 3 litres et un pot de 5 litres.

Il n'y a pas de gradations sur les deux cruches; la fontaine est abondante en eau et le réservoir est censé être vidé au début de chaque exécution du code.

Vous ne pouvez pas accéder à l'eau du réservoir une fois qu'elle entre dans le réservoir.

Le format d'exécution est le suivant:

Contribution:

4 par exemple.

Production

Sortez chaque étape numérotée, comme indiqué, suivi d'un décompte des volumes du pichet 5L, du pichet 3L et du réservoir. Format de comptage également indiqué ci-dessous. Le nombre d'étapes doit également être sorti à la fin des étapes.

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

Exemple 2

Contribution: 8

Production:

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

Conventions

1. Fill xL jug - remplit la cruche associée vers le haut depuis la fontaine
2. Empty xL jug - vide le contenu de la cruche associée dans la fontaine
3. Pour from xL jug into yL jug - Verse le contenu de la verseuse xL dans la verseuse yL
4. Pour from xL jug into tank - Verse le contenu du pichet xL dans le réservoir

Le code le plus court gagne.

Rubis, 407 376 365 331 324 323

Cela devient un peu difficile à lire ...

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"

Prend entrée sur STDIN. Exemple d'exécution pour 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

T-SQL 2012: 1410 1302

Une autre tentative quixotique à une question dans SQL, mais celle-ci a offert une occasion agréable de jouer avec certaines des nouvelles options de fonction de fenêtre dans la version 2012. En outre, il exploite les CTE récursifs, qui ne sont peut-être pas impressionnants dans la plupart des langages de programmation, mais la récursivité en SQL, c'est comme passer du cheval et du buggy à une Ferrari.

Le moteur au cœur de ceci est dans les lignes 5-12, qui utilise un CTE récursif et une fonction de fenêtre pour construire un tableau de la plupart des nombres nécessaires pour résoudre le problème. Notons en particulier le test pour 3, 4, 6 ou 9, qui assure une approche optimale de la solution par 3s à partir de ces nombres. (Techniquement, c'est une égalité pour 4 entre l'approche 3-1 et le 2-2, mais le faire de cette façon m'a fait jouer beaucoup de personnages.) Ensuite, il est simple de se joindre à une table de recherche des étapes optimales pour différents des morceaux du problème et utiliser une autre fonction de fenêtre pour numéroter correctement les étapes.

Si vous ne disposez pas de MS SQL, jouez avec lui sur 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

Résultats pour l'entrée 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 

Éditer:

Amélioré le score décent par

• éliminer un +5 inutile dans la première ligne du CTE, et la clause WHERE qu'elle nécessitait
• en alignant les tables VALUES, économisant des instructions DECLARE coûteuses
• n'oubliez pas de convertir cette fois les CRLF à double octet de Windows en style Unix.

Javascript: 481

Première tentative de golf, conseils appréciés

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

Il dérange certains chiffres car il ne vérifie pas s'il vaut mieux en verser 3 ou 5, exemple: 9 donne 9 tours au lieu de 6, je pourrais le réparer plus tard

Collez-le dans la console

De 553 à 481 grâce à @WallyWest

Java, 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))}}

J'ai pris la solution de Sumedh et l' . Je voulais le mettre dans les commentaires mais ma réputation ne suffit pas :(. C'est un 40% de moins, je pense qu'il faudrait au moins le partager. Encore loin d'être le premier quand même ...

Voici non golfé:

    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: cela ne fonctionne que sur la première manche. Réexécutez-le et le résultat sera erroné (en raison d'une variable globale).

La version suivante est sûre, mais nous perdons 2 caractères, passant de 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));
    }
}

Exemple de sortie pour 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

Java: 984

Voici le code

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

L'entrée provient de la ligne de commande. par exemple: java X 4

Python 2.7 - 437

Ce n'est pas le code le plus court, mais je pense que c'est la façon la plus optimale de résoudre ce problème.

Comme je l'ai indiqué dans les commentaires, la façon la plus optimale de calculer cela:

1. Prenez autant de morceaux de 5L que possible - divmod(amount,5). Cela vous donnera l'un des 4,3,2,1 comme reste.
2. Prenez 3 (si possible) du reste.

3. Ce qui laisse 1 ou 2 comme reste. Utilisez la solution optimale pour l'un ou l'autre qui peut être connue à l'avance comme:

   1. 1L, 5 étapes: 3L -> 5L, 3L -> 5L, laissant 1L dans le 3L, 3L (en tenant 1L) -> réservoir
   2. 2L, 3 étapes: 5L -> 3L, laisse 2L dans le 5L, 5L (tenant 2L) -> réservoir

Le code:

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)

Et une sortie pour 4L en 7 étapes:

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

Smalltalk (Smalltalk / X), 568 560 516

entrée en n:

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

C'est certainement le programme le plus obscur que j'aie jamais écrit ...

Modifier: certains autres Smalltalks peuvent ne pas autoriser les variables d'espace de travail autodéclarées et vous devrez ajouter des déclarations. De plus, bindWith: peut être différent (expandWith: '<p>').

exemple de sortie pour 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

C, 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);}

version non valide précédente:

#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);}

et voici le code dégolfé:

#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);
}

C ( 480 465 octets)

#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);}

Version optimale (ajoute 10 octets)

#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);}

Probablement plus de golf à faire ici - les fonctions de sortie me tuaient. Cela devrait donner la solution optimale (le moins d'étapes). Semblable à d'autres codes ici, il remplit et vide les cruches de 5 litres jusqu'à ce qu'il atteigne moins de 5, puis passe aux cruches de 3 litres. Il teste 2 cas spéciaux (6 et 9) et s'il les trouve passe à des cruches 3L. Les instructions pour obtenir 1L et 2L sont codées en dur.

Version plus lisible:

#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);
}

Modifications:

• Suppression de 10 octets qui ont donné les performances optimales pour la version notée sur la base de la clarification de l'OP.
• Rasez 5 octets en convertissant la fonction en définition.

Sortie de test pour n = 11 (version optimale):

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

T-SQL (2012): 794 689 580

Inspiré par la réponse T-SQL de @ Jonathan-Van-Matre en combinaison avec l' algorithme de @ Lego-Stormtroopr . Je voulais le faire parce que j'aimais tellement le défi des 99 bouteilles de bière .

J'ai essayé de garder les OVERfonctions window ( ) au minimum, de préférence aux fonctions mathématiques / booléennes.

SQLFiddle est ici .

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

Contribution: 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

Lisible par l'homme:

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

Python 3 (417 caractères)

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

Expliqué

Notez que nous avons 4 objets, à savoir la cruche 3L, la cruche 5L, le réservoir et la fontaine. Les seules opérations que nous pouvons faire sont de déplacer l'eau d'un objet aà l'autre b. Voilà quelle fonctiono(a, b) fait dans mon code, il déplace l'eau et l'imprime et continue de compter.

Des trucs

• N=['3L jug','5L jug','tank',0]. Ici, j'ai besoin du dernier élément à éviter IndexError. En outre, il peut être utilisé comme variable de comptage globale, sans le globalmot clé expansif . Par exemple,N[3] += 1

• Puisque 0 <= a < 4, 0 <= b < 4dans la fonction o(a, b), nous pouvons encoder (a, b)en un chiffre hexadécimal en utilisant (a << 2) | b, et le décoder en utilisant divmod(x, 4). Avec cette astuce, les 5 solutions ( reminder=0, 1, 2, 3, 4) peuvent être encodées en tableau ['','c1c12','d46','c2','d434d46'], ce qui est un peu plus court que sa forme originale:

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

Exemple de sortie (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

COBOL (IBM Enterprise COBOL) 192 lignes de 72 caractères

Ceci est une preuve de concept pour la question, et le début d'une pour Golf-COBOL :-)

La question demande le plus rapidement. Donc, implémentez le parallélisme. Une seule personne peut facilement remplir un pot de 3 litres et un pot de 5 litres en même temps.

Divisez simplement l'entrée par huit, en laissant également le reste. Faites quelques remplissages rapides de 5L / 3L au nombre de fois où huit ajustements sont exacts, puis traitez celui qui reste jusqu'à sept litres.

Le plus intéressant du reste est pour quatre litres. Le faire en un litre plus trois litres pousse beaucoup moins d'eau, seulement 18 litres contre 23 pour les autres possibilités.

Le Code (en marche)

   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

Cela obtient un délestage absolu de messages de diagnostic pour le code démarrant au mauvais endroit et la pénurie d'arrêts complets requis.

Aucun des diagnostics n'indique d'impact sur le code objet. Donc, bien qu'il s'agisse d'un RC cassé = 8, je sais que l'objet sera OK, alors liez-le et exécutez-le.

Voici les sorties pour un à huit litres. Après cela, tous les résultats peuvent être intuitifs. 17 et 100 sont inclus comme exemples de parallélisme.

Il y a encore beaucoup à faire pour compresser le programme en caractères, la sortie correcte était la chose importante en premier. Compter les caractères lorsqu'ils sont sur des lignes de longueur fixe est une tout autre chose.

Exemple de sortie:

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