[48in24 Exercise] [05-07] Zebra Puzzle

Exercism 48in24
1

This issue is a discussion for contributors to collaborate in getting ready to be featured in 48in24. Please refer to this forum topic for more info.

We will be featuring Zebra Puzzle from May 07 onwards.

Staff jobs

These are things for Erik/Jeremy to do:

  • ☐ Check/update exercise in Problem Specifications
  • ☐ Create + schedule video

Community jobs

For each track:

  • Implement Zebra Puzzle
  • Add approaches (and an approaches introduction!) for each idiomatic or interesting/educational approach.
  • Add video walkthroughs (record yourself solving and digging deeper into the exercise).
  • Highlight up to 16 different featured exercises (coming soon)

Existing Approaches

You can use these as the basis for approaches on your own tracks. Feel free to copy/paste/reuse/rewrite/etc as you see fit! Maybe ask ChatGPT to translate to your programming language.

Track Statuses

You can see an overview of which tracks have implemented the exercise at the #48in24 implementation status page.

2

I’ve currently gathered the following solutions to feature:

  1. Kotlin: directly return answer
    The simplest solution :)

  2. Python: check all permutations
    Generate all permutations and then check them for validity

  3. Scala: check only valid permutations
    Generate permutations and before the next permutations, check them for validity

  4. Prolog: logic-based pattern
    Use prolog’s built-in logic solver

  5. C: use unsigned int to encode options and use bit manipulation
    Less than 32 options so uint is enough, use bit manipulation for fast checking

  6. Elixir: mutate using rules via depth-first search
    Start with “random” seed, mutate values using rules and do depth-first search

  7. Java: use AC-3 algorithm
    Use the AC-3 algorithm to define variables and their domain

  8. C#: use generic algorithm
    Use a genetic algorithm to “guide” random solutions to the right one

Mention:

  • Total number of permutations is 5!^5=24_883_200_000 which is 24 billion, so filtering is key

If anyone has more suggestions, do let us know!

3

@ErikSchierboom Ups:

grafik
grafik839×127 20.5 KB

Seen here: Solve Zebra Puzzle on Exercism It’s in the problem specs and mass-pull-requested.

I tried to fix it, but Markdownlint doesn’t like it. Fix:

4

Elixir: apply the rules to mutate towards the solution
Start with a “seed” and then apply each rule to mutate to get closer to the solution.

1 Like
5

@kahgoh Lovely! It’s a depth-first search right?

6

@ErikSchierboom By “depth-first”, are you talking about the how it checks the mutations from the later rules first? If so, I think that’s right as the mutations happen to be prepended to the front of the queue (as prepending takes constant time, but appending takes longer as the list grows).

1 Like
7

Java: Use the AC-3 algorithm to eliminate values
Use the constraints and the AC-3 algorithm to remove values from the set of possible values.

In case it helps, I also found this video helpful to get my head around AC-3.

(Thanks to @aifrak for mentioning AC-3 to me)

1 Like