Timeline for Total Derangement (Difficulty Level: Hard)
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2022 at 4:45 | comment | added | Ajax1234 |
@AndersKaseorg Thanks for the clarification on O(n!), will take a look at the possibility of dead-end rows later.
|
|
| Jun 25, 2022 at 4:45 | history | edited | Ajax1234 | CC BY-SA 4.0 |
deleted 902 characters in body
|
| Jun 25, 2022 at 4:03 | comment | added | Anders Kaseorg |
You still aren’t outputting a single random block of m cycles. There is no reason for main to be a generator; the challenge just asks you to output one random block of m cycles. (If the challenge asked for a uniformly random die roll, a solution would be def main(): return random.randrange(1, 7)—nothing else.) Putting that aside, your generator can still get stuck on the same dead-end rows I described earlier, and when it doesn’t get stuck, it still doesn’t satisfy the equal probability requirement. And it takes at least \$O(n!)\$ time to generate your cycle pool.
|
|
| Jun 25, 2022 at 3:49 | comment | added | Ajax1234 |
@AndersKaseorg Added a bit of explanation to a randomized version of my previous solution, although even Python's random module is pseudo-random, so who knows. I suppose it would be valid to simply produce all possible m cycles, and then choose one randomly, but I think that goes against the spirit of the question.
|
|
| Jun 25, 2022 at 3:46 | history | edited | Ajax1234 | CC BY-SA 4.0 |
added 903 characters in body
|
| Jun 25, 2022 at 3:15 | comment | added | Anders Kaseorg | Now this doesn’t have any randomness at all. The challenge asks for a single random block of m cycles, where all valid outputs occur with equal probability. And I don’t know what you’re measuring with \$O(n^3)\$, but it’s definitely wrong. | |
| Jun 25, 2022 at 2:49 | history | edited | Ajax1234 | CC BY-SA 4.0 |
added 59 characters in body
|
| Jun 24, 2022 at 23:33 | comment | added | Anders Kaseorg | I’m skeptical that this strategy or anything similar can satisfy the challenge’s requirement that “All possible sets of m cycles of length n that fit the criteria should have equal probability of occurring”; do you have any reason to believe that it does? Also, your \$O(mn)\$ claim is not even remotely plausible, given that you have at least three nested loops with lots of restart conditions, and you generate less than half an output per second at n = 6, m = 4. | |
| Jun 24, 2022 at 23:18 | history | edited | Ajax1234 | CC BY-SA 4.0 |
added 324 characters in body
|
| Jun 24, 2022 at 22:28 | comment | added | Ajax1234 |
@AndersKaseorg I was under the impression that only one block of m cycles had to be produced for the solution to be valid (based on "Example outputs"), hence the use of a generator + next. Anyway, I will look deeper into this later.
|
|
| Jun 24, 2022 at 21:39 | history | edited | Ajax1234 | CC BY-SA 4.0 |
deleted 6 characters in body
|
| Jun 24, 2022 at 21:08 | comment | added | Anders Kaseorg | No. There do exist solutions for n = 6, m = 4—an example is listed in the challenge—and the challenge requires you to find them all with equal probability. You just can’t use your row-by-row strategy, since you might start with those dead-end rows. This is marked “difficulty level: hard” for a reason. | |
| Jun 24, 2022 at 20:46 | history | edited | Ajax1234 | CC BY-SA 4.0 |
deleted 48 characters in body
|
| Jun 24, 2022 at 19:51 | comment | added | Anders Kaseorg |
This doesn’t work. next(main(5, 3)) hangs forever about 1 in 6 times. (Convenient that your TIO link only tests 5 times!) I think that’s due to a bug, but even with the bug fixed, a strategy like this can’t possibly work. For example, with n = 6, m = 4, there is no way to extend [1, 2, 3, 4, 5, 0], [2, 3, 5, 0, 1, 4], [3, 4, 1, 5, 0, 2] with a fourth cycle.
|
|
| Jun 24, 2022 at 19:02 | history | answered | Ajax1234 | CC BY-SA 4.0 |