24
\$\begingroup\$

Challenge

Premise

Bob is a novice pianist who can only play sequences of single notes. In addition, he does quite an interesting thing: for every note after the first, if it's higher than the previous note was, he uses the finger directly to the right of the previous finger used; if lower, to the left; if the same pitch, well, the same finger.

Let's take Auld Lang Syne as an example, and arbitrarily suppose, only for the sake of this example, that Bob uses the very right side of his right hand.

Pitch: Should < auld = ac- = quain- < tance > be > for- < got
Digit: mid      ring   ring  ring     pinky   ring mid    ring

Alice wants to convince him of the stupidity of his playing...

Task

Input: a sequence of \$n\$ MIDI note numbers (which are integers between 0 and 127 inclusive), where \$2\leq n\leq10000\$.

Output: the number of fingers required to finish the melody with the playing style outlined in 'Premise'.

Please note that the answer may be more than 5.

No consideration of the starting finger is needed. Assume that the choice is optimal for playable melodies and has nothing (else) to do with the number of fingers required.

Example 1

Input: 0 0 0 0

Output: 1

Example 2

Input: 43 48 48 48 52 50 48 50

Output: 3

Example 3

Input: 86 88 84 81 83 79 74 76 72 69 71 67 62 64 60 57 59 57 56 55

Output: 9

Example 4

Input: 82 79 78 76 78 76 74 73 70 67 66 64 66 64 62 61

Output: 12

Remarks

\$\endgroup\$
  • \$\begingroup\$ Does the human have 4 fingers to the left and to the right of the middle one? \$\endgroup\$ – the default. Apr 21 at 15:10
  • \$\begingroup\$ The question addresses your concern in more than one way... (Please see 'arbitrarily suppose for the sake of this example', 'may not assume'.) \$\endgroup\$ – subdermatoglyphic Apr 21 at 15:15
  • 6
    \$\begingroup\$ You may not assume the answer is no more than 5 Suggested wording: Note that the answer may be more than 5 \$\endgroup\$ – Luis Mendo Apr 21 at 16:13
  • 1
    \$\begingroup\$ @mypronounismonicareinstate Yes, if you swap your thumbs with your middle finger and connect both of your hands. \$\endgroup\$ – user92069 Apr 22 at 9:20
  • 2
    \$\begingroup\$ @JDL Edited. Bob would in fact first work out which finger would be best, albeit, if we want to be really realistic, by trial and error. Starting with the right middle finger was just for the sake of the example in 'Premise'! \$\endgroup\$ – subdermatoglyphic Apr 22 at 13:43

17 Answers 17

13
\$\begingroup\$

Perl 6, 27 bytes

{+minmax [\+] @_ Z<=>0,|@_}

Try it online!

Explanation

@_ Z<=>0,|@_ uses the zip metaoperator (Z) with the compare operator (<=>) to zip the list with itself offset by 1 and return the result of the comparison., e.g. [43, 48, 48, 48, 52, 50, 48, 50] -> (More More Same Same More Less Less More)

[\+] Reduces the list by summing over it (More = 1, Same = 0, Less = -1), however the \ does a 'triangular reduction' which produces a list of each calculation instead of the end result, e.g. (More More Same Same More Less Less More) -> (More 2 2 2 3 2 1 2)

minmax returns the range of smallest..largest, effectively removing duplicates. (More 2 2 2 3 2 1 2) -> Order::More..3

+ just returns the length of this range (list), which is the result

| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

05AB1E, 8 bytes

¥.±ŒOÄZ>

Try it online!


Explanation

¥              - Get the differences 
 .±            - Get the signs of these (so if they go up or down)    
   ŒO          - Sum the sublists of these 
     ÄZ        - And find the biggest absolute change
       >       - Add one (since we need a finger to play the first note)
| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

Python 3.8, 64 63 57 bytes

-6 bytes thanks to @xnor's abuse of walrus!

lambda l,t=0,a=0:len({(t:=t+(a<b)-(a>(a:=b)))for b in l})

Try it online!

A function that takes input l as a list of integers, and returns the number of fingers needed.

How:

t keeps track of the current finger (represented by an integer). For each 2 consecutive notes a, b, the finger is increased by -1, 0, or 1 depending on whether a>b, a==b or a<b:

t:=t+(a<b)-(a>b)

All values of t are then gathered into a set, whose size is the number of unique fingers.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ More walrus shenanigans: Try it online! \$\endgroup\$ – xnor Apr 22 at 4:25
6
\$\begingroup\$

R, 45 42 bytes

`?`=diff;1+?range(0,cumsum(sign(?scan())))

Try it online!

Thanks to JDL for -3 bytes.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ range accepts arbitrarily many arguments, so I think you can do range(0,cumsum(sign(?scan())) instead of what you have (saves three characters for the call to c()) \$\endgroup\$ – JDL Apr 22 at 13:39
6
\$\begingroup\$

FRACTRAN 29 fractions (244 bytes)

7*61/2^129*59 3*61/2*59 47/59 59/61 2*53/7*47 31/47 47/53 7*37/2^129*31
17/31 31/37 67/2^128*17 5*19/2*3*17 5*11*23/2*13*17 5*11*23/2*17 13*23/3*11*17
13*23/3*17 41/17 17/19 29/3*23 41/23 23/29 3*43/5*41 3*43/2*41 47/41
41/43 2/67 1/3 2/13 2/11

Input: \$59\cdot 2^n\$, where \$n\$ is the MIDI list (terminated in the sentinel 128) in base-129. That is, if the list is \$\{n_0, n_1, n_2, \dots, n_m\}\$, then \$n=n_0 + 129n_1 + 129^2n_2 + \cdots + 129^{m}n_m + 129^{m+1}\cdot 128\$.

Output: \$2^k\$, where \$k\$ is the number of necessary fingers.


To try this online, the interpreter at https://pimlu.github.io/fractran/ is able to evaluate the program relatively quickly, and it takes the program in the following syntax:

7*61%2^129*59
3*61%2*59
47%59
59%61
2*53%7*47
31%47
47%53
7*37%2^129*31
17%31
31%37
67%2^128*17
5*19%2*3*17
5*11*23%2*13*17
5*11*23%2*17
13*23%3*11*17
13*23%3*17
41%17
17%19
29%3*23
41%23
23%29
3*43%5*41
3*43%2*41
47%41
41%43
2%67
1%3
2%13
2%11

For the four examples, the program accepts this syntax for the input:

[59, 1], [2, 35446128768]
[59, 1], [2, 9845790461648320003]
[59, 1], [2, 209150948383325817811492382511176427430698872]
[59, 1], [2, 755543512556056338685630134436248304]

These are prime factorizations, saving having to multiply out the gigantic exponentials.

How does it work?

In FRACTRAN, there is a state, which is initially set to the input value. The state is multiplied by each fraction one at a time, and if any results in a whole number, that number replaces the state and the program returns to the beginning of the list. If no fractions apply in this way, then the state is output and the program halts.

This is a terse way of describing a register machine. By prime factorizing everything, a fraction like 75/7 = 3*5^2/7 means "if register seven is at least 1, then decrement it and add 1 to register three and 2 to register five."

Each prime in the program can be given a descriptive name, like 3 is 'a' and 59 is 'line1'. The rest don't particularly matter, since I'll give a disassembled version of the program, and you could figure out the rest of the assignments if you really wanted. Each line is like a chemical reaction; for example, the first line means "if line1 >= 1 and a >= 129, then decrement line1 by 1, decrement a by 129, increment line1r by 1, and increment adiv1 by 1."

0. line1 + 129 a -> line1r + adiv
1. line1 + a -> line1r + b
2. line1 -> line3
3. line1r -> line1
4. line3 + adiv -> line3r + a
5. line3 -> line4
6. line3r -> line3
7. line4 + 129 a -> line4r + adiv
8. line4 -> line5
9. line4r -> line4
10. line5 + 128 a -> line8
11. line5 + a + b -> line5r + c
12. line5 + a + MAX -> line6 + c + MIN
13. line5 + a -> line6 + c + MIN
14. line5 + b + MIN -> line6 + MAX
15. line5 + b -> line6 + MAX
16. line5 -> line7
17. line5r -> line5
18. line6 + b -> line6r
19. line6 -> line7
20. line6r -> line6
21. line7 + c -> line7r + b
22. line7 + a -> line7r + b
23. line7 -> line3
24. line7r -> line7
25. line8 -> a
26. b -> 0
27. MAX -> a
28. MIN -> a

So, here's an analysis. At the beginning, the input is line1 + n a. This means, the first relevant part of the program is

0. line1 + 129 a -> line1r + adiv
1. line1 + a -> line1r + b
2. line1 -> line3
3. line1r -> line1

which reduces the a register mod 129, putting the quotient in adiv and the remainder into b, which serves as a register to hold the previous MIDI note, which in this case is the very first one. Once this is done, it continues onto

4. line3 + adiv -> line3r + a
5. line3 -> line4
6. line3r -> line3

which moves adiv back into the a register, and for the main loop the a register starts with the remaining part of the MIDI list. Then,

7. line4 + 129 a -> line4r + adiv
8. line4 -> line5
9. line4r -> line4

The MIDI list is reduced mod 129, putting the rest of the list into adiv, leaving the MIDI note in the a register. This continues on to the the core calculation loop.

10. line5 + 128 a -> line8
11. line5 + a + b -> line5r + c
12. line5 + a + MAX -> line6 + c + MIN
13. line5 + a -> line6 + c + MIN
14. line5 + b + MIN -> line6 + MAX
15. line5 + b -> line6 + MAX
16. line5 -> line7
17. line5r -> line5

Reaction 10 detects if the sentinel 128 has occured, in which case it goes to line8 (the cleanup routine). Otherwise, we begin the comparison of a with b, to see which is larger. There are two registers MAX and MIN, representing the maximum and minimum relative finger numbers relative to note b so far. If a is greater than b, then we need to decrement MAX and increment MIN; if MAX is zero, then we don't decrement it, since this has the effect of widening the necessary number of fingers. Similarly, if b is greater than a, we need to decrement MIN (if nonzero) and increment MAX.

The comparison works by decrementing both a and b until one of them is zero. We will need the a register later on, to store it back into b, so whenever we decrement a, we increment a temporary variable c. Reaction 11 decrements a and b if they are both nonzero. Past this point, we know either b=0 or a=0. Reactions 12 and 13 are for the b=0 case, implementing the decrement-MAX-if-nonzero operation, and reactions 14 and 15 are for a=0. Reaction 16 is when a and be were equal.

If a and b were unequal in some way, then b is zeroed out with the following block

18. line6 + b -> line6r
19. line6 -> line7
20. line6r -> line6

And, along with the a=b case, this continues on to

21. line7 + c -> line7r + b
22. line7 + a -> line7r + b
23. line7 -> line3
24. line7r -> line7

which stores a+c into b, clearing a and c in the process. This has the effect of copying the original value of a at the start of the main loop into b. From here, we return to line3 to set up the main loop.

At the very end, once the sentinel is detected, the following block is run.

25. line8 -> a
26. b -> 0
27. MAX -> a
28. MIN -> a

Since the sentinel detection subtracts 128 from a, we know a is zero when entering this block. Then, the value of 1 + MAX + MIN is stored into a, and the value of b is cleared out. Once done, no other reactions apply, and the program terminates with the number of necessary fingers in the a register.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6),  55 53  52 bytes

a=>a.map(o=v=>o[i+=-(a>v)|a<(a=v)]=n+=!o[i],i=n=0)|n

Try it online!

Commented

a =>                // a[] = input array of notes, re-used to store
  a.map(            //       the previous finger index
    o =             // o = object used to store the fingers
    v =>            // for each note v in a[]:
    o[              //   update o[i]:
      i +=          //     update i:
        -(a > v) |  //       decrement i if the previous value is greater than v
        a < (a = v) //       increment i if it's lower than v; and update a to v
    ] =             //       (if a = v or a is non-numeric, i is left unchanged)
      n += !o[i],   //     mark this finger as used and increment n if it was
                    //     not already used
    i = n = 0       //   start with i = n = 0
  ) | n             // end of map(); return n
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Perl 5 -MList::Util=uniq -pa, 35 bytes

$_=uniq map{$c+=$_<=>$p;$p=$_;$c}@F

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Io, 107 105 bytes

-2 bytes after using "push" instead of "append".

method(x,(r :=x slice(0,-1)map(i,v,(v-x at(i+1))compare(0)))map(i,v,r slice(0,i+1)sum)push(0)unique size)

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 53 46 bytes

Tr[1^{0}~Union~Accumulate@Sign@Differences@#]&

Try it online!

Thanks to @J42161217 for pointing out that Tr[1^list] is a 1-character-shorter alternative to Length@list.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 52 bytes \$\endgroup\$ – J42161217 May 5 at 6:07
  • \$\begingroup\$ @J42161217 Thanks for the trick. Pairing that with multi-argument Union shaves off a few more bytes. \$\endgroup\$ – Kyle Miller May 5 at 20:05
1
\$\begingroup\$

Retina, 76 bytes

\d+
*_:$&*
+`_=_
=
=_
<
_=
>
[_:=]

Lw$`(.)(?>(\1)|(?<-2>.))*
_$#2*
O^`
1G`

Try it online! Link includes test suite. Takes input as a =-separated list of integers (I could have used space or , but = was prettier) but the test suite adapts the space-separated test cases to work with the code. Explanation:

\d+
*_:$&*

Convert each integer to unary in duplicate.

+`_=_
=

Subtract pairs of adjacent integers.

=_
<
_=
>

Note whether adjacent integers were ascending or descending.

[_:=]

Delete everything else.

Lw$`(.)(?>(\1)|(?<-2>.))*
_$#2*

Find runs of notes. Runs can be interrupted by a reverse run as long as the run does not return to its starting finger; this is achieved via the .NET regexp balancing group construct (?<-2>.). The run always starts with an ascending or descending pair which requires two fingers; since one finger is added at the end to handle the degenerate case where only one note is played, only one finger is added here, resulting in the number of additional fingers required for this run. The w modifier allows all valid runs to be collected.

O^`

Sort the longest number of fingers to the start.

1G`

Consider only the longest number of fingers. (I would count the longest fingers using \G.? but that doesn't work for some reason.)


Convert back to decimal and add one for the starting finger.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Husk, 11 bytes

→▲mamΣQm±Ẋ-

Port of @ExpiredData's 05AB1E answer, so make sure to upvote him!

Try it online.

Explanation:

         Ẋ   # For each overlapping pair of the (implicit) argument:
          -  #  Subtract them from one another
       m     # Then map over each forward difference:
        ±    #  And take its signum (-1 if <0; 0 if 0; 1 if >0)
      Q      # Get all sublists of those
    m        # Map over each sublist:
     Σ       #  And take its sum
  m          # Map over each sum:
   a         #  And take its absolute value
 ▲           # Then take the maximum of this list
→            # Increase it by 1
             # (after which it is output implicitly as result)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

[C#], 86 bytes

s.Aggregate(0,(i,y)=>{var t=z>y?++i:z<y?--i:i;h[i]=1;z=y;return t;});return h.Count();

Try It online!

My goal was to do this using the Linq Aggregate function, but surely not the best way.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

J, 36 18 bytes

Bubbler managed to shave off a full 50% off my program with a few nice tricks and some deft handling of trains.

0#@=@(,+/\)2*@-/\]

Try it online!

The dyadic verb *@-/\ takes a prefix size and a list, then computes the sign of the difference of the list (from inserting - between elements of the list). In this case, it is used as 2 *@-/\ ], which is a fork that takes a list and gives a list of the signs of differences between adjacent elements. (This is an idiom I hoped would exist but couldn't come up with myself.)

Letting d denote this result, the rest of the train is 0 #@=@(, +/\) d, which is equivalent to # = (0 , +/\ d). First, +/\ d computes the sum of each prefix of d, which like in the previous answer gives a relative finger numbering of all notes of the song. But, since the differences only give relative differences, the fingering of the first note is not present, so zero is prefixed to the list with the , dyad.

For some reason I thought I had to take one more than the difference of the maximum and minimum values of this array to count the number of necessary fingers, despite the fact all I had to do was count the number of distinct elements, which would be # ~. of the array. However, J has a one-character shorter idiom for this. The = monad gives an array with one row per unique element (the rows indicating where that element appears), and the # monad counts the number of rows, hence the number of necessary fingers.


The original 36-byte solution:

1:+(>./-<./)@(0&,)@(+/\)@(}.(*@-)}:)

Try it online!

This is a monadic verb that takes a list of numbers.

*@- takes the sign of the difference of two numbers. Since }. and }: cut off the head and tail of a list, the fork }. (*@-) }: constructs a list of signs of differences between consecutive elements of the given list.

This is composed with +/\, which takes the sums of the prefixes of the list, giving relative finger numbers through the song. This is prefixed with 0 using 0&, since the song starts with some finger.

This is composed with >./ - <./, which takes the difference of the maximum and the minimum of these relative finger numbers, and then the 1:+ fixes a fencepost error: we start counting fingers from 1.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 25 bytes. Check out J golfing tips. \$\endgroup\$ – Bubbler Apr 22 at 1:16
  • 2
    \$\begingroup\$ 19 bytes by directly counting unique numbers. \$\endgroup\$ – Bubbler Apr 22 at 1:22
  • 4
    \$\begingroup\$ 18 bytes using self-classify =. \$\endgroup\$ – Bubbler Apr 22 at 1:39
  • \$\begingroup\$ @Bubbler Nice solution! I hope you don't mind I updated my answer to explain it. \$\endgroup\$ – Kyle Miller Apr 22 at 20:00
1
\$\begingroup\$

PHP, 66 59 bytes

for(;$b=$argv[++$i];$a=$b)$f[$n+=$b<=>$a]=1;echo count($f);

Try it online!

Pretty straightforward: uses a index counter $n which is incremented each time a superior note is to play and decremented when a lower note, with the PHP comparison operator <=>. Then an array is set to the value 1 at this index. At the end count the array.

EDIT: saved 7 bytes removing the test on $i, we actually don't care if the starting value for $n is 0 or 1

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

T-SQL, 125 bytes

Input is taken from table T (according to the Code Golf rules for SQL): column P represents position and column V represents the value.

SELECT MAX(S)-MIN(S)+1FROM(SELECT*,SUM(ISNULL(X,0))OVER(ORDER BY P)S FROM(SELECT*,SIGN(V-LAG(V)OVER(ORDER BY P))X FROM T)A)B

DB Fiddle

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Japt, 8 bytes

Port of Expired Data's solution.

äÎãx rÔÄ

Try it

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Stax, 11 bytes

£→▓J←εm@φ┤»

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

                                    input:[43 48 48 48 52 50 48 50]
:-      get pairwise differences    main:[5, 0, 0, 4, -2, -2, 2] 
Z+      prepend a 0                 main:[0, 5, 0, 0, 4, -2, -2, 2] 
{:+m    map: numeric sign           main:[0, 1, 0, 0, 1, -1, -1, 1] 
:+      prefix sums                 main:[0, 1, 1, 1, 2, 1, 0, 1] 
:s^     max - min + 1               main:3 

Run this one

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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