State transition problems

simonh1000 2018-02-14 08:34:28 UTC #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?

rob 2018-02-14 11:38:14 UTC #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 }.)

rupert 2018-02-14 16:50:34 UTC #3

Here is my Wolf, Goat, Cabbage solution:

github.com

the-sett/ai-search/blob/master/example/RiverCrossing.elm

module RiverCrossing exposing (uninformed, start)

import EveryDict as Dict exposing (EveryDict)
import Search
import Maybe.Extra
import Html exposing (text)


main =
    text <|
        toString <|
            Search.nextN 250 <|
                Search.iterativeDeepening 1 uninformed [ start ]



{- Description of the puzzles state. -}


type Character

This file has been truncated. show original

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.

rupert 2018-02-14 16:57:17 UTC #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

simonh1000 2018-02-15 19:28:20 UTC #5

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

simonh1000 2018-02-15 19:31:12 UTC #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)

rupert 2018-02-15 21:25:35 UTC #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.