Activating project at `~/Documents/julia/TowerOfHanoi`Experimenting with Julia
I’ve always loved the Towers of Hanoi ever since I was introduced to it as a kid by chance. I thought it would be perfect to write a solver using Julia to learn it. This is my first project using Julia and I found it enjoyable. I’m still learning the ropes so to speak. For future projects, I would like to stick to a more strict functional style of programming for the solvers and use the naming convention of using “!” postfix to denote stateful functions.
Julia initially picqued my interest with its take on types, multiple dispatch, and no objects. It forces you away from generic types which can make for more readable code. The typing system gets you thinking about the problem differently and how you can use types to better document intent without relying on problematic “if” statements. The packaging system, REPL, and jupyter integration make developing and trying out packages easy. There is a learning curve and some frustrations with how code is loaded that gets in the way of development initially. But, nothing a Google search can’t fix. All part of learning something new and a different take on programming.
The lack of encapsulation is worrisome for large projects. I have the same issue with Python, but documentation and a few team guidelines help. It’s always good to have strict enforcement though. Minimizing mutable state structures and documenting the functions that mutate to use goes a long way. All in all a minor quibble.
Overall, I enjoyed coding in Julia and plan to implement more projects with it. The type system is the intriguing piece and I did some experiements in the code to try to push my understanding. Look at the implementation of moves in the domain for an example. This was a quick weekend project and comments are minimal. There are several emergent design patterns in Julia that I would love to explore as well like the Holy Trait Pattern and work more through the excellent “Hands on Design Patterns and Best Practices with Julia” book.
If you would like to follow along, I have provided the source for the domain along with the tests. I implemented two solvers and provided the source for the naive version and the A* with heurstic version.
Naive
A sample run with 4 discs is shown below. Keep scrolling for the A* version.
Moves to solve: 79
***
*****
*******
*********
heurstic value: 16
Move from 1 to 3
*****
*******
********* ***
heurstic value: 14
Move from 3 to 2
*****
*******
********* ***
heurstic value: 14
Move from 1 to 3
*******
********* *** *****
heurstic value: 14
Move from 2 to 3
******* ***
********* *****
heurstic value: 16
Move from 3 to 1
***
*******
********* *****
heurstic value: 15
Move from 3 to 2
***
*******
********* *****
heurstic value: 15
Move from 1 to 3
*******
********* ***** ***
heurstic value: 14
Move from 3 to 2
******* ***
********* *****
heurstic value: 16
Move from 1 to 3
***
********* ***** *******
heurstic value: 18
Move from 2 to 3
***
********* ***** *******
heurstic value: 18
Move from 3 to 1
***
********* ***** *******
heurstic value: 16
Move from 2 to 3
*** *****
********* *******
heurstic value: 18
Move from 1 to 3
***
*****
********* *******
heurstic value: 22
Move from 3 to 2
*****
********* *** *******
heurstic value: 18
Move from 3 to 1
*****
********* *** *******
heurstic value: 15
Move from 2 to 3
***** ***
********* *******
heurstic value: 17
Move from 3 to 1
***
*****
********* *******
heurstic value: 16
Move from 3 to 2
***
*****
********* *******
heurstic value: 16
Move from 1 to 3
*****
********* ******* ***
heurstic value: 15
Move from 3 to 2
***** ***
********* *******
heurstic value: 17
Move from 1 to 3
***
********* ******* *****
heurstic value: 18
Move from 2 to 3
***
********* ******* *****
heurstic value: 18
Move from 3 to 1
***
********* ******* *****
heurstic value: 16
Move from 3 to 2
*** *****
********* *******
heurstic value: 18
Move from 1 to 3
*****
********* ******* ***
heurstic value: 18
Move from 3 to 2
***
*****
********* *******
heurstic value: 22
Move from 1 to 3
***
*****
******* *********
heurstic value: 26
Move from 2 to 3
***** ***
******* *********
heurstic value: 24
Move from 3 to 1
*****
*** ******* *********
heurstic value: 21
Move from 2 to 3
*****
*** ******* *********
heurstic value: 21
Move from 1 to 3
***
*****
******* *********
heurstic value: 26
Move from 3 to 2
*** *****
******* *********
heurstic value: 24
Move from 3 to 1
***
***** ******* *********
heurstic value: 20
Move from 2 to 3
***
***** ******* *********
heurstic value: 20
Move from 3 to 1
***
***** ******* *********
heurstic value: 18
Move from 2 to 3
*** *******
***** *********
heurstic value: 20
Move from 1 to 3
***
*******
***** *********
heurstic value: 24
Move from 3 to 2
*******
***** *** *********
heurstic value: 20
Move from 1 to 3
*****
*******
*** *********
heurstic value: 26
Move from 2 to 3
***
*****
*******
*********
heurstic value: 32
Move from 3 to 1
*****
*******
*** *********
heurstic value: 25
Move from 3 to 2
*******
*** ***** *********
heurstic value: 21
Move from 1 to 3
***
*******
***** *********
heurstic value: 26
Move from 3 to 2
*** *******
***** *********
heurstic value: 24
Move from 3 to 1
***
******* ***** *********
heurstic value: 19
Move from 2 to 3
***
******* ***** *********
heurstic value: 19
Move from 3 to 1
***
******* ***** *********
heurstic value: 17
Move from 2 to 3
*** *****
******* *********
heurstic value: 19
Move from 1 to 3
***
*****
******* *********
heurstic value: 23
Move from 3 to 2
*****
******* *** *********
heurstic value: 19
Move from 3 to 1
*****
******* *** *********
heurstic value: 16
Move from 2 to 3
***** ***
******* *********
heurstic value: 18
Move from 3 to 1
***
*****
******* *********
heurstic value: 17
Move from 3 to 2
***
*****
******* *********
heurstic value: 17
Move from 1 to 3
*****
******* ********* ***
heurstic value: 16
Move from 3 to 2
***** ***
******* *********
heurstic value: 18
Move from 1 to 3
***
******* ********* *****
heurstic value: 19
Move from 2 to 3
***
******* ********* *****
heurstic value: 19
Move from 3 to 1
***
******* ********* *****
heurstic value: 17
Move from 3 to 2
*** *****
******* *********
heurstic value: 19
Move from 1 to 3
*****
******* ********* ***
heurstic value: 19
Move from 3 to 2
***
*****
******* *********
heurstic value: 23
Move from 1 to 3
***
*****
********* *******
heurstic value: 26
Move from 2 to 3
***** ***
********* *******
heurstic value: 24
Move from 3 to 1
*****
*** ********* *******
heurstic value: 21
Move from 2 to 3
*****
*** ********* *******
heurstic value: 21
Move from 1 to 3
***
*****
********* *******
heurstic value: 26
Move from 3 to 2
*** *****
********* *******
heurstic value: 24
Move from 3 to 1
***
***** ********* *******
heurstic value: 20
Move from 2 to 3
***
***** ********* *******
heurstic value: 20
Move from 3 to 1
***
***** ********* *******
heurstic value: 18
Move from 3 to 2
*** *******
***** *********
heurstic value: 20
Move from 1 to 3
*******
***** ********* ***
heurstic value: 20
Move from 3 to 2
***
*******
***** *********
heurstic value: 24
Move from 1 to 3
***
*******
********* *****
heurstic value: 26
Move from 2 to 3
******* ***
********* *****
heurstic value: 24
Move from 3 to 1
*******
*** ********* *****
heurstic value: 21
Move from 3 to 2
*****
*******
*** *********
heurstic value: 25
Move from 1 to 2
final:
***
*****
*******
*********
A* Heuristic
I implemented the A* algorigithm and used the following heurstic function:
function heuristic(initial::Tower, state::Tower)
disc_cache = Dict()
for (r, rod) in enumerate(initial.rods)
for (d, disc) in enumerate(rod.discs)
disc_cache[disc]=(r,d)
end
end
num_discs = length(disc_cache)
result = 0
for (r, rod) in enumerate(state.rods)
for (d, disc) in enumerate(rod.discs)
(ir, id) = disc_cache[disc]
rod_diff = abs(ir - r) > 0 ? 2 : 1
disc_diff = num_discs - abs(id - d)
result += rod_diff * disc_diff
end
end
result
endIt simply sums how many discs are not in the goal state from the given intial. Thus, a higher score is closer to the goal and the A* algorithm maximizes search for it.
A sample run with 4 discs is shown below.
The naive solver took 79 moves and the A* solver took 21 moves. A huge improvement in finding the solution. This was a great project to learn the basics of Julia.
Number of moves: 21
***
*****
*******
*********
heurstic value: 16
Move from 1 to 2
*****
*******
********* ***
heurstic value: 14
Move from 2 to 3
*****
*******
********* ***
heurstic value: 14
Move from 1 to 2
*******
********* ***** ***
heurstic value: 14
Move from 3 to 2
******* ***
********* *****
heurstic value: 16
Move from 1 to 3
***
********* ***** *******
heurstic value: 18
Move from 2 to 3
***
********* ***** *******
heurstic value: 18
Move from 3 to 1
***
********* ***** *******
heurstic value: 16
Move from 2 to 3
*** *****
********* *******
heurstic value: 18
Move from 1 to 3
***
*****
********* *******
heurstic value: 22
Move from 1 to 2
***
*****
********* *******
heurstic value: 26
Move from 3 to 2
*** *****
********* *******
heurstic value: 24
Move from 3 to 1
***
***** ********* *******
heurstic value: 20
Move from 2 to 3
***
***** ********* *******
heurstic value: 20
Move from 3 to 1
***
***** ********* *******
heurstic value: 18
Move from 3 to 2
*** *******
***** *********
heurstic value: 20
Move from 1 to 2
***
*******
***** *********
heurstic value: 24
Move from 1 to 3
***
*******
********* *****
heurstic value: 26
Move from 2 to 3
******* ***
********* *****
heurstic value: 24
Move from 3 to 1
*******
*** ********* *****
heurstic value: 21
Move from 3 to 2
*****
*******
*** *********
heurstic value: 25
Move from 1 to 2
***
*****
*******
*********