Add NFA Simulator hole

[stefangimmillaro]

Collaboration with @msbranicky

• Thank you to @lynn for her thoughtful update to the DFA description https://github.com/code-golf/code-golf/pull/1013/files. We are using this language here too.
• And thank you to all those who contributed on discussion and bug finding https://github.com/code-golf/code-golf/issues/1006

by popularish demand...

we bring you Finite Automaton Chapter II

Description

See https://github.com/code-golf/code-golf/pull/1037/files

Example input (if any)

    | a | b | c |
→ 0 |{0}|{0}|{0,1}| 
  1 |{2}| ∅ |  ∅ |
  2 | ∅ |{3}|  ∅ |
 F3 | ∅ | ∅ | ∅ |
acbcab

Example output

{0,3} Accept

[btnlq]

Every DFA is also an NFA. We can support contravariance here: every NFA Simulator solution should be a DFA Simulator solution. It changes the example to something like this:

Example input

    a b c
> 0 0 0 01
  1 2 ∅ ∅
  2 ∅ 3 ∅
 F3 ∅ ∅ ∅
"acbcab"

Example output

03 Accept

We can also use {} instead of ∅ to avoid non-ASCII characters.

[SirBogman]

I don't think DFA simulator is popular enough to justify adding related holes that are similar.

[stefangimmillaro]

From SirBogman here

Based on the screenshots, I really dislike the "→" character used for the initial state. It's going to mess up the alignment of strings in languages where you have to deal with each UTF-8 byte separately. "∅" is going to cause the same issue and I don't like it.

One thing that the other hole didn't have that would be useful is some kind of indicator just to the left of the state names. Ex:

>FS0
 FS1
  S2

Where S indicates the definition of the state. It would be a lot easier to search for it in some languages. S is just a suggestion.

[stefangimmillaro]

I am happy to update the arrow and empty set symbol to > and {}. I will ponder adding the S. I think there is an argument to be made that one of the interesting parts of DFA was to identify the correct next row. Adding this simplification has merit for this variant.

[5cw]

Seconding the call for a switch from → to >, I think the hole should mimic the DFA hole as much as possible. I personally don't feel the need for the S, the info is all found consistent distances after the newline, and the DFA hole didn't have it. I don't mind the ∅ much either way, the solution would be a little shorter and cleaner without it but it's not an unreasonable edge case to handle and it looks pretty.

Wasn't an issue in terms of the actual text processing, but for aesthetics I'd prefer if the table looked a little neater by padding the columns out to line up.

    |    g    |    6    |    w    |    h    |    q    |    n    |   r   |
 F0 |   {7}   |    ∅    |   {6}   |  {0,7}  | {0,2,7} | {0,6,7} |   ∅   |
 F2 |    ∅    | {2,6,7} |{0,2,6,7}|   {7}   |    ∅    |   {6}   |{0,6,7}|
> 6 |{0,2,6,7}|{0,2,6,7}|   {6}   |   {2}   | {2,6,7} |{0,2,6,7}|  {7}  |
 F7 |    ∅    |    ∅    |    ∅    |{0,2,6,7}|{0,2,6,7}| {0,2,7} | {0,7} |

or

    | g       | 6       | w       | h       | q       | n       | r     |
 F0 |{7}      | ∅       |{6}      |{0,7}    |{0,2,7}  |{0,6,7}  | ∅     |
 F2 | ∅       |{2,6,7}  |{0,2,6,7}|{7}      | ∅       |{6}      |{0,6,7}|
> 6 |{0,2,6,7}|{0,2,6,7}|{6}      |{2}      |{2,6,7}  |{0,2,6,7}|{7}    |
 F7 | ∅       | ∅       | ∅       |{0,2,6,7}|{0,2,6,7}|{0,2,7}  |{0,7}  |

and just for good measure, a wild, out there proposal that because the states are one-digit numbers, the set notation is not strictly necessary

    | g    | 6    | w    | h    | q    | n    | r   |
 F0 | 7    | ∅    | 6    | 07   | 027  | 067  | ∅   |
 F2 | ∅    | 267  | 0267 | 7    | ∅    | 6    | 067 |
> 6 | 0267 | 0267 | 6    | 2    | 267  | 0267 | 7   |
 F7 | ∅    | ∅    | ∅    | 0267 | 0267 | 027  | 07  |

neither are the dividers

     g    6    w    h    q    n    r
 F0  7    ∅    6    07   027  067  ∅
 F2  ∅    267  0267 7    ∅    6    067
> 6  0267 0267 6    2    267  0267 7
 F7  ∅    ∅    ∅    0267 0267 027  07

and for maximal minimalism

     g    6    w    h    q    n    r
 F0  7         6    07   027  067
 F2       267  0267 7         6    067
> 6  0267 0267 6    2    267  0267 7
 F7                 0267 0267 027  07

this would declutter the screen and make it look more similar to the DFA hole, but at the expense of some clarity. and who doesn't love brackets? So i think there's good cases to be made for many setups. But I had fun solving it and I think it's a good hole.

edit: didn't realize btnlq basically proposed option 4 already, my main point is the columns should line up.

[Yewzir]

Since @stefangimmillaro requested help from anyone to look into the formatting, I went ahead and gave it a shot as per #1046. The thing is, everyone wants something and it can go so many ways, according to what I just saw here. I've done several modifications to what he had implemented to come up with one example of pretty, nicely formatted output.

Yes, agreed, I'm well aware that it's just one of many directions we can take and alignments we can make. I'm willing to help him because I'm sure he has his reasons for not being able to work on his experiment, but there has to be some kind of a decision. I'll start easy: just anything is acceptable for me.

I don't think DFA simulator is popular enough to justify adding related holes that are similar.

For what it's worth, I couldn't agree more on that in all honesty, but the hole's experimentally live anyhow so might as well make the best of it.

[stefangimmillaro]

Thanks for taking a look @Yewzir. I think we should just close this one up. There's a lot of excitement around the other holes. I do think the formatting that you have applied here is much more appealing though probably more of a pain to implement in a solution. If you decide you like the idea you're more than welcome to iterate! I'll follow up on your notes in the PR. LMK if you would rather just close this out, it has been open without much interest long enough imo.

[Yewzir]

Thanks for taking a look @Yewzir. I think we should just close this one up. There's a lot of excitement around the other holes. I do think the formatting that you have applied here is much more appealing though probably more of a pain to implement in a solution. If you decide you like the idea you're more than welcome to iterate! I'll follow up on your notes in the PR. LMK if you would rather just close this out, it has been open without much interest long enough imo.

@stefangimmillaro You simply caught me at an unfortunate time to cooperate extensively on this with what I'm doing, like I explained on Discord yesterday. Whether you want to want to close the issue and erase hole data, or let it linger, is not my decision to make.