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:

1. 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.
2. 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: It must be so much fun playing on this keyboard! :p
• Sundar R: @Arnauld Tricky constraints that make simple tasks difficult? Surely nothing familiar to us code golfers! :D
• tsh: Will all input number always be unique? If not, consider add some testcase for it.
• Lecdi: @tsh I've added some extra test cases
• Steve Bennett: 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.

Answer 1

JavaScript (ES6), 30 bytes

Returns a Boolean value.

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

Try it online!

• ophact: Wow, that was fast.

Answer 2

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)

Answer 3

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!

Answer 4

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?

Answer 5

Python 2, 42 bytes

-7 thanks to Jonathan :)

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

Try it online!

• Jonathan Allan: set(...) can be {...} saving three.
• Jonathan Allan: Swap truthy and falsey outputs by replacing == with - for another.
• Jonathan Allan: ...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

Answer 6

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.

Answer 7

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)

Answer 8

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.

Answer 9

APL+WIN, 20 bytes

Prompts for tune. 1=true, 0=false

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

Try it online! Thanks to Dyalog Classic

Answer 10

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.

Answer 11

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.

Answer 12

Charcoal, 12 bytes

UMθ−κι⊙θ⊖Noθι

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:

UMθ−κι

Subtract each element's value from its index.

⊙θ⊖Noθι

Check whether any of the results were duplicated.

Answer 13

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?

Answer 14

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?

Answer 15

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)

Answer 16

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)

Answer 17

Factor, 31 bytes

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

Try it online!

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

Answer 18

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.

Answer 19

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

Answer 20

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!