Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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  
share|improve this question
    
Can the input be the string including quotes? – Luis Mendo Jan 26 at 20:47
    
@LuisMendo Sure, I'll allow it -- I'm interested in your algorithm, not making you jump through hoops to get the input. Anyway, there's unofficial community consensus that it's generally okay: String input with or without “”? – apsillers Jan 26 at 20:51
    
I didn't know that. Thanks for the link! – Luis Mendo Jan 26 at 20:52
    
Is there a limit to the maximum number of times a song will make me go all the way around? – AJMansfield Jan 26 at 21:37
1  
@AJMansfield No, solutions should allow for arbitrarily many cycles. Of course, if some input causes your code to exceed a limit in your language's interpreter or your computer's memory, that's fine (since it's merely limited by however much memory you physically have or your interpreter allows), but your solution should not impose extra limitations on how far or how many times the crank moves. – apsillers Jan 26 at 21:41

14 Answers 14

up vote 5 down vote accepted

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.

share|improve this answer

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-}/
share|improve this answer
31  
Every time someone answers with some difficult language like cjam and says "did this on my phone" I die a little inside – Dennis van Gils Jan 26 at 23:36
2  
He probably meant the text was outputted using a phone, but it was done in his head. – Nelson Jan 27 at 6:37

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.

share|improve this answer

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
share|improve this answer

MATL, 55 57 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.

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
share|improve this answer

Retina, 50 bytes

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

I think this works?

Try it here.

share|improve this answer

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
share|improve this answer

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.

share|improve this answer
    
What do you mean by "the results are split on 0"? In particular, what would you get for 1221221 and 1221441? – Neil Jan 28 at 20:36
    
@Neil 1221221 is false and 1221441 gives true overall, but if I understand you want the result after that step in the algorithm? If that is the case it gives: from [3, 0, 1, 3, 0, 1] to [[3], [1, 3], [1]] and [3, 0, 1, 1, 0, 3] to [[3], [1, 1], [3]]. Let me know if you want something else explained :) – FryAmTheEggman Jan 28 at 20:55
    
I think I'm more confused than before, so could you please finish those two examples to explain how the (correct) results are achieved? – Neil Jan 28 at 22:02
    
@Neil Sure, no problem :) From there, we do the subtraction to get: [[1], [-1, 1], [-1]] and [[1], [-1, -1], [1]] from here, you can see that the first one does not have lists that alternate between -1 and 1 while the other list does, giving the final result. The algorithm is a bit obtuse, but it's basically mapping direction changes to 0 and direction as +/-1, then checking that no jumps are made and the directions make sense. – FryAmTheEggman Jan 28 at 22:09
    
Oh, so the bit I was missing was that each split list must consist of the same value, and those values must alternate. Thanks! – Neil Jan 28 at 22:49

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.

share|improve this answer
    
f("1122") => true @DigitalTrauma – Cᴏɴᴏʀ O'Bʀɪᴇɴ Jan 26 at 21:28
    
@CᴏɴᴏʀO'Bʀɪᴇɴ I see nothing wrong with that. On the other hand I've realised that f("1221221") outputs the wrong answer, so I'll have to rethink. – Neil Jan 26 at 22:43
    
It's alway nice to include a test suite, '43221' fails: jsbin.com/vafitotequ/1/edit?js,console – Pavlo Jan 27 at 11:08
    
@Pavlo Whoops, I'd golfed [24][24] to (2|4)\1 but I hadn't tested adequately. Sorry about that. – Neil Jan 27 at 12:59
    
Can you golf [24][24] to [24]{2}? – Digital Trauma Jan 27 at 23:21

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>

share|improve this answer
    
Nicely done. Would you explain how | works in this case? – Pavlo Feb 3 at 8:32
1  
@pavlo Thanks. It's a shorter way of writing (x.map(...),v). It works because the array that the map returns casts to 0 and 0|v == v. – user81655 Feb 3 at 9:09

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
share|improve this answer
    
121 should output false. – lirtosiast Jan 26 at 20:06
    
Ah, nevermind. I see. Will fix shortly – Skyl3r Jan 26 at 20:08
    
+1 for using Lua – Insane Jan 28 at 3:54
    
You might be interested in adding some of those Lua tips to Tips for golfing in Lua if you don't see them listed there already. – apsillers Jan 28 at 14:43
    
Thanks, I'll check it out. – Skyl3r Jan 28 at 14:58

Python (3.5) 160 151 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]
share|improve this answer

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

share|improve this answer
1  
Saved you 17 bytes: (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))) – Neil Feb 2 at 22:44
    
Still not as short as @user81655's answer though. – Neil Feb 2 at 22:45

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.