text:
Parse a Baseball Pitch String
Take an arbitrarily sized string as input. This string represents a baseball plate appearance, in which each character represents a pitch as follows:

Strike: S
Ball: B
Foul ball: F
Hit by pitch: H
Ball in play: X

(For those wondering, this is a very very simplified version of Retrosheet's notation)

Your program must output 1 of 3 possible outputs to signify 1 of the mutually exclusive outcomes:

Strikeout
Walk
Ball in play

It doesn't matter what the outputs are exactly, as long as they are guaranteed to be distinct.

For those unfamiliar with the rules of baseball:

3 strikes results in a strikeout
4 balls results in a walk
A foul ball is a strike UNLESS the batter already has 2 strikes, in that case nothing happens
Hit by pitch immediately results in a walk
"Ball in play" immediately results in the "Ball in play" outcome

You may assume that:

the input string is encoded as ASCII
the input string represents an entire plate appearance (in other words it will end in one of the 3 outcomes above)
there are no other characters other than the ones above

You may not assume that:

there are no extra pitches/characters after the plate appearance is supposed to legally end
your program must return on the last pitch/character

Examples:
"Strikeout"fy:
SSS
SBSBS
BBBSSS
BSBSBS
BSFFBFS
BBSSFFFFFFFFS
SSSBBBB
FSS

"Walk"y:
BBBFB
BBBB
BBBSB
SSBBBB
SSH
SBSFFBFFFFBFFFFFFFFB
BBBBSSS
HSSS
SBBBBSS

"Ball in play"ly:
X
SSX
BBBX
SBSX
FFFFFFFFFFFFFFX
XBSBSBSB

This is code-golf, so fewest bytes wins.
(This challenge was inspired by this YouTube video)

How does XBSBSBSB work? The ball's in play, and then there's a strikeout, and then a fourth ball and it ends up in play?

@Noodle9 "You may not assume that there are no extra pitches/characters after the plate appearance is supposed to legally end." This is a dirty input case. Your program should return after parsing the X, effectively ignoring the rest of the characters.

@Giuseppe uh... that's this question...

oh, duh, I meant this one is closely related.

Is it OK to return different values for the same outcome, as long as it's different from the values for the other outcomes? (see my 64-byte version)

Can we use an input translation like S = 1, B = 2, ... and then take a list of ints as input?

It seems everything about the ball in play is missing.  I don't know baseball terminology so I have no idea what sort of state this even indicates.  Could you explain this for people who don't know baseball terminology?

@dan9er I've added a couple of test cases and attempted to clarify the behaviour of "Ball in play" according to my understanding. Let me know if I misunderstood anything and I can change it back

May we take the input as lowercase instead of uppercase characters?

What does this mean: "You must not asumme that: ... your program must return on the last pitch/character" ? I can't find any sensible interpretation for this sentence?

Retina 0.8.2, 22 bytes
4=`B
H
2`F|S

1!`[XHS]

Try it online! Link includes test cases. Outputs X for ball in play, H for walk, and S for strikeout. Explanation:
4=`B
H

The fourth ball results in a walk, same as hit by pitch.
2`F|S

The first two foul balls/strikes are ignored.
1!`[XHS]

Take the first available result.

JavaScript (ES9),  68 66  55 bytes
Saved 11 bytes thanks to @Neil!
Returns \$S\$ for Strikeout, \$X\$ for Ball in play or an empty string for Walk.
s=>/(?<=(B.*){4})|(?=H)|X|(?<=([SF].*){2})S/.exec(s)[0]

Try it online!
How?
We match either:

(?<=(B.*){4}) : an empty string preceded by 4 B's
(?=H) : an empty string followed by an H
X : the character X
(?<=([SF].*){2})S : an S preceded by 2 other strike characters (S or F)

As a result, we get an S for a Strikeout, an X for a Ball in play, or an empty string for a Walk.

(S|F) can be [SF], but if S, X and (empty string) are acceptable outputs, you can just use s=>/(?<=(B.*){4})|(?=H)|X|(?<=([SF].*){2})S/.exec(s)[0].

I have a "SyntaxError: invalid regexp group" (because non-fixed width lookbehind it seems) when I try in the console or in Regex101 (or with PHP, no I swear I wasn't about to port the answer).. How can it work for NodeJS?

@Kaddath This should work fine in recent versions of Chrome, Edge or Node, but not yet in Firefox.

And so should I conclude that ES9 supports non-fixed width lookbehinds (although not on all browsers) while PCRE doesn't?

@Kaddath I think so, but I didn't check the ECAMScript spec.

Looks like the first two lookarounds can be merged: 51.

Python 3, 90 88 86 85 bytes
-2 bytes thanks to @ovs
s=b=0
for i in map(ord,input()):s+=~i%2*~s*i%71<3;b+=i<67;b//4+s//3==i%4//2>exit(i%6)

Try it online!
Returns via exit code: 0 for a walk, 4 for ball-in-play, and 5 for a strikeout.

The last statement can be b//4+s//3>=(i%8<1)>exit(i%6) for -2.

@ovs Thanks! I had to adjust it slightly to get it to work, but I used the same idea

SNOBOL4 (CSNOBOL4), 172 bytes
	I =INPUT
N	I LEN(1) . P REM . I	:($P)
S	S =LT(S,2) S + 1	:F(K)S(N)
B	B =LT(B,3) B + 1	:F(H)S(N)
F	S =LT(S,2) S + 1	:(N)
X	OUTPUT =0	:(E)
K	OUTPUT =1	:(E)
H	OUTPUT =2
E
END

Try it online!
0 for a ball in play, 1 for a strikeout, and 2 for a walk.
gosh, I miss baseball :-(
Thanks to Mitchell Spector for pointing out several bugs!

I like seeing a SNOBOL answer, but this seems to be incorrect for SSBBBBS -- it says it's a strike-out, but it should be a walk.
https://tio.run/##VY0xC8IwEIXny6@4wSGHRUx1KmQJXiG0xuCltLOz2MH/T4wtFnzLHd/H471f82N@nnMGj9aHOCQVyttz0IbwgBHvfC3XQ6N3kZSAoO1ZS1UTCu7RQNPqjkQHUg7cIl11InQ/Oa6yXZrpr/nlE9yGVHbRHgtgUt0GzArGDdSKFYdLziKuRD4

@MitchellSpector I think the LE(B,3) should be LT(B,3). I've always had trouble with off-by-one issues.

I see what you're doing now -- it looks good.  The only issue remaining is not handling H (batter hit by pitch), but that's easily taken care of!

@MitchellSpector thanks, sorry, it's been a busy few weeks.

05AB1E, 28 26 24 22 20 bytes
Ç.Δ6Ö½$¾4@N¾Ì@)yè}6%

Try it online!
Outputs 5 for strike out, 0 for walk, or 4 for ball in play.
Ç                   # convert the input to a list of ASCII codepoints
 .Δ              }  # find the first codepoint y such that:
   6Ö               #  is y divisible by 6? (true for B and H only)
     ½              #  if yes, increment the counter variable c
      $             #  push 1 and input
       ¾4@          #  is c >= 4?
          N¾Ì@      #  is the iteration count N >= c + 2?
              )     #  wrap the stack in a list: [1, input, c >= 4, N >= v + 2]
               yè   #  get the y-th element of that list (wraps around)

# * H and X are mapped to 1, so those characters always result in a match
# * nothing is mapped to `input`, it's just there to pad the list
# * B and F are mapped to `c >= 4`, so the 4th B results in a match (this would also
#   match HBBB or BBBBF, but we stop after the first match, so that's irrelevant)
# * S is mapped to `N >= c + 2`, so an S matches if it's preceded by at least 2 characters not in (B, H)

6%                  # after the loop: modulo 6 (B => 0, H => 0, S => 5, X => 4)

Very nice! Got a lot of small things that makes the total great. :) Like the $ to push a 1 for both X and H, as well as a filler value (the input) that won't be indexed. Or the 6Ö½ to only increase the counter variable for H and B.

C (gcc), 124 \$\cdots\$ 87 86 bytes
Saved 12 13 bytes thanks to ceilingcat!!!
Saved 6 bytes thanks to dingledooper!!!
c;b;s;f(char*p){for(b=s=0;c=*p++-66,s+=c==4&s<2|c==17,b+=!c,c!=6&b<4&s<3&c<22;);c%=3;}

Try it online!
Returns \$0\$ for a walk, \$1\$ for a ball in play, and \$2\$ for a strikeout.

Retina 0.8.2, 42 41 bytes
Thanks to @Neil for saving a byte!
(?<=(B.*){3})B
H
1!`X|H|(?<=([SF].*){2})S

Try it online!
Based on @Arnauld's JavaScript answer.
Returns X for ball-in-play, H for a walk, and S for a strikeout.

(S|F) can be [SF].

Io, 142 bytes
Returns 0 for a strikeout, 5 for a walk, 4 for a ball-in-play.
method(I, s :=b :=0
I foreach(i,s=s+i%2+if((s-1)*i%69<3,1,0);b=b+if(i<67,1,0);if(((b/4)floor!=0)or(i%8<1)or((s/3)floor!=0),System exit(i%6))))

Try it online!

121 bytes: Try it online! (Note that strikeout returns 5, walk returns 0 for this one)

05AB1E, 32 bytes
ηε.•Çšy•uS¢`+3@y'SÅ¿*·s4@r;M}0Kн

Outputs 2 for Strikeout; 1 for Walk; and 0.5 for Ball in play.
Try it online or verify all test cases.
Could be 31 bytes by removing the u if we can take the input as lowercase.
Explanation:
η              # Get all prefixed of the (implicit) input-string
 ε             # Map each prefix to:
  .•Çšy•       #  Push compressed string "xhbsf"
        u      #  Convert it to uppercase: "XHBSF"
         S     #  Convert it to a list of characters: ["X","H","B","S","F"]
          ¢    #  Count each character in the current prefix-string
  `            #  Push the counts separated to the stack
   +           #  Add the counts of "S" and "F" together
    3@         #  Check that it's >= 3
           *   #  And:
      y'SÅ¿   '#  Check whether the current prefix ends with an "S"
            ·  #  And double this combined check (so 2 if truthy; 0 if falsey)
   s           #  Swap so the count of 'B' is at the top of the stack
    4@         #  Check that it's >= 4 (1 if truthy; 0 if falsey)
   r           #  Reverse the stack, so the count of 'X' is at the top of the stack
    ;          #  Halve it (0.5 if truthy; 0.0 if falsey)
  M            #  Push the largest value of the stack
 }0K           # After the map: remove all 0s
    н          # And pop and push the first value of the list
               # (after which it is output implicitly as result)

Note that this assumes the count of "H" and "X" can never be larger than 1, which we can due to the assumptions mentioned in the challenge description.
See this 05AB1E tip of mine (section How to compress strings not part of the dictionary?) to understand why .•Çšy• is "xhbsf".

20 with a different approach

sed -E, 69 60 59 bytes
s/([FS][^FS]*){2}S/&K/;s/([^B]*B){4}/&H/;s/[^KHX]*(.).*/\1/

Try it online!
9 bytes off, thanks to math junkie.
Input on stdin.
Output on stdout: H for walk, K for strikeout, X for in play.

I think you can save some bytes by returning H and X instead of w and p. I don't know sed too well though, so I could be wrong

@mathjunkie Good idea -- thanks!

[C#], 147 bytes
d=(p,s,b,i)=>{var P=p[i];int t=0;if(P=='B')b++;if(P=='S'||(P=='F'&&s<2))s++;if(P=='H'||b>3)t=2;if(P=='X')t=3;if(s>2)t=1;return t!=0?t:d(p,s,b,++i);};

Try It online!
Return values: 1 = Strikeout, 2 = Walk, 3 = Ball in play.
(I wanted to use recursion for this answer, for learning)

Hi, welcome to CGCC! If you're using a recursive method, the d= should be counted towards the byte-count as well, so this is actually 149 bytes. But, you can golf this to 122 bytes by nesting ternary-ifs; changing the characters to code-point integers for the checks; and changing all || and && to | and & respectively (except for the || in P=='S'||(P=='F'&&s<2), since we need it to get rid of the parenthesis).

Also, if you haven't seen it yet, tips for golfing in C# and tips for golfing in  might both be interesting to read through. Enjoy your stay! :)

Thanks Kevin, I just saw this, I'll check it out, and improve my answer!

119 bytes

Z80Golf, 49 bytes
00000000: 0603 0e04 cd03 80fe 5320 0105 fe42 2001  ........S ...B .
00000010: 0dfe 4620 0310 0104 fe48 2001 4afe 5828  ..F .....H .J.X(
00000020: 0caf b93e 5728 06af b820 d93e 53cd 0080  ...>W(... .>S...
00000030: 76                                       v

Try it online!
Prints W for walk, S for strikeout, and X for ball in play.
Ungolfed
        ld b,3  ; number of strikes until strikeout
        ld c,4  ; number of balls until walk
input:
        call $8003      ; A = next character from stdin
strike:
        ; if A == 'S', record a strike
        cp 'S'
        jr nz,ball
        dec b
ball:
        ; if A == 'B', record a ball
        cp 'B'
        jr nz, foul
        dec c
foul:
        ; if A == 'F',
        cp 'F'
        jr nz, hit_by_pitch
        ; record a strike
        ; jump to the next section if batter hasn't struck out
        djnz hit_by_pitch
        ; if batter has struck out, give them another chance
        ; foul balls can't strike out a batter
        inc b
hit_by_pitch:
        cp 'H'
        jr nz, ball_in_play
        ld c, d ; d is initialized to 0 by default
ball_in_play:
        cp 'X'
        jr z, exit
walk:
        xor a   ; 1 byte shorter than ld a, 0
        cp c
        ld a, 'W'
        jr z, exit
strikeout:
        xor a
        cp b
        jr nz, input
        ld a, 'S'
exit:
        call $8000
        halt

Charcoal, 52 bytes
≔⪪Ｓ¹θＦ⪪B34HF02SS02F⁴Ｆ✂⌕Ａθ§ι⁰Ｉ§ι¹Ｉ§ι²§≔θκ§ι³§Φθ№XHSι⁰

Try it online! Link is to verbose version of code. Outputs X, H or S as appropriate. Explanation:
≔⪪Ｓ¹θ

Split the input string into an array of characters. (If that is a legal input format, then these 5 bytes could be removed, but it would be really hard to enter in any of the examples.)
Ｆ⪪B34HF02SS02F⁴

Iterate over a string literal which encodes the following rules: The fourth Ball counts as a Hit by pitch. The first two Fouls might count as Strikes. The first two Fouls or Strikes don't strike the batsman out so turn them back into Fouls.
Ｆ✂⌕Ａθ§ι⁰Ｉ§ι¹Ｉ§ι²

Find the range of matches of the source character that we're interested in.
§≔θκ

Update those matches with the destination character.
§ι³§Φθ№XHSι⁰

Filter out all characters except X, H and S and output the first remaining character.

Javascript, 84 characters
z=>{y={B:-1,S:i=0,F:0};while(c=z[i++],d={H:'B',F:'S'}[c]||c,y[d]++,y[c]<3);return d}

Returns S, X or B for a strike-out, on-base or walk.
Auto-formatted version:
f = (z) => {
    y = { B: -1, S: (i = 0), F: 0 };
    while (((c = z[i++]), (d = { H: 'B', F: 'S' }[c] || c), y[d]++, y[c] < 3));
    return d;
};

Foxrabbit's Finite-State Binary (FSB), 57 bytes
The 57 bytes in hexadecimal are:
01
04 43 04 01
06 47 08 02
06 49 0c 03
06 54 09 0c
00 00 05 05
02 04 06 07
01 00 00 00
02 48 07 0c
01 02 0a 0b
01 00 0a 0a
02 03 0b 0c
00 00 00 00
05 00 0d 0d
07 00 0d 0d

Assumes an ASCII-superset environment. Outputs a single byte with value 3 for strike-out, value 72 (ASCII 'H') for walk, or value 88 (ASCII 'X') for ball in play.
As an FFM program:
Get;inp;67;Ball:NotB
NotB;nop;71;Foul:NotBF
NotBF;nop;73;Print:NotBFH
NotBFH:nop;84;Strike:Print
Ball;lft;0;CountBall:CountBall
CountBall;inc;4;BallRet:SetH
BallRet;rgt;0;Get:Get
SetH;inc;72;SetH:Print
Foul;rgt;2;CountStrike:StrikeRet
Strike;rgt;0;CountStrike:CountStrike
CountStrike;inc;3;StrikeRet:Print
StrikeRet;lft;0;Get:Get
Print;out;0;End:End
End;hlt;0;End:End

The VM for both languages is a finite-state machine with access to an infinite tape of byte values. I used the initial tape cell for the most recent input character, the cell to the right for the number of strikes, and the cell to the left for the number of balls.
Try it online! In that link, the header and footer are the FFB interpreter written in Python and linked from the esolangs page, but modified a little to take an io.BytesIO instead of opening a binary file, and to skip the chr on an output instruction (since a printed byte 3 is annoying to verify). So the output there will be the decimal string "3", "72", or "88".


text:
Positioning a fake mirror for best effect
Challenge
Premise
Consider a mosaic of \$m\times n\$ tiles, in \$k\$ unique colours designated by integers. Example (\$3\times6\$, four colours):
4 1 3 2 4 2
1 2 4 2 1 3
4 3 2 1 4 4

My poor man's mirror is a pane of glass of width \$\sqrt{2}\cdot\min(m,n)\$. I stand it diagonally on the mosaic, like so:
4 1 3 M 4 2
1 2 M 2 1 3
4 M 2 1 4 4

For this example I can pretend it reflects exactly two full tiles:
x 1 x M x x
x 2 M x x x
x M 2 1 x x

No matter what diagonal I choose, this is the greatest number of full tiles I can fake-reflect. Yay.
Task
Input: an integer matrix of \$m\$ rows and \$n\$ columns where \$2\leq m\leq1000,2\leq n\leq1000\$. The number of unique values is \$k\$ where \$3\leq k\ll mn\$.
Output: three integers, in any format. The first and second respectively represent the row coordinate and column coordinate of the matrix element ('mosaic tile') at the left end of the 45-degree diagonal where the fake mirror should be placed for 'best effect', effectiveness being defined as shown above. The third integer is 0 or 1, respectively meaning a rising (bottom left to top right) or falling (top left to bottom right) diagonal.
For clarity's sake, here are some simple test cases.
Example 1
Input:
4 1 3 2 4 2
1 2 4 2 1 3
4 3 2 1 4 4

Output: 3 2 0
Example 2
Input:
3 6
4 7
5 8
1 2
2 1

Output: 4 1 1 or 5 1 0 (not both)
As you can see, a unique solution isn't guaranteed.
Example 3
Input:
2  7  4  10 7  8  9  5  6  4  2  4  10 2  1  7  10 7  2  4  10 10 8  7
6  5  6  2  2  3  6  1  6  9  7  2  10 3  4  7  8  8  3  7  1  8  4  2
3  3  7  6  10 1  7  9  10 10 2  6  4  7  5  6  9  1  1  5  7  6  2  7
7  10 3  9  8  10 9  3  6  1  6  10 3  8  9  6  3  6  2  10 1  2  8  1
7  7  8  1  1  6  4  8  10 3  10 4  9  3  1  9  5  9  10 4  6  7  10 4
1  10 9  7  7  10 3  3  7  8  2  2  4  2  4  7  1  7  7  1  9  9  8  7
5  9  5  3  8  6  5  7  6  7  2  7  9  9  7  10 8  8  7  3  5  9  9  10
9  3  8  2  9  2  1  3  6  3  8  5  7  10 10 9  1  1  10 2  5  1  6  9
8  7  6  2  3  2  9  9  9  7  9  5  8  3  8  2  2  5  2  2  10 10 3  5
7  1  1  2  3  2  10 1  2  10 3  3  2  1  4  2  5  6  10 9  6  5  3  8
8  9  5  2  1  4  10 6  8  6  9  10 10 8  1  6  10 6  4  8  7  9  3  5
8  1  5  7  1  8  7  5  8  6  4  5  10 1  6  1  4  4  10 7  6  3  3  6

Output: 1 10 1
Edit - indexing
The example outputs are 1-indexed, but 0-indexing is allowed.
Remarks

This is code-golf, so fewest bytes wins.
Standard rules, I/O rules and loophole rules apply.
If possible, link an online demo of your code.
Please explain your code.

Also, how would this configuration be scored? Is it $3$ (the longest reflected ray) or $5$ (the sum of all reflected rays)?

@Arnauld 5. As stated in the post, we're only counting reflected elements.

Can the mirror leave the mosaic or must it be placed such that it fits (e.g. in the 3x6 example are 2 1 0 and 2 4 1 placements to be considered or not)?

It has to fit; there's a reason why I talked about 45 degrees and $\sqrt{2}\cdot\min(m,n)$.

Can you add another larger test case, maybe something whose min side is 10-15?

@Jonah Done. Remember, the example outputs are 1-indexed.

Thanks.  I have it working but the output format makes it almost 2 challenges.  A more natural format would be (<index in the larger of the two axes>, <rising or falling>) -- I don't suppose that's acceptable?

I admit that sounds nice, but the one answer already made as at the time of adding this comment isn't like that.

Charcoal, 91 bytes
≔⟦⟧θＷＳ⊞θＩ⪪ι ≔Ｌ§θ⁰η≔⊖⌊⟦Ｌθη⟧ζＦ⁻ＬθζＦ⁻ηζＦ²⊞υ⟦Σ⭆⊕ζ⭆⊕ζ⁼§§θ⁺ι⎇λμ⁻ζμ⁺κξ§§θ⁺ι⎇λξ⁻ζξ⁺κμ⎇λι⁺ιζκλ⟧Ｉ✂⌈υ¹

Try it online! Link is to verbose version of code. 0-indexed. Explanation:
≔⟦⟧θＷＳ⊞θＩ⪪ι

Input the mosaic. (These 12 bytes could be avoided by requiring the input to be in JSON format, but I was too lazy to punctuate the example.)
≔Ｌ§θ⁰η

Get the width of the mosaic.
≔⊖⌊⟦Ｌθη⟧ζ

Get the inner size of the mirror, i.e. the distance from the first to the last character of the mirror in terms of diagonal steps.
Ｆ⁻Ｌθζ

Loop over the possible row(s) of the top left corner of the mirror's enclosing square.
Ｆ⁻ηζ

Loop over the possible column(s) of the top left corner of the mirror's square.
Ｆ²

Loop over the possible rotations of the mirror.
⊞υ⟦Σ⭆⊕ζ⭆⊕ζ⁼§§θ⁺ι⎇λμ⁻ζμ⁺κξ§§θ⁺ι⎇λξ⁻ζξ⁺κμ⎇λι⁺ιζκλ⟧

Calculate the number of tiles it reflects exactly. Exact matches are counted twice and the diagonal is also counted but this doesn't affect the relative score. Push this number along with the potential solution to the predefined empty list.
Ｉ✂⌈υ¹

Output the solution with the highest number of exactly reflected tiles.

Python3, 557 bytes:
E=enumerate
V=lambda x,y,n,m:0<=x<n and 0<=y<m
U=lambda j,k,J,K,b,n,m:b[j][k]==b[J][K]if V(j,k,n,m)and V(J,K,n,m)else 0
def f(b):
 n,m=len(b),len(b[0])
 q,r=[i for x,u in E(b)for y,_ in E(u)for i in[(x,y,0,0,x,y)]*(x+1>=min(n,m)and y+min(n,m)<=m)+[(x,y,1,0,x,y)]*(x+1>=min(n,m)and y+1>=min(n,m))],[]
 while q:
  x,y,d,c,X,Y=q.pop(0)
  if abs(X-x)+1==min(n,m):r+=[(*[[x,y],[X,Y]][d],d,c)];continue
  q+=[(x,y,d,c+U(*[[X+1,Y+1,X-1,Y-1],[X+1,Y-1,X-1,Y+1]][d],b,n,m)+U(*[[X,Y+1,X-1,Y],[X,Y-1,X+1,Y]][d],b,n,m),X-1,Y+[1,-1][d])]
 return max(r,key=lambda x:x[-1])

Try it online!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Tribute to John Conway: Collatz in FRACTRAN
John Horton Conway was a brilliant mathematician. Among his contributions were three Turing-complete esolangs: Game of Life (esolangs wiki), FRACTRAN (esolangs wiki), and Collatz function (esolangs wiki).
Because we did an extremely amazing job around GoL, it is time for the challenge with the other two.
Background
A FRACTRAN program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.
A Collatz sequence is defined as the following: given a positive integer \$n\$,
$$
\begin{align}
a_0 &= n \\
a_{i+1} &= \begin{cases}
a_i/2,  & \text{if $a_i$ is even} \\
3a_i+1, & \text{if $a_i$ is odd}
\end{cases}
\end{align}
$$
It is conjectured that, for every positive integer \$n\$, the sequence eventually reaches 1.
Task
Write a FRACTRAN program that takes \$p^n\$ as input (for a prime \$p\$ of your choice) and halts if and only if the Collatz sequence starting at \$n\$ reaches 1.
You may see Avi F. S.'s COLLATZGAME as an example. Also, TIO has an implementation of FRACTRAN, so you can test your program with it. (Enter the starting number in the Arguments section; it accepts base-exponent form e.g. 2^27 as well as plain integer form.)
The shortest program in terms of the number of fractions wins.

Why didn't you think of interpreting FRACTRAN with iterations of the Collatz function?

@petStorm Because that one doesn't have a known interpreter.

Is the onus on the writer of the program to prove its correctness? :-)

@MeesdeVries Yes. We don't require a rigorous proof in the mathematical sense, but an answer should at least convince the reader that it is correct.

Would a program 1/2 for inputs of form 3^n be a correct solution if the collatz conjecture were proven to be true?

9 8 7 fractions
$$\frac{5}{4}, \frac{63}{22}, \frac{14}{55}, \frac{66}{35}, \frac{1}{7}, \frac{2}{3}, \frac{44}{5}$$
Takes input as \$3^n\$.
Try it online!
How it works
The first transition is
$$3^n \xrightarrow{\frac{2}{3}} 2 \cdot 3^{n - 1},$$
which we will consider the “real” representation of the number \$n\$, because some intermediate control flows will bypass the above transition.
If \$n = 1\$, the program now halts immediately.
If \$n = 2k\$ is even, we have
$$\begin{multline*}
2 \cdot 3^{2k - 1}
\xrightarrow{\frac{2}{3}}
2^2 \cdot 3^{2k - 2}
\xrightarrow{\frac{5}{4}}
3^{2k - 2} \cdot 5
\xrightarrow{\left(\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{5}{4}\right)^{k - 1}}
5^k
\xrightarrow{\frac{44}{5}}
2^2 \cdot 5^{k - 1} \cdot 11
\\
\xrightarrow{\frac{5}{4}}
5^k \cdot 11
\xrightarrow{\frac{14}{55}}
2 \cdot 5^{k - 1} \cdot 7
\xrightarrow{\left(\frac{66}{35} \cdot \frac{5}{4} \cdot \frac{14}{55}\right)^{k - 1}}
2 \cdot 3^{k - 1} \cdot 7
\xrightarrow{\frac{1}{7}}
2 \cdot 3^{k - 1},
\end{multline*}$$
which represents \$\frac{n}{2}\$.
If \$n = 2k + 1\$ is odd, we instead have
$$\begin{multline*}
2 \cdot 3^{2k}
\xrightarrow{\left(\frac{2}{3} \cdot \frac{5}{4} \cdot \frac{2}{3}\right)^k}
2 \cdot 5^k
\xrightarrow{\frac{44}{5}}
2^3 \cdot 5^{k - 1} \cdot 11
\xrightarrow{\frac{5}{4}}
2 \cdot 5^k \cdot 11
\\
\xrightarrow{\frac{63}{22}}
3^2 \cdot 5^k \cdot 7
\xrightarrow{\left(\frac{66}{35} \cdot \frac{63}{22}\right)^k}
3^{3k + 2} \cdot 7
\xrightarrow{\frac{1}{7}}
3^{3k + 2}
\xrightarrow{\frac{2}{3}}
2 \cdot 3^{3k + 1},
\end{multline*}$$
which represents \$3k + 2 = \frac{3n + 1}{2}\$, which is two steps ahead of \$n\$.

Could you please provide an explanation?

@mypronounismonicareinstate After I finish optimizing!

What was the procedure (or flowchart, etc) for deriving those fractions?  Was it "easier" to work backwards from a final  fraction?

@CarlWitthoft I can't speak for Anders, but here's my analysis of his program: https://gist.github.com/kmill/266ef6bb5690f9c26110673dcc59f710  It has some real cleverness in getting around some of FRACTRANs quirks! And also how it calculates $2r+(1+2r)d$ where $d$ is the floor of $n/2$ and $r$ is the remainder of this quotient.

9 fractions
13/11 22/39 1/13 7/5 320/21 1024/7 3/4 5/6 22/3

Try it online! Input is a power of 2.
It's probably easier to think about FRACTRAN code in terms of the powers of the primes in each fraction. I list these below for the code, with positive exponents coming from numerators and negative values from denominators, omitting 0's to reduce clutter. Thinking of programs as lists of vectors and the current value as a vector, FRACTRAN repeatedly modifies the value by adding the first-listed row such this results in no negatives entries.
  2  3  5  7 11 13
  ----------------
             -1 +1
 +1 -1       +1 -1
                -1
       -1 +1
 +6 -1 +1 -1
+10       -1
 -2 +1
 -1 -1 +1
 +1 -1       +1

I suspect this solution is similar to Anders Kaseorg's earlier 9-byte solution, who has already explained how his now-more-golfed answer works in detail. So, I'll instead explain a useful conceptual idea in my code.
Switcher gadget
I'll talk about a control flow gadget that I'll call a switcher that my code heavily relies on. You can see two copies of it, one in columns 3 and 4, and another in columns 5 and 6. It looks like this:
   -1 +1
B  +1 -1
b     -1
A
a  +1

Here, A, a, B, and a are some FRACTRAN operations, taking up multiple columns. A switcher alternates between two things:

Repeat A as long as it's legal, then do a once.
Repeat B as long as it's legal, then do b once.

The first row -1 +1 doesn't do any code operation is just used for control flow.
Here's how a switcher it might look like operating. The first column shows the operation performed, and the other two columns showing the value of those variables used for control flow, which are always 0 or 1.
 A  0  0
 A  0  0
 A  0  0
 a  1  0
    0  1
 B  1  0
    0  1
 B  1  0
    0  1
 B  1  0
    0  1
 b  0  0
 A  0  0
 A  0  0
 ...

What is it good for?
So, why do we want a switcher? Well, without a gadget like this, it's hard to keep FRACTRAN focused on a task. Say we want to alternate between doing A repeatedly and doing B repeatedly. FRACTRAN prioritizes the one that's listed first, so if we list A then B, then when doing B, FRACTRAN will keep jumping back to A when it can. Of course, the other order means we just have the same problem with it jumping back to B.
For example, consider this simple program made of two operations:
A = [-2, +1]
B = [+1, -1]

Starting with [2*n, 0], these operations almost work to product [n, 0] but not quite. First, A is applies as long as possible, adding [-2, +1] until we arrive at[0, n]. For example, with n=3, this goes:
        [6, 0]
add A:  [4, 1]
add A:  [2, 2]
add A:  [0, 3]

Now we have [0, n] and want to get [n, 0]. To move n back to the first entry, we want to to keep adding B = [+1, -1]. Since we can't do A at first, the code indeed switches to B, but then things go wrong:
        [0, 3]
add B:  [1, 2]
add B:  [2, 1]
add A:  [0, 2]

Because doing B twice made A applicable again, it never finishes applying B and so doesn't get to [n, 0].
A switcher lets us fix exactly this by keeping the program on task with B, making it alternates between A-mode and B-mode until each respective task is complete and can be done no further. It also let us run additional one-time operations a and b when switching modes.
The Collatz code
This operation of halving is exactly what the Collatz code does on even values. If we ignore the third and fourth columns (which are for odd values) and their rows, we get:
       code switcher
             -1 +1
(B)   +1 -1  +1 -1
(b)             -1
(A)   -2 +1
(a)   +1 -1  +1

This is exactly a switcher (in columns 3 and 4) applies to the operations in the first two columns. These are the halving operations A = [-2, +1], B = [+1, -1] described before. A detail is that we also have b = A to make the transition from B work out by doing A an additional time in advance.
Similarly, columns 3 and 4 are a switcher for the operation used for odd values. To take [n,0] -> [3*n+1,0] for odd n, we use:
A = [-2, +1]
a = [-1, -1]
B = [+6, -1]
b = [+10, 0]

Note that making B be [+6, -1] rather than [+1, -1] as for the even case means that we end up with a result about 6 times as big, so 3*n rather than n/2. The a and b work out to give the +1 in 3*n+1 while serving other useful purposes. Specifically, they make the code go into the odd switcher rather than the even switcher when the first entry is odd, as well as make the program terminate when the Collatz sequence reaches 1.
The odd code might be a bit simpler producing (3*n+1)/2, that is pre-doing an addition halving step, which is always what follows because 3*n+1 is even for odd n. But, I think that this would just make the numerical entries in the rows smaller rather than cutting a row (fraction), which is what counts for scoring.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Make 1s using a bunch of 1s
Your task is to form an expression equaling \$ 11111111111 \text{ (11 ones)} \$ using only the following characters: 1+(). Keep in mind that the result is in base 10, and not some other base like binary. Of course, these expressions should follow the order of operations. Furthermore, the only operations which should be performed are addition, multiplication, and exponentation.
Some examples of valid expressions include
$$ 1 + 1 + 1 = 3 $$
$$ (1 + 1)(1 + 1) = 4 $$
$$ (1 + 1)^{1 + 1 + 1} = 8 $$
$$ 1 + (1 + 1(1 + 1)^{1 + 1^{1 + 1}}) = 6 $$
Some examples of invalid expressions include
$$ 11 + 11 \quad | \quad \text{concatenation of ones}$$
$$ 1 + ((1) \quad | \quad \text{unbalanced parentheses} $$
$$ \displaystyle\binom{1}{1 + 1} \quad | \quad \text{disallowed operation} $$
Scoring
After forming an expression which equals \$ 11111111111 \$, your score will be calculated by the sum of the \$ \text{no. of 1} \$, the \$ \text{no. of +} \$, and the \$ \text{no. of} \$ pairs of parentheses. For example, \$ (1 + 1)(1 + 1)^{1 + (1)} \$ has a score of \$ 12 \$, because it has \$ 6 \$ \$ 1 \$s, \$ 3 \$ pluses, and \$ 3 \$ pairs of parentheses.
The submission with the lowest score wins!

to be clear, is the trivial solution 11111111111 is forbidden? :D and slightly longer variants like +11111111111, (11111111111) etc.

@innisfree - the rules clearly say concatenation isn't valid, meaning you can't even have 11, let alone 11111111111.

Oh now I see, but I don’t think it’s that clearly stated

It's clear (it's the first example of an invalid expression), it's just a bit weirdly stated, since "concatenation" wouldn't normally be thought of as an operation.

@steve and also weirdly stated  because 1+1, which is allowed, is also a concatenation of 1, + and 1.

Yeah. Maybe better to write it as "using only the number 1, the + operator, and parentheses".

This is apparently causing some controversy, so I went ahead and edited it be more clear.

Is base 2 allowed?

@S.S. Anne base 2 is not allowed, only base 10 please

@dingledooper You should make that explicit. I just spent half an hour on a binary answer.

@S.S. Anne Sorry about that :( I've made it explicit now.

After spending rather too much computer time, I thought I would share that the optimal answer seems to be in the range [50,69] operations. 50, because my brute force optimizer has excluded everything with 49 or fewer operations, 69 because we have a constructive example of that being possible, below. The solver, for the record, is here (https://gist.github.com/imallett/35b95dc1b4535b6b3c35b642029add17), and can doubtless be improved or used for partial results.

score = 82 71 69 (34 ‘1’s + 23 ‘+’s + 12 parenthesis pairs)
$$\begin{multline*}
11111111111 = 1 + (1 + 1) \cdot {}
\\
(1 + 1 + 1 + (1 + 1)^{(1 + 1)^{1 + 1 + 1}}(1 + ((1 + 1)(1 + 1 + 1))^{1 + 1 + 1})) \cdot {}
\\
(1 + (1 + (1 + 1 + 1)^{1 + 1})^{1 + (1 + 1)^{1 + 1}})
\end{multline*}$$
Try it online!
Search program in Rust
This finds optimal solutions for up to about 8 digit numbers.  Don’t try it on anything larger—it will eat all your memory.
I constructed the above solution by manually writing \$11111111111 = 1 + 111110 \cdot 100001\$ and searching for optimal solutions to \$111110\$ and \$100001\$.
use std::env;

#[derive(Clone, Debug)]
enum Op {
    One,
    Add(u32, u32),
    Mul(u32, u32),
    Pow(u32, u32),
}

fn show(ops: &[Option<Op>], z: u32, prec: u32) {
    match ops[z as usize].as_ref().unwrap() {
        Op::One => print!("1"),
        Op::Add(x, y) => {
            if prec > 0 {
                print!("(");
            }
            show(ops, *x, 0);
            print!(" + ");
            show(ops, *y, 0);
            if prec > 0 {
                print!(")");
            }
        }
        Op::Mul(x, y) => {
            if prec > 1 {
                print!("(");
            }
            show(ops, *x, 1);
            show(ops, *y, 1);
            if prec > 1 {
                print!(")");
            }
        }
        Op::Pow(x, y) => {
            if prec > 2 {
                print!("(");
            }
            show(ops, *x, 3);
            print!("^{{");
            show(ops, *y, 0);
            print!("}}");
            if prec > 2 {
                print!(")");
            }
        }
    }
}

fn main() {
    for target in env::args().skip(1).map(|arg| arg.parse().unwrap()) {
        let mut ops: Vec<Option<Op>> = vec![None; target as usize + 1];
        let mut vs: Vec<Vec<u32>> = vec![];
        while !ops[target as usize].is_some() {
            let mut v: Vec<u32> = vec![];
            let mut visit = |x, op| {
                if let Some(x) = x {
                    if x <= target {
                        if ops[x as usize].is_none() {
                            ops[x as usize] = Some(op);
                            v.push(x);
                        }
                    }
                }
            };
            let level = vs.len();
            let score = level / 2;
            match level % 2 {
                0 => {
                    if score == 1 {
                        visit(Some(1), Op::One);
                    }
                    for i in 1..score.saturating_sub(1) {
                        let j = score - 1 - i;
                        for u in &vs[i * 2..i * 2 + 2] {
                            for v in &vs[j * 2..j * 2 + 2] {
                                for &x in u {
                                    for &y in v {
                                        visit(x.checked_pow(y), Op::Pow(x, y));
                                    }
                                }
                            }
                        }
                    }
                    for i in 1..score {
                        let j = score - i;
                        for u in &vs[i * 2 - 1..i * 2 + 1] {
                            for v in &vs[j * 2 - 2..j * 2 + 1] {
                                for &x in u {
                                    for &y in v {
                                        visit(x.checked_mul(y), Op::Mul(x, y));
                                    }
                                }
                            }
                        }
                    }
                }
                1 => {
                    for i in 1..score.saturating_sub(1) {
                        let j = score - 1 - i;
                        for u in &vs[i * 2..i * 2 + 2] {
                            for v in &vs[j * 2..j * 2 + 2] {
                                for &x in u {
                                    for &y in v {
                                        visit(x.checked_add(y), Op::Add(x, y));
                                    }
                                }
                            }
                        }
                    }
                }
                _ => unreachable!(),
            }
            vs.push(v);
        }
        print!("{} = ", target);
        show(&ops, target, 0);
        println!();
    }
}

Try it online!

WolframAlpha. Do you have some generating code to post?

Is it expected that your program's solution for 111110 is worse than just doubling its solution for 55555?

@Neil I fixed that a while ago, you must be using an old version.

By hand -  118 112 111  82
$$(1+(1+1)^{(1+1)^{1+1}}(1+(1+1)(1+(1+(1+1)^{1+1})^{1+1})^{1+1}))(1+(1+1+(1+1+1)^{1+1})(1+1+(((1+1)(1+1+1))^{1+1})^{1+1+1}))$$
Try it at Wolfram Alpha
This was found by working my way down from \$11111111111\$ looking for close divisibility considering factors which are close in construction to powers and is:
$$(((8(9^4)+(3(9^2))+8)((16+1)^2)+8)81+2)9+2$$
There are \$16\$ parentheses pairs, \$40\$ ones, and \$26\$ additions.

Previous @111
$$((1+1)(1+1+1)^{1+1})^{(1+1)^{1+1+1}}+((1+1)(1+1+1)^{1+1}(1+1+1+1+1)^{1+1})^{1+1+1}+((1+1+1)^{1+1+1})^{1+1+1}+((1+1)(1+1+1)^{1+1})^{1+1+1}+(1+1)((1+1+1)^{1+1}+1)$$
Try it at Wolfram Alpha
This is
$$18^8+450^3+(3^3)^3+18^3+20$$
Where:
\$18 = 2\times 9 = (1+1)(1+1+1)^{1+1}\$
\$8 = 2^3 = (1+1)^{1+1+1}\$
\$450 = 18\times 25 = (1+1)(1+1+1)^{1+1}(1+1+1+1+1)^{1+1}\$
\$20 = 2\times (9+1) = (1+1)((1+1+1)^{1+1}+1)\$

69 operations
$$1+(1+((1+1+1)^{1+1}+1)^{1+1+1+1+1})(1+1)\\
\cdot(1+1+1+(1+((1+1+1)(1+1))^{1+1+1})(1+1)^{(1+1)^{1+1+1}})$$
Try it online!
Verifier thanks to @AndersKaseorg
34 1s, 24 +s, 11 ()s.
Decomposition, by layers:

11111111111 = 100001 * 111110 + 1
100001 = 10^5+1
111110 = 55555*2
55555 = 3 + 217*256
217 = 6^3+1
256 = 2^2^3

I wrote a program to brute-force this, but I'm still working on the program.

I guess 111110 = 6 + 217*512 results in the same number of operations.

You don't need the dot there. It's implicit.

score = 22222222221
The sequence $$1 + 1 +\ ... 1$$ where ... is 11111111108 pairs of 1 +. I think I can probably shorten this, though.

Score:  113  111
Breakdown:

ones: \$56\$
plus signs: \$45\$
pairs of parentheses: \$10\$
no multiplication

The expression below is in JS syntax, with \$p^q\$ computed as p**[q].
(((1+1)**[1+1+1+1]+1+1)**[1+1+1+1]+((1+1)**[1+1+1+1]+1)**[1+1]+((1+1+1)**[1+1]+1+1+1)**[1+1])**[1+1]+((1+1+1+1+1+1)**[1+1+1]+(1+1)**[1+1+1+1])**[1+1]+1+1+1+1+1+1

Try it online!
Formula
$$(((1+1)^{1+1+1+1}+1+1)^{1+1+1+1}+((1+1)^{1+1+1+1}+1)^{1+1}+((1+1+1)^{1+1}+1+1+1)^{1+1})^{1+1}+((1+1+1+1+1+1)^{1+1+1}+(1+1)^{1+1+1+1})^{1+1}+1+1+1+1+1+1$$
which simplifies down to:
$$\big((2^4+2)^4+(2^4+1)^2+(3^2+3)^2\big)^2+(6^3+2^4)^2+6$$
$$=(18^4+17^2+12^2)^2+232^2+6$$
$$=105409^2+232^2+6$$
$$=11111057281+53824+6$$
$$=11111111111$$

111 is an apt score :)

Score 92 (46 1's, 33 +'s, 13 parentheses)
$$((1+1)(1+1+1)^{1+1})^{(1+1)^{1+1+1}}$$
$$+$$
$$((1+1)^{(1+1)(1+1+1)^{1+1}}+((1+1+1+1+1)(1+1+1)(1+1+1+1))^{1+1}+1)$$
$$*$$
$$(1+1+1+1+1+1+1)^{1+1+1}$$
18^8 + (2^18+60^2+1) * 7^3
18^8 + 91,150,535 Similar to Jonathan Allen but I factorize the 91,150,535.
Try at wolfram Alpha
Check calculation Link to TIO, Ruby language (wolfram alpha website is playing up for me)
Try it online!

You have a typo (twice) -- 91,150,535. Also, I think you have 30 rather than 60. Other than that I think this will be crushing :)

@JonathanAllan yeah typing this up is almost as hard as solving it! I was already working on the 18^8 when I saw your answer, but you got it out first.

With the fix I think it's 92 - WolframAlpha

135 = 67 '1's + 49 '+'s + 19 parens
1st attempt with manual calculator fiddling:

Method

11111111111 = 21649*513239
21649 = 1 + ((2^4)*3*11*41)
513239 = 1 + (2*11*41*569)
569 = 2 + (3^4)*7
then the small numbers are built up manually

Try it on Wolfram-Alpha

Score 115 97 93
\$ ((1+1)^{(1+1+1)^{1+1+1}}+((1+1+1)^{1+1+1}+1+1)((1+1+1)^{1+1}(((1+1)^{(1+1)^{1+1}}+1)^{1+1+1}+1+1+1+1+1)+1))((1+1+1)^{1+1+1+1}+1)+1 = (2^{3^3}+(3^3+2)(3^2((2^{2^2}+1)^3+5)+1))(3^4+1)+1 = (2^{27}+29(9(17^3+5)+1)))(82)+1 = (2^{27}+29(44263))(82)+1 = 135501355(82)+1 = 11111111111\$
Found by using @AndersKaseorg's Rust program to generate a solution for \$ 44263 \$. (I was using an old version of his program when I created my previous answer; the current version also finds this answer when I plug in \$ 1283627 \$.)

Score 187 (87 1s, 68 +s, 32 () pairs)
$$\begin{multline*}
\left(1+1\right)\left(1+1+1+1+1\right)\left(\left(1+1\right)^{\left(1+1+1\right)}+1+1+1\right)
\\
\left(\left(1+1\right)^{\left(1+1+1+1+1\right)}+\left(1+1\right)^{\left(1+1+1\right)}+1\right)
\\
\left(\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}\right)}+\left(1+1\right)^{\left(1+1+1\right)}+1+1+1+1+1+1+1\right)
\\
\left(\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}+1+1+1+1+1\right)}+\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}+1\right)}
\right. \\ \left. {}
+\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}\right)}+\left(1+1\right)^{\left(1+1+1+1+1+1+1\right)}+1+1+1\right)+1
\end{multline*}$$
Try it online!
Based on the fact that $$11111111110 = 2×5×11×41×271×9091$$ The formula is that, based on powers of two.

this could be optimized a fair bit, for example you could replace each instance of (1+1)^(1+1+1) + 1 with (1+1+1)^(1+1) and subtract 2 from your score each time -
EDIT: you also don't need the parentheses in the exponents

@Sagittarius I do need them: without them the exponents are done in the wrong order.

how would that make a difference if there is only one exponent? I've seen other people leave them out

@Sagittarius Oh, yes for some parts. Honestly, I'd forgotten about this ages ago.


text:
Conway's $1(0),000 challenge
Background
This challenge is about A004001, a.k.a. Hofstadter-Conway $10000 sequence:
$$
a_1 = a_2 = 1, \quad a_n = a_{a_{n-1}} + a_{n-a_{n-1}}
$$
which starts with
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, 12, 13, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, ...

John Conway proved the following property of the sequence:
$$
\lim_{n\rightarrow\infty}{\frac{a_n}{n}}=\frac12
$$
After the proof, he offered $1(0),000 for the smallest \$k\$ such that all subsequent terms of \$a_j/j\$ after the \$k\$-th term are within 10% margin from the value \$1/2\$, i.e.
$$
\left|\frac{a_j}{j}-\frac12\right|<\frac1{20},\quad j > k
$$
To quote Sloane's comment on the OEIS page (which explains the title):

John said afterwards that he meant to say $1000, but in fact he said $10,000. [...] The prize was claimed by Colin Mallows, who agreed not to cash the check.

Here are some graphs to get some feel of the sequence (copied from this MathOverflow.SE answer):

Also check out A004074, which lists the values of \$2a_n-n\$.
Challenge
Given the amount of margin \$r\$, solve the generalized Conway's challenge: find the smallest \$k\$ which satisfies
$$
\left|\frac{a_j}{j}-\frac12\right|<\frac{r}{2},\quad j > k
$$
This can be also phrased as the largest \$k\$ that satisfies \$\left|\frac{a_k}{k}-\frac12\right|\ge\frac{r}{2}\$. You can assume \$0<r<1\$, so that the task is well-defined in both ways.
(The original challenge is \$r=0.1\$, and the answer by Colin Mallows is 1489, according to Mathworld (which agrees with my own implementation). The value of 3173375556 on the MO answer is probably the one for \$r=0.05\$.)
For simplicity, you may assume a few conjectured properties of the sequence:

\$a_n = n/2\$ when \$n = 2^k, k \in \mathbb{N}\$.
\$2a_n - n\$

is nonnegative everywhere,
is 0 when \$n = 2^k, k \in \mathbb{N}\$,
follows the Blancmange curve-like pattern between the powers of two (as visible in the second figure above), and
when divided by \$n\$, has the maximum values between powers of two decreasing as \$n\$ increases (as visible in the first figure above).

Standard code-golf rules apply. The shortest code in bytes wins.
Test cases
r     | answer
------+-------
0.9   | 1
0.4   | 1
0.3   | 6
0.2   | 25
0.15  | 92
0.13  | 184
0.12  | 200
0.11  | 398
0.1   | 1489
0.09  | 3009
0.085 | 6112
0.08  | 22251

Reference implementation in Python.
(A hint for termination check: A value of \$k\$ is the answer if \$\frac{2a_k}{k}-1\ge r\$ and \$\frac{2a_j}{j}-1< r\$ for \$k < j \le 4k\$.)

I thought this post is spam when I first read its title.

This would be a great fastest-code.

JavaScript (ES6), 83 bytes
Slow as hell.
g=n=>n<3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=>(x=g(n)*2-n)|m?f(r,n+1,x<r*n?x&&m:o=n):o

Try it online!
How?
We look for the highest \$n\$ such that:
$$2\cdot a(n)-n \ge r\cdot n$$
We stop when no greater value is found in a whole interval:
$$[2^k+1,2^{k+1}], k>0$$
whose upper bound is characterized by \$2\cdot a(n)-n=0\$.

JavaScript (ES6), 94 bytes
A much faster version using a cache to prevent too many recursive calls.
g=n=>g[n]=g[n]||n<3||g(n-g(--n))+g(g(n))
f=(r,n=1,m)=>(x=g(n)*2-n)|m?f(r,n+1,x<r*n?x&&m:o=n):o

Try it online!

What does $k$ stand for here?

@petStorm Any positive integer.

@petStorm To be a bit more specific, we don't care about the value of $k$. We just need to know that we've reached the boundary of the Blancmange curve, which happens whenever $n$ is a power of $2$.

05AB1E, 49 48 40 bytes
∞oüŸvy¦R.ΔтS_λè₅N₁-₅+}·yαIy*@}Dˆ(i¯àDdiq

-1 byte thanks to @Grimmy.
Try it online. (No test suite, because of the q.)
Explanation:
Inspired by @Arnauld's approach, so I too look for the largest \$n\$ such that:
$$2\cdot a(n)-n \ge r\cdot n$$
And I also stop when no greater value is found in a whole interval:
$$\left(2^k,2^{k+1}\right],k>0$$
∞                 # Push an infinite positive list: [1,2,3,...]
 o                # Take each as 2 to the power: [2,4,8,...]
  ü               # For each overlapping pair:
   Ÿ              #  Create a list in that range:
                  #   [[2,3,4],[4,5,6,7,8],[8,9,10,11,12,13,14,15,16],...]
vy                # Loop over each inner list in the range [a,b]:
  ¦               #  Remove the first value to make the range (a,b]
   R              #  Reverse it to [b,a)
  .Δ              #  Find the first value `y` in this list which is truthy for,
                  #  or -1 if none are found:
       λ          #   Create a recursive environment,
        è         #   to output the `y`'th value afterwards
    тS_           #   Start it at a(0)=0, a(1)=a(2)=1
                  #   (push 100 as list [1,0,0] and invert booleans to [0,1,1])
                  #    (implicitly push a(n-1))
         ₅        #    And use that for a(x): a(a(n-1))
         N₁-      #    Push n-a(n-1)
            ₅     #    And use that for a(x) as well: a(n-a(n-1))
             +    #    And add those together
       }·         #   After the recursive environment, double it: 2*a(y)
         yα       #   Take the absolute difference with `y`: |2*a(y)-y|
           Iy*    #   Push the input multiplied by `y`
              @   #   Check |2*a(y)-y| >= input*y
   }Dˆ            #  After the found_first, add a copy to the global_array
      (i          #  If this value was -1 (thus none were found):
        ¯         #   Push the global_array
         à        #   Pop and push its maximum
          D       #   Duplicate it
           di     #   Pop the copy, and if this maximum is NOT -1:
             q    #    Terminate the program
                  #    (after which this maximum is output implicitly as result)

NOTE: The vy cannot be ε or ʒ to act as a foreach with implicit y, because we'd need a --no-lazy flag in order to have a proper output, which isn't possible due to the lazy infinite recursive list.

011S => тS_

@Grimmy Thanks. I had the feeling that could be golfed, but didn't think about that..

Pure Bash, 110 109 108 105 bytes
a=(0 1 1)
v=1
m=1
for((n=3;c<2;n++)){
c=$[a[n]=v=a[v]+a[n-v],(2*v-n)*$2>=$1*n?m=n,0:c+!(n&n-1)]
}
echo $m

Try it online!
3 bytes off due to the same improvements made by ceilingcat for my C answer.
Input is a fraction, passed as arguments -- the numerator in the first argument, and the denominator in the second argument.  For example, to pass 0.13, the command would look like: ./program 13 100
(Bash doesn't support floating-point numbers natively, but rational numbers are perfect for this challenge.)
The program runs quickly enough that it can get through all the OP's test cases in a single run at TIO, even though bash is a relatively slow interpreted language.
Output is on stdout.

Erlang (escript), 178 bytes
a(X)->case X>2 of true->a(a(X-1))+a(X-a(X-1));_->1end.
c(R)->c(R,1,0,0).
c(R,N,M,O)->case 2*a(N)-N>R*N of true->c(R,N+1,N,N+1);_->case N>O bsl 1of true->M;_->c(R,N+1,M,O)end end.

Try it online!

C (gcc), 119 116 113 bytes
f(float r){int a[99999]={0,1,1},v=1,m=1,n=2,c=0;for(;c<2;c=2*v>=r*n+n?m=n,0:c+!(n&n-1))a[n]=v=a[v]+a[++n-v];v=m;}

Try it online!
3 bytes off thanks to ceilingcat.
And now 3 more bytes off from ceilingcat.
This is a port of my bash answer.  It's a function which accepts r as an argument (a float this time) and returns the desired result.

@ceilingcat Thanks -- bash arithmetic expressions are close enough to C that the same improvements worked on my bash answer too.

@ceilingcat Thank you.


text:
Create pixel art!
The task
Given an image as input, your task is to do the following:

Resize the image so it is At least 2 times smaller, but still has the same width/height ratio by taking every second (if resized to 2x) pixel in both horizontal and vertical directions and using those in the pixel art image. Example:

a 4x4 image

[abcd
,efgh
,ijkl
,mnop]

When resized to 2x will become one of the following:

[ac  [bd  [eg  [fh
,ik] ,jl] ,mo] ,np]

Each RGB pixel in the newly resized image must be converted to a 3-bit color, so there are 8 different possible colors:

Red        (255,0,0)
Green      (0,255,0)
Blue       (0,0,255)
Light Blue (0,255,255)
Magenta    (255,0,255)
Yellow     (255,255,0)
White      (255,255,255)
Black      (0,0,0)

An image of the colors:

And output the resulting image.

Input
Your input may be:

An image
A path to the inputting image

Output
Can be:

An image
A path to the outputting image

Rules

The inputting image will not be larger than 2048x2048 and will always be at least 256x256
The outputting image must be at least 64x64
When changing pixels, the original pixel must be converted to the closest (euclidean) pixel in the 3-bit scheme, no randomization
You may hardcode how much you resize the image if you want to
When submitting your answer, please include the following:

Your byte-count in the title
Your code
An pair of images, one original of your choice and the other being the "pixel-art" from that image

This is code-golf, so lowest byte count for each language wins.

Test cases

(2x resize)

(2x resize)

@Noodle9 will edit and clarify, the resizing works by taking every second (if resized to 2x) pixel from the original image.

What is the metric used for "closest" for colors? What stops us from outputting an 1x1 image?

@mypronounismonicareinstate When i made an ungolfed version of this, I used (r//128255,g//128255,b//128*255) for (r,g,b) in every pixel (python). As for the size, will add in rules to output at least 64x64 image

@Noodle9 added an explanation in the post

@Noodle9 It can, updating the examples

I will repeat @mypronounismonicareinstate : What stops us from outputting a 1x1 image since the ratio is ours to decide?

@OlivierGrégoire please read the updated rules

@Noodle9 as i've answered, what i've used in python was for each channel n//128*255, where n is an rgb channel. However, it is up to you to decide how you define closest

@Noodle9 an rgb channel is simple - each pixel (usually) has three channels: RedGreenBlue, hence the name

@Noodle9 yep, gonna put euclidean. As for matrixes, only images allowed

Looks good! +1 (removed my comments).

Sledgehammer, 22 17 bytes
I noticed I'm no longer winning for some reason and made a minor IO golf
⢟⢡⡂⠴⠒⢂⢜⠧⣘⡨⡏⣻⢈⠯⣧⠼⡫

Corresponding Mathematica code: Export[".bmp",ImageAdjust[Import[#]~Downsample~2, 9!]]& . Takes input from the file with name specified in the program's arguments (for some reason these are put in a file, too), outputs to the file .bmp. There are literally built-ins for everything!

built-in for reading arbitrary image format
built-in for downsampling
built-in for adjusting the contrast by \$9!\$
built-in for writing all that into a file

At least it's not PixelArtify[Input[]].
Mathematica, 61 31 bytes
ImageAdjust[#~Downsample~2,9!]&

Adjusts the contrast of the downsampled image by the factorial of nine.

I guess my answer helped you to remove Import/Export

I included them in the Sledgehammer code because while I could input and output a bunch of pixel values, that's not very kind, and that answer is probably winning anyway, so I could sacrifice a few bytes for that purpose.

MATL, 18 bytes
Yi2Lt3:K$)127>o2YG

The input is a string with the file name. The output is an image displayed in a window.
Input image:

Output image:

Explanation
Yi    % Implicit input: filename. Read image. Gives an N×M×3 uint8 array
2L    % Push [2 2 j] (predefined literal). When interpreted as an index,
      % this means 2:2:end
t     % Duplicate
3:    % Push [1 2 3]
K$)   % 4-input indexing. Downsamples the image by a factor of 2 in each
      % dimension of the first two dimensions (vertical and horizontal),
      % while keeping the three colour components
127>  % Greater than 127? Gives true (1) or false (0)
o     % Convert to double
2YG   % Display image. For double data type this assumes range from 0 to 1

Python 3 + imageio, 68 67 bytes
Takes the filename as input, overwrites the original file.
from imageio import*
lambda f:imwrite(f,(~imread(f)[::2,::2]>>7)-1)

imageio.imread returns a numpy 3d array of unsigned 8-bit integers corresponding to the RGB value of each pixel. array[::2, ::2] takes every other row and every other column of the array.
Because of the 8-bit data type (~array>>7)-1 is equivalent to ((255-array)//128-1)%256.
image source

Is it me or this output is not downsampled?

@mypronounismonicareinstate I displayed a downscaled version of the original because it took up so much space, the true original would open if you click on it. I have changed this now because this will probably confuse more people.

Damn, i also used python 3 but used PIL as it's the only image library I know. Well done!

Wolfram Language (Mathematica), 69 bytes
Image[#&@@Nearest[{0,1}~Tuples~3,#]&/@#&/@ImageData@Downsample[#,2]]&

I out-builtinned you!

@mypronounismonicareinstate yes, I forgot about downsample...

Java 10, 255 254 252 251 248 bytes
import java.awt.image.*;I->{int w=I.getWidth()/2,h=I.getHeight()/2,c[]={0,255,65535,65280,255<<16,16711935,16776960,-1>>>8};var r=new BufferedImage(w,h,13,new IndexColorModel(3,8,c,0,0>1,1,0));r.createGraphics().drawImage(I,0,0,w,h,null);return r;}

-2 bytes thanks to @mypronounismonicareinstate
-4 bytes thanks to @OlivierGrégoire.
Some example I/O:

I/O as a java.awt.image.BufferedImage.
Explanation:
import java.awt.image.*;      // Import for BufferedImage and IndexColorModel
I->{                          // Method with BufferedImage as both parameter & return
  int w=I.getWidth()/2,       //  Get the width/2 of the input-image
      h=I.getHeight()/2,      //  Get the height/2 of the input-image
      c[]={                   //  Integer-arry for the colors:
       0,                     //   0x000000 (black)
       255,                   //   0x0000ff (blue)
       65535,                 //   0x00ff00 (green)
       65280,                 //   0x00ffff (aqua)
       255<<16,               //   0xff0000 (red)
       16711935,              //   0xff00ff (magenta)
       16776960,              //   0xffff00 (yellow)
       -1>>>8};               //   0xffffff (white)
  var r=new BufferedImage(w,h,//  Create the return-BufferdImage with this size, and:
         13,                  //   An indexed byte image (BufferedImage.TYPE_BYTE_INDEXED)
         new IndexColorModel( //   Using the following ColorModel:
          3,                  //    3-bits
          8,c,                //    with the 8 colors of the earlier created array
          0,                  //    without an offset index
          0>1,                //    without alpha layers (false)
          1,                  //    without transparent colors (Transparency.OPAQUE)
          0));                //    using unsigned bytes as data (DataBuffer.TYPE_BYTE)
  r.createGraphics()          //  Convert this image to a Graphics2D object
   .drawImage(I,              //  So we can use the input-image for it
              0,0,            //   with 0,0 as starting x,y coordinates
              w,h,            //   the same halved width & height
              null);          //   and no ImageObserver
  return r;}                  //  Return this created BufferedImage as result

Are the last 3 parameters of IndexColorModel necessary?

Does something like -1u>>8 work for 16777215?

@OlivierGrégoire I'm afraid so. The constructors of the IndexColorModel are limited when using an int[] for the colors. It's either (int,int,int[],int,boolean,int,int) or int,int,int[],int,int,BigInteger). It also has a constructor with byte[], but those can't fit some of the colors, and the three separated parameters for red,green,blue, but I doubt those would save bytes considering the three loose arrays.

@mypronounismonicareinstate Thanks, that indeed works (although it's >>> instead of u>> in Java). I tried to find something shorter for some of those numbers, but didn't really worked out. Thanks!

Ok for the constructors, I hadn't noticed the change from byte[] to int[]. Also, same idea as @mypronounismonicareinstate: 255<<16 == 16711680.

,c[]={0,255,65535,65280,255<<16,16711935,16776960,-1>>>8} and use c instead of new int[]{...}.

Does this use the correct downscaling algorithm?

Red, 150 148 bytes
func[s][r: func[a][round/to a 255]i: load s forall i[i/1: as-rgba r i/1/1
r i/1/2 r i/1/3 0]view compose[base(i/size / 2)draw[scale .5 .5 image i]]]

The output is an image displayed in a window.

Original

Scale 0.5

Original

Scale x 0.5

That downsampled dog is pretty scary looking :p

@RedwolfPrograms It's the first time I hear someone to call a samoyed dog "scary looking" :) It's good that you were talking about the downsampled one.
I have a samoyed dog myself, not as fluffy as the one above though and still she's adorable!

Python 3 + PIL, 211 208 bytes
from PIL import Image as I
i=I.open(input(),'r')
p=i.load()
q,g=i.size;a=q//4;c=g//4
u=I.new('RGB',(a,c))
o=u.load()
for w in range(a):
 for h in range(c):o[w,h]=tuple(e//128*255 for e in p[w*4,h*4])
u.show()

Golfed the testing script I used to create the test cases for this challenge

When you post a challenge, it's good to let a few days before you post your try, so that people can try in all the languages they want.

@OlivierGrégoire I don't see how this answer prevents people from answering...

bash + ImageMagick, 123 50 bytes
convert "$1" -sample 50% +dither -posterize 2 "$2"

Untested, as I haven't actually installed it; I've just cribbed stuff from Stack Overflow. Edit: Saved 73 bytes thanks to @someone.

There's the -posterize flag that probably does the equivalent of the red,lime,blue,... thingy (I don't understand that line properly though).

@someone What that line did was to generate an image with that palette so that the input image could be converted to the same palette.

I think the double quotes are unnecessary (on this website). Mogrify instead of convert can probably save a few bytes too.

bash + netpbm, 30 bytes
pnmdepth 1|pnmscale -nomix 0.5

Takes input on stdin as a PNM file, and outputs on stdout as a PNM file.
pnmdepth 1 reduces the depth of the image on its stdin to 1, and pnmscale 0.5 reduces the size by a half in each direction. The -nomix option is required for pnmscale to choose a pixel from the starting image for each output pixel, instead of mixing adjacent input pixels into one output pixel.

Does it parse .5 as 0.5? (I haven't tried)

MATLAB, 32 bytes
@(x)(x(1:2:end,1:2:end,:)>127)*1

Both input and output are images. Output is an array storing image data, it's not specified in challenge that output image must be displayed. (to display result add 8 bytes for imshow(...) command)
The actual result and original:

Art credit to Janna Sophia.

Processing, 463 bytes
size(500,500);String u="";PImage p=loadImage(u);p.resize(p.width/2,p.height/2);noStroke();color[]c={#ff0000,#00ff00,#0000ff,#00ffff,#ff00ff,#ffff00,#ffffff,0};p.loadPixels();for(int i=0;i<p.width;i++){for(int j=0;j<p.height;j++){float[]d=new float[8];color x=p.get(i,j);for(int k=0;k<8;k++)d[k]=sqrt(sq(red(x)-red(c[k]))+sq(blue(x)-blue(c[k]))+sq(green(x)-green(c[k])));int b=0;for(int l=0;l<8;l++){if(d[l]<=d[b]){b=l;}}fill(c[b]);rect(i,j,1,1);}}save(u+"1.png");

Takes image location, saves pixel art as image1.png.

Image from beeple.


text:
How many fingers does bad pianist need?
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

This is code-golf, so fewest bytes wins.
Standard rules, I/O rules and loophole rules apply.
If possible, link an online demo of your code.
Please explain your code.

Does the human have 4 fingers to the left and to the right of the middle one?

The question addresses your concern in more than one way... (Please see 'arbitrarily suppose for the sake of this example', 'may not assume'.)

You may not assume the answer is no more than 5 Suggested wording: Note that the answer may be more than 5

@mypronounismonicareinstate Yes, if you swap your thumbs with your middle finger and connect both of your hands.

does the novice pianist work out ahead of time which finger is best to start with, or do we have to assume that they start with the finger in the middle of their hand? (so for 5-4-3-2-1 might they need 9 fingers, if they start with the middle one and need four to the left of it)?

@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'!

Slightly related: Parsons code for melodic contours

suggested test case: any array with a zero not in the first position, for languages that directly test the variable to see if it exists (yeah i'm shooting in the foot with PHP ^^)

Huh, I always thought the tune was Should < auld > ac- < quain- < tance > be > for- < got, as shown in the sheet music here.  But looking at various sources online, people seem to be split pretty evenly between what the pitch of that third note should be.

@MichaelSeifert Wikipedia

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

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)

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.

More walrus shenanigans: Try it online!

R, 45 42 bytes
`?`=diff;1+?range(0,cumsum(sign(?scan())))

Try it online!
Thanks to JDL for -3 bytes.

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())

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.

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

Perl 5 -MList::Util=uniq -pa, 35 bytes
$_=uniq map{$c+=$_<=>$p;$p=$_;$c}@F

Try it online!

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!

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.

52 bytes

@J42161217 Thanks for the trick.  Pairing that with multi-argument Union shaves off a few more bytes.

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.

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.

25 bytes. Check out J golfing tips.

19 bytes by directly counting unique numbers.

18 bytes using self-classify =.

@Bubbler Nice solution! I hope you don't mind I updated my answer to explain it.

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)

[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.

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

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

Japt, 8 bytes
Port of Expired Data's solution.
äÎãx rÔÄ

Try it

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


text:
Acyclic orientations of an n-dimensional cube
The goal of this challenge is to check and extend the OEIS sequence A334248: Number of distinct acyclic orientations of the edges of an n-dimensional cube.
Take an n-dimensional cube (if n=1, this is a line; if n=2, a square; if n=3, a cube; if n=4, a hypercube/tesseract; etc), and give a direction to all of its edges so that no cycles are formed. The terms of the sequence are the number of (rotationally and reflectively) distinct orientations that can be obtained.
Example
For n=2, there are 14 ways to assign directions to the edges of a square with no cycles formed:

However, only three of these are distinct if they are rotated and reflected:

So when n=2, the answer is 3.

The winner of this fastest-code challenge will be the program that calculates the most terms when run on my computer (Ubuntu, 64GB RAM) in one hour. If there is a tie, the program that computes the terms in the shortest time will be the winner.

You should consider extending the challenge to include n=5. Or make the winning criterion the number of terms that can be computed in under an hour.

This is a better criterion, I'll adjust it

Oh gosh, this is counting among the exponentially many orientations of graphs that are themselves exponential in size, which likely gives doubly exponential growth. Finding more terms for OEIS will be hard.

I'm afraid running time goes up so quickly that any stupid program works 4 out quickly but quite optimized one can't do with 5

The OEIS sequence has been updated to reflect that A334248(5) = 12284402192625939. Any hope of computing the next term? Obviously this isn’t something that can be brute forced.

Wolfram Language (Mathematica), n = 4, <1 second on my computer
(* Elements of the hyperoctahedral group,represented by matrices *)
HyperoctahedralGroup[n_] :=
  Join @@ Table[
    Permute[IdentityMatrix@n, perm]*sign, {perm,
     Permutations@Range@n}, {sign, Tuples[{1, -1}, n]}];

(* Action of group elements on a vertex of the hypercube,
where each vertex is represented by an integer from 1 to 2^n *)
ActOn[n_, g_, v_] :=
  FromDigits[(1 + (IntegerDigits[v - 1, 2, n]*2 - 1) . g)/2, 2] + 1;

(* Orbits of vertices under such action *)
Orbits[n_, g_] :=
  ConnectedComponents@Table[v <-> ActOn[n, g, v], {v, 2^n}];

(* Whether any orbit contains adjacent vertices *)
OrbitConatinsAdjacentVertices[edges_, orbits_] :=
  Or @@ Or @@@ Outer[SubsetQ, orbits, edges, 1];

(* Merging vertices in each orbit into a single vertex *)
MergeVertices[edges_, orbits_] :=
  Graph@DeleteDuplicates[
    Sort /@ (edges /. (Alternatives@##2 -> #1 & @@@ orbits))];

(* Number of acyclic orientations fixed by some group element *)
InvariantAcyclicOrientations[n_, edges_, g_] :=
  With[{orbits = Orbits[n, g]},
   If[OrbitConatinsAdjacentVertices[edges, orbits], 0,
    Abs[ChromaticPolynomial[MergeVertices[edges, orbits], -1]]]];

(* OEIS sequence A334248 *)
A334248[n_] :=
  With[{edges = List @@@ EdgeList@HypercubeGraph@n},
   Sum[InvariantAcyclicOrientations[n, edges, g], {g,
      HyperoctahedralGroup[n]}]/(2^n*n!)];

Do[Print[n -> A334248[n]], {n, 1, 4}]

Try it online!
Not really optimized. Takes less than 1 seconds on my computer to calculate the first four terms, but takes forever for the fifth term. It seems that Mathematica cannot compute the chromatic polynomial of HypercubeGraph[5] in a reasonable time.
Based on Peter Kagey's deleted answer (which did not consider rotations and reflections), and uses Burnside's lemma.