태그 보관물: puzzle-solver

puzzle-solver

3과 5 리터 주전자 퍼즐 제공하는 코드를 작성하십시오. 주전자 중 하나에

당신은 Die Hard : Vengeance와 함께 이것을 보았을 것입니다 .

1에서 100 사이의 정수가 주어지면 탱크에서 3 리터짜리 주전자와 5 리터짜리 주전자를 사용하여 분수에서 나오는 물의 리터 수를 측정하는 가장 빠른 지침을 제공하는 코드를 작성하십시오.

주전자 중 하나에 그라데이션이 없습니다. 분수대에는 물이 풍부하고 코드가 실행될 때마다 탱크가 비운 것으로 가정합니다.

탱크로 들어가면 탱크의 물에 접근 할 수 없습니다.

실행 형식은 다음과 같습니다.

입력:

4 예를 들어.

산출

그림과 같이 번호가 매겨진 각 단계를 출력 한 다음 5L 주전자, 3L 주전자 및 탱크의 부피를 집계합니다. 탈리 형식도 아래에 나와 있습니다. 단계의 끝에서도 단계 수를 출력해야합니다.

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 용기의 내용물을 탱크에 붓습니다.

가장 짧은 코드가 승리합니다.

답변

루비, 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

답변

T-SQL 2012 : 1410 1302

SQL의 질문에 대한 또 다른 빠른 시도이지만 버전 2012의 새로운 창 기능 옵션 중 일부를 재생할 수있는 즐거운 기회를 제공했습니다. 또한 재귀 CTE를 활용합니다. 이는 대부분의 프로그래밍 언어에서는 인상적이지 않지만 재귀입니다. SQL에서 말과 버기에서 페라리로 전환하는 것과 같습니다.

이 엔진의 핵심은 5-12 행에 있으며 재귀 CTE와 창 함수를 사용하여 문제를 해결하는 데 필요한 대부분의 숫자 테이블을 만듭니다. 특히 3, 4, 6 또는 9에 대한 테스트를 참고하십시오. 그러면 3에서 4까지 솔루션에 대한 최적의 접근 방식이 보장됩니다. (기술적으로는 3-1 접근 방식과 2-2 접근 방식 사이에 4를 묶는 것이지만 이런 식으로 그렇게하면 많은 캐릭터가 골프를 쳤습니다.) 그러면 다른 단계에 대한 최적의 단계를 조회 테이블에 조인하는 것이 간단합니다. 문제를 해결하고 다른 창 기능을 사용하여 단계의 번호를 올바르게 지정하십시오.

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

편집하다:

로 좋은 점수 향상을 골프

  • CTE의 첫 번째 행에서 불필요한 +5를 제거하고 필요한 WHERE 절
  • VALUES 테이블을 인라인하여 비용이 많이 드는 DECLARE 문 저장
  • 이번에는 Windows 더블 바이트 CRLF를 유닉스 스타일로 변환하는 것을 기억했습니다.

답변

자바 스크립트 : 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는 6 대신 9 회전을 제공합니다. 나중에 고칠 수 있습니다.

콘솔에 붙여 넣기

@WallyWest 덕분에 553에서 481까지

답변

자바, 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))}}

나는 Sumedh 의 해결책을 가져 갔다 를 쳤다. 나는 의견에 그것을 넣고 싶었지만 내 명성은 충분하지 않다 :

골퍼가 없습니다 :

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

주의 : 그것은 첫 번째 실행에서만 작동합니다. 다시 실행하면 전역 변수로 인해 결과가 잘못됩니다.

다음 버전은 안전하지만 610에서 612로 2 문자를 잃습니다.

    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

답변

자바 : 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

답변

파이썬 2.7-437

가장 짧은 코드는 아니지만 이것이 이것을 해결하는 가장 최적의 방법이라고 생각합니다.

주석에서 언급했듯이 이것을 계산하는 가장 최적의 방법은 다음과 같습니다.

  1. 가능한 한 많은 5L 청크를 섭취하십시오 divmod(amount,5). 그러면 나머지로 4,3,2,1 중 하나가 제공됩니다.
  2. 나머지에서 가능한 경우 3을 가져옵니다.

  3. 나머지는 1 또는 2로 남습니다. 다음과 같이 미리 알려진 최적의 솔루션을 사용하십시오.

    1. 1L, 5 단계 : 3L-> 5L, 3L-> 5L, 3L, 3L (1L 유지)-> 탱크에 1L 유지
    2. 2L, 3 단계 : 5L-> 3L, 5L, 2L에서 2L 유지-2L 유지-> 탱크

코드:

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)

그리고 7 단계로 4L 출력 :

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

답변

스몰 토크 (스몰 / X) 568 560 516

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

이건 내가 쓴 것 중 가장 난독 화 된 프로그램이다.

편집 : 다른 스몰 토크는 자동 선언 된 작업 공간 변수를 허용하지 않을 수 있으며 선언을 앞에 추가해야합니다. 또한 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