My son came home from school with the following riddle, or rather a math puzzle:
Let’s slay a monster. Here are the rules:
– The monster has 3 heads and 3 tails.
– You have a SWORD and you can choose between these actions:
1. Slash off ONE HEAD. Result: one head will grow back.
2. Slash off TWO HEADS. Result: monster will loose two heads!
3. Slash off ONE TAIL. Result: TWO tails will grow back.
4. Slash off TWO TAILS. Result: one head will grow back.
Can you slay the monster, and in how many swings?
So first let’s envision what we are looking at 😉
Wow, that’s terrible. And I don’t even mean the monster. Let’s forget the drawing skills.. leave the copy and paste skills aside as well… maybe it’s better to just give an indication of the monster by telling how many heads and tails it has, like this:
3H3T -> a monster with 3 Heads(H) and 3 Tails(T).
So what will happen if we just try to do any of the four possible sword-moves? Let’s just start off ambitious, with slashing off TWO HEADS. Slash!
1H3T -> monster with 1 head and 3 tails.
Fine, two heads down. Ok, now 2 Tails. Slash!
2H1T -> monster with 2 heads and 1 tail.
Hey? What happened? Yeah two Tails down but one head has grown back because of the two tails.. ouch… Ok, let’s slash off those two heads:
0H1T
Good, just one tail left to slash off, Slash! this results in:
0H2T
What? Ah, when you slash off one tail, two grow back. Fine! Ok, the final two Tails! SLASH! And we’ve got:
1H0T
One head grows back!! Oh wait, this is not good. A one-headed monster.. that’s.. that’s invincible! If we slash off this one head, it grows back immediately… let’s try anyway. Slash!
1H0T
Oh no.. Ouch… something went wrong in our strategy. Can we do better? We should never end up with a one-headed monster, that’s for sure, as that one headed monster is totally invincible. There are no tails left to change the outcome.. we should have started off differently!
A different approach?
What would be the strategy as a developer? We should first think this through a bit more. We could of course first just figure out what moves result in what outcomes. We have four different moves, and after doing any of those, we again have four possible moves, for that particular outcome.
Well, four? Not really. The move to slash off one head is quite useless as we just saw. That one head immediately grows back so we are left with only three possible different moves, as in different outcomes for each of those three moves. Only three moves actually change the dragon in a way that leads is to new possibilities. We could draw that out as a tree of possible moves, and write some program to figure out how many swings we actually need. Neat!
Let’s just try drawing that out, first. We’ll draw a tree on its side with branches branching off to the right.
When we just write 2H for slashing two heads, 1T and 2T for slashing either 1 or 2 tails, we can draw a ‘tree of possibilities’, from the start, like this:
|-> 2H?-> X
-> 2H -> 1H3T +-> 1T -> 1H4T
| |-> 2T -> 2H3T
|
| |-> 2H -> 1H4T
3H3T +-> 1T -> 3H4T +-> 1T -> 3H5T
| |-> 2T -> 4H2T
|
| |-> 2H -> 2H3T
|-> 2T -> 4H3T +-> 1T -> 4H4T
|-> 2T -> 5H1T
Lots of different outcomes. From a monster with 1 Head and 4 tails at the top to a monster with 5 Heads and 1 Tail at the bottom, and all kinds of monsters in between. You can imagine that with each next slash of our sword, the tree can grow to the right, extending every outcome with new branches only where possible, of course! It turns out that certain moves are actually not possible at all in certain stages. Like above, when we end up with only 1 head and 3 tails at the top. We can’t chop off 2 heads anymore. So, that’s one end of a branch of the tree, so to speak. There’s no other outcome at that branch to be searched any deeper, and as the monster is not slain there yet, we do not have to search any further on that branch! And looking at the other outcomes, we do not really get much closer to the wanted outcome of 0 Heads and 0 Tails, at least not yet.
Developers lifestyle questions
How far should we search?
Is there a possible outcome?
Yes, my son says the teacher has guaranteed there is a solution. That’s good to know.
Instead of doing this by hand, can we write a program to try this out for us, so that we do not have to administer the whole search tree by hand?
The answer is a given of course: Yes.
Computers are perfect for these kind of tracking tasks. In this case, we are actually drawing out, or building, a search-tree. That’s not all too difficult. Each step in the search leads to an outcome, and each outcome has a few possible follow-up ‘moves’. It looks a bit like game search-trees. Although in this case there are no opponents, just a few different possible types of moves.
So how to put this in a language? Let’s start defining moves, and the monster with its heads and tails. The monster will also keep track of the moves we’ve tried. In GoLang, this looks as follows.
type TryMove int32
const (
ONE_HEAD TryMove = 0
TWO_HEADS TryMove = 1
ONE_TAIL TryMove = 2
TWO_TAILS TryMove = 3
)
var Move_name = map[TryMove]string{
ONE_HEAD: "ONE_HEAD",
TWO_HEADS: "TWO_HEADS",
ONE_TAIL: "ONE_TAIL",
TWO_TAILS: "TWO_TAILS",
}
// Monster holds the number of heads and tails
type Monster struct {
heads int
tails int
trackmoves []TryMove // array of tried moves
}
Now we do not know really how many times we have to slash, so we setup a loop that tries to a certain maximum of moves. This is just to kick off the actual building of the search-tree.
limit := 20
func main() {
fmt.Println("start.")
for maxturns := 1; maxturns < limit; maxturns++ {
fmt.Println("Maxturns depth", maxturns)
beast := NewMonster()
*beast = slayMonster(*beast, 0, maxturns)
if beast.Death() {
// we're done :)
fmt.Println("Yes! We slayed the monster!")
beast.PrintMoves(maxturns)
break // break out of the loop
}
}
}
The above loop just tries to ‘slayMonster’, first by doing it in just 1 turn, than 2, both which will not succeed, but it is just doing kind of iterative deepening, which in this case means making the tree of possible moves larger until we find a solution. The solution is found when the beast is ‘death’, in code, this is just the result of one of the small helper functions:
// The helper functions.
// NewMonster gives you a new monster,
// initialized with 3 heads and 3 tails
func NewMonster() *Monster {
m := new(Monster)
m.heads = 3
m.tails = 3
m.trackmoves = make([]TryMove, 12)
return m
}
// print the object to console
func (m *Monster) showMonster() {
fmt.Printf("%+v", m)
}
// Death returns success when the monster has no heads or tails
func (m *Monster) Death() bool {
if m.heads == 0 && m.tails == 0 {
return true
}
return false
}
// MonsterWins when it has become invincible
func (m *Monster) MonsterWins() bool {
if m.heads == 1 && m.tails == 0 {
return true
}
return false
}
All the above was just definition, or rather, preparation, for the actual search.
Now the trick is in the slayMonster recursive function, below, which just loops over all possible moves on a certain ‘node of the tree (link: tree-traversal)‘, takes the outcome of that, and tries all possible moves again. This method is broadening the tree of possibilities, like if it is drawing out the entire tree of possibilities:
func slayMonster(m Monster, turns int, maxturns int) Monster {
// each recursive function needs a stopcondition, in our case
// this is when we reached the end of the search-tree (turns>maxturns), or if the monster has won or the monster is dead:
if turns > maxturns || m.MonsterWins() || m.Death() {
// we either did not succeed in the amount of time allotted,
// or we lost, or we won. Either way we are at the end of our tries:
return m
}
for idx, _ := range Move_name {
beast := m // copy the beast for this try
beast.ExecuteMove(idx, turns)
result := slayMonster(beast, turns+1, maxturns)
if result.Death() {
return result // just return, no need to try the other moves
}
}
return m
}
The not-shown ExecuteMove method, just keeps track of the move that is currently being executed. It stores the move in the array that was defined the monster.
When running the program, you’ll find it takes surprisingly way more than six slashes(!) to kill this monster! If you want to know how to do it, you can download and run the MonsterSlash program at github. . And you might be surprised to see it finds the solution incredibly fast.
The funny thing is that we can use the computer for all kinds of search problems. Especially when the search-space is limited, as in, not too many possible different moves to try out, in other words a small branching factor, the computer is incredibly quick in finding a solution. I’ll write another blog-post soon with the same technique, but just for a different question.
Oh by the way: My son found the answer much quicker than me. As he just kept trying on paper. And used his mind. That just shows that using your brain can still be much quicker than trying to translate a puzzle to a machine, which than looks like a ‘quick answer from the machine’ 😉
More on searchtrees, click the blog category searchtree to see other related posts on search or recursion.