Way waaaaaay faster algorithm… takes seconds instead of minutes/hours

[dlenski]

I've been thinking about this a lot, and suddenly figured out how to do it while out for a run.

🏃🏻💭🧠💡👨🏻‍💻🌃…😮⏩💆🏻‍♂️

I thought we needed O(_N_×_M_²) runtime to figure out the best next guess (O(_N_³) for the first guess). But no!
It's possible to figure out the best next guess in O(N_×_M) (O(_N_²) for the first guess).

The way to do it is… actually amazingly simple and beautiful.

• See 8128325 for the change to the algorithm.
• See 154c36f for a detailed explanation in the comment.

[HenkPoley]

Technically calloc() and realloc() should use the sizeof() of a **.

% clang --analyze best_guess.c
best_guess.c:252:18: warning: Result of 'calloc' is converted to a pointer of type 'char *', which is incompatible with sizeof operand type 'char **' [unix.MallocSizeof]
    char **buf = calloc(bufsize, sizeof(*output));
    ~~~~~~~      ^~~~~~          ~~~~~~~~~~~~~~~
best_guess.c:293:19: warning: Result of 'realloc' is converted to a pointer of type 'char *', which is incompatible with sizeof operand type 'char **' [unix.MallocSizeof]
            buf = realloc(buf, bufsize * sizeof(*output));
                  ^~~~~~~                ~~~~~~~~~~~~~~~
2 warnings generated.

[dlenski]

Thank you, @HenkPoley, fixed that dumb mistake. 🤦‍♂️