# Utility functions
def intersect(line0, line1)
  def aux(line0,line1)
    a,b = line0[0]
    c,d = line0[1]
    e,f = b-d,c-a
    p0x,p0y = line1[0][0]-a, line1[0][1]-b
    p1x,p1y = line1[1][0]-a, line1[1][1]-b

    (e*p0x+f*p0y)*(e*p1x+f*p1y) < 0.0
  end

  aux(line0,line1) && aux(line1,line0)
end

def i2r_x(i)
  @bounds[0][0] + i*@grid_width + @delta
end

def i2r_y(i)
  @bounds[1][0] + i*@grid_width + @delta
end

def grid_to_cartesian(p)
  [i2r_x(p[0]), i2r_y(p[1])]
end

def reducible?(p0,p1)
  line = [grid_to_cartesian(p0), grid_to_cartesian(p1)]
  @boards.each do |board|
    return false if intersect(line, board)
  end

  true
end

def reduce(src)
  r = []
  loop do
    if src.length < 3
      r << src[0]
      r << src[1]
      break
    else
      if reducible?(src[0],src[2])
        src.delete_at(1)
      else
        r << src.shift
      end
    end
  end

  r
end

def make_taboo(grid_n)
  def template(grid_n, type, r)
    (grid_n-type).times do |j|
      (grid_n-(1-type)).times do |i|
        p0,p1 = type == 0 ? [[i,j],[i+1,j]] : [[i,j],[i,j+1]]
        line0 = [grid_to_cartesian(p0),grid_to_cartesian(p1)]
        @boards.each do |line1|
          if intersect(line0, line1)
            r[p0] ||= []
            r[p1] ||= []
            r[p0] << p1
            r[p1] << p0
          end
        end
      end
    end
  end
  r = {}
  template(grid_n, 0, r)
  template(grid_n, 1, r)

  r
end

def make_taboo_fast(grid_n)
  def w2g_x(r)
    (r - @bounds[0][0] - @delta) / @grid_width
  end
  def w2g_y(r)
    (r - @bounds[1][0] - @delta) / @grid_width
  end
  def cartesian_to_grid(p0)
    [w2g_x(p0[0]), w2g_y(p0[1])]
  end
  def line_to_coverrange(line)
    x0,y0 = cartesian_to_grid(line[0])
    x1,y1 = cartesian_to_grid(line[1])
    x_min,x_max = [x0,x1].minmax
    y_min,y_max = [y0,y1].minmax
    [[x_min.floor, x_max.ceil],[y_min.floor, y_max.ceil]]
  end
  def add(r,p0,p1)
    r[p0] ||= []
    r[p1] ||= []
    r[p0] << p1
    r[p1] << p0
  end
  r = {}
  @boards.each do |b|
    line = [cartesian_to_grid(b[0]), cartesian_to_grid(b[1])]
    x_range,y_range = line_to_coverrange(b)
    xd = line[1][0]-line[0][0]
    yd = line[1][1]-line[0][1]

    if xd != 0.0
      i = x_range[0] + 1
      i = 0 if i < 0
      while i < x_range[1]
        y_f = yd * (i.to_f-line[0][0]) / xd + line[0][1]
        y = y_f.floor
        add(r,[i,y],[i,y+1])
        i += 1
      end
    end

    if yd != 0.0
      i = y_range[0] + 1
      i = 0 if i < 0
      while i < y_range[1]
        x_f = xd * (i.to_f-line[0][1]) / yd + line[0][0]
        x = x_f.floor
        add(r,[x,i],[x+1,i])
        i += 1
      end
    end
  end

  r
end

# Search on Grid (Beam Search) Definition
class Search
  def initialize(grid_n, taboo, start_pos, target_pos)
    @grid_n = grid_n
    @taboo = taboo
    @start_pos, @target_pos = start_pos, target_pos
    @has_answer = false
    @answer = nil
  end
  def h(pos)
    # Manhattan distance
    (@target_pos[0]-pos[0]).abs+(@target_pos[1]-pos[1]).abs
  end
  def successors(pos)
    r = []
    [[1,0],[0,1],[-1,0],[0,-1]].each do |d|
      i,j = pos[0]+d[0], pos[1]+d[1]
      next unless 0 <= i && i < @grid_n && 0 <= j && j < @grid_n
      succ = [i,j]
      r << succ unless @taboo[pos] && @taboo[pos].include?(succ)
    end

    r
  end
  def calc(beamwidth)
    states = [@start_pos]
    history = {}
    tmp = []
    loop do
      break unless 0 < states.length

      states.each do |cur_pos|
        succs = []
        successors(cur_pos).each do |succ|
          if succ == @target_pos
            result = [@target_pos, cur_pos]
            pos = cur_pos
            while prev_pos = history[pos]
              result << prev_pos
              break if prev_pos == @start_pos
              pos = prev_pos
            end
            return [true, result.reverse]
          end
          unless history[succ]
            history[succ] = cur_pos
            succs << [h(succ), succ]
          end
        end
        tmp.concat(succs)
      end

      tmp.sort!
      states.clear

      n = [tmp.length, beamwidth].min
      n.times do |i|
        states << tmp[i][1]
      end

      tmp.clear
    end

    [false, nil]
  end
end

# Simulated Anealing Definition
class SimulatedAnealing
  def initialize(energy_func, neighbour_func, temparature_func, probablity_func)
    @energy = energy_func # state -> float(energy)
    @neighbour = neighbour_func # state -> state
    @temparature = temparature_func # float(progress degree) -> float(temparature)
    @probability = probablity_func # float(energy_src) -> float(energy_dst) -> temparature -> float(probablity)
  end
  def calc(start_state, max_iter, goal_energy)
    state = start_state
    e = @energy.call(state)
    best_state = state
    best_e = e
    max_iter.times do |iter|
      next_state = @neighbour.call(state)
      next_e = @energy.call(next_state)
      if next_e <= best_e
        best_state = next_state
        best_e = next_e
        if best_e <= goal_energy
          return best_state
        end
      end

      t = @temparature.call(iter.to_f / max_iter)
      prob = @probability.call(e, next_e, t)
      if Random.rand <= prob
        state = next_state
        e = next_e
      end
    end

    best_state
  end
end

# Setting functions
def set_boards(n) # parallel zigzag pattern
  dy = (@bounds[1][1] - @bounds[1][0]) / (n+1)

  n.times do |i|
    y0 = @bounds[1][0]
    yval = y0+dy*(i+1)
    board =
      if i%2 == 0
        [[0.0, yval], [0.66, yval]]
      else
        [[0.33, yval], [1.0, yval]]
      end
    @boards << board
  end
end

def set_boards2(n) # diagonal zigzag pattern
  def add(delta,width,x,y)
    p0 = [x*width-delta, y*width+delta]
    p1 = [(x+1)*width+delta, (y-1)*width-delta]
    @boards << [p0, p1]
  end
  delta = 0.00001
  width = 1.0 / (n-1)

  (2..(2*(n-2))).each do |k|
    iter_num = k < n ? k : (2*(n-1)-k)
    pass_index0 = Random.rand(iter_num)
    pass_index1 = Random.rand(iter_num)
    iter_num.times do |i|
      next if i == pass_index0 || i == pass_index1
      x,y = k < n ? [i,k-i] : [k-n+1+i,n-1-i]
      add(delta,width,x,y)
    end
  end
end

def set_boards3(k)
  def add(d,w,sx,sy,x0,y0,x1,y1)
    if y0 == y1
      #horizontal
      x0,x1,y0,y1 = x1,x0,y1,y0 if x1 < x0
    else
      #vertical
      x0,x1,y0,y1 = x1,x0,y1,y0 if y1 < y0
    end
    p0 = [sx+x0*w-d, sy+y0*w-d]
    p1 = [sx+x1*w+d, sy+y1*w+d]
    p2 = [sx+x0*w-d, sy+y0*w+d]
    p3 = [sx+x1*w+d, sy+y1*w-d]
    @boards << [p0, p1]
    @boards << [p2, p3]
  end
  def sub(delta, max_width, sx, sy, n)
    width = max_width / (n-1)

    (n-2).times do |j|
      (n-2).times do |i|
        dir_i = Random.rand(j == 0 ? 4 : 3)
        dx,dy = [[-1,0],[0,1],[1,0],[0,-1]][dir_i]
        x0,y0 = i+1,j+1
        x1,y1 = x0+dx,y0+dy
        add(delta,width,sx,sy,x0,y0,x1,y1)
      end
    end
  end
  delta = 0.00001
  sub(delta, 1.0, 0.0, 0.0, k)
end

# Main functions
def grid_search(grid_n, taboo, beam_width)
  n = grid_n
  start_pos = [0,0]
  end_pos = [n-1,n-1]

  Search.new(n, taboo, start_pos, end_pos).calc(beam_width)
end

def make_sa_params
  grid_n = @grid_n
  e_func = lambda{|state|
    state.length.to_f
  }
  n_func = lambda{|state|
    return state if state.length < 3
    i = 1 + Random.rand(state.length-2)
    np = state[i]
    x,y = np

    100.times do
      nx,ny = Random.rand(grid_n), Random.rand(grid_n)
      if 0 <= nx && nx < grid_n && 0 <= ny && ny < grid_n
        tp = [nx,ny]
        if reducible?(state[i-1], tp) && reducible?(tp, state[i+1])
          np = tp
          break
        end
      end
    end

    new_state = state.dup
    new_state[i] = np

    if 0 <= i-2 && reducible?(new_state[i-2], np)
      new_state.delete_at(i-1)
      i -= 1
    end
    if i+2 < new_state.length && reducible?(np, new_state[i+2])
      new_state.delete_at(i+1)
    end

    new_state
  }
  t_func = lambda{|progress|
    a = 0.3
    Math.exp(progress*Math.log(a))
  }
  p_func = lambda{|e0,e1,t|
    if e0 >= e1
      1.0
    else
      k = 1.0
      Math.exp((e0-e1) / (k*t))
    end
  }
  max_iter = 1000
  goal_e = 0.0

  [e_func, n_func, t_func, p_func, max_iter, goal_e]
end

def reduce_by_sa(init_state)
  energy,neighbour,temparature,probability,max_iter,goal_e = make_sa_params
  sa = SimulatedAnealing.new(energy, neighbour, temparature, probability)

  sa.calc(init_state, max_iter, goal_e)
end

def display_answer(answer)
  puts answer.length
  puts answer.map{|e| "%.3f %.3f" % e}
end

def output_json(seed, prof, boards, intermediate, answer)
  require 'json'
  puts JSON.pretty_generate({"seed" => seed}.merge(prof.merge({"answer" => answer, "intermediate" => intermediate, "boards" => boards})))
end

def prof_exec(result, id_name, &f)
  start_time = Time.now
  f.call
  t = Time.now - start_time
  result[id_name] = t
end

# Run
@bounds = [[0.0,1.0],[0.0,1.0]]
@boards = []
@delta = 0.0001
@grid_n = 132
@grid_width = (1.0-@delta*2)/(@grid_n-1)

seed = Random.rand(1000)
seed = 13
prof = {}
taboo,found,route,reduced,final_state = nil,nil,nil,nil,nil

srand(seed)

prof_exec(prof, "set_boards") do
  set_boards2(6)
  set_boards3(31)
end

prof_exec(prof, "make_taboo") do
  taboo = make_taboo_fast(@grid_n)
end

prof_exec(prof, "grid_search") do
  found, route = grid_search(@grid_n, taboo, 1000)
end

unless found
  output_json(seed,prof,@boards,[],[])
  exit
end

prof_exec(prof, "reduce_greedy") do
  reduced = reduce(route)
end

prof_exec(prof, "reduce_by_sa") do
  final_state = []
  final_state = reduce_by_sa(reduced)
end

output_json(seed,
            prof,
            @boards,
            reduced.map{|e| grid_to_cartesian(e)},
            final_state.map{|e| grid_to_cartesian(e)})
#display_answer(final_state.map{|e| grid_to_cartesian(e)})