하노이 타워가 무엇인지 모르는 경우 간단히 설명하겠습니다. 막대 3 개와 디스크 크기가 각각 다릅니다. 처음에는 모든 디스크가 정렬 된 순서대로 첫 번째 타워에 있습니다. 가장 큰 디스크는 맨 아래에 있고 가장 작은 디스크는 맨 위에 있습니다. 목표는 모든 디스크를 세 번째 막대로 가져 오는 것입니다. 쉽게 들리나요? 캐치가 있습니다. 다른 디스크보다 작은 디스크 위에 디스크를 놓을 수 없습니다. 한 번에 한 장의 디스크 만 잡고 다른 막대로 옮길 수 있으며 테이블이 아닌 막대에만 디스크를 놓을 수 있습니다.
ASCII 예제 솔루션 :
A B C
| | |
_|_ | |
__|__ | |
A B C
| | |
| | |
__|__ _|_ |
A B C
| | |
| | |
| _|_ __|__
A B C
| | |
| | _|_
| | __|__
도전
A, B, C라는 3 개의 막대가 있습니다.
하노이의 탑을위한 솔루션을 확인하는 것이 도전입니다. 다음을 확인해야합니다.
- 결국 모든 n 개의 디스크는로드 C (3)에 있습니다.
- 특정 상태의 특정 디스크에 대해서는 그 아래에 더 작은 디스크가 없습니다.
- 공 막대에서 디스크를 가져 오거나 디스크를 존재하지 않는 막대로 옮기는 것과 같은 명백한 오류는 없습니다.
솔루션이 최적 일 필요는 없습니다.
입력
프로그램은 두 가지 입력을받습니다 :
- 디스크 수 n (정수)
-
수행되는 동작은 다음과 같은 튜플 세트로 구성됩니다. 당신은 그들이 표현되는 방법을 선택할 수 있습니다. 예를 들어 위의 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
, B
및 C
그룹에 해당하는 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 stack
N is larger than the one we're trying to match with
\ 1` 이어서 a) 일치하지 않는 경우에만 발생할 수 있습니다 .
마지막으로, 남은 모든 것을 우리가 모든 지시와 b) 봉을 일치 한)은에게 보장되는 A
및 B
, 비어 있으므로 모든 디스크가 상으로 이동 한 것을 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)])
내 프로그램에. 출력합니다 IndexError
3 조건이 충족되지 않는 경우 NameError
2 조건이 충족되지 않을 경우, 및 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 개의 경고를 제공하므로이를 침묵시키는 환경에서 실행해야합니다.