내 4 노트 뮤직 박스가 그 노래를 재생할 수 있습니까? 상자는 두 가지 음 중 하나를 재생할

크랭크로 작동되는 뮤직 박스에 일련의 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되는지 확인합니다 .anyTrue


답변

망막, 50 바이트

A`13|31|24|42|(.)(?!\1)(.)(\2\2)*(\1|\2(?!\1|\2).)

나는 이것이 효과가 있다고 생각합니까?

여기에서 시도하십시오.


답변

망막 , 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 forceconvolution을 기반으로 합니다.

코드는 정의 경로 좌표의 관점에서 크랭크이어서 0.5, 1.5등 각 숫자는 음의 크랭크의 위치를 알 수있다. 이 코드는 먼저 입력 문자열의 첫 번째 메모로 시작하는 가능한 모든 경로로 경로 배열 을 만듭니다 . 각 경로는이 배열의 열입니다. 이것이 무차별 대입 구성 요소입니다.

이 경로 배열에서 음표 배열 을 얻습니다. 여기서 각 열은 연주 가능한 음표의 시퀀스입니다. 예를 들어, 위치에서 이동 하면 메모 0.51.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를 출력합니다.