text:
Reachability measure in Conway's Soldiers
Background
Conway's Soldiers is a version of peg solitaire played on an infinite checkerboard. The board is initially full of pegs below an infinite horizontal line, and empty above it. Following the ordinary peg solitaire rules (move a peg by jumping over another one horizontally or vertically, removing the one that was jumped over), the objective is to move a peg as far above the horizontal line as possible.
Wikipedia page has the solutions for 1 to 4 units above the line: (A and B denote two possible alternatives.)

In ASCII notation (using alternative B):
                         X
               X         .
        X      .         .
_X_   __._   __.__   ____.____
 O    OOO    OOOOO   OOOOOOOOO
 O      O      OOO     OOOO
                      OOOOO
                        OO

Conway proved that it is impossible to reach 5 units above the line with finite number of moves. To prove it, he assigned a value to each peg: if a peg is \$n\$ units away from the target position in terms of Manhattan distance, it is assigned the value of \$\varphi^n\$, where
$$
\varphi = \frac{\sqrt5 - 1}{2}
$$
(The value is the golden ratio minus 1.)
This value was carefully chosen to ensure that every possible move keeps the total value constant when a move is towards X, and decreasing when a move is away from it. Also, the final state must have a peg precisely at the target position, giving the value of \$\varphi^0 = 1\$, so the target position is unreachable if the initial configuration has the value sum less than 1.
For the target position at 5 units above the line, the configuration looks like this:
     X
     .
     .
     .
_____._____
OOOCBABCOOO
OOOOCBCOOOO
OOOOOCOOOOO
    ...

The peg at the position A is given \$\varphi^5\$, the ones at B are \$\varphi^6\$ each, and so on. Then he showed that the sum for the infinite number of pegs is exactly 1, and therefore the value sum of any finite subset is less than 1, concluding the proof of non-reachability.
Task
Now, let's apply this measure to an arbitrary configuration, not just for the original problem, e.g. the pegs may surround the target position:
OOOOO
O...O
O.X.O
O...O
OOOOO

Given such a configuration, calculate Conway's measure on it and output truthy if the measure is at least 1, falsey otherwise. (Note that the truthy output does not guarantee that the target is actually reachable, while the falsey output does say that the target is too far away from the pegs to reach it.)
The calculated measure should be within 1e-6 margin. A program that produces wrong answers when the computed one falls within \$\pm10^{-6}\$ from the true measure is acceptable. You can use (sqrt(5)-1)/2 or 0.618034, but not 0.61803 or 0.61804.
You can choose any three distinct symbols (characters, numbers, or any other kind of values) to indicate a peg, an empty space, and the target position respectively. You can take the grid as a matrix, a list of strings (or lists of symbols), or a single string (or a list of symbols) with a delimiter of your choice. You can assume that the input has exactly one target position, and it is not already occupied by a peg.
Test cases
In the test cases below, O is a peg, X is the target position, and . is a blank.
True
measure = 1 (0.61803 will fail all of the measure=1 cases)
OOX
--------------
measure = 1
OO.X
.O..
.O..
--------------
measure = 1
..X..
.....
.....
OOOOO
..OOO
--------------
measure = 1
....X....
.........
.........
.........
OOOOOOOOO
..OOOO...
.OOOOO...
...OO....
--------------
measure = 4
OOOOO
O...O
O.X.O
O...O
OOOOO
--------------
measure ~ 1.00813
X....OOOO
....OOOO.
...OOOO..
..OOOO...
.OOOO....

False
measure ~ 0.618
OO.X
--------------
measure ~ 0.999975 (0.61804 will fail)
OOOOOOOOOOOOOOOOOOOOOO.X
--------------
measure ~ 0.9868
X....OOO
....OOOO
...OOOO.
..OOOO..
.OOOO...
--------------
measure = 0
.....
.....
..X..
.....
.....

Can we take as input a /-separated string for the grid, such as OO.X/.O../.O..?

@mathjunkie Yes, it's fine.

Conway Checkers - Numberphile

Can we assume that there is at least one peg?

@fireflame241 No.

Python 3.8, 109 bytes
lambda s,i=-1:sum(c%2*.618034**(abs((i:=i+1)//(n:=(h:=s.index)(0)+1)-(x:=h(2))//n)+abs(i%n-x%n))for c in s)>1

Try it online!
Input is a list of integers, created by concatenating all rows of the grid. Each row is terminated by the number 0. Use the numbers 1, 2, 4 to represents "O", "X", ".".

Python 3.8, 108 bytes
lambda s,i=-1:sum(c%2*.618034**(abs((i:=i+1)//(n:=s.find(0)+1)-(x:=s.find(2))//n)+abs(i%n-x%n))for c in s)>1

Try it online!
Pushing the input format a little bit here by using unprintable characters. Input is a single byte string of concatenated rows, where each row is terminated by a NULL character (code point 0).
Replace X with the character SOT (code point 2).
Byte string is essentially an integer list of code points. The reason I'm not using list of integer is because list doesn't have find method. The code points of the row terminator and X are chosen to be single digit.

How:
The length of each row (including the terminator) can be simply calculated as:
n:=s.find(0)+1  # terminator is represented as 0

Similarly, the target position is
x:=s.find(2)    # X is represented as 2

We can then do some modular tricks to figure out the Manhattan distance between a position i and the target x:
abs(i//n + x//n) + abs(i%n + x%n)

All of these are shoved into a single expression by abusing walrus operator.

Python 2, 111 110 bytes
Thanks to @xnor for suggesting to use numbers as input, rather than a list of strings
g=input()
f=g.index;l=f(5)+1
c=i=0
for r in g:c+=r/9*.618034**(abs(f(2)/l-i/l)+abs(f(2)%l-i%l));i+=1
print c>1

Try it online!
Input is a single list of numbers. Uses 9 for pegs, 0 for blanks, 2 for the target, and 5 as a line terminator.

Python 2, 118 bytes
Solution provided by @Surculose Sputum
g=input()
f=g.find;l=f(',')+1;m=f('X')
c=i=0
for r in g:c+=(r<',')*.618034**(abs(m/l-i/l)+abs(m%l-i%l));i+=1
print c>1

Try it online!
Uses + instead of O to represent a peg. Input is a single string where rows are terminated by commas (,).

Original solution, 128 bytes
g=input();l=len(g[0]);g=''.join(g)
m=g.find('X')
c=i=0
for r in g:c+=(r<'-')*.618034**(abs(m/l-i/l)+abs(m%l-i%l));i+=1
print c>1

Try it online!
Uses + instead of O to represent a peg. Input is a list of strings representing the rows

118 bytes by using a different input format: a single string, where all rows are separated by comma.

The challenge also allows numbers rather than characters, which probably lets you shorten stuff.

@xnor Thanks, you're right. I didn't realize it would make a difference at first, but it looks like doing that will let me golf it down quite a bit

J, 46 bytes
$(1<:1#.0.618034^1&#.)@(|@-"1{.)/@(#:I.)1 2=/,

Try it online!

Charcoal, 86 84 bytes
ＷＳ⊞υι≔⌕Ｅυ№ιX¹θ≔⟦⟧ζＦＬυＦ⁻⌕Ａ§υιO⌕§υθX⊞ζ⁺↔⁻ιθ↔κ≔Ｅ²ιδＦ⌈ζ⊞δ↨…⮌δ²±¹Ｉ⊘⁺ΣＥζ⁺§δ⊖ι§δ⊕ι×₂⁵ΣＥζ§δι

Try it online! Link is to verbose version of code. Uses exact surd arithmetic, and then converts the final surd to floating-point using \$ \sqrt 5 \$. Explanation:
ＷＳ⊞υι

Input the configuration.
≔⌕Ｅυ№ιX¹θ

Find the row that contains the X.
≔⟦⟧ζ

Start a list of O distances.
ＦＬυ

Loop through each row.
Ｆ⁻⌕Ａ§υιO⌕§υθX

Loop through each column that contains an O, and calculate the relative column offset from the X.
⊞ζ⁺↔⁻ιθ↔κ

For each relative column offset, add its absolute value to the absolute value of the relative row offset, and push that to the list of O distances.
(I would prefer to write the above as Ｆ⁺↔⁻ιθ↔⁻⌕Ａ§υιO⌕§υθX⊞ζκ which is slightly more efficient but Charcoal can't take the absolute value of an empty list.)
≔Ｅ²ιδ

Now start generating negative Fibonacci numbers starting with \$ F_0, F_{-1} \$ and working down.
Ｆ⌈ζ⊞δ↨…⮌δ²±¹

Get the maximum distance and add that many more negative Fibonacci numbers.
Ｉ⊘⁺ΣＥζ⁺§δ⊖ι§δ⊕ι×₂⁵ΣＥζ§δι

Calculate the total distance using the formula \$ \sum \phi^{-n} = \frac 1 2 \left ( \sum L_{-n} + \sqrt 5 \sum F_{-n} \right ) \$ where \$ L_n = F_{n-1} + F_{n+1} \$.

Jelly, 25 bytes
ŒĠḊạ€Ɲ§µ5½’H*SS<1¬
SS>3aÇ

Try it Online!
All testcases This should yield 6 truthy then 5 falsey outputs (I added the extra cases OX and X, which cause special problems with this algorithm). See the calculated value sums if interested.
Takes input as a rectangular array, where .OX corresponds to 012 (empty, peg, target).
How it works
ŒĠḊạ€Ɲ§µ5½’H*SS<1¬  # Is the value sum at least 1?
ŒĠ                    # Get an tuple of (coords of all 0 entries, coords of all 1 entries, coords of all 2 entries)
                      # If the matrix does not contain one of these, then that element of the tuple is left out, necessitating the SS>3 check
  Ḋ                   # Dequeue: remove the irrelevant coords of all 0 entries
   ạ€Ɲ                # Get the absolute (x,y) offset of all 1 entries from the 2 entry
      §               # Sum for Manhattan distance
       µ              # We are left with the Manhattan distances of each 1 from the 2
        5½’H          # (sqrt(5)-1)/2
            *         # to the power of
             S        # Each distance (S is sum, why is this an identity?)
              S       # Sum these powers to get the value sum
               <1¬    # Is this not less than 1? (Jelly has no <= operator)
                      # As a side note, ‘ÆC counts the number of primes <= z+1
                      # This is the same number of bytes as <1¬ and also returns a nonnegative value iff z is at least 1

SS>3aÇ               # Main link
SS>3                  # Is the sum of all entries > 3? (this is necessary to deal with having no pegs or no blanks, which messes with ŒĠ)
    a                 # and
     Ç                # the value sum is at least one

Extras
Another 25-byte solution:
;0ŒĠḊạ€Ɲ§µ5½’H*SS<1¬
ḢLaÇ

21 bytes if [[2]] (target but no pegs) is not included as a testcase;
;0ŒĠḊạ€Ɲ§µ5½’H*SS

Pyth, 37 bytes
!>1s.e*/b9^t.n3+a/KxQ2JhxQ5/kJa%KJ%kJ

Try it online! (You can copy-paste formatted test cases from my Python answer)
Port of my Python answer. Input is a single list of numbers. Uses 9 for pegs, 0 for blanks, 2 for the target, and 5 as a line terminator.
!>1s.e*/b9^t.n3+a/KxQ2JhxQ5/kJa%KJ%kJ
                  KxQ2       Initialize K to be the index of 2 in the input
                      JhxQ5  Initialize J to be the index of 5, plus 1
    .e                       Enumerated Map over the input, with b as the value, k as the index
            .n3              pre-initialized constant: phi (~1.6180339)
           t                  minus 1
          ^                  raised to the exponent:
                a/KJ/kJ       absolute difference between K/J and (index)/J
               +               plus
                a%KJ%kJ       absolute difference between K%J and (index)%J
                             (this gives us the manhattan distance between the current point and the target)
      *                      Multiply by
       /b9                    divide b by 9, yields 1 if b is a peg, 0 otherwise
   s                    Sum the mapped values
!>1                     Return true if greater than or equal to 1, false otherwise
                       (We can't use "less than" because the first test case yields 1.0 exactly)


text:
Evaluating Logic Gates
Logic gates are functions which perform basic logic operations. In this problem, we will account for the following 6 logic gates: AND, OR, XOR, NAND, NOR, and XNOR. Each of these takes two boolean inputs \$ a \$ and \$ b \$, and outputs a boolean. Below are the truth tables which show the output of each gate given two inputs.

Task
Given two boolean inputs \$ a \$ and \$ b \$, return/output a list of the names of all gates which would return a Truthy value. The order doesn't matter, but the names must be in the exact format as given in the 2nd sentence of the above paragraph (not the ones in the diagram). You are also allowed to output them exclusively in lowercase, if desired.
Clarifications

You may also output a delimiter-separated string
I will allow leading/trailing spaces

Test Cases
Input
0 0
0 1
1 0
1 1

Output
[NOR, NAND, XNOR]
[OR, NAND, XOR]
[OR, NAND, XOR]
[OR, AND, XNOR]

This is code-golf, so the shortest code in bytes wins!

Can output be a string with a space between elements, such as or and xnor?

@Cloudy7 Yes, that's allowed.

Can output have leading/trailing spaces?

@Bubbler Sure thing.

Can I output the bitwise operators for each one?

@Iamkindofalanguagedev No, it has to be those specific words. Sorry for the (semi)-late response.

Python 3, 53 50 49 bytes
Thanks @JonathanAllan for saving 1 byte!
lambda a,b:"NOR N"[a|b:5-a*b]+"AND X"+"NOR"[a^b:]

Try it online!

I really like how you use the bitwise operations themselves for indexing.

Unfortunately it loses the use of & but lambda a,b:"NOR N"[a|b:5-a*b]+"AND X"+"NOR"[a^b:] is 49 bytes TIO.

@JonathanAllan multiplication is pretty much  the same as &, so I'll take that. Thanks!

J, 46 bytes
;:@'AND NAND OR NOR XOR XNOR'#~*,*:,+.,+:,~:,=

Try it online!
-5 bytes thanks to Bubbler
We execute a train *,*:,+.,+:,~:,= corresponding to the gates on the arguments, which will produce a single boolean mask of the results.
We then apply that mask as a filter #~ on the list of words, which is in the same order.
Note: Since the returned strings of are of unequal length, J requires them to be boxed.

You don't need parens there for an obvious reason. But then, you can go for filtering Ns at 42 bytes.

Well it's shorter without Evoke Gerund... (Basically replace all backticks with , and remove the trailing 3 bytes)

Thanks Bubbler!  I've taken 2 of the 3 suggestions.  As for the 42 byte solution, it's clever and different enough that you can feel free to post yourself.  It's similar to the python solution, and this is rare case where I think I prefer the cleanness of this single mask solution to the cleverness of the string manipulations (even though it's slightly less golfy).

Python 2.7, 117 111 102 98 bytes
-6 bytes thanks to @math junkie!
-13 bytes thanks to @Surculose Sputum!
Try it online!
Probably could be made shorter with lambda but I don't know how to use it:
a,b=input()
s="or nand xor"
if a==b:s=s.replace("o","no")
if a&b:s=s.replace("na","a")[1:]
print s

EDIT: Yep. This program uses string manipulation to solve the problem, which I thought was simpler, but now I'm not so sure.

Surculose Sputum's answer is compatible with Python 2 and is much shorter than yours.

You can save some bytes by moving the body of each if statement to the same line as the if

@HighlyRadioactive I posted my answer within a minute of Surculose, so when I was writing this Surculose had not answered yet.

There are a couple of saves here: s can be initialized as a default argument, saving 1 byte. Getting rid of i, and replacing i!=1 and i==2 directly with a==b and a&b saves another 8 bytes. Try it online!

@SurculoseSputum Odd. Don't know how that one slipped by. Also, that footer thing is neat.

@Cloudy7 I really like the header/footer feature too. You can even test a whole Python program with it by wrapping the code block in a string and calling exec. Demonstration with a 4 bytes save.

@SurculoseSputum Is that really shorter? It must be because of the indentations required. Definitely will need practice golfing in this language.

@Cloudy7 Off-topic: So it's extremely similar to one of my first answers. I payed 0% efforts on that though.

Ruby, 49 bytes
->a,b{"#{?N[a|b]}OR #{?N[a&b]}AND X#{?N[a^b]}OR"}

Try it online!
Interpolates 'N' into the output string conditionally for each gate.
Alternatively, a direct port of @Surculose Sputum's excellent Python answer (be sure to upvote it!) is also 49 bytes:
->a,b{"NOR "[a|b,4]+"NAND X"[a&b,6]+"NOR"[a^b,3]}

Try it online!

J, 39 37 bytes
[:;(_5<\'NAND NOR XNOR')}.~&.>*,+.,~:

Try it online!
-2 bytes thanks to @Jonah.
A solution that pretty much works like Surculose Sputum's Python 3 answer.
How it works
NB. The three segments in the new version
_5<\'NAND NOR XNOR'
    'NAND NOR XNOR'  NB. a length-13 string
_5<\                 NB. enclose non-overlapping length-5 chunks
      (which works because the three N's to filter appear at indexes 0, 5, 10)

NB. Previous version
[:;('NAND ';'NOR X';'NOR')}.~&.>*,+.,~:  NB. Input: two bits as left/right args
                                *,+.,~:  NB. evaluate AND, OR, XOR
   ('NAND ';'NOR X';'NOR')               NB. corresponding three segments
                             &.>  NB. pair up both sides unboxed and
                          }.~     NB.   drop the first char from left if right is 1
[:;  NB. Remove boxing and concatenate into a single vector

37 bytes

@Jonah Nice. I knew that the N's are at nice positions, but somehow I missed that one.

brainfuck, 234 bytes
>-[-[-<]>>+<]>-[<<++>+>-]<<+<<<-[+>++[++<]>]>-->>[>>>>[-]<<<<[>>+>>+<<<<-]<]<<,<,[>+<-]>[>+>+>>+<<<<-]>>>>--[>.<[-]]>>.>.>+++.>.[<]<<[>>+<<-]>+>[<[-]>[-]]<[->+<]>[>.<[-]]>+.+++.<<<<[>>>+<<<-]>>>>>>>>.<<<<++++++.<-[>>>.<<<[-]]>>>+.+++.

Try it online!
Takes input as two bytes (0 or 1) on stdin, outputs space-separated to stdout without trailing whitespace.
The TIO link has the 11 test case because I couldn't figure out how to type the null character into a web browser, but if you delete the second input character it will do the same thing as the 10 test-case, and if you delete both it will be the same as the 00 test-case.
Here's my annotated version (the two input bytes are b and a, their sum is c):
-[-[-<]>>+<]>- *32* from https://esolangs dot org/wiki/Brainfuck_constants#32
[<<++>+>-]      64 32 *0*
<<+<<<            *0* 0 0 65 32
-[+>++[++<]>]>-- *78* 65 32 from https://esolangs dot org/wiki/Brainfuck_constants#78

>>

 [>>>>[-]<<<<[>>+>>+<<<<-]<] 0 *0* 0 0 78 65 78 65 32

<<
,<,          *b* a     0 0 0 0 78 65 78 65 32
[>+<-]>      0 *b plus a=c* 0 0 0 0 78 65 78 65 32
[>+>+>>+<<<<-]>>>> 0 0 c c 0 *c* 78 65 78 65 32

--                      0 0 c c 0 *c minus 2* 78 65 78 65 32
[>.<[-]]>>.>.>+++.>.    0 0 c c 0 0   78 65 78 *68* 32    (N)AND space  print N if c != 2
[<]<<[>>+<<-]>>         0 0 c 0 0 *c* 78 65 78 68 32
<+>[<[-]>[-]]<[->+<]>   0 0 c 0 0 *!c* 78 65 78 68 32
[>.<[-]]>+.+++.         0 0 c 0 0 0  *82* 65 78 68 32     (N)OR         print N if c == 0
< <<<[>>>+<<<-]>>>      0 0 0 0 0 *c* 82 65 78 68 32
>>>>>.<<<<++++++.<      0 0 0 0 0 *c* 88 65 78 68 32      space X
-[>>>.<<<[-]]           0 0 0 0 0 *0* 88 65 78 68 32      (N)           print N if c != 1
>>>+.+++.               0 0 0 0 0 0   88 65 *82* 68 32

05AB1E, 28 bytes
.•UNœ5Z’dµ•#εI…PàONè.Vi'nõ.;

Try it online!

Nice approach with the indexing and .V. :) Equal-bytes alternative for the first part using the dictionary: ’n€ƒxš¯š¯’4ôεI…POà

JavaScript (ES6), 55 bytes
a=>b=>'1OR 3AND X5OR'.replace(/\d/g,n=>n>>a+b&1?'N':'')

Try it online!
How?
For each gate type, we use the sum of \$a\$ and \$b\$ to right-shift a bit mask. We test the least significant bit of the result to find out if we must return the complementary form of the gate.
   a  | 1 | 0 | 1 | 0 |
   b  | 1 | 1 | 0 | 0 |
------+---+-------+---+---------
  a+b | 2 |   1   | 0 | decimal
------+---+-------+---+---------
  NOR | 0 |   0   | 1 |    1
 NAND | 0 |   1   | 1 |    3
 XNOR | 1 |   0   | 1 |    5

JavaScript (ES6), 55 bytes
Using a template literal is just as long.
a=>b=>['N'[a|b]]+`OR ${['N'[a&b]]}AND X${['N'[a^b]]}OR`

Try it online!

C (gcc), 65 60 58 bytes
f(a,b){printf("NOR %s X%s"+(a|b),"NAND"+a*b,"NOR"+(a^b));}

Try it online!

The " X" part can go in the format string to make it more idiomatic C.  This direct port is kind of obfuscated for no reason because Python was using string concat, not a separate format string.  I don't see any savings, though, unless any of those operators or logical versions of them like a&&b have higher precedence than +.  &"NOR"[a|b] might be legal but it's not clearer and is break-even on byte count.

@PeterCordes Interesting. Your bit about moving the " X" part into the format string gave me the idea of moving the whole first argument into the format sting for -5 bytes - thanks! :-)

@PeterCordes && doesn't have higher precedence than + but * does for -2 bytes! :D

Cool, glad there's some C-specific golfing to do here to make this answer more interesting. :)

Retina 0.8.2, 37 bytes
00
N2N
11
ODN
\d+
OND
D
AND X
O|$
OR

Try it online!
Input is as a single 2-digit string (one of 00, 01, 10, or 11). Performs a series of replacements to arrive at the required output.
Explanation
AND X is a string common to all 4 outputs, so we encode the string as D.
OR appears in a bunch of places so we encode that as O.
Then, we can replace each pair of digits with a string of Ns, Os and Ds. (The 00 -> N2N and the \d+ -> OND are golfs arising from 10 and 01 yielding the same output and sharing some overlap with the output for 00.
Finally, we just replace the Os and Ds with the expanded string mentioned above and we get the required list!

Wow, that's some serious golfing, the best I could do was 40 bytes...

Bash + Core utilities, 53 49 bytes
tr 01 N\\0<<<"$[$1|$2]OR $[$1&$2]AND X$[$1^$2]OR"

Try it online!
This is a full program.  Input is passed as arguments, and the output is written to stdout.

Pyth, 37 bytes
AQ%"%sOR X%sOR %sAND"*R\N!M[|GHxGH&GH

Try it online!
Takes a list of two values as input, outputs in the form AND OR XNOR
Explanation
AQ                                     # Q is the input. Set G:=Q[0], H:=Q[1]
  %                                    # Format a string (printf-style)
   "%sOR X%sOR %sAND"                  # Format string
                     *R\N!M[|GHxGH&GH  # replacement values as a list:
                           [           # [                        ]
                            |GH        #  G or H
                               xGH     #          G xor H
                                  &GH  #                   G and H
                         !M            # map each to its negation
                     *R\N              # map each x to "N"*x

(Ab)uses the fact that in Python and thus Pyth, True == 1 and False == 0 and thus "N"*True == "N" and "N"*False == "".

Cool solution, but you can get it down to 31 bytes by porting @Surculose Sputum's answer: Try it online!

29 bytes: Try it online!

Jelly, 23 bytes
S11,:Sµ“×®ṫ.¡Ḍẹhɗ»x€⁸¦0

A monadic Link accepting a list of two integers (in [0,1]) which yields a list of characters - the gate names separated by spaces.
Try it online! Or see the test-suite.
How?
Observe that there are three outputs, aligning with the sums and that the sum \$1\$ and sum \$2\$ outputs are the sum \$0\$ one missing certain characters. When one-indexed the sum \$1\$ needs characters 1 and 11 removed while the sum \$2\$  one needs characters 1 and 5 removed. Furthermore \$\lfloor \frac{11}{2} \rfloor = 5\$.
S11,:Sµ“×®ṫ.¡Ḍẹhɗ»x€⁸¦0 - Link: list of integers, B  e.g [0,0]            [1,1]            [1,0] (or [0,1])
S                       - sum (B)                        0                2                1
 11                     - literal eleven                 11               11               11
   ,                    - pair                           [11,0]           [11,2]           [11,1]
     S                  - sum (B)                        0                2                1
    :                   - integer division               [inf,nan]        [5,1]            [11,1]
      µ                 - start a new monadic link, call that X
       “×®ṫ.¡Ḍẹhɗ»      - compressed string              "NOR NAND XNOR"  "NOR NAND XNOR"  "NOR NAND XNOR"
                   € ¦  - sparse application...
                    ⁸   - ...to indices: chain's left argument
                  x   0 - ...action: repeat zero times   "NOR NAND XNOR"  "OR AND XNOR"    "OR NAND XOR"

APL (Dyalog Unicode), 30 bytes
∊'NAND ' 'NOR X' 'NOR'↓⍨¨∧,∨,≠

Try it online!
A port of my own J answer.
How it works
∊'NAND ' 'NOR X' 'NOR'↓⍨¨∧,∨,≠
                         ∧,∨,≠  ⍝ AND, OR, XOR
 'NAND ' 'NOR X' 'NOR'↓⍨¨       ⍝ Drop an N from the string segments at ones
∊                               ⍝ Flatten

05AB1E, 42 bytes
.•Vs’9ìï´¸•.•B»Î5γ'¸•DŠ‚s.•B»¯4qld•‚«IðмCè

Try it online!
Makes a list: ["nor nand xnor", "or nand xor", "or nand xor", "or and xnor"]; the input is read as a binary number and that corresponds to the position in the list. This could probably be reduced heavily as I see the other 05ab1e answer just uses "nand nor xnor" as its string.

x86-16 machine code, IBM PC DOS, 57 52 bytes
Binary:
00000000: a182 0025 0101 8bd8 ba2f 0152 0ac4 7401  ...%...../.R..t.
00000010: 42b4 09cd 21ba 2801 84df 7401 42cd 215a  B...!.(...t.B.!Z
00000020: 32df 7401 42cd 21c3 4e41 4e44 2058 244e  2.t.B.!.NAND X$N
00000030: 4f52 2024                                OR $

Listing:
A1 0082     MOV  AX, [0082H]        ; load command line chars into AH/AL
25 0101     AND  AX, 0101H          ; ASCII convert
8B D8       MOV  BX, AX             ; save input to BX for later
BA 012F     MOV  DX, OFFSET NOR     ; DX = string 'NOR'
52          PUSH DX                 ; save 'NOR' for later
0A C4       OR   AL, AH             ; OR or NOR?
74 01       JZ   OUT_NOR            ; is OR?
42          INC  DX                 ; increment string pointer to skip 'N'
        OUT_NOR:
B4 09       MOV  AH, 9              ; DOS write string function
CD 21       INT  21H                ; write to STDOUT
BA 0128     MOV  DX, OFFSET NAND    ; DX = string 'NAND X'
84 DF       TEST BL, BH             ; AND or NAND?
74 01       JZ   OUT_NAND           ; is AND?
42          INC  DX                 ; increment string pointer to skip 'N'
        OUT_NAND:
CD 21       INT  21H                ; write string to STDOUT
5A          POP  DX                 ; Restore DX = 'NOR'
32 DF       XOR  BL, BH             ; XOR or XNOR?
74 01       JZ   OUT_XOR            ; is OR?
42          INC  DX                 ; increment string pointer to skip 'N'
        OUT_XOR:
CD 21       INT  21H                ; write string to STDOUT
C3          RET                     ; return to DOS

    NAND    DB  'NAND X$'
    NOR     DB  'NOR $'

A standalone PC DOS executable.  Input via command line, output string to STDOUT.
I/O:

OIL, 81 bytes
5
1
5
NAND OR XOR
10
NAND NOR XNOR
1
9
20
10
AND OR XNOR
6
14
17
4
10
3
4
5
3
4
3

As usual with golfed OIL code, we use cells as both data and code. All the strings also serve as references to the cell #0 (which will later contain the second input), and we use cell #6 (the one containing a 1) as both a reference to cell #1, as well as the value 1.

Aceto, 67 bytes
pdA`ANpn
"Ln>"D"L
RON'  Ov
 "p   Vu
p^`p"pX
N''XRO
irHL "<`
riMdpN'

Try it online!

I'm using quick storage for one of the inputs, the stack for the other. It's mostly conditionally escaped movement to avoid printing N, but I also used the reverse-and-jump-to-the-end trick for a few saved bytes.

Common Lisp, 154 bytes
Not a short answer, but relies on BOOLE, which is a function that is practically never used:
(lambda(a b)(loop for(n o)in`((and,boole-and)(nand,boole-nand)(or,boole-ior)(nor,boole-nor)(xor,boole-xor)(xnor,boole-eqv))if(/=(boole o a b)0)collect n))

Readable version:
(loop
   for (name op) in `((and  ,boole-and)
                      (nand ,boole-nand)
                      (or   ,boole-ior)
                      (nor  ,boole-nor)
                      (xor  ,boole-xor)
                      (xnor ,boole-eqv))
   unless (= (boole op a b) 0)
   collect name)

All couples (name op) in the list are made of name, a symbol used for the output, and op, a constant integer value that represents a particular boolean operation.
The boole functions knows how to perform the operation based on such value. Note that xnor is the equivalence operation, namely boole-eqv.
The loop builds a list of names such that the associated operation yields a non-zero result.
Indeed, if you do:
(boole boole-nand 1 1)

The result is -2, a.k.a. -10 in binary; this is because those operations assume an infinite two's complement representation (https://comp.lang.lisp.narkive.com/OXYD1hNK/two-s-complement-representation-and-common-lisp)

Factor, 55 bytes
[ + { "NOR NAND XNOR""OR NAND XOR""OR AND XNOR" } nth ]

Try it online!
Add and index into list of strings.
This one's pretty boring, so here's a longer but more interesting version:
Factor, 73 bytes
[ [ or ] [ and ] [ xor ] 2tri [ "" "N"? ] tri@ "%sOR %sAND X%sOR"printf ]

Try it online!
My first submission in Factor! Hopefully the first of many, since this language is really cool. Technically this doesn't run on new versions of the language because I didn't put spaces after some strings, but it works on the old version TIO has. (I would use ATO, but it's offline at the moment.)
Explanation:
[ ... ] Quotation (anonymous function) taking two booleans
[ or ] [ and ] [ xor ] 2tri Apply each of the three quotations or, and, xor on the two booleans
[ "" "N"? ] tri@ Apply  to each of the three results:  If true, "", else "N"
"%sOR %sAND X%sOR"printf Insert each "" or "N" into the right part of the string, and print.

Python 3, 60 bytes
Not really close to the gold, but found it interesting that just picking from the list of options is within 11 bytes of the best python answer, and more than 30 bytes smaller than the other python answer. Shows how impressive golfing those 11 bytes are imo.
Also shorter than some other langs that i think could also implement the same method.
lambda a,b:['nor nand xn','or nand x','or and xn'][a+b]+'or'

Try it online!

Io, 65 bytes
Port of Surculose Sputum's Python answer.
method(a,b,"NOR "slice(a|b).."NAND X"slice(a&b).."NOR"slice(a^b))

Try it online!

Charcoal, 160 bytes
×N¬ΣθOR ×N‹Σθ²AND X×N↔⊖ΣθOR

Try it online! Link is to verbose version of code. Takes input as an array or string of two bits. Explanation: Just interpolates the Ns as appropriate based on the count of 1 bits (zero for the first N, less than 2 for the second, and absolute difference from 1 for the third).

Haskell, 78 Bytes
a?b=[h(a||b)"OR""NOR",h(a&&b)"AND""NAND",h(a/=b)"XOR""XNOR"];h x a b|x=a|9>0=b

source: Stack Exchange

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

sort: votes


text:
Missile-mounted cameras
You are employed as Administrator in charge of Road Maintenance and Planning. The intelligence division  of the Agency for Road Maintenance and Planning has come up with a brilliant and not at all inefficient way to take random sample pictures of the roads: missiles with cameras on them.
In this genius and not at all wasteful technique, smart non-explosive missiles are sent hurtling down each road. Each missile moves in a straight line and captures images at equal spatial intervals. Eventually the Agency will get a good overall sample of the state of affairs for each road. On Masagaki Road, for example, images are captured at positions 1, 4, 5, 6, 8, 11, 12 and 14:
1 X X 4 5 6 X 8 X X 11 12 X 14 (X represents no image)
Your job is to find the largest number of images that could have been captured by the camera on a single missile. A single camera could have captured the three images at positions 4, 5, 6 (having a spacing of 1); the three images at positions 4, 6, 8 (spacing 2); or the three images at 4, 8, 12 (spacing 4). However, here the answer is four: positions 5, 8, 11, 14 (spacing 3).
Input: a sequence of \$1\leq n\leq1000\$ unique integers, each satisfying \$1\leq i\leq1000000\$, representing the positions of the images captured for a certain road. These will be given from smallest to largest.
Output: a single integer representing the largest number of images that could have been captured by a single camera.
Sample 1
Input: 1 4 5 6 8 11 12 14
Output: 4
Sample 2
Input: 5 8 9 10 12 15 16 17
Output: 3

code-golf; the shortest code in bytes wins.
The linked rules apply.
Please explain your code.
Please link to Try It Online! or another online demo.

Inspired by 'Air Drop' (AIO 2007, Senior)

Ah yes. Missiles. The best and most common way of conducting road planning! \s

Q: Why is no one rioting over the use of missiles? A: This is not within the scope of the question.

Maybe I'm missing something obvious, but for sample 2, how do you get 4 ?

@xnor Sorry, 3.

Python 2, 74 bytes
lambda l:max(reduce(lambda i,x:i+(a+i*(b-a)==x),l,0)for a in l for b in l)

Try it online!
Tries every possible sequence of the form a,b,... with a and b in the input l.
To find the smallest index i of this arithmetic progression that's outside l, we do something a bit unusual. Instead of counting up the progression to find an element not in l, we iterate over l, taking advantage of it being sorted. For each successive element x of l, we move to the next index in the arithmetic progression if its current value matches x, and stay at the current index otherwise.

I like how you use reduce to find sequence length, very clever!

05AB1E, 8 bytes
æʒ¥Ë}€gà

Try it online!
æ          # power set
 ʒ  }      # filtered by:
  ¥        #  deltas
   Ë       #  all equal
     €g    # length of each
       à   # maximum

Power set??? The runtime exceeds 60 s once you get to the hundreds of elements.

Of course, I didn't say anything about time in the question...

@lightlyheld yup, the default for code-golf questions is that any runtime is fine, as long as the code works for arbitrarily large inputs in theory. If that's not what you want, you sould add the restricted-complexity tag. (Might be too late here, but for future questions).

Python 2, 98 bytes
f=lambda l,i=1:i/l[-1]or max(f(l,i+1),*[g(a,l,i)for a in l])
g=lambda a,l,i:a in l and-~g(a+i,l,i)

Try it online!
A function that takes in a list of integers and returns the max number of images
Approach: Try for each element a in the list, and for each increment i in the range 1 to max(l).

Charcoal, 22 bytes
Ｉ⊟Φ⊕Ｌθ⊙θΦ⌈θ¬⁻⁺×…⁰ι⊕νλθ

Try it online! Link is to verbose version of code. Explanation:
     θ                  Input array
    Ｌ                   Length
   ⊕                    Incremented
  Φ                     Filter over implicit range
       θ                Input array
      ⊙                 Any element where
          θ             Input array
         ⌈              Maximum
        Φ               Filter over implicit range where
               …⁰ι      Range of length given by outer index
              ×   ⊕ν    Multiplied by incremented inner index
             ⁺      λ   Offset by selected element
            ⁻        θ  Set difference with input array
           ¬            Is empty (i.e. this is a subset)
 ⊟                      Take the last (i.e. highest) element
Ｉ                       Cast to string for implicit print

The second Φ would be ⊙ except Charcoal doesn't support this.

Red, 127 bytes
func[b][m: 0 repeat s t: last b[n: 1 forall b[d: s until[either
find b b/1 + d[n: n + 1][m: max n m n: 1 d: t]t < d: d + s]]]m]

Try it online!
Naive imperative solution.
Explanation:
f: func [b][
    m: 0                                 ; the max number of images so far
    repeat s t: last b [                 ; s (for step) is a list 1..last
        n: 1                             ; current max
        forall b [                       ; iterate over the input
            d: s                         ; current step
            until [                      ; and do the following :
                either find b b/1 + d [  ; if there is a number in the list that is equal
                                         ; to the current number + the current step
                    n: n + 1             ; increase the current max
                ][                       ; else
                    m: max n m           ; update max,
                    n: 1                 ; reset current max
                    d: t                 ; and set the current step at the last number
                ]
                t < d: d + s             ; until current step is beyond the last number
            ]

        ]
    ]
    m                                    ; return max
]

JavaScript (ES6), 89 bytes
A=>A.reduce((a,x)=>[...a,...a.map(y=>x-2*y[0]+y[1]?y:(b+=!!y[b],[x,...y]))],[[]],b=0)|b+1

Try it online!
Commented
A =>                  // A[] = input array
  A.reduce((a, x) =>  // for each value x in A[],
                      // using a[] as the previous list of lists:
    [                 //   build a new list of lists:
      ...a,           //     append all previous lists stored in a[]
      ...a.map(y =>   //     for each list y[] in a[]:
        x -           //       if both y[0] and y[1] are defined
        2 * y[0] +    //       and (x - y[0]) is not equal
        y[1] ?        //       to (y[0] - y[1]):
          y           //         leave y[] unchanged
        :             //       else:
          ( b +=      //         increment b if:
              !!y[b], //           y[b] is defined (i.e. the length of y[] is b+1)
            [x, ...y] //         prepend x to y[]
          )           //
      )               //     end of map()
    ],                //   end of the new list of lists
    [[]],             //   start with a[] containing a single empty list
    b = 0             //   start with b = 0
  )                   // end of reduce()
  | b + 1             // return b + 1

Perl 5, 111 bytes
$_=max(map{$j=$_;(grep{(reduce{$a.(' 'x(-1+$b-length$a)).'x'}@F)=~join'.'x$j,('x')x$_}1..$F[-1])[-1]}0..$F[-1])

Try it online!

Jelly, 8 bytes
ŒPIE$ƇṪL

A monadic Link accepting a list which yields an integer.
Try it online!
How?
We are looking for the longest sub-sequence which has equal incremental differences, this just filters all sub-sequences in length order and takes the length of the last one.
ŒPIE$ƇṪL - Link: list of numbers
ŒP       - powerset (all sub-sequences ordered by length)
    $    - last two links as a monad:
  I      -   incremental differences (e.g. [4, 7, 11] -> [7-4,11-7] = [3,4])
   E     -   all equal?
      Ṫ  - tail
       L - length

Erlang (escript), 102 bytes
Port of xnor's Python 2 answer.
f(R)->lists:max([lists:foldl(fun(X,I)->I+(case A+I*(B-A)==X of true->1;_->0 end)end,0,R)||A<-R,B<-R]).

Try it online!

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


text:
Donation arms race
The barfoos, a hypothetical alien species, go about charity in an interesting way.
Every morning, barfoo Specialists come up with an ordered list of causes to donate to, and for each cause they recommend what quantity of resources should be donated.
That wasn't the weird part. Here's the weird part:
A random civilian barfoo will donate the recommended quantity of resources to the first cause. Another one will likewise donate to the very next cause on the list, and keep going down the list until it has given at least as much as its compatriot, at which point it immediately stops.
This continues, each civilian giving at least as much as the one directly before, until the remaining elements of the Great List of Charitable Causes can no longer satisfy this donation arms race, at which point the Specialists themselves just chip in.
How many civilian barfoos are involved?
Input: a sequence of \$1\leq n\leq100000\$ integers each of value \$1\leq i\leq1000\$, representing the recommended donation sizes for the Great List of Charitable Causes in the order in which it's given to the barfoos.
Output: a single integer representing the number of civilian barfoos who donate something.
Sample 1
Input: 5 2 3 1 3 4 2 5
Output: 3
This may be divided into the buckets 5, 2 3 (sum 5), 1 3 4 (sum 8) and 2 5 (sum 7, cannot satisfy a fourth civilian barfoo).
Sample 2
Input: 4 1 2 3 6 6
Output: 4
This may be divided into the buckets 4, 1 2 3 (sum 6), 6 and 6. (In this case, no Specialists need to involve themselves.)

code-golf; the shortest code in bytes wins.
The linked rules apply.
Please explain your code.
Please link to Try It Online! or another online demo.

Credit: 'Nomnomnom' (AIO 2009, Senior)

I appreciate how you're rewriting from the olympiad and linking them to give credit.

For some reason, all three rules links are getting redirected to random code golf answers. Is that a bug?

@Kale_Surfer_Dude The problem was that they were supposed to point to Codegolf Meta.

Python 2, 60 bytes
d=p=t=0
for x in input():
 d-=x
 if d<1:t+=1;p=d=p-d
print t

Try it online!
The code is easier to understand in the below version, which is fairly natural: t tracks the number of barfoos who donate, p tracks the previous donation, and s tracks the sum of the current barfoo's donation.
61 bytes
s=p=t=0
for x in input():
 s+=x
 if s>=p:t+=1;p=s;s=0
print t

Try it online!
The original replaces tracking s with tracking d=p-s, the amount the current barfoo needs to donate to catch up with the previous donation. This lets us replace s>=p with d<1, saving a byte. Note that s/p doesn't work because p starts at 0.

out of curiosity, what's the reason you (and many others) golf in python2 rather than python3?  is it just familiarity or did python3 changes make it somehow less golfy?

@Jonah One reason for me is because in Python 2, input() evaluates the input string and can returns any type of object, as oppose to Python 3 where input() always returns a string. Also, print, exec, and integer division in Python 2 is shorter.

@Jonah Though I do sometimes strategically pick between Python 2 and 3 depending on which on is shorter for the problem at hand, I also do have a sentimental bias for Python 2, which is what I first started golfing in. And, for instance, Python 3.6's f-strings make some ASCII art challenges too straightforward in my mind, so I like golfing those in Python 2 where more tricks are needed.

What is the input format for this?
I tried passing in 5 2 3 1 3 4 2 5, it errors out with invalid syntax on the first "2".
EDIT: Oh, just saw the TIO link, it's accepting list.

Python 3.8 (pre-release), 59 57 59 58 bytes
Don't mind me, just abusing the walrus
lambda y,p=0,d=0:len([p:=(d:=p-d)for x in y if(d:=d-x)<1])

Surculose Sputum shaved a byte using xnor's idea to keep track of the remaining amount of donation needed instead of the current donation.
Try it online!

58 bytes by using @xnor's idea. a keeps track of the remaining amount of donation needed.

JavaScript (ES6), 50 bytes
f=([v,...a],p,s=0)=>v?(s+=v)<p?f(a,p,s):1+f(a,s):0

Try it online!
Commented
f = (            // f is a recursive function taking:
  [ v,           //   v = next entry in the input array
    ...a ],      //   a[] = all remaining entries in the input array
  p,             //   p = previous donation, initially undefined
  s = 0          //   s = current donation
) =>             //
  v ?            // if v is defined:
    (s += v)     //   add v to s
    < p ?        //   if the result is less than the previous donation:
      f(a, p, s) //     do a recursive call with the updated s
    :            //   else:
      1 +        //     increment the final result
      f(a, s)    //     do a recursive call with p = s (and s = 0, implicitly)
  :              // else:
    0            //   stop recursion

Jelly, 8 bytes
ŒṖ§ṢƑƇḢL

A monadic Link accepting a list of numbers which yields a non-negative integer.
Try it online! (not efficient)
How?
ŒṖ§ṢƑƇḢL - Link: list
ŒṖ       - all partitions (order is such that those with shorter sublists at the left appear first)
  §      - sums (sum each part of each partition)
     Ƈ   - filter keep those for which:
    Ƒ    -   is invariant under:
   Ṣ     -     sort
      Ḣ  - head
       L - length

Pyth, 8 bytes
lesDI#./

Try it online!
Form all ordered partitions ./, then filter # for the partitions which are invariant I under sorting D by sum s. Take the last one the survived the filler e, which is also the longest due to the order that ./ outputs partitions, and return its length l.
This is one of the longest string of prefix modifiers (DI#) I've ever used, it's a challenge that fits Pyth quite well.

Python 2, 64 62 bytes
f=lambda l,p=1,c=0:c/p and-~f(l,c)or l>[]and f(l[1:],p,c+l[0])

Try it online!
A recursive function that takes in a list of integers and returns the number of barfoos.
How: p and c keeps track of the previous donation and the current donation. If the current donation is sufficient, moves to a new barfoo. Otherwise, adds another cause to the current donation.

05AB1E, 10 bytes
.œ.ΔOD{Q}g

Try it online!

Not bad, but even when I input an array of only 1,000 integers, runtime goes above 60 s. Of course, I didn't say anything about time in the question...

C (gcc), 60 bytes
Port of xnor's Python answer.
n;m;s;f(int*l){for(n=m=s=0;*l;s=s<1?++n,m-=s:s)s-=*l++;s=n;}

Try it online!
Inputs a zero-terminated integer array.

C (gcc), 56 bytes
Similar to my JS answer, but with \$p\$ and \$s\$ declared in the global scope. They are reset to \$0\$ on the last iteration to make sure that the function is reusable.
Takes a zero-terminated array of integers as input.
p,s;f(int*a){a=!*a?p=s=0:!((s+=*a++)>=p?s-=p=s:1)+f(a);}

Try it online!

PHP, 62 bytes
for(;$a=$argv[++$i];)if(($s+=$a)>=$t){$r++;$t=$s;$s=0;}echo$r;

Try it online!
Pretty straightforward implementation, saying that "s" is for "sum", "t" for "total" and "r" for "result" should be enough ;)

Perl 5, 35 + 1 bytes
$d-=$_;if($d<1){$\++;$p=$d=$p-$d}}{

Try it online!
I counted one additional byte for replacing the standard command-line switch -e by -pe.
This program reads the list of causes from its standard input, one amount per line.  When there is nothing left to read, it prints the number of civilian barfoos who donated something.
This is a port of xnor's Python2 solution with a few Perl golfing tricks thrown in.  I use the following variables: $\ tracks the number of barfoos who have successfully donated, $p tracks the previous donation, and $d tracks the amount that the current barfoo still needs to donate to catch up with the previous donation.
Slightly more natural, 36 + 1 bytes
$s+=$_;if($s>=$p){$\++;$p=$s;$s=0}}{

Try it online!
In this version, $s counts the sum of what the current barfoo is trying to donate instead of tracking what is still missing (as done with $d above).
Ungolfed and commented
The implementation is simple but it uses a few well-known Perl golfing tips:

The -p switch wraps while (<>) { ... ; print } around the program but it does so literally, in a way that allows unmatched curly braces in the code to match those that are added by the wrapper.  So perl -p 'foo}{bar' becomes while (<>) { foo } { bar ; print }.  In this codegolf entry, I have an empty bar (which is kind of sad, but this is another topic).
The special variable $\ is the output record separator for the print operator.  Using print without arguments would print $_ followed by $\, but $_ is undefined at the end of the while loop, so assigning a value to $\ is a convenient way to print something at the end of the program.
Incrementing an undefined variable sets its value to 1.  $\ is undefined by default.

To make the ungolfed code more readable and to make it easier to understand what is printed, here I use a variable $t for counting the number of successful donations instead of using the output record separator $\.  The natural version of the code would look like this:
while (<>) {           # Read all input lines (one amount per line).
  $s += $_;            # Add the amount for the current cause to $s.
  if ($s >= $p) {      # If we can match or exceed the last donation,
    $t++;              # then count it and invite the next barfoo.
    $p = $s;
    $s = 0;
  }
}                      # When we reach the end of the input,
print $t;              # print the number of barfoos who donated.

...and the slightly optimized version would look like this:
while (<>) {           # Read all input lines (one amount per line).
  $d -= $_;            # Subtract the amount from what we need to catch up.
  if ($d < 1) {        # If the difference from the last donation is 0 or lower,
    $t++;              # then count it and invite the next barfoo.
    $d = $p - $d;
    $p = $d;
  }
}                      # When we reach the end of the input,
print $t;              # print the number of barfoos who donated.

[C#], 108 bytes
f=(i,c,p,s,q)=>{y=c;if(i==L.Length)return;var t=L[i++];p=i==0?t:p;q=s+t>=p;f(i,q?++c:c,q?s+t:p,q?0:s+t,q);};

Try It online!
Very verbose recursion implementation, but I'm proud of this ugly baby. Call function with ever greater sum of donations until donation is equal to or greater then increment a counter, and set sum to 0. Increase index (to loop through donations). Return when index is equal to length of donations.

Charcoal, 41 bytes
≔⁰ηＷΦＥθ…θ⊕λ¬‹Σκη«⊞υω≔Σ§ι⁰η≔✂θＬ§ι⁰Ｌθ¹θ»ＩＬυ

Try it online! Link is to verbose version of code. Explanation:
≔⁰η

Start off with no resources.
ＷΦＥθ…θ⊕λ¬‹Σκη«

Find out which prefixes of the remaining list contain as least as many resources as the last donation.
⊞υω

Keep track of how many times a donation was found.
≔Σ§ι⁰η

Calculate the minimum donation for next time.
≔✂θＬ§ι⁰Ｌθ¹θ

Remove the recommendations that were donated.
»ＩＬυ

Print the count of donations.

Io, 72 bytes
Port of xnor's Python solution.
method(I,d :=p :=t :=0;I foreach(x,d=d-x;if(d<1,t=t+1;p=d=p-d))return t)

Try it online!

MMIX, 52 bytes (13 instrs)
Takes pointer to sequence of 16-bit integers as sole argument, sequence terminated by a 0.
(jelly xxd)
00000000: e301 0000 e302 0000 e303 0000 87ff 0000  ẉ¢¡¡ẉ£¡¡ẉ¤¡¡⁷”¡¡
00000010: 42ff 0008 e700 0002 2002 02ff 5102 fffc  B”¡®ḃ¡¡£ ££”Q£”‘
00000020: 2003 0302 3402 0003 e701 0001 f1ff fff8   ¤¤£4£¡¤ḃ¢¡¢ȯ””ẏ
00000030: f802 0000                                ẏ£¡¡

Disassembly and explanation
charity SETL $1,0       // ndonors = 0
        SETL $2,0       // amtleft = 0
        SETL $3,0       // prevdonor = 0
0H      LDWU $255,$0,0  // loop: amt = *causes (causes is const uint16_t *)
        BZ   $255,0F        // if(!amt) goto end
        INCL $0,2       // causes++
        ADD  $2,$2,$255 // amtleft += amt
        PBN  $2,0B      // iflikely(amtleft < 0) goto loop
        ADD  $3,$3,$2   // prevdonor += amtleft
        NEG  $2,0,$3    // amtleft = -prevdonor
        INCL $1,1       // ndonors++
        JMP  0B         // goto loop
0H      POP  2,0        // end: return ndonors


text:
When is the closest Conway's Doomsday?
A quote from MO.SE answer:

Although it is well known that Conway was able to quickly calculate the day of the week of any given date, it is less well known that one part of the algorithm is easy to remember and useful in practice: In any given year, the following dates all fall on the same day of the week: 4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, 11/7, and the last day of February. For example, in 2020, all these dates fall on a Saturday. Conway, in his characteristically colorful way, would say that the Doomsday of 2020 is Saturday. Knowing this fact allows you to calculate fairly quickly in your head, with no special training, the day of the week for any date in 2020.

Well, it sounds easy, but then we need to check which doomsday is the closest from the given date in order to quickly calculate the day of week. Now that sounds hard.
Practically, we'd just compare a given date with the Doomsday in the same month (or adjacent month in case of January and March).
Task
Given a date consisting of full year, month, and day, output the closest Conway's Doomsday (i.e. one of 4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, 11/7, and the last day of February) from the given date.
The closest Doomsday can be in the same month, a different month, or even a different year. If the given date has two nearest Doomsdays, output any one or both of them. Also note that the last day of February can be either 28th or 29th (depending on leap-year-ness).
You can take input and produce output in any suitable format, e.g. three integers, a formatted string, or even a built-in Date object (if your language has one). You can assume the given date is valid, and the input year is between 1901 and 2099 inclusive. Gregorian calendar is assumed in this challenge.
Test cases
YYYY-MM-DD => YYYY-MM-DD, ...
-------------------------------
2020-05-18 => 2020-05-09
2020-05-30 => 2020-06-06
2020-10-31 => 2020-11-07
2020-10-24 => 2020-10-10 or 2020-11-07
2020-01-20 => 2019-12-12
2020-01-21 => 2020-02-29
2019-01-20 => 2018-12-12 or 2019-02-28

Reference implementation in Python.

Nice challenge! I think you probably either need a test case for the exception to the 'multiple of 4' leap year rule - i.e. except for years evenly divisible by 100, unless also divisible by 400, or limit the range of inputs to avoid needing to handle it

I thought the Doomsday for 2020, for instance, was "Saturday", so that any Saturday in 2020 would be considered a Doomsday.  Are you looking for the closest Doomsday that happens to be on Conway's easy-to-remember list (4/4, 6/6, etc.?)

If I don't have a built-in date type, what counts as a leap year?

@Neil A leap year (where Feb 29th exists) is a year divisible by 4. Unless it's divisible by 100, then it isn't. But if it's divisible by 400 it is. So 2020 is divisible by 4 and thus a leap year. 1700, 1800, 1900, 2100 are not leap years, but 1600, 2000 and 2400 is.

I think this is likely unclear without you specifying what calendar to use, and an acceptable date range. Even your reference implementation will give errors for things I would assume should be valid, such as year 1.

@KjetilS. I think Neil was wondering what counts as a leap year in this challenge. In other words, which range of years are we supposed to support. (If it's, say, 1901-2099, then 'divisible by 4' is enough.)

Sorry to all of you for late response. A few clarifications (already edited main post to reflect all of them): 1) I decided to go for 1901-2099 for a couple of reasons. 2) I'm looking for the nearest date that is on the easy-to-remember list. 3) The calendar used is Gregorian.

@KevinCruijssen I don't think so, I count 39 days in both ways.

Numberphile just released a video on this: https://www.youtube.com/watch?v=z2x3SSBVGJU

Charcoal, 138 110 98 bytes
≔§⪪”)¶⊟eΦＯ∨ü&-T[¿Ｑ№i⧴⊕%⁰q”⁴ＬΦ⪪”)¶ »Ｒ≦ＰH↘{⎚″4χχβ´ΣP”⁴›ι✂θ⁴χ¹η¿⁼Ｉη¹²⁺⊖…θ⁴1212«…θ⁴¿⁻Ση³η«022§9888Ｉ…θ⁴

Try it online! Link is to verbose version of code. Edit: Saved 28 bytes by switching I/O to compact ISO format (yyyymmdd). Saved 12 bytes when the supported year range was restricted to 1901 to 2099. Explanation:
≔§⪪”)¶⊟eΦＯ∨ü&-T[¿Ｑ№i⧴⊕%⁰q”⁴ＬΦ⪪”)¶ »Ｒ≦ＰH↘{⎚″4χχβ´ΣP”⁴›ι✂θ⁴χ¹η

Take the dates (in mmdd format) 0120, 0317, 0421, 0523, 0623, 0725, 0822, 0922, 1024, 1124. These represent the cutoff points above which the next Doomsday is nearer. (In some cases the Doomsday is equidistant but in particular for 0120 that is not true on leap years.) Work out which cutoff point applies by counting the number of dates that fall before the input date. Then look up the relevant Doomsday date from the list (in mmdd format) 1212, 1107, 1010, 0905, 0808, 0711, 0606, 0509, 0404, 0300, 0012.
If I had access to a date library I could then ask it to fix up my date, but unfortunately I have to do that manually:
¿⁼Ｉη¹²

Is this the 0012 date, meaning the 12th of month 0, i.e. last December?
⁺⊖…θ⁴1212«

If so then output the previous year and a month and day of 12.
…θ⁴

Otherwise the year is at least correct...
¿⁻Ση³

Is this the 0300 date, meaning the 0th of March, i.e. the last day of February?
η«

If not then this is the date we seek.
022

Output February the 2?th.
§9888Ｉ…θ⁴

Output 9 if the year is a multiple of 4, otherwise 8.

The input year range is now restricted to 1901-2099.

@Bubbler Thanks; there goes another 12 bytes!

JavaScript (ES7),  125 ... 114  113 bytes
Takes and returns a Date object.
D=>[25,-15,...'108088080'].map(b=d=>(v=(q=new Date(D.getFullYear(x+=21-d),x>>4,x&15))-D)*v>b||(b=v*v,o=q),x=0)&&o

Try it online!
How?
The array [25,-15,...'108088080'] encodes the following pairs \$(m,d)\$ where \$m\$ is a 0-indexed month and \$d\$ is a day:
[-1,12], [2,0], [3,4], [4,9], [5,6], [6,11], [7,8], [8,5], [9,10], [10,7], [11,12]

Special cases:

[-1,12] is the 12th of December of the previous year
[2,0] (literally "March 0") is the last day of February

It is decoded as follows:
[25, -15, ...'108088080'] // array of delta values
.map(d =>                 // for each value d in this list:
  [                       //   build the pair (month, day):
    (x += 21 - d) >> 4,   //     add 21 - d to x; the month is floor(x / 16)
    x & 15                //     the day is (x + 16) mod 16
  ],                      //   end of pair
  x = 0                   //   start with x = 0
)                         // end of map()

Try it online!
For each pair \$(m,d)\$ we compute the square of the difference (in milliseconds) between the input date \$D\$ and a new date \$q\$ generated with this month and this day.
(v = (q = new Date(D.getFullYear(), m, d)) - D) * v

We eventually return the date that leads to the smallest squared difference.

Wolfram Language (Mathematica), 102 bytes
aMinimalBy[DateObject@{a[[1,1]],##}&@@@36^^3cx83c24e4aw06er~IntegerDigits~13~Partition~2,Abs[#-a]&]

Try it online! Pure function. Takes a DateObject as input and returns a list of DateObjects as output. The Unicode character is U+F4A1 (\[Function]). I'd use Nearest here, but its default DistanceFunction refuses to compare Quantity values. Note that the function emits a few warnings on TIO due to its sandboxing.

APL (Dyalog Unicode), 115 99 91 bytes
{u/⍨(⊢=⌊/)|(1∆DT⊂⍵)-1∘∆DT¨⊂¨u←(,y∘.,(2/¨2+2×⍳5),(⊢,⌽¨)0 2+⊂5 9),↓y,↑2∘,¨28+0=4|y←(2-⍳3)+⊃⍵}

Try it online!
Takes a date array yyyy mm dd, and returns all the closest doomsdays. If that is not allowed, then +1 byte.
-16 bytes from Bubbler(simplifying leap year check)
-8 bytes from Bubbler(compressing doomsdays)
⎕DT is polyfilled as ∆DT here(Courtesy of Adám) since tio's version doesn't allow it's usage.
Explanation
(2-⍳3) array (-1,0,1)
y←(2-⍳3)+⊃⍵ add that to the year and store it as y.
0=4| check if each of those is a leap year(This works due to the year range.)
28+ add 28 to those booleans to get the correct february dates
↓y,↑2∘,¨ add the respective years, and months(2) to them to get the appropriate dates
(...), concatenate with:
(⊢,⌽¨)0 2 generate array (5 9)(7 11)(9 5)(11 7)
(2/¨2+2×⍳5) and the numbers 4 6 8 10 12 repeated twice
,y∘., join with the years and flatten to a list to get all the dates
u← save all the dates together as u
1∘∆DT¨⊂¨ get each of their date numbers
(1∆DT⊂⍵) and subtract from the input's date number.
| convert to their absolute values:
(⊢=⌊/) tacit fn: array = minimum? (generates bitmask)
u/⍨ filter the dates by that (get the dates with minimum distance)

You can simplify the leap year test to (0=4|⊢) because of the year range.

(0=4|⊢)¨ → 0=4| because arithmetics are scalar.

⊃,/(⊂,⊂∘⌽)¨(5 9)(7 11) → (⊢,⌽¨)(5 9)(7 11) → (⊢,⌽¨)0 2+⊂5 9. Your initial version is the same length as (5 9)(7 11)(9 5)(11 7) :D

05AB1E, 84 bytes
4Ö¹тÖ_²3@PU•ΘÏF•5°X*+ºS₂+©²<£O+•23õ₄ƶ₃-¹å•60в.¥X+¦19(šs.xDVdi®ηODY‹O©£θYα®>¹)ë12D¹<)

Can definitely be golfed some more.. 05AB1E doesn't have any date builtins, so everything is done manually.
Input as three loose inputs in the order year,month,day, output as a triplet in the format [day,month,year].
Try it online.
Explanation:
Determine if the input is a leap year, and if the input-month is NOT January nor February:
4Ö            # Check if the (implicit) first input-year is divisible by 4
¹тÖ_          # Check that the first input-year is NOT divisible by 100
²3@           # Check that the second input-month is >= 3
    P         # Check if all three are truthy by taking the product of the stack
              # (1 if truthy; 0 if falsey)
     U        # Pop and store this in variable `X`

Convert the input to an integer \$n\$, being the (1-based) \$n^{th}\$ day of the year:
•ΘÏF•         # Push compressed integer 5254545
5°            # Push 10 to the power 5: 100000
  X*          # Multiply it by `X`
    +         # Add it to the integer (5354545 if `X` is truthy; 5254545 if falsey)
º             # Mirror it: 5354545454535 or 5254545454525
 S            # Convert it to a list of digits
  ₂+          # Add 26 to each: [31,28 or 29,31,30,31,30,31,31,30,31,30,31,28 or 29,31]
    ©         # Store this list in variable `®` (without popping)
²<            # Push the second input-month, and decrease it by 1
  £           # Leave that many leading values of the list
   O          # Sum them
    +         # And add them to the (implicit) third input-day

Create a list of values \$k\$, representing the \$k^{th}\$ day of the year for the dates [prevYear-12-12, year-02-28 or 29, year-04-04, year-05-09, year-06-06, year-07-11, year-08-08, year-09-05, year-10-10, year-11-07, year-12-12]:
•23õ₄ƶ₃-¹å•   # Push compressed integer 36033721893183342948
 60в          # Convert it to base-60 as list: [59,35,35,28,35,28,28,35,28,35,48]
    .¥        # Undelta it with leading 0: [0,59,94,129,157,192,220,248,283,311,346,394]
      X+      # Add `X` to each
        ¦     # Remove the leading 0 (or 1)
         19(š # And prepend -19 instead

Get \$k\$ closest to \$n\$:
s             # Swap so `n` is at the top of the stack
 .x           # And get the value of the list closest to it
   DV         # And store a copy in variable `Y`

And convert that result back into a date to output:
di            # If the result is non-negative (>=0):
  ®           #  Push the list from variable `®`
   η          #  Get its prefixes
    O         #  And sum each prefix: [31,60,91,121,152,182,213,244,274,305,335,366,395,426]
  D           #  Duplicate it
   Y‹         #  Check for each whether it's smaller than `Y` (1 if truthy; 0 if falsey)
     O        #  Sum those checks
      ©       #  Store it in variable `®` (without popping)
   £          #  Leave that many leading values from the list
    θ         #  Then only leave its last value
     Yα       #  And take its absolute difference with `Y`
       ®>     #  Push `®` + 1
         ¹    #  Push the first input-year
          )   #  And wrap all three values on the stack into a list
 ë            # Else:
  12D         #  Push two 12s
     ¹<       #  Push the first input-year - 1
       )      #  And wrap all three values on the stack into a list
              # (after which it is output implicitly as result)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •ΘÏF• is 5254545; •23õ₄ƶ₃-¹å• is 36033721893183342948; and •23õ₄ƶ₃-¹å•60в is [59,35,35,28,35,28,28,35,28,35,48].

Red, 234 182 176 bytes
func[n][y: n/2 t: to-date[y 3]second sort/skip
collect[foreach[d m]reduce[4 4 6 6 8 8 10 10 12 12 5 9 9 5 7 11 11 7 t/4 2 -19 1][a:
to-date[d m y]keep absolute a - n keep a]]2]

Try it online!

Bash + Core utilities, 173 169 bytes
y=${1%%-*}
for E in {4..12} {3/1/{$y,$[y+1]}-,1/2/$y-2}1day
{
((E))&&E+=/$[E%2?12^E:E]/$y
a=date\ -d;k=$[(`$a$1 +%s`-`$a$E +%s`)**2];((k<n|!n))&&{ n=$k;D=$E;}
}
$a$D +%F

Try the test cases online!
This is a full program.  Input is passed as an argument in yyyy-mm-dd format.  Output is on stdout in the same format.
This uses several tricks:

For each month E from April to December, the Doomsday day in that month is computed as E for even months and E xor 12 for odd months.
The last day of February is computed as 1 day before March 1.  (This applies to both the current year and the next year.)
December 12 of the previous year is computed as 21 days before January 2 of the current year.
The last two computations (ending with -1day and -21day) are combined using bash's brace expansion).
The date command with first option -d is saved in a variable for use like a macro.
Some spurious error messages are written to stderr.


text:
How quickly can you convert an NFA to a DFA?
Convert NFA to DFA as quickly as possible.
Input
Your input will be an NFA. In order to be able to test your code, it needs to be able to handle an NFA in the following format. This is taken  directly from GAP (and slightly simplified).
Automaton( Type, Size, Alphabet, TransitionTable, Initial, Accepting )

For the input, Type will always be "nondet".  Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are lists of non-negative integers not greater than the size of the automaton are also allowed. Initial and Accepting are, respectively, the lists of initial and accepting states.
Example input:
Automaton("nondet", 4, 2, [[[], [2], [3], [1, 2, 3, 4], [2, 4]],
                                [[], [1, 3, 4], [1], [2, 4]]], [1], [2, 3])

This is slightly easier to read as a transition table.
   |  1    2             3                4
--------------------------------------------------
 a |      [ 2 ]         [ 1, 2, 3, 4 ]   [ 2, 4 ]
 b |      [ 1, 3, 4 ]   [ 1 ]            [ 2, 4 ]
Initial state:    [ 1 ]
Accepting states: [ 2, 3 ]

Output
Your output must be a DFA that is equivalent to the input NFA.  There is no need for your DFA to be minimal. For the output, Type will always be "det".  Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are non-negative integers not greater than the size of the automaton. The states should be labelled by consecutive integers.  Initial and Accepting are, respectively, the lists of initial and accepting states.  In the case of the example above, this would be:
Automaton("det", 2, 2, [[2, 2], [2, 2]], [1], [])

As a transition table this is:
   |  1  2
-----------
 a |  2  2
 b |  2  2
Initial state:   [ 1 ]
Accepting state: [  ]

(It is now clear this is a DFA that will not accept any input strings.)
Test cases:

Input:

Automaton("nondet",2,4,[[[1], [2]], [[2], []], [[2], []] , [[1], [2]]],[1],[1, 2])

As a transition matrix:
   |  1       2
-------------------
 a | [ 1 ]   [ 2 ]
 b | [ 2 ]
 c | [ 2 ]
 d | [ 1 ]   [ 2 ]
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]

Here is the diagram of the NFA.

Output:
Automaton("det",3, 4,[[1, 2, 3], [2, 3, 3], [2, 3, 3], [1, 2, 3]], [1],[1, 2])

As a transition matrix:
   |  1  2  3
--------------
 a |  1  2  3
 b |  2  3  3
 c |  2  3  3
 d |  1  2  3
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]

Here is the diagram of the DFA.

Input:

Automaton("nondet",7,4,[[[1, 3, 4, 5], [2], [3], [3, 4], [3, 5], [], []], [[2, 3, 4, 7], [3], [], [], [3, 7], [3, 4], []], [[2, 3, 5, 6], [3], [], [3, 6], [], [], [3, 5]], [[1, 3, 6, 7], [2], [3], [], [], [3, 6], [3, 7]]],[1],[1, 2, 3, 4, 5, 6, 7])

Output:
Automaton("det",16,4,[[1, 2, 15, 15, 5, 6, 7, 7, 6, 2, 16, 12, 12, 16, 15, 16], [1, 3, 1, 7, 9, 15, 1, 1, 15, 8, 7, 3, 8, 15, 1, 15], [1, 1, 2, 1, 13, 4, 4, 10, 10, 1, 15, 15, 15, 2, 1, 15], [1, 15, 3, 4, 5, 16, 15, 3, 14, 4, 11, 16, 11, 14, 15, 16]],[5],[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16])

Input:

Automaton("nondet",12, 4,[[[1, 3, 5, 6], [2, 4, 7, 8], [3], [6], [3, 5], [3, 6], [4, 7], [4, 8], [4, 7], [4, 8], [], []], [[2, 3, 5, 10], [3, 4, 7, 12], [6], [], [4, 7], [3, 10], [], [4, 12], [3, 5], [4, 12], [4, 7], []], [[2, 3, 6, 9], [3, 4, 8, 11], [6], [], [3, 9], [4, 8], [4, 11], [], [4, 11], [3, 6], [], [4, 8 ]], [[1, 3, 9, 10], [2, 4, 11, 12], [3], [6], [4, 11], [4, 12], [], [], [3, 9], [3, 10], [4, 11], [4, 12]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])

Output:
Automaton("det",39,4,[ [ 1, 19, 8, 5, 10, 10, 9, 25, 10, 10, 25, 10, 13, 35, 15, 20, 15, 19, 19, 21, 21, 10, 13, 19, 25, 25, 25, 36, 35, 10, 35, 35, 10, 10, 35, 36, 25, 19, 25 ], [ 1, 23, 1, 3, 6, 39, 39, 7, 39, 12, 8, 12, 32, 23, 21, 36, 16, 36, 32, 36, 32, 12, 32, 13, 22, 29, 32, 23, 39, 32, 39, 12, 32, 31, 12, 22, 22, 23, 7 ], [ 1, 30, 4, 1, 4, 10, 25, 4, 8, 5, 5, 10, 14, 34, 2, 14, 38, 30, 30, 14, 14, 10, 14, 30, 5, 4, 5, 34, 27, 5, 30, 30, 10, 4, 34, 34, 5, 30, 4 ], [ 1, 2, 39, 8, 39, 12, 7, 3, 25, 37, 37, 12, 27, 28, 15, 18, 15, 19, 19, 19, 19, 6, 33, 2, 11, 26, 27, 28, 22, 27, 12, 12, 33, 26, 37, 37, 37, 24, 39 ] ],[ 17 ],[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 ])

Input:

Automaton("nondet",25,4,[[[1, 3, 6, 7], [2, 4, 8, 9], [3, 5, 10, 11], [4], [5], [3, 5, 6, 10, 18], [3, 5, 7, 11, 19], [4, 8], [4, 9], [5, 10], [5, 11], [4, 5, 8, 10, 22], [4, 5, 9, 11, 23], [5, 10], [5, 11], [], [], [5, 10, 18], [5, 11, 19], [5, 10, 22], [5, 11, 23], [], [], [], []], [[2, 3, 6, 13], [3, 4, 8, 15], [4, 5, 10, 17], [5], [], [4, 5, 8, 10, 18], [3, 5, 13, 17, 21], [5, 10], [4, 15], [], [5, 17], [3, 5, 6, 10, 22], [4, 5, 15, 17, 25], [4, 8], [5, 17], [5, 10], [], [], [5, 17, 21], [], [5, 17, 25], [5, 10, 18], [], [5, 10, 22], []], [[2, 3, 7, 12], [3, 4, 9, 14], [4, 5, 11, 16], [5], [], [3, 5, 12, 16, 20], [4, 5, 9, 11, 19], [4, 14], [5, 11], [5, 16], [], [4, 5, 14, 16, 24], [3, 5, 7, 11, 23], [5, 16], [4, 9], [], [5, 11], [5, 16, 20], [], [5, 16, 24], [], [], [5, 11, 19], [], [5, 11, 23]], [[1, 3, 12, 13], [2, 4, 14, 15], [3, 5, 16, 17], [4], [5], [4, 5, 14, 16, 20], [4, 5, 15, 17, 21], [5, 16], [5, 17], [], [], [3, 5, 12, 16, 24], [3, 5, 13, 17, 25], [4, 14], [4, 15], [5, 16], [5, 17], [], [], [], [], [5, 16, 20], [5, 17, 21], [5, 16, 24], [5, 17, 25]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 ])

Input:

Automaton("nondet",38,4,[[[1, 3, 7, 8], [2, 4, 9, 10], [3, 5, 11, 12], [4, 6, 13, 14], [7], [8], [3, 5, 7, 11, 23], [3, 5, 8, 12, 24], [4, 6, 9, 13, 25], [4, 6, 10, 14, 26], [5, 11], [5, 12], [6, 13], [6, 14], [4, 5, 9, 11, 31], [4, 5, 10, 12, 32], [5, 6, 11, 13, 33], [5, 6, 12, 14, 34], [6, 13], [6, 14], [], [], [5, 11, 23], [5, 12, 24], [6, 13, 25], [6, 14, 26], [5, 11, 31], [5, 12, 32], [6, 13, 33], [6, 14, 34], [6, 13, 25], [6, 14, 26], [], [], [6, 13, 33], [6, 14, 34], [], []], [[2, 3, 7, 16], [3, 4, 9, 18], [4, 5, 11, 20], [5, 6, 13, 22], [8], [], [4, 5, 9, 11, 23], [3, 5, 16, 20, 28], [5, 6, 11, 13, 25], [4, 6, 18, 22, 30], [6, 13], [5, 20], [], [6, 22], [3, 5, 7, 11, 31], [4, 5, 18, 20, 36], [4, 6, 9, 13, 33], [5, 6, 20, 22, 38], [5, 11], [6, 22], [6, 13], [], [6, 13, 25], [5, 20, 28], [], [6, 22, 30], [6, 13, 33], [5, 20, 36], [], [6, 22, 38], [5, 11, 23], [6, 22, 30], [6, 13, 25], [], [5, 11, 31], [6, 22, 38], [6, 13, 33], []], [[2, 3, 8, 15], [3, 4, 10, 17], [4, 5, 12, 19], [5, 6, 14, 21], [8], [], [3, 5, 15, 19, 27], [4, 5, 10, 12, 24], [4, 6, 17, 21, 29], [5, 6, 12, 14, 26], [5, 19], [6, 14], [6, 21], [], [4, 5, 17, 19, 35], [3, 5, 8, 12, 32], [5, 6, 19, 21, 37], [4, 6, 10, 14, 34], [6, 21], [5, 12], [], [6, 14], [5, 19, 27], [6, 14, 26], [6, 21, 29], [], [5, 19, 35], [6, 14, 34], [6, 21, 37], [], [6, 21, 29], [5, 12, 24], [], [6, 14, 26 ], [6, 21, 37], [5, 12, 32], [], [6, 14, 34]], [[1, 3, 15, 16], [2, 4, 17, 18], [3, 5, 19, 20], [4, 6, 21, 22], [7], [8], [ 4, 5, 17, 19, 27], [4, 5, 18, 20, 28], [5, 6, 19, 21, 29], [5, 6, 20, 22, 30], [6, 21], [6, 22], [], [], [3, 5, 15, 19, 35], [3, 5, 16, 20, 36], [4, 6, 17, 21, 37], [4, 6, 18, 22, 38], [5, 19], [5, 20], [6, 21], [6, 22], [6, 21, 29], [6, 22, 30], [], [], [6, 21, 37], [6, 22, 38], [], [], [5, 19, 27], [5, 20, 28], [6, 21, 29], [6, 22, 30], [5, 19, 35], [5, 20, 36], [6, 21, 37], [6, 22, 38]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38])

Input:

Automaton("nondet",67,4,[[[1, 3, 8, 9], [2, 4, 10, 11], [3, 5, 12, 13], [4, 6, 14, 15], [5, 7, 16, 17], [8], [8], [3, 5, 8, 12, 28], [3, 5, 9, 13, 29], [4, 6, 10, 14, 30], [4, 6, 11, 15, 31], [5, 7, 12, 16, 32], [5, 7, 13, 17, 33], [6, 14], [6, 15], [ 7, 16], [7, 17], [4, 5, 10, 12, 40], [4, 5, 11, 13, 41], [5, 6, 12, 14, 42], [5, 6, 13, 15, 43], [6, 7, 14, 16, 44], [6, 7, 15, 17, 45], [7, 16], [7, 17], [], [], [5, 7, 12, 16, 28, 32, 52], [5, 7, 13, 17, 29, 33, 53], [6, 14, 30], [6, 15, 31], [7, 16, 32], [7, 17, 33], [5, 7, 12, 16, 40, 44, 56], [5, 7, 13, 17, 41, 45, 57], [6, 14, 42], [6, 15, 43], [7, 16, 44], [7, 17, 45], [6, 7, 14, 16, 30, 32, 60], [6, 7, 15, 17, 31, 33, 61], [7, 16, 32], [7, 17, 33], [], [], [6, 7, 14, 16, 42, 44, 64], [6, 7, 15, 17, 43, 45, 65], [7, 16, 44], [7, 17, 45], [], [], [7, 16, 32, 52], [7, 17, 33, 53], [7, 16, 44, 56], [7, 17, 45, 57], [7, 16, 32, 60], [7, 17, 33, 61], [7, 16, 44, 64], [7, 17, 45, 65], [], [], [], [], [], [], [], []], [[2, 3, 8, 19], [3, 4, 10, 21], [4, 5, 12, 23], [5, 6, 14, 25], [6, 7, 16, 27], [8], [], [4, 5, 10, 12, 28], [3, 5, 19, 23, 35], [5, 6, 12, 14, 30], [4, 6, 21, 25, 37], [6, 7, 14, 16, 32], [5, 7, 23, 27, 39], [7, 16], [6, 25], [], [7, 27], [3, 5, 8, 12, 40], [4, 5, 21, 23, 47], [4, 6, 10, 14, 42], [5, 6, 23, 25, 49], [5, 7, 12, 16, 44], [6, 7, 25, 27, 51], [6, 14], [7, 27], [7, 16], [], [6, 7, 14, 16, 30, 32, 52], [5, 7, 23, 27, 35, 39, 55], [7, 16, 32], [6, 25, 37], [], [7, 27, 39], [6, 7, 14, 16, 42, 44, 56], [5, 7, 23, 27, 47, 51, 59], [7, 16, 44], [6, 25, 49], [], [7, 27, 51], [5, 7, 12, 16, 28, 32, 60], [6, 7, 25, 27, 37, 39, 63], [6, 14, 30], [7, 27, 39], [7, 16, 32], [], [5, 7, 12, 16, 40, 44, 64], [6, 7, 25, 27, 49, 51, 67], [6, 14, 42], [7, 27, 51], [7, 16, 44], [], [], [7, 27, 39, 55], [], [7, 27, 51, 59], [], [7, 27, 39, 63], [], [7, 27, 51, 67], [7, 16, 32, 52], [], [7, 16, 44, 56], [], [7, 16, 32, 60], [], [7, 16, 44, 64], []], [[2, 3, 9, 18], [3, 4, 11, 20], [4, 5, 13, 22], [5, 6, 15, 24], [6, 7, 17, 26], [8], [], [3, 5, 18, 22, 34], [4, 5, 11, 13, 29], [4, 6, 20, 24, 36], [5, 6, 13, 15, 31], [5, 7, 22, 26, 38], [6, 7, 15, 17, 33], [6, 24], [7, 17], [7, 26 ], [], [4, 5, 20, 22, 46], [3, 5, 9, 13, 41], [5, 6, 22, 24, 48], [4, 6, 11, 15, 43], [6, 7, 24, 26, 50], [5, 7, 13, 17, 45], [7, 26], [6, 15], [], [7, 17], [5, 7, 22, 26, 34, 38, 54], [6, 7, 15, 17, 31, 33, 53], [6, 24, 36], [7, 17, 33], [7, 26, 38], [], [ 5, 7, 22, 26, 46, 50, 58], [6, 7, 15, 17, 43, 45, 57], [6, 24, 48], [7, 17, 45], [7, 26, 50], [], [6, 7, 24, 26, 36, 38, 62], [5, 7, 13, 17, 29, 33, 61], [7, 26, 38], [6, 15, 31], [], [7, 17, 33], [6, 7, 24, 26, 48, 50, 66], [5, 7, 13, 17, 41, 45, 65], [7, 26, 50], [6, 15, 43], [], [7, 17, 45], [7, 26, 38, 54], [], [7, 26, 50, 58], [], [7, 26, 38, 62], [], [7, 26, 50, 66], [], [], [7, 17, 33, 53], [], [7, 17, 45, 57], [], [7, 17, 33, 61], [], [7, 17, 45, 65]], [[1, 3, 18, 19], [2, 4, 20, 21], [3, 5, 22, 23 ], [4, 6, 24, 25], [5, 7, 26, 27], [8], [8], [4, 5, 20, 22, 34], [4, 5, 21, 23, 35], [5, 6, 22, 24, 36], [5, 6, 23, 25, 37], [6, 7, 24, 26, 38], [6, 7, 25, 27, 39], [7, 26], [7, 27], [], [], [3, 5, 18, 22, 46], [3, 5, 19, 23, 47], [4, 6, 20, 24, 48], [4, 6, 21, 25, 49], [5, 7, 22, 26, 50], [5, 7, 23, 27, 51], [6, 24], [6, 25], [7, 26], [7, 27], [6, 7, 24, 26, 36, 38, 54], [6, 7, 25, 27, 37, 39, 55], [7, 26, 38], [7, 27, 39], [], [], [6, 7, 24, 26, 48, 50, 58], [6, 7, 25, 27, 49, 51, 59], [7, 26, 50], [7, 27, 51], [], [], [5, 7, 22, 26, 34, 38, 62], [5, 7, 23, 27, 35, 39, 63], [6, 24, 36], [6, 25, 37], [7, 26, 38], [7, 27, 39], [5, 7, 22, 26, 46, 50, 66], [5, 7, 23, 27, 47, 51, 67], [6, 24, 48], [6, 25, 49], [7, 26, 50], [7, 27, 51], [], [], [], [], [], [], [], [], [7, 26, 38, 54], [7, 27, 39, 55], [7, 26, 50, 58], [7, 27, 51, 59], [7, 26, 38, 62], [7, 27, 39, 63], [7, 26, 50, 66], [7, 27, 51, 67]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67])

Input:

Automaton("nondet",96,4,[[[1, 3, 9, 10], [2, 4, 11, 12], [3, 5, 13, 14], [4, 6, 15, 16], [5, 7, 17, 18], [6, 8, 19, 20], [7 ], [8], [3, 5, 9, 13, 33], [3, 5, 10, 14, 34], [4, 6, 11, 15, 35], [4, 6, 12, 16, 36], [5, 7, 13, 17, 37], [5, 7, 14, 18, 38], [6, 8, 15, 19, 39], [6, 8, 16, 20, 40], [7, 17], [7, 18], [8, 19], [8, 20], [4, 5, 11, 13, 49], [4, 5, 12, 14, 50], [5, 6, 13, 15, 51], [5, 6, 14, 16, 52], [6, 7, 15, 17, 53], [6, 7, 16, 18, 54], [7, 8, 17, 19, 55], [7, 8, 18, 20, 56], [8, 19], [8, 20], [], [], [5, 7, 13, 17, 33, 37, 65], [5, 7, 14, 18, 34, 38, 66], [6, 8, 15, 19, 35, 39, 67], [6, 8, 16, 20, 36, 40, 68], [7, 17, 37], [7, 18, 38], [8, 19, 39], [8, 20, 40], [5, 7, 13, 17, 49, 53, 73], [5, 7, 14, 18, 50, 54, 74], [6, 8, 15, 19, 51, 55, 75], [6, 8, 16, 20, 52, 56, 76], [7, 17, 53], [7, 18, 54], [8, 19, 55], [8, 20, 56], [6, 7, 15, 17, 35, 37, 81], [6, 7, 16, 18, 36, 38, 82], [7, 8, 17, 19, 37, 39, 83], [7, 8, 18, 20, 38, 40, 84], [8, 19, 39], [8, 20, 40], [], [], [6, 7, 15, 17, 51, 53, 89], [6, 7, 16, 18, 52, 54, 90], [7, 8, 17, 19, 53, 55, 91], [7, 8, 18, 20, 54, 56, 92], [8, 19, 55], [8, 20, 56], [], [], [7, 17, 37, 65], [7, 18, 38, 66 ], [8, 19, 39, 67], [8, 20, 40, 68], [7, 17, 53, 73], [7, 18, 54, 74], [8, 19, 55, 75], [8, 20, 56, 76], [7, 17, 37, 81], [7, 18, 38, 82], [8, 19, 39, 83], [8, 20, 40, 84], [7, 17, 53, 89], [7, 18, 54, 90], [8, 19, 55, 91], [8, 20, 56, 92], [8, 19, 39, 67], [8, 20, 40, 68], [], [], [8, 19, 55, 75], [8, 20, 56, 76], [], [], [8, 19, 39, 83], [8, 20, 40, 84], [], [], [8, 19, 55, 91], [8, 20, 56, 92], [], []], [[2, 3, 9, 22], [3, 4, 11, 24], [4, 5, 13, 26], [5, 6, 15, 28], [6, 7, 17, 30], [7, 8, 19, 32], [8 ], [], [4, 5, 11, 13, 33], [3, 5, 22, 26, 42], [5, 6, 13, 15, 35], [4, 6, 24, 28, 44], [6, 7, 15, 17, 37], [5, 7, 26, 30, 46], [7, 8, 17, 19, 39], [6, 8, 28, 32, 48], [8, 19], [7, 30], [], [8, 32], [3, 5, 9, 13, 49], [4, 5, 24, 26, 58], [4, 6, 11, 15, 51], [ 5, 6, 26, 28, 60], [5, 7, 13, 17, 53], [6, 7, 28, 30, 62], [6, 8, 15, 19, 55], [7, 8, 30, 32, 64], [7, 17], [8, 32], [8, 19], [], [6, 7, 15, 17, 35, 37, 65], [5, 7, 26, 30, 42, 46, 70], [7, 8, 17, 19, 37, 39, 67], [6, 8, 28, 32, 44, 48, 72], [8, 19, 39], [7, 30, 46], [], [8, 32, 48], [6, 7, 15, 17, 51, 53, 73], [5, 7, 26, 30, 58, 62, 78], [7, 8, 17, 19, 53, 55, 75], [6, 8, 28, 32, 60, 64, 80], [8, 19, 55], [7, 30, 62], [], [8, 32, 64], [5, 7, 13, 17, 33, 37, 81], [6, 7, 28, 30, 44, 46, 86], [6, 8, 15, 19, 35, 39, 83], [7, 8, 30, 32, 46, 48, 88], [7, 17, 37], [8, 32, 48], [8, 19, 39], [], [5, 7, 13, 17, 49, 53, 89], [6, 7, 28, 30, 60, 62, 94], [6, 8, 15, 19, 51, 55, 91], [7, 8, 30, 32, 62, 64, 96], [7, 17, 53], [8, 32, 64], [8, 19, 55], [], [8, 19, 39, 67], [7, 30, 46, 70], [], [8, 32, 48, 72], [8, 19, 55, 75], [7, 30, 62, 78], [], [8, 32, 64, 80], [8, 19, 39, 83], [7, 30, 46, 86], [], [8, 32, 48, 88], [8, 19, 55, 91], [7, 30, 62, 94], [], [8, 32, 64, 96], [7, 17, 37, 65], [8, 32, 48, 72], [8, 19, 39, 67], [], [7, 17, 53, 73], [8, 32, 64, 80], [8, 19, 55, 75], [], [7, 17, 37, 81], [8, 32, 48, 88], [8, 19, 39, 83], [], [7, 17, 53, 89], [8, 32, 64, 96 ], [8, 19, 55, 91], []], [[2, 3, 10, 21], [3, 4, 12, 23], [4, 5, 14, 25], [5, 6, 16, 27], [6, 7, 18, 29], [7, 8, 20, 31], [8], [], [3, 5, 21, 25, 41], [4, 5, 12, 14, 34], [4, 6, 23, 27, 43], [5, 6, 14, 16, 36], [5, 7, 25, 29, 45], [6, 7, 16, 18, 38], [6, 8, 27, 31, 47], [7, 8, 18, 20, 40], [7, 29], [8, 20], [8, 31], [], [4, 5, 23, 25, 57], [3, 5, 10, 14, 50], [5, 6, 25, 27, 59], [ 4, 6, 12, 16, 52], [6, 7, 27, 29, 61], [5, 7, 14, 18, 54], [7, 8, 29, 31, 63], [6, 8, 16, 20, 56], [8, 31], [7, 18], [], [8, 20 ], [5, 7, 25, 29, 41, 45, 69], [6, 7, 16, 18, 36, 38, 66], [6, 8, 27, 31, 43, 47, 71], [7, 8, 18, 20, 38, 40, 68], [7, 29, 45], [8, 20, 40], [8, 31, 47], [], [5, 7, 25, 29, 57, 61, 77], [6, 7, 16, 18, 52, 54, 74], [6, 8, 27, 31, 59, 63, 79], [7, 8, 18, 20, 54, 56, 76], [7, 29, 61], [8, 20, 56], [8, 31, 63], [], [6, 7, 27, 29, 43, 45, 85], [5, 7, 14, 18, 34, 38, 82], [7, 8, 29, 31, 45, 47, 87], [6, 8, 16, 20, 36, 40, 84], [8, 31, 47], [7, 18, 38], [], [8, 20, 40], [6, 7, 27, 29, 59, 61, 93], [5, 7, 14, 18, 50, 54, 90], [7, 8, 29, 31, 61, 63, 95], [6, 8, 16, 20, 52, 56, 92], [8, 31, 63], [7, 18, 54], [], [8, 20, 56], [7, 29, 45, 69], [8, 20, 40, 68], [8, 31, 47, 71], [], [7, 29, 61, 77], [8, 20, 56, 76], [8, 31, 63, 79], [], [7, 29, 45, 85], [8, 20, 40, 84], [8, 31, 47, 87], [], [7, 29, 61, 93], [8, 20, 56, 92], [8, 31, 63, 95], [], [8, 31, 47, 71], [7, 18, 38, 66], [], [8, 20, 40, 68], [8, 31, 63, 79], [7, 18, 54, 74], [], [8, 20, 56, 76], [8, 31, 47, 87], [7, 18, 38, 82], [], [8, 20, 40, 84], [8, 31, 63, 95], [7, 18, 54, 90 ], [], [8, 20, 56, 92]], [[1, 3, 21, 22], [2, 4, 23, 24], [3, 5, 25, 26], [4, 6, 27, 28], [5, 7, 29, 30], [6, 8, 31, 32], [8], [8], [4, 5, 23, 25, 41], [4, 5, 24, 26, 42], [5, 6, 25, 27, 43], [5, 6, 26, 28, 44], [6, 7, 27, 29, 45], [6, 7, 28, 30, 46], [7, 8, 29, 31, 47], [7, 8, 30, 32, 48], [8, 31], [8, 32], [], [], [3, 5, 21, 25, 57], [3, 5, 22, 26, 58], [4, 6, 23, 27, 59], [4, 6, 24, 28, 60], [5, 7, 25, 29, 61], [5, 7, 26, 30, 62], [6, 8, 27, 31, 63], [6, 8, 28, 32, 64], [7, 29], [7, 30], [8, 31], [8, 32], [6, 7, 27, 29, 43, 45, 69], [6, 7, 28, 30, 44, 46, 70], [7, 8, 29, 31, 45, 47, 71], [7, 8, 30, 32, 46, 48, 72], [8, 31, 47], [8, 32, 48], [], [], [6, 7, 27, 29, 59, 61, 77], [6, 7, 28, 30, 60, 62, 78], [7, 8, 29, 31, 61, 63, 79], [7, 8, 30, 32, 62, 64, 80], [8, 31, 63], [8, 32, 64], [], [], [5, 7, 25, 29, 41, 45, 85], [5, 7, 26, 30, 42, 46, 86], [6, 8, 27, 31, 43, 47, 87], [6, 8, 28, 32, 44, 48, 88], [7, 29, 45], [7, 30, 46], [8, 31, 47], [8, 32, 48], [5, 7, 25, 29, 57, 61, 93], [5, 7, 26, 30, 58, 62, 94], [6, 8, 27, 31, 59, 63, 95], [6, 8, 28, 32, 60, 64, 96], [7, 29, 61], [7, 30, 62], [8, 31, 63], [8, 32, 64], [8, 31, 47, 71], [8, 32, 48, 72 ], [], [], [8, 31, 63, 79], [8, 32, 64, 80], [], [], [8, 31, 47, 87], [8, 32, 48, 88], [], [], [8, 31, 63, 95], [8, 32, 64, 96 ], [], [], [7, 29, 45, 69], [7, 30, 46, 70], [8, 31, 47, 71], [8, 32, 48, 72], [7, 29, 61, 77], [7, 30, 62, 78], [8, 31, 63, 79], [8, 32, 64, 80], [7, 29, 45, 85], [7, 30, 46, 86], [8, 31, 47, 87], [8, 32, 48, 88], [7, 29, 61, 93], [7, 30, 62, 94], [8, 31, 63, 95], [8, 32, 64, 96]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96])

The NFAs for 8, 9, 10, 11, 12, 13, 14, 15, 16 are here.The files have names  k7nfa, k8nfa etc. As an example, the input for problem 7 is k7nfa.  Hopefully the rest of the names are clear.  If your code is correct for problem sizes I can test, I am happy to believe it is correct in general.

Score
I will time your code on test cases 1..16 from above of increasing size. For each test \$n\$, the time limit is \$2^n\$ seconds. Your score will be the largest test case your code can process within its time limit.  If two answers get to the same size then the one that is fastest on that largest test case wins. The test machine is an Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz. You can use at most 16 of its cores.
A possible solution method
One method for converting NFAs to DFAs is called subset construction. Because our NFAs will not have any \$\epsilon\$-moves it is slightly simpler than usual. Here is an overview of the algorithm:
Start at the initial state

Perform the following for the new DFA state.
For each possible input symbol:
    Apply move to the newly-created state and the input symbol; this will return a set of states.
   This set of NFA states will be a single state in the DFA.
Each time we generate a new DFA state, we must apply step 1 to it. The process is complete when applying step 1 does not yield any new states.

The accepting states of the DFA are those which contain any of the finish states of the NFA.
How can this be sped up?
There are have been some attempts to parallelize subset construction. E.g.

https://crpit.scem.westernsydney.edu.au/confpapers/CRPITV140Choi.pdf
https://link.springer.com/chapter/10.1007/978-3-662-47401-3_3

Other work has focussed on making the data structures as fast as possible, amongst other things.

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D48BED26B35E96F5FB5E9740585F5C67?doi=10.1.1.8.7435&rep=rep1&type=pdf

Testing
I will check your answers (for the smaller cases) using AreEquivAut .
[Thank you to Christian Sievers for the example NFAs.]
Results

16 in  \$33812 < 2^{16} = 65536\$ seconds in Rust by Anders Kaseorg.

Also, how much memory can we use? (I’m already using 6 GB for case 13…)

@AndersKaseorg Thanks for the problem reports! I have fixed them all except for "it does not believe that for cases 3 through 6" which I am working on. I have fixed 3 and am working on the others. For RAM, I can handle up to 64GB of RAM.

@AndersKaseorg I removed most of the dfas as I am not sure what was wrong with them and it doesn't really help to have them. I look forward to testing your code!

@AndersKaseorg I don't know why it's proving so difficult to copy and paste. Hopefully fixed now.

Rust, score 15 in ≈ 6000 s
Most of my optimization effort has actually gone into memory usage rather than speed, for reasons you can see in this table of results on my system (AMD Ryzen 1800X):
case       time     memory   DFA size
   1     0.00 s      2 MiB          3
   2     0.00 s      2 MiB         18
   3     0.00 s      2 MiB         57
   4     0.00 s      2 MiB        207
   5     0.00 s      2 MiB        318
   6     0.00 s      2 MiB       1201
   7     0.01 s      3 MiB      12230
   8     0.14 s      9 MiB      66324
   9     0.47 s     18 MiB     179766
  10     3.16 s     68 MiB     879932
  11    11.40 s    241 MiB    2385052
  12   100.64 s    886 MiB   10750324
  13   333.82 s   2026 MiB   29158718
  14  1810.72 s   9073 MiB  123222354
  15  6008.30 s  20631 MiB  333765796

Build with cargo build --release and run with target/release/automaton < INPUT.
src/main.rs
use ahash::AHasher;
use hashbrown::hash_map::{HashMap, RawEntryMut};
use mimalloc::MiMalloc;
use nom::bytes::complete::tag;
use nom::character::complete::{char, digit1, multispace0};
use nom::combinator::{map, map_res};
use nom::multi::separated_list0;
use nom::sequence::{delimited, preceded};
use nom::IResult;
use std::collections::VecDeque;
use std::convert::TryInto;
use std::error::Error;
use std::hash::{Hash, Hasher};
use std::io;
use std::mem;
use std::str::FromStr;

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

#[derive(Debug)]
struct Automaton<Set> {
    size: u32,
    alphabet: usize,
    transitions: Vec<Vec<Set>>,
    initial: Set,
    accepting: Vec<u32>,
}

fn parse_vec<'a, T>(
    item: impl FnMut(&'a str) -> IResult<&'a str, T>,
    input: &'a str,
) -> IResult<&'a str, Vec<T>> {
    delimited(
        char('['),
        map(
            separated_list0(
                preceded(multispace0, char(',')),
                preceded(multispace0, item),
            ),
            |v| v.into_iter().collect(),
        ),
        preceded(multispace0, char(']')),
    )(input)
}

type Id = u32;
type Node = u128;
const ID_BITS: u32 = mem::size_of::<Id>() as u32 * 8;
const NODE_BITS: u32 = mem::size_of::<Node>() as u32 * 8;
const DEGREE: u32 = NODE_BITS / ID_BITS;

struct Trie {
    size: u32,
    nodes: Vec<Node>,
    ids: HashMap<Id, ()>,
}

fn pack(ids: [Id; DEGREE as usize]) -> Node {
    let mut node = 0;
    for k in 0..DEGREE {
        node |= (ids[k as usize] as Node) << ID_BITS * k;
    }
    node
}

fn unpack(node: Node) -> [Id; DEGREE as usize] {
    let mut ids = [0; DEGREE as usize];
    for k in 0..DEGREE {
        ids[k as usize] = (node >> ID_BITS * k) as Id;
    }
    ids
}

fn node_hash(node: Node) -> u64 {
    let mut hasher = AHasher::default();
    node.hash(&mut hasher);
    hasher.finish()
}

impl Trie {
    fn new(real_size: u32) -> Trie {
        let mut size = NODE_BITS;
        while size < real_size {
            size *= DEGREE;
        }
        let mut trie = Trie {
            size,
            nodes: vec![],
            ids: HashMap::new(),
        };
        let zero_id = trie.node_id(0);
        debug_assert_eq!(zero_id, 0);
        trie
    }

    fn node_id(&mut self, node: Node) -> Id {
        let hash = node_hash(node);
        let nodes = &mut self.nodes;
        match self
            .ids
            .raw_entry_mut()
            .from_hash(hash, |&id| nodes[id as usize] == node)
        {
            RawEntryMut::Occupied(e) => *e.key(),
            RawEntryMut::Vacant(e) => {
                let id: Id = nodes.len().try_into().unwrap();
                nodes.push(node);
                e.insert_with_hasher(hash, id, (), |&id| node_hash(nodes[id as usize]));
                id
            }
        }
    }

    fn vec_id(&mut self, low: u32, high: u32, vec: Vec<u32>) -> Id {
        if vec.is_empty() {
            0
        } else if high - low <= NODE_BITS {
            let mut node: Node = 0;
            for n in vec {
                node |= 1 << n - low;
            }
            self.node_id(node)
        } else {
            let step = (high - low) / DEGREE;
            let mut vecs: [Vec<u32>; DEGREE as usize] = Default::default();
            for n in vec {
                vecs[((n - low) / step) as usize].push(n);
            }
            let mut ids = [0; DEGREE as usize];
            for k in 0..DEGREE {
                ids[k as usize] = self.vec_id(
                    low + k * step,
                    low + (k + 1) * step,
                    mem::take(&mut vecs[k as usize]),
                );
            }
            self.node_id(pack(ids))
        }
    }

    fn parse_set<'a>(&mut self, input: &'a str) -> IResult<&'a str, Id> {
        let (input, vec) = parse_vec(map_res(digit1, u32::from_str), input)?;
        Ok((input, self.vec_id(0, self.size, vec)))
    }

    fn intersects(&self, size: u32, a: Id, b: Id) -> bool {
        if a == 0 || b == 0 {
            false
        } else {
            let a_node = self.nodes[a as usize];
            let b_node = self.nodes[b as usize];
            if size <= NODE_BITS {
                a_node & b_node != 0
            } else {
                let step = size / DEGREE;
                let a_ids = unpack(a_node);
                let b_ids = unpack(b_node);
                (0..DEGREE).any(|k| self.intersects(step, a_ids[k as usize], b_ids[k as usize]))
            }
        }
    }

    fn union(&mut self, size: u32, ids: &mut Vec<Id>) -> Id {
        ids.retain(|&id| id != 0);
        if ids.len() < 2 {
            ids.drain(..).next().unwrap_or(0)
        } else {
            let mut node;
            if size <= NODE_BITS {
                node = 0;
                for id in ids.drain(..) {
                    node |= self.nodes[id as usize];
                }
            } else {
                let step = size / DEGREE;
                let mut vecs: [Vec<Id>; DEGREE as usize] = Default::default();
                for vec in &mut vecs {
                    vec.reserve(ids.len());
                }
                for id in ids.drain(..) {
                    let ids1 = unpack(self.nodes[id as usize]);
                    for k in 0..DEGREE {
                        vecs[k as usize].push(ids1[k as usize]);
                    }
                }
                let mut ids = [0; DEGREE as usize];
                for k in 0..DEGREE {
                    ids[k as usize] = self.union(step, &mut vecs[k as usize]);
                }
                node = pack(ids)
            };
            self.node_id(node)
        }
    }

    fn for_each(&self, low: u32, high: u32, id: Id, f: &mut impl FnMut(u32)) {
        if id != 0 {
            let mut node = self.nodes[id as usize];
            if high - low <= NODE_BITS {
                while node != 0 {
                    let k = node.trailing_zeros();
                    f(low + k);
                    node &= !(1 << k);
                }
            } else {
                let step = (high - low) / DEGREE;
                let ids = unpack(node);
                for k in 0..DEGREE {
                    self.for_each(low + k * step, low + (k + 1) * step, ids[k as usize], f);
                }
            }
        }
    }
}

fn parse_nfa(input: &str) -> IResult<&str, (Trie, Automaton<Id>)> {
    let (input, _) = tag("Automaton")(input)?;
    let (input, _) = preceded(multispace0, char('('))(input)?;
    let (input, _) = preceded(multispace0, tag("\"nondet\""))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, size) = preceded(multispace0, map_res(digit1, u32::from_str))(input)?;
    let mut trie = Trie::new(size);
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, alphabet) = preceded(multispace0, map_res(digit1, usize::from_str))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, transitions) = preceded(multispace0, |input| {
        parse_vec(
            |input| parse_vec(|input| trie.parse_set(input), input),
            input,
        )
    })(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, initial) = preceded(multispace0, |input| trie.parse_set(input))(input)?;
    let (input, _) = preceded(multispace0, char(','))(input)?;
    let (input, accepting) = preceded(multispace0, |input| {
        parse_vec(|input| map_res(digit1, u32::from_str)(input), input)
    })(input)?;
    let (input, _) = preceded(multispace0, char(')'))(input)?;

    Ok((
        input,
        (
            trie,
            Automaton {
                size,
                alphabet,
                transitions,
                initial,
                accepting,
            },
        ),
    ))
}

struct DFABuilder {
    nfa_accepting: Id,
    trie: Trie,
    set_dstate: HashMap<Id, u32>,
    queue: VecDeque<Id>,
    dfa: Automaton<u32>,
}

impl DFABuilder {
    fn visit(&mut self, set: Id) -> u32 {
        let DFABuilder {
            nfa_accepting,
            trie,
            set_dstate,
            queue,
            dfa,
        } = self;
        *set_dstate.entry(set).or_insert_with(|| {
            dfa.size += 1;
            if trie.intersects(trie.size, *nfa_accepting, set) {
                dfa.accepting.push(dfa.size);
            }
            queue.push_back(set);
            dfa.size
        })
    }
}

fn nfa_to_dfa(mut trie: Trie, nfa: Automaton<Id>) -> Automaton<u32> {
    let mut builder = DFABuilder {
        nfa_accepting: trie.vec_id(0, trie.size, nfa.accepting.clone()),
        trie,
        set_dstate: HashMap::new(),
        queue: VecDeque::new(),
        dfa: Automaton {
            size: 0,
            alphabet: nfa.alphabet,
            transitions: vec![vec![]; nfa.alphabet],
            initial: !0,
            accepting: vec![],
        },
    };
    builder.dfa.initial = builder.visit(nfa.initial);

    let mut sets = Vec::new();
    while let Some(set) = builder.queue.pop_front() {
        for (letter, transition) in nfa.transitions.iter().enumerate() {
            builder
                .trie
                .for_each(0, builder.trie.size, set, &mut |nstate| {
                    sets.push(transition[nstate as usize - 1])
                });
            let set1 = builder.trie.union(builder.trie.size, &mut sets);
            debug_assert!(sets.is_empty());
            let dstate = builder.visit(set1);
            builder.dfa.transitions[letter].push(dstate);
        }
    }

    builder.dfa
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut line = String::new();
    io::stdin().read_line(&mut line)?;
    let (rest, (trie, nfa)) =
        delimited(multispace0, parse_nfa, multispace0)(&line).map_err(|e| e.to_string())?;
    if rest != "" {
        return Err("expected end of input".into());
    }

    let dfa = nfa_to_dfa(trie, nfa);
    println!(
        "Automaton(\"det\", {}, {}, {:?}, [{}], {:?})",
        dfa.size, dfa.alphabet, dfa.transitions, dfa.initial, dfa.accepting
    );

    Ok(())
}

Cargo.toml
[package]
name = "automaton"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"

[dependencies]
nom = "6.2.1"
mimalloc = { version = "0.1.26", default-features = false }
hashbrown = { version = "0.11.2", features = ["raw"] }
ahash = "0.7.4"

This is great. I think it can be parallelised by a factor equal to the number of symbols at least.  For each row, I think we can do the operations for each symbol separately.  Would that work with your code? (Did you write the code in 2018?)

@Anush Parallelizing this is a challenge because there’s so much shared mutable state at every step. edition = 2018 selects the current Rust 2018 edition of Rust.

I added some links to the question in any case they are helpful.

Problem 16 has 1338264594 states!

That’s approaching the size where overflowing the 32-bit Id might be a concern (the Id tends to grow a bit larger than the number of states). It’ll probably be fine as long as you aren’t crazy enough to devise even larger test cases , but I’ve added an overflow check to be safe.

If I want to try 17, do I just do a global search and replace with 32 -> 64 in your code?

@Anush You could try (also node.trailing_zeros() ↦ node.trailing_zeros() as u64), but it’d be slower and even more RAM-hungry, and I suspect the program as written is already using nearly all of your 64 GB for case 16. The number of Ids is only 0.4% more than the number of states for case 15, so maaybe the 32-bit Id might be enough for case 17, even if your RAM still isn’t.

Thanks. I found a computer with more RAM so that shouldn't be the limiting factor.