State transition problems

Request Feedback
1

As a bit of fun I wanted to see how much type safety I could leverage to solve the Wolf, Goat, Cabbage problem in Elm using just Basics and the repl. My effort is at https://gist.github.com/simonh1000/8d288456f5b71d9fa97b908b3e2bdbdc

This is not a large problem, and I’m happy with my solution in most respects. But the weaknesses I saw were:

  • The need to use List rather than the more obvious Set to represent the characters on each bank. A union type is not comparable in Elm
  • the equality test using stringify is pretty messy, even if (I think) provably correct

Has anyone solved this more elegantly?

2

Some thoughts from giving the code a read-over.

  • compareState does not really implement a proper ordering (STR > STL and STL >STR). Why not juststateEqual : State -> State -> Bool`?
  • STR and STL could be spelled out, they’re pretty obscure
  • validMoves seems poorly named, it searches for the whole solution
  • How about a dedicated type CharacterSet that implements the various operations you do on the List Character? You could start with type alias CharacterSet = List Character, that would already make the code more readable. (I’d consider giving up on the type Character and going for type alias CharacterSet = { goat : Bool, cabbage : Bool, wolf : Bool }.)
3

Here is my Wolf, Goat, Cabbage solution:

It is an example under my ai-search library. The problem space and the search strategy are defined separately, so you can change the underlying search. This level of flexibility is obviously not needed to solve the problem, so my solution is a bit longer than it might otherwise be, and I cannot really say it is a more elegant way of doing it.

I had a go at the 8-puzzle too, but didn’t finish that one.

I have also been thinking of writing a solver for the Rubix cube. I don’t know if there are search heuristics for that one.

4

These two libraries can help with that:

http://package.elm-lang.org/packages/Gizra/elm-all-set/latest

http://package.elm-lang.org/packages/eeue56/elm-all-dict/latest

5

Ugh - forgot to mention that I deliberately did not use any libraries

6

thanks

Your last point is interesting - perhaps the state could have been implemented as a single record type (using perhaps a Left | Right type instead of a Bool)

7

The reason I did not model it this way, is that I wanted to be able to iterate the list of characters in order to try each of them out in turn. That seemed easier with a List Character.

I do find looking for the best data model in Elm can be challenging, I think because it is such an exacting and minimal language. Problems like this one are great for learning on, so keep 'em coming if you’ve got more.

P.S. I would also love to do an animation of this, with the characters getting in the boat and farmer rowing them accross. In Elm of course.