As with so many of our Ruby Q. problems, this is another pathfinding

challenge. We’re probably pretty use to seeing that pruning of the

search space

is usually a big win in these cases and this problem is no exception.

Let’s

talk a little about exactly why that is the case.

When you think about the operations allowed by this quiz, one thing that

becomes

obvious is that n * 2 and n / 2 are opposites. If you do one and then

the

other, you end up right back at the number you had before you applied

any

operations. That kind of busy work isn’t helpful. In fact, visiting

any number

a second time is pointless since we’ve already seen an equal or faster

path for

the same thing.

There’s a lot more duplication in the problem than the opposite

operations too.

Let’s start working 2 to 9 by hand, so we can see that:

```
2
2, 4 (double)
2, 4, 8 (double)
2, 4, 8, 16 (double)
2, 4, 8, 4 (halve)
2, 4, 8, 10 (add two)
2, 4, 2 (halve)
2, 4, 2, 4 (double)
2, 4, 2, 1 (halve)
2, 4, 2, 4 (add two)
2, 4, 6 (add two)
2, 4, 6, 12 (double)
2, 4, 6, 3 (halve)
2, 4, 6, 8 (add two)
2, 1 (halve)
2, 1, 2 (double)
2, 4, 2, 4 (double)
2, 4, 2, 1 (halve)
2, 4, 2, 4 (add two)
2, 1, 3 (add two)
2, 4, 3, 6 (double)
2, 4, 3, 5 (add two)
2, 4 (add two)
2, 4, 8 (double)
2, 4, 8, 16 (double)
2, 4, 8, 4 (halve)
2, 4, 8, 10 (add two)
2, 4, 2 (halve)
2, 4, 2, 4 (double)
2, 4, 2, 1 (halve)
2, 4, 2, 4 (add two)
2, 4, 6 (add two)
2, 4, 6, 12 (double)
2, 4, 6, 3 (halve)
2, 4, 6, 8 (add two)
```

There’s a lot of paths already and we’re not there yet. Let’s look at

the exact

same tree, but with one simple rule of pruning applied: We can toss out

any

operation that results in a number we have already seen. Watch how that

changes

things:

```
2
2, 4 (double)
2, 4, 8 (double)
2, 4, 8, 16 (double)
2, 4, 8, 10 (add two)
2, 4, 6 (add two)
2, 4, 6, 12 (double)
2, 4, 6, 3 (halve)
2, 1 (halve)
2, 1, 3 (add two)
2, 4, 3, 5 (add two)
```

Those two trees go to the same depth and both represent the same set of

numbers.

However, the second one is over three times less work. Imagine how much

we can

save as the numbers keep growing and growing.

Another important optimization involves limits. Even with our simple 2

to 9

example, we can be up to 64 after only five operations (2, 4, 8, 16, 32,

64).

64 is a long way from 9 and probably not helping us get there. We can

limit

upper and lower bounds for the numbers, or even by limiting the steps

the path

can take. (Florian Pflug made a great post in the quiz thread about the

latter.) The only thing to be careful of with an optimization like this

is that

you make sure you don’t impose a limit low enough to prevent an optimal

solution.

Many other optimizations were used. Some, like storing instance data in

Integer

objects, have that questionable code smell and are probably best

avoided. Other

solutions, while super fast on huge inputs, did not produce the shortest

path in

all cases. Finally, many optimizations involve timing various elements

of Ruby

syntax for minor increases here and there, but that’s more detail than

we need

to go into in this summary. Given that, let’s examine a nice solution,

by

Tristan Allwood, using the two optimizations described above:

```
require 'set'
class MazeSolver
def solve start, finish
visited = Set.new
tul, tll = if start > finish
[(start << 1) + 4, nil]
else
[(finish << 1) + 4, nil]
end
solve_it [[start]], finish, visited, tul, tll
end
def solve_it lpos, target, visited, tul, tll
n = []
lpos.each do |vs|
v = vs.last
next if tul and v > tul
next if tll and v < tll
return vs if v == target
d = v << 1 # double
h = v >> 1 unless (v & 1) == 1 # half
p2 = v + 2 # plus 2
n << (vs.clone << d) if visited.add? d
n << (vs.clone << h) if h and visited.add? h
n << (vs.clone << p2) if visited.add? p2
end
return solve_it(n, target, visited,tul, tll)
end
end
if __FILE__ == $0
puts MazeSolver.new.solve(ARGV[0].to_i, ARGV[1].to_i).join(" ")
end
```

Tristan’s solution makes use of bit operations, because they tend to be

faster

than multiplication and division. All you need to know about these is

that n <<

1 == n * 2 and n >> 1 == n / 2.

The primary interface method for the code above is solve(). It takes

the start

and finish numbers. As you can see, it sets up a visited Set object to

keep

track of the numbers we’ve seen, assigns upper and lower limits, then

hands off

to solve_it().

In solve_it(), each path of numbers is walked and expanded by the three

operations. Note the calls to visited.add?() before new paths are

added. This

is the optimization keeping us from revisiting numbers. The next if tul

and v >

tul line skips to the next iteration if we’ve passed the upper limit.

That’s

the other big optimization. After another level of paths have been

added,

solve_it() just recurses to find the next set of operations. This only

ever

goes as deep as there are steps in the solution, so there’s not much

danger of

overrunning the stack for problems we can reasonably solve.

The final if statement of the program triggers the process from the two

parameters passed to the program.

My thanks to the many, many participants that generated great solutions

and

discussion, especially all you new guys! I also need to thank the quiz

creator

who was very involved in the discussion and gave me a bunch of tips for

this

summary.

Tomorrow, we have a dice rolling challenge for all you RPG players out

there…