3 ms·
Btw, note that the line const randomNumbers = random ? [1, 2, 3, 4, 5, 6, 7, 8, 9].sort(() => Math.random() - 0.5).sort(() => Math.random() - 0.5) : null
by mzl 11mo ago
Btw, note that the line
const randomNumbers = random ? [1, 2, 3, 4, 5, 6, 7, 8, 9].sort(() => Math.random() - 0.5).sort(() => Math.random() - 0.5) : null
does not really do what you seem to intend. Sort requires a comparison function that is stable, and there are a lot of things that could go wrong if this is not supplied.
For shuffling, use a shuffle algorithm. Fisher-Yates is the common suggestion on what to use.
- senfiaj 11mo agoThis is just for generation of sudoku image. The actual solver doesn't do this this expensive operation (the sudoku generator just reuses the solver function to fill with random numbers). From my experience for just generation it works good enough and fast enough. Yes I know how to efficiently shuffle by swaps in O(n) time with the correct distribution of probabilities (I didn't know that algorithm name BTW), I'm just too lazy =).
- mzl 11mo agoWhile Fisher-Yates or similar algorithms are more efficient, the real reason I wanted to mention it is that in many systems the sorting algorithm might crash or corrupt memory when used with a randomized comparison operator. It is inherently unsafe.
- senfiaj 11mo agoIn JavaScript it's OK. At that time I knew that it is not the most efficient solution (for generation O(n log n) shuffle is not critical), just wanted to do this with simple one liner. With C++ I would definitely use this https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html https://en.cppreference.com/w/cpp/algorithm/random_shuffle.h... .
- mzl 11mo agoAccording to MDN it is expected to be an actual comparator: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#description:~:text=More%20formally%2C%20the%20comparator%20is%20expected%20to%20have%20the%20following%20properties https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... The specification says that if the comparator is not a consistent comparator, the sort order is implementation defined: https://tc39.es/ecma262/multipage/indexed-collections.html#sort-order https://tc39.es/ecma262/multipage/indexed-collections.html#s... Further along, it is specified that only if the sort order is correct, are you guaranteed to get a permutation of the input as the result. I would not write code expecting this to work.
- senfiaj 11mo agoThanks. I changed to a proper shuffling. Although there was nothing catastrophic in JS (like corruption, duplication / loss of elements), just more biased randomness and slower execution time (not critical for generation). But yeah, it was worth it for fair randomness.