Can my 4-note music box play that song?

Question

I have a crank-operated music box that can play a series of four notes. When I turn the crank, it plucks one of four strings, depending on the position of the crank and the direction of the turn. When the crank is turned due north, the box (with its strings numbered 1 through 4) looks like this:

1  |  2
   |
   O   

4     3

From there, I can turn the crank clockwise to pluck the #2 string and point the crank east:

1     2

   O---   

4     3

Alternatively, I could have also turned the crank counterclockwise from north to play the #1 string and end with a crank pointing west:

1     2

---O   

4     3

At any given time, then, the box can play one of two notes: the next note available in the clockwise direction or the next note in the counterclockwise direction.

Challenge

Your challenge is to write a program or function that accepts a non-empty string of note values (i.e., numerals 1 through 4) and determine if it is ever possible to play that sequence of notes on the music box. Produce a truthy or falsy result to indicate the playability or non-playability of the input.

Some notes:

• The input makes no assumptions about initial start position. The inputs 214 (starting east and moving strictly counterclockwise) and 234 (starting north and moving strictly clockwise) and both valid.

• The crank may move freely in either direction after each note. A series of the same note is possible (e.g., 33333) by moving back and forth across one string. The series 1221441 is perfectly playable (starting west, moving clockwise two steps, then counterclockwise three steps, then clockwise two steps).

Samples

Some true cases:

1
1234
1221
3333
143332
22234
2234
22214
1221441
41233

Some false cases:

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  

Answer 1

Pyth, 30 27 bytes

f!-aVJ.u%-ysYN8zTtJ,1 7cR2T

Here's the idea:

 1.5  1  0.5

  2       0

 2.5  3  3.5

The crank is always at a half-integer position c. At each step, we reflect it over an integer position note n by setting c = 2*n-c. If n is valid, c changes by ±1 mod 8. If n is invalid, c changes by ±3 mod 8. We cumulatively reduce over the input to collect all values of c, and then see if all notes were valid. We do this for every starting value of c, because it's shorter than checking just the ones adjacent to the first note.

Formatted:

f
  ! -
      aV J .u
              % -
                  y s Y
                  N
                8
              z
              T
         t J
      ,
        1 
        7
  cR2 T

Test suite.

Answer 2

CJam, 34 31 bytes

8,q{~2*f{_@-_zF8b&,@@+8,=*}0-}/

Did this on my phone, so I'll have to put up an explanation later. Output is nonempty iff truthy.

Try it online | Test suite

Explanation

The new code shifts the layout a little:

2    3    4

1    .    5

0/8  7    6

Even numbers correspond to string positions and odd numbers correspond to crank positions.

Here's what happens:

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

The stack is then automatically printed at the end. Any possible ending positions will be in the output, e.g. for the input 1 the output is 31, which means the crank can end facing either left or up.

^{If only CJam had filter with extra parameter...}

---

Edit: Temporarily rolling back while I convince myself that this 29-byte works:

8,q{~2*f{_@-_7b1#@@+8,=|}W-}/

Answer 3

Haskell, 93 88 87 bytes

any(all(\(a,b:c)->1>mod(a!!1-b)4).(zip=<<tail)).mapM((\a->[[a,a+1],[a+1,a]]).read.pure)

This evaluates to an anonymous function that takes a string and returns a boolean. Test suite here.

Explanation

The idea is that the lambda on the right maps a number a to [[a,a+1],[a+1,a]], the two possible "moves" that take the crank over that number, according to the following diagram:

  1 (2) 2

(1/5)  (3)

  4 (4) 3

In the main anonymous function, we first do mapM((...).read.pure), which converts each character to an integer, applies the above lambda to it, and chooses one of the two moves, returning the list of all resulting move sequences. Then, we check if any of these sequences has the property that the second number of each move equals the first number of the next modulo 4, which means that it's a physically possible sequence. To do this, we zip each move sequence with its tail, check the condition for all the pairs, and see if any sequence evaluates to True.

Answer 4

Retina, 50 bytes

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

I think this works?

Try it here.

Answer 5

Retina, 127 109 bytes

^((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))*$

This prints 0 or 1, accordingly.

Try it online! (This is a slightly modified version which marks all matches in the input instead of printing 0 or 1.)

I tried coming up with an elegant algorithm, but my first few attempts weren't able to circumvent backtracking... and implementing backtracking is annoying... so I used a language which does the backtracking for me where I just need to encode a valid solution. Unfortunately, the encoding is fairly verbose and fairly redundant... I'm sure this can be shortened.

While I try to figure out something neater, if anyone wants to sort out how this works, here is a somewhat more readable version:

^
(
    (?<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)
)*
$

And here is a hint:

1  a  2

d  O  b

4  c  3

Answer 6

MATL, 57 55 bytes

1t_hjnZ^!t1tL3$)2_/wvG1)UGnl2$Ov+Ys.5tv3X53$Y+4X\G!U=Aa

This uses current release (10.2.1), which is earlier than this challenge.

EDIT (17 January, 2017): due to changes in the language, v needs to be replaced by &v, and tL3$) by Y) (in addition, some other improvements could be done). The following link includes those two modifications

Try it online!

Explanation

This is based on two of my favourite tools for code golf: brute force and convolution.

The code defines the path followed by the crank in terms of coordinates 0.5, 1.5 etc. Each number tells the position of the crank between notes. The code first builds a path array with all possible paths that start with the first note of the input string. Each path is a column in this array. This is the brute force component.

From this path array, a note array is obtained, where each column is a realizable sequence of played notes. For example, movement from position 0.5 to 1.5 produces a note 1. This consists in taking the average between positions and then applying a modulo 4 operation. The running average along each column is done with a 2D convolution.

Finally, the program checks if any column of the note array coincides with the input.

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

Answer 7

Pyth, 43

Km-R2sMdc`M%R4-VJjQTtJ`0|Fm!s-VKdCm_B^_1dlK

Test Suite

This is probably very golfable, and also not the optimal algorithm for golfing (I expect enumerating all paths will be shorter?)... Anyway, if you find any error with the algorithm please let me know, I think it should work but I've been wrong before!

I'll explain my algorithm using the example input of 1221. This program first maps the digits against their successors, like so: [[1,2],[2,2],[2,1]]. Then it gets their differences mod 4 (Pyth gets the result that matches the sign of the right argument of %, so this is always positive) : [3,0,1]. Then the results are split on 0 and have 2 subtracted from each of them: [[1],[-1]].

Now that the setup is done, we create a list of [-1,1,-1...] and its negation [1,-1,...], both the same length as the resulting array from before. Then, for each of these lists, perform setwise subtraction between the elements of the list and the list generated in the earlier step. Then, if either of the results contains only empty lists, we output true.

Answer 8

ES6, 104 100 bytes

s=>!/13|24|31|42|3[24]{2}1|4[13]{2}2|1[24]{2}3|2[13]{2}4|(.).\1/.test(s.replace(/(.)(\1\1)+/g,"$1"))

Edit: Saved 4 bytes thanks to @DigitalTrauma.

This is a complete rewrite as my previous approach was flawed.

I start by reducing all runs of digits to 1 or 2 depending on whether there was an odd or even number in the run. I then look for all the illegal combinations:

• 13|24|31|42 (opposite sides)
• 3[24]{2}1 as 3221 and 3441 are illegal
• similarly for 4xx2, 1xx3 and 2xx4 where x is either of the missing digits
• (.).\1 as things like 121 are illegal (111 has been reduced to 1 earlier)

If there are no illegal pairs or "triples" then the whole string is legal (proof by induction is left as an exercise because it's late night here).

I tried to simplify 3[24]{2}1|1[24]{2}3 using a negative lookahead assertion but it turned out to be longer that way.

Answer 9

Matlab, 279 180 bytes

o=eye(4);a=input('')-'0';M=[o,o(:,[4,1:3]);o(:,[2:4,1:4,1])];x=2;for p=[a(1),mod(a(1),4)+1];for k=a;i=find(M*[o(:,k);o(:,p)]>1);if i;p=mod(i-1,4)+1;else;x=x-1;break;end;end;end;x>0

Quite a lazy solution, but the shortest I was able to come up with. I created special matrix: When you encode the state of the plucker and the last string that is to be plucked, it returns a vector, that encodes the new position of the plucker, and whether the previous pluck was possible at all. Now we just loop over all notes from the two possible start positions and see if one of them results in a playable melody. Can probably be golfed a lot more.

Expanded and explained source:

o=eye(4);
a=input('')-'0';

% encoding of plucker/notes
%      1
%   1     2
%4           2
%   4     3
%      3
%

M=[...
%12 3 4 1 2 3 4 <
1,0,0,0,0,1,0,0; %1  k = current note
0,1,0,0,0,0,1,0; %2  
0,0,1,0,0,0,0,1; %3  
0,0,0,1,1,0,0,0; %4  
0,0,0,1,0,0,0,1; %1  p = current position of plucker
1,0,0,0,1,0,0,0; %2
0,1,0,0,0,1,0,0; %3
0,0,1,0,0,0,1,0];%4
% the vector we multiply with this matrix has following structure,
% the k-th and the p+4 th entries are 1, the rest 0
% when we multiply this vecotr with this matrix, we get a vector with an
% entry of value 2 IF this is a valid move ( mod(positionOfThe2 -1,4)+1 is
% the position of the plucker now)
% or only entries less than 2 it is impossible
x=2;  %number of "chances" to get it right
for p=[a(1),mod(a(1),4)+1] %check both starting values;
    for k=a;                %loop throu the notes
        size(M);

        c = M * [o(:,k);o(:,p)];
        i=find(c>1);               %did we find a 2?
        if i;
           p=mod(i-1,4)+1;         %if yes, valid move
        else;
            x=x-1;                 %if no, invalid, 
            break;
        end 
    end
end
x=x>0 %if we failed more than once, it is not possible

Answer 10

MATL, 49 bytes (non-competing¹)

^{1. The answer (ab)uses the less strict indexing of newer versions of MATL, and would not have worked at the time this challenge was posted.}

dt~aX`tt~f1)q:)w3MQJh)_ht~a]tT-3hX|n2=wT_3hX|n2=+

Try it online!.

I saw this challenge at the Best of PPCG 2016, and figured that this could use my favourite operator:

d

Or, diff in MATLAB/Octave (I will freely use MATLAB/Octave terminology in my explanation, since it is easier to read for humans). This command calculates the element-wise difference in a vector or, in this case, in a character array.

For this problem, the differences exhibit an interesting pattern. Note that

An change in direction must mean that a note is played twice.

For the difference pattern (ignoring the 1-4 transition for now), this means that

A change in sign in diff(input) must have an odd number of zeroes in between. Conversely, the sign is not allowed to change after an even number of zeroes.

---

I implemented this by, for each array, finding the first zero. I trim the zero out, and multiply all elements after it by -1. For the end result, this means that all elements must have the same sign. Of course, there is the small issue of the -3 equalling +1, and 2 being disallowed in general. I solved this by taking the set union of the result with [1 -3], and checking whether this is of size 2 (i.e., no disallowed elements 'entered' the set through the union). Repeat for [-1 3], and check whether either (or both, in the case of a 1-length input) is true.

d                                % Difference of input
 t~a                             % Check if any element equals 0
    X`                     t~a]  % Start while loop, ending in the same check
       t~                           % Get a new vector, logical negated to find zeroes.
          f1)                       % Find the position of the first zero. 
      t         q:)                 % Decrement by 1, to index all elements before that zero.
                   w3MQJh)          % Push the result of 'find', but increment to get all elements after.
                         _h         % Multiply the second half by -1, and concatenate horizontally.

  T-3hX|n2=                      % Check if set union with [1 -3] is size 2
 t        wT_3hX|n2=             % Check if set union with [-1 3] is size 2
                    +            % Logical OR. 

Answer 11

Python 2, 65 bytes

n=15
for c in input():k=2**int(c);n=n*17/k%4*5/2%4*k%15
print n>0

Try it online!

Answer 12

Lua, 146 142 108 162 159 149 144 135 132 118 113 bytes

z,q,s=0,0,io.read()for i in s:gmatch'.'do t=i-z if 2==math.abs(t)or t==q then return''end q=-t z=i end return 2>1

Returns true or false given a string of numbers between 1 and 4. (Doesn't handle no data or out of range numbers.

Simply tracks what the last movement was and checks if this movement is a reversal of the last movement (IE, 121 or 12221) or if the distance moving is more than possible.

EDIT 1:

Saved 6 bytes. I forgot that if (int) then returns true if int is non zero.

Thus:

if t~=0 then

changes to:

if t then

Also saved a few bytes by restructuring.

EDIT 2:

I'm slowly figuring this out. I've been reading the documentation here: http://www.lua.org/pil/ And one of the more useful pages there for golfing is http://www.lua.org/pil/3.3.html

In particular, this is very helpful:

Like control structures, all logical operators consider false and nil as false and anything else as true.

What this means for me is that I can go ahead and remove my declaration for q (which was initially set to 0) as it will be regarded as "false" until it is set. So I save a few more bytes through this.

Another thing worth mentioning, though I don't use it, is if you want to swap values in Lua, you can simply do a,b=b,a without the need for a temporary variable.

EDIT 3

So, through some clever reconstruction as well as a new function, I've got the byte count down by 9 more.

Best Mode for Receiving Input

If you need to read in a list of numbers and do operations on them one at a time, you can use:

for x in string:gmatch('.') do
    print(x) --This is our number
end

When compared to your alternative using string:sub, you can see the value for golf (or general use):

for x=1,string:len() do
    print(string:sub(x,x)) --This is our number
end

Restructure Functions or Strings

Second thing, if you have multiple declarations on one line and one of the values is a function or you have a condition in which you compare a number to the result of a function like these:

x,y,z=io.read(),0,0 print('test')

if math.abs(x)==2 then

by restructuring it so the closing parenthesis are the last character in the condition or declaration, you can cut out a character like so:

y,z,x=0,0,io.read()print('test') --Notice no space

if 2==math.abs(x)then --If we put the '2' first in the conditional statement, we can now remove a space character

Return Conditions that Equate to True or False instead of 'True' or 'False'

I found a semi amusing way to cut my byte count down yet further. If you need to return true or false, you can return a statement that equates to true or false that has less characters than "true" or "false" themselves.

For instance, compare:

return true
return false

To:

return 2>1
return 1>2

Answer 13

JavaScript (ES6), 80 bytes

s=>[r=0,1,2,3].map(i=>[...s].map(n=>n-1-i%4?n%4-i%4?v=0:i+=3:i++,v=1)|v?r=1:0)|r

Explanation

i%4 is the current crank position:

    1 (i%4 == 1) 2   

(i%4 == 0) (i%4 == 2)

    4 (i%4 == 3) 3   

Indented and Commented

s=>
  [r=0,1,2,3].map(i=> // i = crank position, test for i starting at 0 to 3, r = result
    [...s].map(n=>    // for each note n
      n-1-i%4?        // if n is not at the position after i
        n%4-i%4?      // if n is not at the position before i
          v=0         // set the result of this test to invalid
        :i+=3         // else i-- (+3 used because i%4 would break for negative values)
      :i++,           // else i++
      v=1             // v = result of test, initialise to 1 (valid)
    )
    |v?r=1:0          // if the test returned true, set the result to true
  )
  |r                  // return the result

Test

var solution = s=>[r=0,1,2,3].map(i=>[...s].map(n=>n-1-i%4?n%4-i%4?v=0:i+=3:i++,v=1)|v?r=1:0)|r

<input type="text" value="1221441" oninput="result.textContent=solution(this.value)" />
<pre id="result"></pre>

Answer 14

Python (3.5) 160 151 150 bytes

A recursive solution

def f(s):g=lambda s,c:s==''or g(s[1:],(c[:4]*2)[(s[0]==c[0])*2+1:])if s==''or s[0]in c[:2]else 0;return any([g(s,"1234123"[i:])for i in range(4)])

Ungolfed without lambda

def f(s):
    def g(s,c):
        if s=='' or s[0] in c[:2] :
            return s=='' or g(s[1:],(c[:4]*2)[(s[0]==c[0])*2+1:])
        else:
            return False
    return any([g(s,"1234123"[i:]) for i in range(4)])

I rotate all the box instead of the crank. The crank position is between first and second character of the c string. I need to test all beginning position of the crank.

Trick use to rotate the string

The usual way to rotate a string in python (s[i:]+s[:i]) need too repeat both index and string. In this case i duplicate the string and crop first characters.

(c*2)                        # duplicate the string
     [(s[0]==c[0])*2+1       # test that return 1 if firsts characters match 3 instead 
                      :]     
                        [:4] # crop again to have a 4 characters string

Test cases

[f(i) for i in ["1", "1234", "1221", "3333", "143332", "22234", "2234", "22214", "1221441", "41233", "13", "1224", "121", "12221", "43221"]]
[True, True, True, True, True, True, True, True, True, True, False, False, False, False, False]

Answer 15

Prolog (SWI), 117 bytes

a(N,P):-P=N;N=1,P=4,!;P is N-1.
m([A,B|C],[X,Y|Z]):-a(A,X),a(B,X),a(B,Y),X\=Y,m([B|C],[Y|Z]).
m([_],_).
p(N):-m(N,_).

Defines a predicate p that succeeds on playable inputs (given as a list of integers) and fails on unplayable ones. Try it online!

Explanation

a defines an adjacency relation between note N and crank position P. We define position p to be between notes p and p+1. Thus, a position is adjacent to note N iff

• it equals N (P=N); or
• the note is 1 and the position is 4 (N=1,P=4); or
• the above case is not true (!) and the position equals N-1 (P is N-1).

m takes a list of notes and tries to generate a list of positions that will play those notes. A is the note just played, B is the note about to be played; X is the current crank position, Y is the next crank position. A move is valid iff

• the note just played is adjacent to the current crank position (a(A,X));
• the note about to be played is also adjacent to the current crank position (a(B,X));
• the note about to be played is adjacent to the next crank position (a(B,Y)); and
• the two crank positions are not equal (X\=Y).

If all of these hold, recurse. If we successfully get down to any one note (m([_],_)), the sequence of notes is playable.

For this question, we only care whether a sequence of moves exists, so we define p to call m and discard the generated list of crank positions.

See an ungolfed version and verify all test cases here.

Answer 16

JavaScript (ES2015), 110 95

p=(s,d)=>(h=s[0],t=s.slice(1),g=t[0],!g||(d?g==h?p(t,-d):g%4==(h-d)%4&&p(t,d):p(s,1)||p(s,-1)))

15 bytes saved by Neil! Original version ungolfed:

p = (s, d) => {
  h = s[0]
  t = s.substr(1)

  if (!t[0]) return true
  if (!d) return p(s, 1) || p(s, -1)
  if (t[0] == h) return p(t, d*-1)
  if (t[0] == (h-d > 4 ? 1 : h-d || 4)) return p(t, d)

  return false
}

Tests: https://jsbin.com/cuqicajuko/1/edit?js,console

Answer 17

Turing machine code, 395 bytes

0 1 _ r a
0 2 _ r b
0 3 _ r c
0 4 _ r d
a 1 _ r a
a 2 _ r E
a 3 _ r h
a 4 _ r S
b 1 _ r W
b 2 _ r b
b 3 _ r S
b 4 _ r h
c 1 _ r h
c 2 _ r N
c 3 _ r c
c 4 _ r W
d 1 _ r N
d 2 _ r h
d 3 _ r E
d 4 _ r d
N 1 _ r W
N 2 _ r E
N _ _ r r
N * _ r h
E 2 _ r N
E 3 _ r S
E _ _ r r
E * _ r h
S 3 _ r E
S 4 _ r W
S _ _ r r
S * _ r h
W 4 _ r S
W 1 _ r N
W _ _ r r
W * _ r h
h _ 0 r halt
h * _ r h
r _ 1 r halt

Try it online!

This is basically a state-based approach:

• The initial state is 0.
• a, b, c, and d are "undecided states" that only occur at the beginning
• N, E, S, and W are the "decided states", obviously standing for North, East, South, and West.

Answer 18

Thue, 203 bytes

I can't think of how to golf this farther.

0::=:::
>11::=>1
>22::=>2
>33::=>3
>44::=>4
>12::=b
>21::=d
>14::=c
>41::=a
>23::=c
>32::=a
>34::=d
>43::=b
a1::=d
a2::=b
b2::=a
b3::=c
c3::=b
c4::=d
d4::=c
d1::=a
a<::=~n
b<::=~e
c<::=~s
d<::=~w
::=
>0<

If the note sequence is possible, will output ending direction, otherwise the output will be empty.