Created
February 27, 2015 11:33
-
-
Save mchericoni/936c8ddc798606ca2427 to your computer and use it in GitHub Desktop.
Breadth-first search problem in Scala
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| object SumProblem { | |
| // States | |
| type State = Int | |
| val initialState: State = 5 //> initialState : SumProblem.State = 5 | |
| val target: State = 23 //> target : SumProblem.State = 23 | |
| // Moves | |
| class Move(addend: Int) { | |
| def change(state: State): State = state + addend | |
| override def toString = addend.toString | |
| } | |
| // Legal Moves | |
| val legalMoves: List[Move] = List(new Move(4), new Move(7), new Move(6), new Move(11)) | |
| //> legalMoves : List[SumProblem.Move] = List(4, 7, 6, 11) | |
| // Example of applying a Move and obtaining a new State | |
| legalMoves(0) change initialState //> res0: SumProblem.State = 9 | |
| // Paths | |
| class Path(history: List[Move]) { | |
| def extend(move: Move): Path = new Path(move :: history) | |
| def endState: State = (history foldRight initialState)(_ change _) | |
| override def toString = initialState + " + " + (history.reverse mkString (" + ")) + " = " + endState | |
| } | |
| // The initial Path | |
| val initialPath = new Path(Nil) //> initialPath : SumProblem.Path = 5 + = 5 | |
| // Example of Path after 2 moves | |
| new Path(List(legalMoves(0), legalMoves(2))) //> res1: SumProblem.Path = 5 + 6 + 4 = 15 | |
| // Where can we go from the initial state with one move? | |
| legalMoves map initialPath.extend //> res2: List[SumProblem.Path] = List(5 + 4 = 9, 5 + 7 = 12, 5 + 6 = 11, 5 + 11 | |
| //| = 16) | |
| // 2nd iteration | |
| val more = for { | |
| path <- legalMoves map initialPath.extend | |
| next <- legalMoves map path.extend | |
| } yield next //> more : List[SumProblem.Path] = List(5 + 4 + 4 = 13, 5 + 4 + 7 = 16, 5 + 4 | |
| //| + 6 = 15, 5 + 4 + 11 = 20, 5 + 7 + 4 = 16, 5 + 7 + 7 = 19, 5 + 7 + 6 = 18, | |
| //| 5 + 7 + 11 = 23, 5 + 6 + 4 = 15, 5 + 6 + 7 = 18, 5 + 6 + 6 = 17, 5 + 6 + 11 | |
| //| = 22, 5 + 11 + 4 = 20, 5 + 11 + 7 = 23, 5 + 11 + 6 = 22, 5 + 11 + 11 = 27) | |
| //| | |
| // All the possible paths starting from a set of paths, given as a Stream | |
| def from(paths: Set[Path]): Stream[Set[Path]] = | |
| if (paths.isEmpty) Stream.Empty | |
| else { | |
| val more = for { | |
| path <- paths | |
| next <- legalMoves map path.extend | |
| if (next.endState <= target) | |
| } yield next | |
| paths #:: from(more) | |
| } //> from: (paths: Set[SumProblem.Path])Stream[Set[SumProblem.Path]] | |
| // All the paths from the initial empty Path | |
| val pathSets = from(Set(initialPath)) //> pathSets : Stream[Set[SumProblem.Path]] = Stream(Set(5 + = 5), ?) | |
| // Print the first 3 elements of the Stream | |
| pathSets take 3 foreach println //> Set(5 + = 5) | |
| //| Set(5 + 4 = 9, 5 + 7 = 12, 5 + 6 = 11, 5 + 11 = 16) | |
| //| Set(5 + 6 + 7 = 18, 5 + 6 + 6 = 17, 5 + 6 + 11 = 22, 5 + 4 + 7 = 16, 5 + 11 | |
| //| + 7 = 23, 5 + 11 + 6 = 22, 5 + 4 + 6 = 15, 5 + 7 + 11 = 23, 5 + 6 + 4 = 15 | |
| //| , 5 + 7 + 6 = 18, 5 + 11 + 4 = 20, 5 + 4 + 11 = 20, 5 + 4 + 4 = 13, 5 + 7 + | |
| //| 4 = 16, 5 + 7 + 7 = 19) | |
| // Find the solutions (if any) | |
| for { | |
| pathSet <- pathSets | |
| path <- pathSet | |
| if path.endState == target | |
| } yield path //> res3: scala.collection.immutable.Stream[SumProblem.Path] = Stream(5 + 11 + | |
| //| 7 = 23, ?) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment