태그 보관물: stack

stack

하노이 타워 솔루션 확인 __|__ 도전 A, B,

하노이 타워가 무엇인지 모르는 경우 간단히 설명하겠습니다. 막대 3 개와 디스크 크기가 각각 다릅니다. 처음에는 모든 디스크가 정렬 된 순서대로 첫 번째 타워에 있습니다. 가장 큰 디스크는 맨 아래에 있고 가장 작은 디스크는 맨 위에 있습니다. 목표는 모든 디스크를 세 번째 막대로 가져 오는 것입니다. 쉽게 들리나요? 캐치가 있습니다. 다른 디스크보다 작은 디스크 위에 디스크를 놓을 수 없습니다. 한 번에 한 장의 디스크 만 잡고 다른 막대로 옮길 수 있으며 테이블이 아닌 막대에만 디스크를 놓을 수 있습니다.

ASCII 예제 솔루션 :

  A      B      C
  |      |      |
 _|_     |      |
__|__    |      |


  A      B      C
  |      |      |
  |      |      |
__|__   _|_     |


  A      B      C
  |      |      |
  |      |      |
  |     _|_   __|__


  A      B      C
  |      |      |
  |      |     _|_
  |      |    __|__

도전

A, B, C라는 3 개의 막대가 있습니다.

하노이의 탑을위한 솔루션을 확인하는 것이 도전입니다. 다음을 확인해야합니다.

  1. 결국 모든 n 개의 디스크는로드 C (3)에 있습니다.
  2. 특정 상태의 특정 디스크에 대해서는 그 아래에 더 작은 디스크가 없습니다.
  3. 공 막대에서 디스크를 가져 오거나 디스크를 존재하지 않는 막대로 옮기는 것과 같은 명백한 오류는 없습니다.

솔루션이 최적 일 필요는 없습니다.

입력

프로그램은 두 가지 입력을받습니다 :

  1. 디스크 수 n (정수)
  2. 수행되는 동작은 다음과 같은 튜플 세트로 구성됩니다. 당신은 그들이 표현되는 방법을 선택할 수 있습니다. 예를 들어 위의 ASCII로 그린 n = 2에 대한 솔루션을 나타내는 다음과 같은 방법이 있습니다. (나는 눈에 편하기 때문에 테스트 케이스에서 첫 번째를 사용할 것이다) :

    “A-> B; A-> C; B-> C”

    [( “A”, “B”), ( “A”, “C”), ( “B”, “C”)]

    [(1,2), (1,3), (2,3)]

    “ABACBC”

    [1,2,1,3,2,3]

산출

  • “도전”에서 찾을 수있는 조건이 유지되는 경우 진실입니다.

  • 그렇지 않으면 거짓입니다.

테스트 사례 :

참된:

n=1, "A->C"

n=1, "A->B ; B->C"

n=2, "A->B ; A->C ; B->C"

n=2, "A->C ; C->B ; A->C ; B->C"

n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"

그릇된:

@MartinEnder가 제안한 3 번째, @Joffan이 7 번째

n=1, "A->B"

n=1, "C->A"

n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=2, "A->B ; A->C ; C->B"

n=2, "A->C ; A->B ; C->B ; B->A"

n=2, "A->C ; A->C"

n=3, "A->B ; A->D; A->C ; D->C ; A->C"

n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"

n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"

n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"

이것은 코드 골프 , 가장 짧은 솔루션 승리입니다. 표준 규칙 및 허점이 적용됩니다. 배터리가 포함되어 있지 않습니다.



답변

망막 , 84 80 바이트

Martin Ender 덕분에 -5 바이트

~
 ~$'
$
ABC
{`^(.)(.*)( ~+)\1
$3$2$1
}`^(\W+)(\w)(.*)(?<=\1~+|\w)\2
$3$1$2
^AB

온라인으로 사용해보십시오!(라인 별 테스트의 경우 5 바이트 추가)

이 코드는 전체 게임을 시뮬레이트합니다.

  • 입력은 ACABCBACBABCAC~~~입니다.
    ~~~3 개의 디스크를 의미합니다.
  • 처음 네 줄은 입력을 게임 형식으로 변환합니다 ACABCBACBABCAC ~~~ ~~ ~ABC.
    처음에는 A 막대에 3 개의 디스크가 있으며 B 및 C 막대가 비어 있습니다.
  • 다음으로 두 단계를 반복합니다.
    • 다음 소스 막대를 나타내는 줄의 첫 글자를 가져갑니다. 이 막대를 찾아 마지막 디스크를 넣습니다. 글자를 제거하고 디스크를 스타크로 옮깁니다 (픽업).
      예를 들어, 첫 번째 단계 후 텍스트는 다음과 같습니다.
      ~CABCBACBABCAC ~~~ ~~ABC .
    • 두 번째 단계에서는 대상 막대를 찾아 디스크를 그곳으로 옮깁니다. 로드가 비어 있거나 상단에 더 큰 디스크가 있는지 확인합니다 ABCBACBABCAC ~~~ ~~AB ~C..
  • 마지막으로 A와 B 막대가 비어 있는지 확인합니다. 이는 모든 디스크가 C에 있음을 의미합니다 (마지막 줄에 추가 공간이 있음).

답변

망막 , 167 165 157 150 123 바이트

이것은 완전히 하나의 정규 표현식으로 해결해야 할 과제처럼 보입니다 …

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?!\3|\4)1

입력 형식이 형태의 명령어의 목록 AB다음에 n숫자를 사용 단항에서 1. 구분 기호가 없습니다. 출력이 1유효하고 0유효하지 않습니다.

온라인으로 사용해보십시오! (처음 두 문자는 줄 바꿈으로 구분 된 테스트 스위트를 활성화합니다.)

대체 솔루션, 동일한 바이트 수 :

^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?<-5>1)+$

이것은 아마도 사용하여 단축 될 수 있습니다 1, 11그리고 111대신에 A, B그리고C 하지만 나중에 조사해야합니다. 프로그램을 여러 단계로 나누는 것이 더 짧을 수도 있지만, 그 문제는 어디에 있습니까? 😉

설명

이 솔루션은 .NET의 밸런싱 그룹을 많이 사용합니다. 전체 설명 은 Stack Overflow에 대한 내 게시물을 참조하십시오 . 그러나 .NET에서 그룹을 캡처하는 것은 스택이며, 각각의 새로운 캡처는 다른 하위 문자열을 푸시하고 그러한 스택에서 다시 팝업 할 수있는 곳입니다. 이를 통해 문자열에서 다양한 수량을 계산할 수 있습니다. 이 경우 3 개의로드를 3 개의 다른 캡처 그룹으로 직접 구현하여 각 디스크를 캡처로 표시 할 수 있습니다.

막대 사이에서 디스크를 움직이기 위해 우리는 이상한 (?<A-B>...)구문을 사용합니다. 일반적으로 B스택 A에서 캡처를 팝하고 팝된 캡처와이 그룹의 시작 사이에 문자열 을 스택으로 푸시합니다 . 그래서 (?<A>a).(?<B-A>c)일치에 대한이 abc떠날 A빈과 B함께 b(반대 c). 그러나 .NET 가변 길이 룩백으로 인해 캡처 (?<A>...)(?<B-A>...)겹치기가 가능합니다. 어떤 이유로 든,이 경우 두 그룹 의 교집합 이로 밀려납니다 B. 이 답변의 그룹 균형 조정에 대한 “고급 섹션”에서이 동작을 자세히 설명했습니다 .

정규식에. 막대 A, BC그룹에 해당하는 3, 4그리고 5정규식한다. 로드를 초기화하여 시작하자 A:

^                 # Ensure that we start at the beginning of the input.
(?=               # Lookahead so that we don't actually move the cursor.
  \D*             # Skip all the instructions by matching non-digit characters.
  (               # For each 1 at the end of the input...
    (?=(?<3>1+))  # ...push the remainder of the string (including that 1)
                  # onto stack 3.
  1)+
)

따라서 입력이로 끝나는 경우 111그룹 3 /로드 A는 이제 캡처 목록 [111, 11, 1](오른쪽 상단)을 보유합니다.

코드의 다음 비트는 다음 구조를 갖습니다.

(
  (?=A...|B...|C...).
  (?=A...|B...|C...).
)+

이 루프의 각 반복은 하나의 명령을 처리합니다. 첫 번째 교대는 주어진 막대에서 디스크를 임시 그룹으로 가져오고 두 번째 교대는 해당 디스크를 다른 주어진 막대에 놓습니다. 우리는 이것이 어떻게 작동하는지 그리고 어떻게 움직일 수 있는지를 볼 것입니다.

먼저 소스로드에서 디스크를 꺼내십시오.

(?=
  A(?<1-3>.+)
|
  B(?<1-4>.+)
|
  C(?<1-5>.+)
)

이것은 위에서 설명한 이상한 그룹 교차 동작을 사용합니다. 해당 그룹을 참고 3, 4그리고 5항상의 문자열 개최 1길이 디스크의 크기에 해당하는 문자열의 끝에들. 우리는 지금 사용하는 (?<1-N>.+)스택에서 맨 디스크를 팝업 N및 경기와 함께이 문자열의 교회법을 밀어 .+스택에 1. 때문에 .+항상 반드시 전체 캡처 오프 팝 커버 N, 우리는 이것이 단순히 캡처를 이동하는 것을 알고있다.

다음으로이 디스크를 스택 1에서 두 번째 막대에 해당하는 스택 에 넣습니다.

(?=
  A.*(?!\3)(\1)
|
  B.*(?!\4)(\1)
|
  C.*(?!\5)(\1)
)

스택을 정리할 필요는 없습니다 1. 스택을 다시 사용하기 전에 새 디스크를 맨 위에 놓기 때문에 디스크를 그대로 둘 수 있습니다. 즉, (?<A-B>...)구문을 피하고 문자열을로 간단히 복사 할 수 있습니다 (\1). 이동이 유효한지 확인하기 위해 부정적 예측을 사용합니다 (?!\N). 이렇게하면 현재 디스크와 일치시키려는 위치에서 이미 스택에있는 디스크를 일치시킬 수 없습니다 N. 이것은 \N스택이 완전히 비어 있거나 b) the disc on top of stackN is larger than the one we're trying to match with\ 1` 이어서 a) 일치하지 않는 경우에만 발생할 수 있습니다 .

마지막으로, 남은 모든 것을 우리가 모든 지시와 b) 봉을 일치 한)은에게 보장되는 AB, 비어 있으므로 모든 디스크가 상으로 이동 한 것을 C.

(?!\3|\4)1

우리는 단순히 일치 하지도 \3않고 \4일치 하지도 않으며 (실제 디스크 일치 하기 때문에 두 디스크 모두 비어있는 경우에만 해당 ) 1명령을 생략하지 않도록 일치시킬 수 있는지 확인합니다.


답변

Java “only” 31127263261260 259256 바이트

저장된 39 이전 디버그 기능을 알아 차리지 인해 @Frozn에 수많은 바이트뿐만 아니라 일부 영리한 골프 트릭.

골프 버전

int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>t,s[]=new Stack[3];for(;j<3;)s[j++]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;k+=2)if((t=s[m[k+1]]).size()>0&&s[m[k]].peek()>t.peek())return 0;else t.push(s[m[k]].pop());return s[2].size()<n?0:1;}

각 단계마다 설명과 꽤 인쇄 된 스택이 담겨 있습니다.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package codegolf;

/**
 *
 * @author rohan
 */
import java.util.Arrays;
import java.util.Stack;
public class CodeGolf {
    //golfed version
    int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>[] s=new Stack[3];for(;j<3;j++)s[j]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;System.out.println(Arrays.toString(s)),k+=2)if(!s[m[k+1]].isEmpty()&&s[m[k]].peek()>s[m[k+1]].peek())return 0;else s[m[k+1]].push(s[m[k]].pop());return s[2].size()==n?1:0;}
    /** Ungolfed
        * 0 as falsy 1 as truthy
        * @param n the number of disks
        * @param m represents the zero indexed stacks in the form of [from,to,from,to]
        * @return 0 or 1 if the puzzle got solved, bad moves result in an exception
        */
    int h(int n, int[] m) {
        //declarations
        int j = 0, k = 0, i = n;
        //create the poles
        Stack<Integer>[] s = new Stack[3];
        for (; j < 3; j++) {
            s[j] = new Stack();
        }
        //set up the first tower using the "downto operator
        for (; i-- > 0;) {
            s[0].push(i);
        }
    //go through and perform all the moves
        for (; k < m.length; System.out.println(Arrays.toString(s)), k += 2) {
            if (!s[m[k + 1]].isEmpty() && s[m[k]].peek() > s[m[k + 1]].peek()) {
                return 0;//bad move
            } else {
                s[m[k + 1]].push(s[m[k]].pop());
            }
        }
        return s[2].size() == n ? 1 : 0;// check if all the disks are done
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    //test case
        System.out.println( new CodeGolf().h(3,new int[]{0,2,0,1,2,1,0,2,1,0,1,2,0,2})==1?"Good!":"Bad!");
    }

}

ungolfed 버전에는 스택이 각 단계에서 어떻게 보이는지 인쇄하는 기능이 있습니다 …

[[2, 1], [], [0]]
[[2], [1], [0]]
[[2], [1, 0], []]
[[], [1, 0], [2]]
[[0], [1], [2]]
[[0], [], [2, 1]]
[[], [], [2, 1, 0]]
Good!

답변

파이썬 2 186 167 158 135 127 115 110 102 바이트

n,m=input()
x=[range(n),[],[]]
for a,b in m:p=x[a].pop();e=x[b];e and 1/(p>e[-1]);e+=p,
if x[0]+x[1]:_

STDIN에 다음 형식으로 입력을받습니다.

(1,[(0,1),(1,2)])

즉, 디스크 수의 Python 튜플과의 튜플의 Python 목록입니다 (from_rod,to_rod). 파이썬에서와 같이 주변 괄호는 선택 사항입니다. 로드는 제로 인덱스입니다.

예를 들어이 테스트 사례는 다음과 같습니다.

n=2; "A->B ; A->C ; B->C"

다음과 같이 주어질 것입니다 :

(2,[(0,1),(0,2),(1,2)])

솔루션이 유효하면 아무것도 출력하지 않고 종료 코드 0으로 종료됩니다. 유효하지 않으면 예외를 throw하고 종료 코드 1로 종료 IndexError합니다. 존재하지 않는로드로 이동하거나 디스크를 꺼내려고하면 디스크가없는 막대 ZeroDivisionError, 디스크가 작은 디스크 위에 놓인 NameError경우 또는 끝에 첫 번째 또는 두 번째 막대에 디스크가 남아 있는 경우.

@KarlKastor 덕분에 13 바이트를 절약했습니다!

@xnor 덕분에 8 바이트가 절약되었습니다!


답변

파이썬 2.7 173 158 138 130 127 123 바이트 :

r=range;a,b=input();U=[r(a,0,-1),[],[]]
for K,J in b:U[J]+=[U[K].pop()]if U[J]<[1]or U[K]<U[J]else Y
print U[-1]==r(a,0,-1)

형식의 표준 입력을 통해 입력을 받아 각각 쉼표의 쌍을 포함하고 각각의 움직임에 대응하는 튜플들을 포함하는 배열 정수 분리로 주어진다. 예를 들어 테스트 사례는 다음과 같습니다.(<Number of Discs>,<Moves>)<Moves>

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

게시물에 주어진 것은 다음과 같이 주어질 것입니다 :

(3,[(0,2),(0,1),(2,1),(0,2),(1,0),(1,2),(0,2)])

내 프로그램에. 출력합니다 IndexError3 조건이 충족되지 않는 경우 NameError2 조건이 충족되지 않을 경우, 및 False제 1 조건이 충족되지 않은 경우. 그렇지 않으면 출력 True합니다.


답변

VBA, 234 217 213 196 바이트

Function H(N,S)
ReDim A(N)
While P<Len(S)
P=P+2:F=1*Mid(S,P-1,1):T=1*Mid(S,P,1)
E=E+(T>2):L=L+T-F
For i=1 To N
If A(i)=F Then A(i)=T:Exit For
E=E+(A(i)=T)+(i=N)
Next
Wend
H=L+9*E=2*N
End Function

이동을위한 입력 형식은 짝수의 자릿수 (012)가있는 문자열입니다. 스프레드 시트에서 호출은 = H ([디스크 수], [이동 문자열])

어레이 A는 다양한 디스크의로드 위치를 유지합니다. 이동은 단순히 “From”로드 번호가 “To”로드 번호로 처음 업데이트되는 것입니다. “To”로드 디스크가 먼저 발생하거나 “From”로드 디스크가없는 경우 잘못된 이동입니다. A의 총 “로드 값”은 L로 유지되며 2N에서 끝나야합니다. 오류는 E에서 음수로 누적됩니다.

다른 솔루션과 마찬가지로 타워에서 동일한 타워로 디스크를 “이동”하는 것은 금지되지 않습니다. 다른 6 바이트에 대해서는 금지 할 수 있습니다.

결과

첫 번째 열의 함수 결과 (마지막 n = 3의 경우 추가 막대를 사용하여 추가 한 것입니다).

TRUE    1   02
TRUE    1   0112
TRUE    2   010212
TRUE    2   02210212
TRUE    2   020121101202
TRUE    3   02012102101202
TRUE    4   010212012021010212102012010212

FALSE   1   01
FALSE   1   20
FALSE   2   02012102101202
FALSE   2   010221
FALSE   2   02012110
FALSE   2   0202
FALSE   3   0202012102101202
FALSE   3   0201210112101202
FALSE   3   02012102101221
FALSE   3   0103023212
FALSE   4   0102120120210102121020120102
FALSE   4   01010102121212

답변

PHP, 141 바이트

<?php $a=$argv;for($t=[$f=range($a[++$i],1),[],[]];($r=array_pop($t[$a[++$i]]))&&$r<(end($t[$a[++$i]])?:$r+1);)$t[$a[$i]][]=$r;echo$t[2]==$f;

명령 줄 스크립트는 높이로 입력 한 다음 일련의 배열 인덱스 (0 인덱스)를 사용합니다 (예 : 1 또는 2 높이 가장 짧은 테스트 사례의 경우 1 0 2 또는 2 0 1 0 2 1 2).
실제 경우에 대한 에코 1, 잘못된 경우에 대한 에코 없음.
2 개의 통지와 1 개의 경고를 제공하므로이를 침묵시키는 환경에서 실행해야합니다.