크랭크로 작동되는 뮤직 박스에 일련의 4 개의 음표를 연주 할 수 있습니다. 크랭크를 돌리면 크랭크의 위치와 회전 방향에 따라 네 줄 중 하나를 뽑습니다. 크랭크를 북쪽으로 돌리면 상자의 문자열 번호가 1-4입니다.
1 | 2
|
O
4 3
거기에서 크랭크를 시계 방향으로 돌려 # 2 스트링을 뽑아 크랭크를 동쪽으로 가리킬 수 있습니다.
1 2
O---
4 3
또는 크랭크를 북쪽에서 시계 반대 방향으로 돌려 # 1 현을 연주하고 크랭크가 서쪽을 가리키는 것으로 끝낼 수도 있습니다.
1 2
---O
4 3
주어진 시간에 상자는 두 가지 음 중 하나를 재생할 수 있습니다. 다음 음은 시계 방향으로 사용 가능하고 다음 음은 반 시계 방향으로 사용 가능합니다.
도전
당신의 도전은 비어 있지 않은 음 값의 문자열을 받아들이는 프로그램이나 함수를 작성하는 것입니다 (즉, 숫자 1
부터 4
~ 까지 ). 입력의 재생 가능성 또는 재생 불가능 성을 나타 내기 위해 진실되거나 거짓된 결과를 생성합니다.
몇 가지 참고 사항 :
-
입력은 초기 시작 위치에 대한 가정을하지 않습니다. 입력은
214
(동쪽으로 시작하고 시계 반대 방향으로 엄격하게 이동) 및234
(북쪽에서 시작하고 시계 방향으로 엄격하게 이동) 두 가지 모두 유효합니다. -
크랭크는 각 음마다 한 방향으로 자유롭게 움직일 수 있습니다.
33333
한 줄을 가로 질러 앞뒤로 움직여서 같은 음표가 연속적으로 가능합니다 (예 :). 이 시리즈1221441
는 완벽하게 재생할 수 있습니다 (서부에서 시작하여 시계 방향으로 2 단계 이동 한 다음 시계 반대 방향으로 3 단계 이동 한 다음 시계 방향으로 2 단계 이동).
시료
어떤 true
경우에는 :
1
1234
1221
3333
143332
22234
2234
22214
1221441
41233
어떤 false
경우에는 :
13 (note 3 is never available after note 1)
1224 (after `122`, the crank must be north, so 4 is not playable)
121 (after `12` the crank is east; 1 is not playable)
12221 (as above, after `1222` the crank is east)
43221
답변
Pyth, 30 27 바이트
f!-aVJ.u%-ysYN8zTtJ,1 7cR2T
아이디어는 다음과 같습니다.
1.5 1 0.5
2 0
2.5 3 3.5
크랭크는 항상 반정 수 위치에 c
있습니다. 각 단계에서을 n
설정 하여 정수 위치 메모 에 반영 합니다 c = 2*n-c
. n
유효한 경우 c
± 1 mod 8 씩 변경됩니다. n
유효하지 않은 경우 c
± 3 mod 8만큼 변경됩니다. 모든 값을 수집하기 위해 입력을 누적하여 줄이고 c
모든 음표가 유효한지 확인합니다. c
첫 번째 노트에 인접한 값만 확인하는 것보다 짧기 때문에 모든 시작 값에 대해이 작업을 수행합니다 .
형식화 :
f
! -
aV J .u
% -
y s Y
N
8
z
T
t J
,
1
7
cR2 T
테스트 스위트 .
답변
CJam, 34 31 바이트
8,q{~2*f{_@-_zF8b&,@@+8,=*}0-}/
휴대폰에서이 작업을 수행 했으므로 나중에 설명을 작성해야합니다. 사실은 출력이 비어 있지 않습니다.
설명
새 코드는 레이아웃을 약간 변경합니다.
2 3 4
1 . 5
0/8 7 6
짝수는 문자열 위치에 해당하고 홀수는 크랭크 위치에 해당합니다.
다음과 같은 일이 발생합니다.
8, Create the range [0 1 .. 7] of possible starting positions
We can leave the string positions [0 2 4 6] in since it doesn't matter
q{ ... }/ For each character in the input...
~2* Evaluate as integer and double, mapping "1234" -> [2 4 6 8]
f{ ... } Map over our possible current crank positions with the string
position as an extra parameter
_@- Calculate (string - crank), giving some number in [-7 ... 7]
_z Duplicate and absolute value
F8b Push 15 base 8, or [1 7]
&, Setwise intersection and get length. If (string - crank) was in
[-7 -1 1 7] then the move was valid and this evaluates to 1, otherwise 0
@@+ Calculate ((string - crank) + string)
8,= Take modulo 8, giving the new crank position. x%y in Java matches the
sign of x, so we need to do ,= (range + index) to get a number in [0 .. 7]
* Multiply the new crank position by our previous 0 or 1
0- Remove all 0s, which correspond to invalid positions
그런 다음 마지막에 스택이 자동으로 인쇄됩니다. 예를 들어 1
, 출력이 31
인 경우 출력이 종료 위치에있을 수 있습니다. 즉, 크랭크가 왼쪽 또는 위를 향하게 될 수 있습니다.
CJam에만 추가 매개 변수가있는 필터가있는 경우 …
편집 :이 29 바이트가 작동한다고 스스로 확신하면서 일시적으로 롤백합니다.
8,q{~2*f{_@-_7b1#@@+8,=|}W-}/
답변
하스켈, 93 88 87 바이트
any(all(\(a,b:c)->1>mod(a!!1-b)4).(zip=<<tail)).mapM((\a->[[a,a+1],[a+1,a]]).read.pure)
이것은 문자열을 가져와 불리언을 리턴하는 익명 함수로 평가됩니다. 여기에서 테스트 스위트.
설명
아이디어는 오른쪽의 람다 는 다음 다이어그램에 따라 숫자를 크랭크로 가져갈 수있는 두 가지 “움직임”에 숫자 a
를 매핑하는 것입니다 [[a,a+1],[a+1,a]]
.
1 (2) 2
(1/5) (3)
4 (4) 3
기본 익명 함수에서는 먼저 mapM((...).read.pure)
각 문자를 정수로 변환하고 위의 람다를 적용하고 두 동작 중 하나를 선택하여 모든 결과 이동 시퀀스 목록을 반환합니다. 그런 다음 각 시퀀스의 두 번째 숫자가 다음 모듈로 4의 첫 번째 숫자와 동일한 속성을 갖는지 확인합니다. 이는 물리적으로 가능한 시퀀스임을 의미합니다. 이를 위해 zip
각 시퀀스를로 이동 하고 쌍 tail
의 조건을 확인하고 시퀀스가로 평가 all
되는지 확인합니다 .any
True
답변
답변
망막 , 127 109 바이트
^((1|2)|(2|3)|(3|4)|(4|1))((?<2-5>1)|(?<5-2>1)|(?<3-2>2)|(?<2-3>2)|(?<4-3>3)|(?<3-4>3)|(?<5-4>4)|(?<4-5>4))*$
이 인쇄 0
또는 1
이에 따라,.
온라인으로 사용해보십시오! (이것은 약간의 수정 된 버전으로 인쇄 0
또는 대신 입력에서 모든 일치 항목을 표시합니다 1
.)
나는 우아한 알고리즘을 생각해 보았지만 처음 몇 번의 시도는 역 추적을 우회 할 수 없었고 역 추적을 구현하는 것은 성가신 일입니다. 유효한 솔루션. 불행히도, 인코딩은 상당히 장황하고 상당히 중복 적입니다 … 이것이 단축 될 수 있다고 확신합니다.
내가 더 깔끔한 것을 알아 내려고 노력하는 동안 누군가가 어떻게 작동하는지 정렬하려면 다음과 같이 좀 더 읽기 쉬운 버전이 있습니다.
^
(
(?<a>1|2)
| (?<b>2|3)
| (?<c>3|4)
| (?<d>4|1)
)
(
(?<a-d>1) | (?<d-a>1)
| (?<b-a>2) | (?<a-b>2)
| (?<c-b>3) | (?<b-c>3)
| (?<d-c>4) | (?<c-d>4)
)*
$
그리고 여기 힌트가 있습니다 :
1 a 2
d O b
4 c 3
답변
MATL , 57 55 바이트
1t_hjnZ^!t1tL3$)2_/wvG1)UGnl2$Ov+Ys.5tv3X53$Y+4X\G!U=Aa
이 문제보다 빠른 현재 릴리스 (10.2.1)를 사용합니다 .
EDIT (2017년 1월 17일)에 의한 언어의 변화는v
필요 에 의해 대체 될 &v
, 그리고 tL3$)
에 의해 Y)
(추가로, 다른 개선 할 수 할 수). 다음 링크에는이 두 가지 수정 사항이 포함되어 있습니다.
설명
이것은 코드 골프를 위해 내가 좋아하는 두 가지 도구 인 brute force 와 convolution을 기반으로 합니다.
코드는 정의 경로 좌표의 관점에서 크랭크이어서 0.5
, 1.5
등 각 숫자는 음의 크랭크의 위치를 알 수있다. 이 코드는 먼저 입력 문자열의 첫 번째 메모로 시작하는 가능한 모든 경로로 경로 배열 을 만듭니다 . 각 경로는이 배열의 열입니다. 이것이 무차별 대입 구성 요소입니다.
이 경로 배열에서 음표 배열 을 얻습니다. 여기서 각 열은 연주 가능한 음표의 시퀀스입니다. 예를 들어, 위치에서 이동 하면 메모 0.5
가 1.5
생성 1
됩니다. 이것은 위치 간 평균을 취한 다음 모듈로 4 연산을 적용하는 것으로 구성됩니다. 각 열의 누적 평균은 2D 컨벌루션으로 수행됩니다 .
마지막으로, 프로그램은 노트 배열의 열이 입력과 일치하는지 확인합니다.
1t_h % row array [1, -1]
j % input string
nZ^! % Cartesian power of [1, -1] raised to N, where "N" is length of string
t % duplicate
1tL3$) % extract first row
2_/ % divide by -2
wv % attach that modified row to the top of Cartesian power array
G1)U % first character of input string converted to number, "x"
Gnl2$O % column array of N-1 zeros, where N is length of input
v % concat vertically into column array [x;0;0...;0]
+ % add with singleton expansion
Ys % cumulative sum along each column. Each column if this array is a path
.5tv % column array [.5;.5]
3X5 % predefined string 'same' (for convolution)
3$Y+ % 2D convolution of path array with [.5;.5]
4X\ % modified modulo operation. This gives note array with values 1,2,3,4
G!U % column array of input string characters converted to numbers
=Aa % true if any column of the note array equals this
답변
피스, 43
Km-R2sMdc`M%R4-VJjQTtJ`0|Fm!s-VKdCm_B^_1dlK
이것은 아마도 매우 골프 타기 가능하며 골프를위한 최적의 알고리즘이 아닙니다 (모든 경로를 열거하는 것이 더 짧을 것으로 예상됩니까?) … 어쨌든 알고리즘에 오류가 있으면 알려주십시오. 작동해야한다고 생각합니다. 전에 잘못했습니다!
예제 입력을 사용하여 알고리즘을 설명하겠습니다 1221
. 이 프로그램은 먼저 다음과 같이 숫자를 해당 후속 작업에 매핑합니다 [[1,2],[2,2],[2,1]]
. 그런 다음 차이점 mod를 얻습니다 4
(Pyth는의 올바른 인수의 부호와 일치하는 결과를 얻으 %
므로 항상 긍정적입니다) [3,0,1]
. 그런 다음 결과에 분할 0
하고있다 2
그들 각각에서 차감 : [[1],[-1]]
.
설정이 완료 [-1,1,-1...]
되었으므로 [1,-1,...]
이전의 결과 배열과 동일한 길이 의 목록 과 해당 부정을 작성합니다 . 그런 다음 각 목록에 대해 목록의 요소와 이전 단계에서 생성 된 목록 사이에서 설정 차감을 수행하십시오. 그런 다음 결과 중 하나에 빈 목록 만 포함 된 경우 true를 출력합니다.