Can the Tune be Played?

Question

Can the Tune be Played?

Explanation

A broken musical keyboard has keys labelled with positive integers. It is broken in two ways:

It takes a long time to process key presses: after pressing the key labelled with the number \$n\$, there is a gap of \$n\$ seconds before the \$n\$th note is heard.
So, for example, the \$5\$th key must be pressed \$5\$ seconds early for its note to sound in the right place.
Only one key can be pressed at a time.

Because of these problems, some tunes cannot be played on the keyboard. To understand why, let us first define a tune:

A tune will be defined as a list of positive integers representing the order in which notes should be heard (not the order in which keys should be pressed). A number \$n\$ represents the note heard when the \$n\$th note on the keyboard is pressed. This definition does not allow for rests, chords or notes of differing lengths, so you can imagine that all notes are played at a speed of exactly one note per second.

Invalid Tune Example

An example of a tune would be [3, 1, 2]. This means that the note \$3\$ should be heard, then, one second later, the note \$1\$, and a second after that, the note \$2\$.

However, when trying to play this tune on the keyboard, there is a problem. To understand why, shift each of the numbers \$n\$ in the tune back by \$n\$ spaces. The result represents the order in which keys must be pressed for the notes to sound in the correct place:

Tune                      [            3 , 1 , 2]
Index                      -3  -2  -1  0   1   2
How keys would be pressed [3 ,        1&2       ]

The problem here is that keys \$1\$ and \$2\$ must be pressed at the same time for their notes to sound in the right place, but it is impossible to press two keys at once on the keyboard. Therefore, the tune [3, 1, 2] cannot be played.

Valid Tune Example

An example of a valid tune would be [2, 1, 3]. To see why, shift the numbers back to find out when the keys must be pressed:

Tune                      [        2 , 1 , 3]
Index                      -2  -1  0   1   2
How keys would be pressed [2 , 3 , 1        ]

Having shifted each of the numbers back (\$2\$ moved back \$2\$ spaces, \$1\$ moved back \$1\$ space and \$3\$ moved back \$3\$ spaces), none of them have landed in the same position. Therefore, this tune can be played on the broken keyboard: the keys would be pressed in the order [2, 3, 1].

Task

Your task is to write a program which takes as input a list representing a tune, and outputs a truthy/falsy value depending on whether or not the tune can be played on the broken keyboard.

Assumptions

You can assume that input lists will always contain only positive integers.
You can assume that input lists will always have at least one element.
You can assume that inputs will always be lists.
Standard loopholes are forbidden.

Test Cases

[1, 2, 3] -> False
[3, 1, 2] -> False
[3, 2, 1] -> True
[6, 4, 7, 3, 5, 2, 1] -> True
[4, 7, 6, 5, 2, 1, 3] -> False // 6 and 4 land in same position
[4, 6, 4, 2, 1, 4] -> False
[2, 1, 6, 4, 4, 4] -> False // 4 and 1
[2, 1, 6, 4, 2, 4] -> True

Scoring

This is code-golf so the shortest answer (as measured in bytes) wins!

@Arnauld Tricky constraints that make simple tasks difficult? Surely nothing familiar to us code golfers! :D — Sundar R, Mar 6, 2022 at 21:32
Will all input number always be unique? If not, consider add some testcase for it. — tsh, Mar 7, 2022 at 2:33
This reminds me a lot of Siteswap notation for juggling, although perhaps backwards. In siteswap, [2,1,3] is invalid, but [3,1,2] is valid. — Steve Bennett, Mar 8, 2022 at 11:35

Arnauld · Accepted Answer · 2022-03-06 13:56:21Z

10

JavaScript (ES6), 30 bytes

Returns a Boolean value.

a=>a.every(b=(n,i)=>b[i-n]^=1)

Try it online!

answered Mar 6, 2022 at 13:56

Arnauld

188k20 gold badges171 silver badges631 bronze badges

\$\begingroup\$ Wow, that was fast. \$\endgroup\$
– ophact
Mar 6, 2022 at 14:17

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-03-08 13:34:48Z

7

Vyxal, 4 bytes

ż-Þu

My first Vyxal answer. Similar approach as the other answer.

Try it online or verify all test cases.

Explanation:

ż     # Push a list in the range [1, input-length]
 -    # Subtract it from the input at the same positions
  Þu  # Check if all values in this list are unique
      # (after which the result is output implicitly)

edited Mar 8, 2022 at 13:34

answered Mar 8, 2022 at 13:18

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

Add a comment |

pajonk · Accepted Answer · 2022-03-06 15:28:25Z

6

R, 34 bytes

Or R>=4.1, 27 bytes by replacing the word function with a \.

function(v)all(table(seq(!v)-v)<2)

Try it online!

answered Mar 6, 2022 at 15:28

pajonk

15.1k3 gold badges21 silver badges65 bronze badges

Add a comment |

ovs · Accepted Answer · 2022-03-06 16:29:49Z

6

Jelly, 4 bytes

_JQƑ

Try it online!

_J     -- difference between each element and its 1-based index
   Ƒ   -- is this list invariant under:
  Q    --   removing duplicates?

answered Mar 6, 2022 at 16:29

ovs

58.2k3 gold badges42 silver badges154 bronze badges

Add a comment |

friddo · Accepted Answer · 2022-03-06 23:23:46Z

5

Python 2, 42 bytes

-7 thanks to Jonathan :)

lambda n:n[len({a-n.index(a)for a in n}):]

Try it online!

edited Mar 6, 2022 at 23:23

answered Mar 6, 2022 at 16:33

friddo

5132 silver badges6 bronze badges

\$\begingroup\$ set(...) can be {...} saving three. \$\endgroup\$
– Jonathan Allan
Mar 6, 2022 at 20:13
\$\begingroup\$ Swap truthy and falsey outputs by replacing == with - for another. \$\endgroup\$
– Jonathan Allan
Mar 6, 2022 at 20:16
1

\$\begingroup\$ ...in fact, how about lambda n:n[len({a-n.index(a)for a in n}):] at 42 bytes, this will output an empty list (falsey) when playable and a non-empty list (truthy) when not playable. TIO \$\endgroup\$
– Jonathan Allan
Mar 6, 2022 at 20:19

Add a comment |

Andrew B · Accepted Answer · 2022-03-07 02:33:59Z

C# (Visual C# Interactive Compiler), 52 51 bytes

j=>j.Count==j.Select((x,y)=>y-x).Distinct().Count()

Try it online!

Nice thing about how verbose C# is is that it is makes the code relatively self-explanatory. The downside is that it makes it hard to golf in. Interactive Compiler C# lets us cheat a bit by removing all the boilerplate.

A technical breakdown: If we can show that two keys need to play at the same time, we know it cannot be played. This approach tackles this by determining when they should play and checking for any duplicates. If we store when they should play and make that list distinct, all duplicates will be removed, however, the number of elements in the list will decrease as a result. By comparing that count against the original's, we get the true/false value we need.

To do this, we use the index overload of Linq's Select. This use of Select converts our collection of integers into another collection of integers, but with different values, that is, the original value subtracted from its respective index. Distinct and Count are both self-explanatory.

Saved one byte by taking a List instead of int[]. 'Count' is a property on a List; the eqivalent on an array is 'Length,' which is one extra byte. On an IEnumerable, 'Count' is a function, which is why 'Count' at the end requires the parens. It's not the best naming choices, but I have no control over that.

att · Accepted Answer · 2022-03-06 23:52:00Z

4

Wolfram Language (Mathematica), 24 bytes

i!=##&@@(i=0;i++-#&/@#)&

Try it online!

                  &/@#  for each:
         i=0;i++-#        index minus value
i!=##&@@(             ) all distinct (and unequal to length)

edited Mar 6, 2022 at 23:52

answered Mar 6, 2022 at 22:06

att

19.8k2 gold badges14 silver badges56 bronze badges

Add a comment |

Sundar R · Accepted Answer · 2022-03-07 15:51:52Z

MATL, 9 8 bytes

tf-&=sqa

Try it online!

0 for 🎵🎶🎹
1 for broken keyboard leads to broken ❤️.

Explanation:

tf- : Subtract from each input element its (1-based) index
&= : Compare each value against the whole array, giving a boolean matrix
s : sum each column to get a row vector of sums
q : Decrement each sum by 1 to take away the self-equality 1s
a : Check if there are any non-zero values still

A more obvious way is tf- 8#uqa (count how many times each unique value occurs in input - indices and see if it's all 1), but unfortunately the need for space between - and 8 pushes it to 9 bytes.
Edit: Luis Mendo's answer on another question taught me the trick of & at the end, to print only the top of the stack, with which this can instead be tf-&uqa& - also 8 bytes. Only works on the current master of MATL though - neither TIO nor MATL Online have the &u feature available yet.

Another 9-byter is tf-&=XRaa.

Graham · Accepted Answer · 2022-03-06 17:04:24Z

3

APL+WIN, 20 bytes

Prompts for tune. 1=true, 0=false

0=+/2=/m[⍋m←n-⍳⍴n←⎕]

Try it online! Thanks to Dyalog Classic

edited Mar 6, 2022 at 17:04

answered Mar 6, 2022 at 16:13

Graham

5,47613 silver badges11 bronze badges

Add a comment |

Sundar R · Accepted Answer · 2022-03-06 21:57:28Z

3

Julia 1.0, 26 23 bytes

~v=allunique(v-keys(v))

Try it online!

-3 bytes thanks to @MarcMush

true for can be played, false otherwise.

edited Mar 6, 2022 at 21:57

answered Mar 6, 2022 at 20:54

Sundar R

6,61218 silver badges33 bronze badges

Add a comment |

Neil · Accepted Answer · 2022-03-06 15:54:36Z

Retina 0.8.2, 33 bytes

\d+(?=((,)|.)*)
$*1$#2$*
D`1+
,\B

Try it online! Link includes test cases. Outputs a truthy value if the tune can't be played and a falsy value if it can. Explanation:

\d+(?=((,)|.)*)

Match values but also count the number of following values.

$*1$#2$*

Convert to unary and add on the number of following values. (This is easier to do than subtracting from number of preceding values.)

D`1+

Delete duplicates.

,\B

Check for a deletion.

19 bytes in Retina 1:

\d+
*_$;&*
D`_+
,\B

Try it online! Link includes test cases. Explanation: In Retina 1 $;& automatically counts the number of remaining matches i.e. the number of following values.

Neil · Accepted Answer · 2022-03-06 16:00:19Z

2

Charcoal, 12 bytes

ＵＭθ⁻κι⊙θ⊖№θι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if the tune can't be played and nothing if it can. Explanation:

ＵＭθ⁻κι

Subtract each element's value from its index.

⊙θ⊖№θι

Check whether any of the results were duplicated.

answered Mar 6, 2022 at 16:00

Neil

166k12 gold badges69 silver badges273 bronze badges

Add a comment |

coltim · Accepted Answer · 2022-03-06 16:25:54Z

2

K (ngn/k), 11 bytes

{x~?x-:!#x}

Try it online!

!#x generate 0..len(input)
x-: subtract the above from the input, "inplace" (i.e. updating x)
x~? is the above composed of only distinct/unique values?

answered Mar 6, 2022 at 16:25

coltim

5,7735 silver badges13 bronze badges

Add a comment |

sinvec · Accepted Answer · 2022-03-07 00:13:53Z

2

Pyth, ^{13 12} 9 bytes

L{I.e-bkb

Try it online!

L{I.e-bkb

L           # lambda b:
   .e-bkb   # difference between each element in the list b and its index
 {          # removes duplicates in the list
  I         # invariant?

edited Mar 7, 2022 at 0:13

answered Mar 6, 2022 at 23:03

sinvec

1,8855 silver badges28 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-03-08 07:35:09Z

2

05AB1E, 5 bytes

ā-DÙQ

Try it online or verify all test cases.

Explanation:

ā      # Push a list in the range [1, input-length]
 -     # Subtract it from the values in the input at the same positions
       # Check if all values are unique:
  D    # Duplicate the list
   Ù   # Unquify the copy
    Q  # Check if both lists are still the same
       # (after which the result is output implicitly)

answered Mar 8, 2022 at 7:35

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-03-08 07:57:33Z

2

MathGolf, 7 bytes

h╒m-_▀=

Try it online.

Explanation:

h        # Push the length of the (implicit) input-array
 ╒       # Pop and push a list in the range [1,length]
  m-     # Subtract these values from the input at the same positions
    _    # Duplicate this list
     ▀   # Uniquify the values in the copy
      =  # Check if the two lists are still the same
         # (after which the entire stack is output implicitly as result)

answered Mar 8, 2022 at 7:57

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

Add a comment |

chunes · Accepted Answer · 2022-03-06 22:51:21Z

1

Factor, 31 bytes

[ [ - ] map-index all-unique? ]

Try it online!

[ - ] map-index Subtract each index from its element.
all-unique? Are they all unique?

answered Mar 6, 2022 at 22:51

chunes

22.8k3 gold badges21 silver badges51 bronze badges

Add a comment |

AZTECCO · Accepted Answer · 2022-03-07 13:23:04Z

1

Haskell, 45 bytes

f l|j<-zipWith(-)[1..]l=[x|x<-j,y<-j,x==y]==j

Try it online!

We put in j the tune as it would be played.
Then we check if its product has only j as duplicates using a list comprehension.

answered Mar 7, 2022 at 13:23

AZTECCO

10.6k1 gold badge13 silver badges58 bronze badges

Add a comment |

DLosc · Accepted Answer · 2022-03-07 16:02:33Z

1

Pip, 11 bytes

g#=UQ$-*ENg

Takes the numbers as separate command-line arguments. Attempt This Online!

Explanation

          g  ; List of command-line args
        EN   ; Enumerate: list of [index; element] pairs
     $-*     ; Fold each on subtraction, giving index-element
   UQ        ; Uniquify
 #=          ; Return truthy if the result is the same length as
g            ; the original list

answered Mar 7, 2022 at 16:02

DLosc

38k5 gold badges67 silver badges131 bronze badges

Add a comment |

robbie crockett · Accepted Answer · 2022-03-07 20:56:10Z

0

Matlab, 33 bytes

K=@(x)all(diff(sort(x-find(x))));

find(x) is the array of 1:length(x), and subtracting the index of each note from the notes value produces the new index of when the note is played. By sorting the resulting array and taking the diff of sequential values, we can determine if there is overlap by making sure that there are no 0 differences (indicating two values are overlapping)

Try it online!

answered Mar 7, 2022 at 20:56

robbie crockett

5823 silver badges5 bronze badges

Add a comment |

Stack Exchange Network

Can the Tune be Played?

Can the Tune be Played?

Explanation

Invalid Tune Example

Valid Tune Example

Task

Assumptions

Test Cases

Scoring

20 Answers 20

JavaScript (ES6), 30 bytes

Vyxal, 4 bytes

R, 34 bytes

Jelly, 4 bytes

Python 2, 42 bytes

C# (Visual C# Interactive Compiler), 52 51 bytes

Wolfram Language (Mathematica), 24 bytes

MATL, 9 8 bytes

APL+WIN, 20 bytes

Julia 1.0, 26 23 bytes

Retina 0.8.2, 33 bytes

Charcoal, 12 bytes

K (ngn/k), 11 bytes

Pyth, ^{13 12} 9 bytes

05AB1E, 5 bytes

MathGolf, 7 bytes

Factor, 31 bytes

Haskell, 45 bytes

Pip, 11 bytes

Explanation

Matlab, 33 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
decision-problem
or ask your own question.

Linked

Hot Network Questions

Can the Tune be Played?

Can the Tune be Played?

Explanation

Invalid Tune Example

Valid Tune Example

Task

Assumptions

Test Cases

Scoring

20 Answers 20

JavaScript (ES6), 30 bytes

Vyxal, 4 bytes

R, 34 bytes

Jelly, 4 bytes

Python 2, 42 bytes

C# (Visual C# Interactive Compiler), 52 51 bytes

Wolfram Language (Mathematica), 24 bytes

MATL, 9 8 bytes

APL+WIN, 20 bytes

Julia 1.0, 26 23 bytes

Retina 0.8.2, 33 bytes

Charcoal, 12 bytes

K (ngn/k), 11 bytes

Pyth, 13 12 9 bytes

05AB1E, 5 bytes

MathGolf, 7 bytes

Factor, 31 bytes

Haskell, 45 bytes

Pip, 11 bytes

Explanation

Matlab, 33 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Pyth, ^{13 12} 9 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
decision-problem
or ask your own question.