```Christer Nilsson wrote:
> Simon wrote:
>
>
>>Hello dear quizzers,
>>
>>could someone please confirm (or disprove) that this i correct?
>>
>
>
> my subproblem solution to (868056,651040) gave the same result as your,
> in 76 secs.
>
> I investigated the ideas suggested by Ilmari and Greg, but found that
> there is no way of knowing if the result is optimal. The result are
> impressing, but misses often trivial cases. It seems as hard to patch
> the non optimal solution as it is to solve it normally.
>
> Are you using a different approach?
>
> Christer

Oops, sorry i kind of 'lost' this thread..

My approach isn't that different but a little bit more optimized.
I use strings instead of hashs (or arrays like you do) to store the
information (and i only store which operation leads us there, ?X is
an empty field, ?M - multiply, ?D - divide, ?A - add, ?S - sub). I
need ?S (Sub 2) because search is done from both sides.

Well, here it is, it solves the the subproblem in 0.062s.

---------------------------------------------------------------------

require 'set'

def find_path from, to
pathf = ''.ljust([from + 2, to + 2].max * 2, 'X')
pathb = pathf.dup
pathf[from] = ?F
pathb[to] = ?F

forward, backward, newbees = [from], [to], []

loop do
forward.each do |n|
pathf[newbees.push(n + 2).last] = ?S if pathf[n+2] == ?X
pathf[newbees.push(n + n).last] = ?D if pathf[n+n] == ?X
pathf[newbees.push(n / 2).last] = ?M if (n%2) == 0 && pathf[n/2]
== ?X
end
forward, newbees = newbees, []
forward.each {|n|return pathf, pathb, n if pathb[n]  != ?X}

backward.each do |n|
pathb[newbees.push(n - 2).last] = ?A if n > 1 && pathb[n-2] == ?X
pathb[newbees.push(n + n).last] = ?D if pathb[n+n] == ?X
pathb[newbees.push(n / 2).last] = ?M if (n % 2) == 0 &&
pathb[n/2] == ?X
end
backward, newbees = newbees, []
backward.each {|n|return pathf, pathb, n if pathf[n]  != ?X}
end
end

def solve from, to
return nil if from < 0 || to <= 0
return [from] if from == to
pathf, pathb, n = find_path(from, to)

result = [n]
[pathf, pathb].each do |path|
loop do
case path[result.last]
when ?A then result << result.last + 2
when ?S then result << result.last - 2
when ?D then result << result.last / 2
when ?M then result << result.last * 2
else break
end
end
result.reverse!
end
result.reverse
end

from, to = (ARGV.shift || 868056).to_i, (ARGV.shift || 651040).to_i

t = Time.now
p solve(from, to)
puts "Time: #{Time.now - t}"

---------------------------------------------------------------------

cheers

Simon

```