[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
8

PR for V track:

9

@kahgoh We just had lots of fun showing off your Elixir and Java solutions for the Zebra Puzzle video. Thanks for everything you’ve done for Exercism :slight_smile:

2 Likes
10

Gleam

1 Like
11

In my Dart solution, I put “Norwegian” as the first choice in nations for permutations as it is set in Constraint 10. It will definitely save time because the solution can be found in the 1st loop of a fixed nation (Norwegian).

12

MIPS PR

1 Like
13

One of the instructions is

The Ukrainian drinks tea.

Most tracks spell Ukrainian correctly in source code:

c
cpp
crystal
dart
elixir
elm
emacs-lisp
go
haskell
java
javascript
kotlin
phix
php
powershell
prolog
python
racket
raku
ruby
scala
unison

Some tracks use the spelling Ukranian, and should be fixed:

csharp
d
fsharp
idris
jq
nim
tcl
vbnet
vlang
wren

D PR
Idris PR
vlang PR
Wren PR

3 Likes
14

Wren PR merged.
Jq fixed.
I’ll get to tcl this weekend.

1 Like
15

I found a minute. tcl PR.

2 Likes
16

C# PR
F# PR
Nim PR
vbnet PR

1 Like