Mazy Mice

[rabestro]

Add Practice Exercise: Mazy Mice

Exercise Description:

This pull request introduces a new practice exercise called "Mazy Mice".

Mickey and Minerva are two clever mice who love to navigate mazes to find cheese. They prefer mazes that have only one correct path to the cheese, with no loops or inaccessible sections.

The goal of this exercise is to write a program that generates "perfect" mazes. A perfect maze is defined as a maze where every cell is reachable and there is exactly one path between any two cells. The generated maze should be rectangular, with an entrance on the left and an exit on the right.

Key Features of the Exercise:

• Maze Generation: Implement an algorithm (e.g., Depth First Search, Randomized Kruskal's, Randomized Prim's) to generate a perfect maze of given dimensions (rows and columns).
• Output Formatting: The maze should be represented as a string using box-drawing characters (e.g., ┌, ─, │, └, ┘, ├, ┤, ┬, ┴, ┼) for walls and passages, and an arrow symbol (⇨) for the entrance and exit.
• Seeded Generation: The generator should accept an optional seed. If a seed is provided, the same maze must be generated every time for that seed. If no seed is provided, a random maze should be generated.
• Constraints: Maze dimensions (rows and columns) should typically be within a specified range (e.g., 5 to 100 cells).

This PR includes a canonical-data.json file with test cases covering:

• Maze Properties:
  • Correct dimensions (width and height based on input rows/cols).
  • Usage of valid characters for walls, paths, entrance, and exit.
  • Presence of a single entrance and a single exit.
  • Verification of "perfectness" (single path, no loops, no isolated sections) for various maze sizes and aspect ratios.
• Seeded Generation:
  • Tests to ensure that providing a specific seed results in a deterministic, predictable maze output. Several cases include the full expected maze string for a given seed.
• Randomness:
  • A test case description to guide tracks in verifying that omitting the seed leads to different mazes on subsequent runs (acknowledging this is often a procedural test at the track level).
• Error Handling:
  • Test cases for invalid input dimensions (e.g., rows/columns outside the allowed range), expecting specific error messages.

This exercise aims to provide a challenging and engaging problem involving algorithm design, data structure manipulation (representing the maze), and careful output formatting.

[github-actions[bot]]

Hello. Thanks for opening a PR on Exercism. We are currently in a phase of our journey where we have paused community contributions to allow us to take a breather and redesign our community model. You can learn more in this blog post. As such, all issues and PRs in this repository are being automatically closed.

That doesn't mean we're not interested in your ideas, or that if you're stuck on something we don't want to help. The best place to discuss things is with our community on the Exercism Community Forum. You can use this link to copy this into a new topic there.

---

Note: If this PR has been pre-approved, please link back to this PR on the forum thread and a maintainer or staff member will reopen it.

[IsaacG]

Please add a forum link to this discussion.

[rabestro]

Please add a forum link to this discussion. https://forum.exercism.org/t/add-mazy-mice-exercise-to-the-repository/7113

[ErikSchierboom]

Thanks for creating the PR! I am not entirely sure how useful the canonical data is right now as the current format does not really allow for easy test generation. This is not something this PR can do a ton about, as randomness is really hard.

It might be worth looking at how we deal with randomness in other canonical data:

• https://github.com/exercism/problem-specifications/blob/main/exercises/diffie-hellman/canonical-data.json
• https://github.com/exercism/problem-specifications/blob/main/exercises/dnd-character/canonical-data.json

I think the idea of a maze generator is really cool, I'd just like us to think a bit on how to best structure the canonical data to allow it to be as helpful as it can be for implementing tracks. CC @exercism/reviewers

[rabestro]

I think the idea of a maze generator is really cool, I'd just like us to think a bit on how to best structure the canonical data to allow it to be as helpful as it can be for implementing tracks. CC @exercism/reviewers

I have updated the canonical data with additional test cases and provided a Java implementation, which can be found at https://github.com/exercism/java/pull/2355. However, I am encountering an issue with my markdown formatting and the CI/CD process is failing as a result. I am unsure of what steps to take to correct the formatting error.

[ErikSchierboom]

@rabestro You can format the file using:

yarn install
yarn run format-md

[ErikSchierboom]

I have updated the canonical data with additional test cases

The expected values are still string values. Did you look at the examples I listed? If so, what did you think? CC @exercism/reviewers for thoughts on how to best structure this canonical data

[rabestro]

@rabestro You can format the file using:

yarn install
yarn run format-md

fixed, thank you!

[ErikSchierboom]

Did you mean to close it?

[rabestro]

I have updated the canonical data with additional test cases

The expected values are still string values. Did you look at the examples I listed? If so, what did you think? CC @exercism/reviewers for thoughts on how to best structure this canonical data

I changed to numbers and boolean values

[rabestro]

Did you mean to close it?

No, I just closed the comments. :)

[senekor]

Some general feelings of mine about this exercise: I don't like exercises with randomness. They are hard to test properly. I think this can be seen here pretty well, where the test data is not very useful. Basically the only information in every test case is the description of what property should be checked. Like Erik said, you can't use that to generate the actual test cases. Every track will have to write the test cases from scratch.

I also have a feeling that it's pretty easy to generate a maze that technically complies with the properties but would be very boring to solve.

I have a very opinionated idea: We could force users to implement a specific algorithm to generate the maze. Then we know what kind of "random" decision the algorithm will have to make at every step. We can supply the list of decisions of the algorithm as input and the precise maze that must be generated as data to test against.

cons:

• Users have no freedom to choose the maze generation algorithm they want.

pros:

• Users have no freedom to choose a boring maze generation algorithm, i.e. "cheesing" the exercise.
• We can create much better tests that lend themselves to TTD like our other exercises. We can start off with simple mazes and work up to mazes with more complicated edge cases.
• The tests can be much better suited for test generation, meaning lower effort to implement it on each track.

[ErikSchierboom]

@senekor Would the maze generation algorithm be easy to explain in steps?

[senekor]

You mean easy to explain to students? I guess it depends on the algorithm we choose. There's a list here. I think it doesn't matter much if we choose an easy or a difficult one, in either case the difficulty is at least standardized. This will also make it easier for tracks to select an appropriate difficulty setting.

[ErikSchierboom]

I'm a bit torn. I quite like the randomness aspect as that fits my mental model or generating mazes. That said, the implementation of its tests is a lot harder. Maybe it would be useful if someone tried implementing this exercise in their language of choice.

[jiegillet]

[I don't know how useful this will be, I have not read the PR and I'm only reacting to the last comment, but] we have a concept exercise in the Elm track that's about generating a random maze with random treasure in it. Link to the exercise, link to my solution, link to github. Elm has this cool thing where you can do fuzz tests and check the distribution of the generated solutions (how many solutions have such or such property). EDIT: more examples on the dnd-character tests

[senekor]

I think it would be pretty easy to make most tests deterministic and then have one or more random ones at the end. Those wouldn't be primarily for checking correctness, but just to drive home the feeling of generating mazes randomly. That would even teach the additional valuable lesson that you can split programs with randomness in a deterministic part that can still be well tested. Basically the "functional core, imperative shell" concept.

[ErikSchierboom]

I'd like to get some more people's thoughts on this. @exercism/reviewers would you mind chiming in here?

[IsaacG]

I'd like to get some more people's thoughts on this. @exercism/reviewers would you mind chiming in here?

Should this be on the forum and targeted at maintainers, who would be the ones building the tests?

Is the concern about the complexity and maintenance around keeping tests reliable? The cost of needing to write a maze solver to test this exercise?

Glenn and I have already approved this exercise in the awk track which is at least somewhat of an implicit approval, though we only approved the test runner and didn't have to write it ourselves.

On the one hand, it's a fun and interesting exercise for students to solve. On the other hand, writing the tests for it would definitely be harder than most (all?) of the other exercises by a large margin. Is that an issue if maintainers can opt to omit this exercise? Would clear docs with guidance on writing tests help?

[ErikSchierboom]

Should this be on the forum and targeted at maintainers, who would be the ones building the tests?

I'll open a forum post. Sorry for the delay @rabestro!

[kotp]

Should this be on the forum and targeted at maintainers, who would be the ones building the tests?

I'll open a forum post. Sorry for the delay @rabestro!

The forum post can be found Mazy Mice exercise proposal here.