Interview Question

interview.jl

using PyPlot
using Base.Test

function minops{T<:Integer}(n::T)
  queue = (T,T)[]
  push!(queue, (n,0))
  visited = Set{T}()
  pops,evals = 0,0
  while true
    pops += 1
    val,depth = shift!(queue)
    val in visited && continue
    evals += 1

    # Subtract one
    val-1 == 1 && return depth+1
    push!(queue, (val-1,depth+1))

    # Divide by two
    if val%2 == 0
      div(val,2) == 1 && return depth+1
      push!(queue, (div(val,2),depth+1))
    end

    # Divide by three
    if val%3 == 0
      div(val,3) == 1 && return depth+1
      push!(queue, (div(val,3),depth+1))
    end

    # Don't duplicate the above work
    push!(visited, val)
  end
end

function minops_rev{T<:Integer}(n::T)
  queue = (T,T)[]
  push!(queue, (1,0))
  visited = Set{T}()
  evals = 0
  while true
    val,depth = shift!(queue)
    evals += 0
    val in visited && continue

    # Add one
    val+1 == n && return depth+1
    push!(queue, (val+1,depth+1))

    # Multiply by two
    if val*2 <= n
      val*2 == n && return depth+1
      push!(queue, (val*2,depth+1))
    end

    # Divide by three
    if val*3 <= n
      val*3 == 1 && return depth+1
      push!(queue, (val*3,depth+1))
    end

    # Don't duplicate the above work
    push!(visited, val)
  end
  @show evals
end

function minops_dp{T<:Integer}(n::T)
  solns = Array(T,n)
  solns[1] = 0
  for i=2:n
    solns[i] = 1 + solns[i-1]
    i%2 == 0 && (solns[i] = min(solns[i], 1 + solns[div(i,2)]))
    i%3 == 0 && (solns[i] = min(solns[i], 1 + solns[div(i,3)]))
  end
  return solns[n]
end

@test minops(5) == 3
@test minops(10) == 3

@test minops_rev(5) == 3
@test minops_rev(10) == 3

@test minops_dp(5) == 3
@test minops_dp(10) == 3

sizes = int(logspace(1,7,20))

loglog(sizes, [@elapsed minops(x) for x in sizes], label="BFS down")
loglog(sizes, [@elapsed minops_rev(x) for x in sizes], label="BFS up")
loglog(sizes, [@elapsed minops_dp(x) for x in sizes], label="DP")

xlabel("Starting positive integer n")
ylabel("Seconds")
title("Time to compute minimum number of operations to unity")
legend(loc="best")

@time minops(typemax(Int)-1)
@time minops(BigInt(2)^100-1)