ICFPC 2017 for both lightning and fuill

life.rb

#!/usr/bin/ruby

require 'json'

SERV = 'punter.inf.ed.ac.uk'
NAME = 'anago'

class Site
  attr_reader :id, :x, :y, :site
  attr_accessor :is_mine, :is_mine_connected, :value

  def initialize(id, x, y, site)
    @id = id
    @x = x
    @y = y
    @is_mine = false
    @site = site
    @value = 0
  end

  def clone
    s = Site.new(@id, @x, @y, @site)
    s.is_mine = @is_mine
    s.is_mine_connected = @is_mine_connected
    s.value = @value
    s
  end

  def is_my_mine
    @is_mine || @is_mine_connected
  end

end

class River
  attr_reader :st, :river
  attr_accessor :pid, :value, :add_value, :value_rank

  def initialize(s, t, river)
    @st = [s, t]
    @river = river
    @pid = nil
    @value = 0
  end

  def id
    @st
  end

  def clone
    r = River.new(@st[0], @st[1], @river)
    r.pid = @pid
    r.value = @value
    r
  end

  def another(s)
    if @st[0] == s
      @st[1]
    elsif @st[1] == s
      @st[0]
    else
      raise
    end
  end

end

class State
  attr_reader :pid, :npt, :done
  attr_reader :sites, :rivers, :mines, :futures
  attr_accessor :use_rand
  attr_accessor :mode

  def initialize
    @mode = :light
    @done = false
  end

  def has_mine(river)
    @sites[river.st[0]].is_mine || @sites[river.st[1]].is_mine
  end

  def clone(o)
    @pid = o.pid
    @npt = o.npt
    @done = o.done

    @sites = {}
    o.sites.each do |_, site|
      @sites[site.id] = site.clone
    end

    @rivers = {}
    o.rivers.each do |_, river|
      @rivers[river.id] = river.clone
    end

    @mines = o.mines.dup

    @futures = o.futures.dup

    self
  end

  def setup(setup)
    @pid = setup['punter']
    @npt = setup['punters']
    map = setup['map']

    if setup['futures']
      set_futures(setup['futures'])
    end

    @sites = {}
    map['sites'].each do |site|
      id = site['id'].to_i
      x = site['x'].to_f
      y = site['y'].to_f
      @sites[id] = Site.new(id, x, y, site)
    end

    @rivers = {}
    map['rivers'].each do |river|
      s = river['source'].to_i
      t = river['target'].to_i
      @rivers[[s,t]] = River.new(s, t, river)
    end

    @mines = []
    map['mines'].each do |mine|
      @mines << mine
      @sites[mine].is_mine = true
    end

    STDERR.puts "pid=#{@pid} npt=#{@npt} sites=#{@sites.size} rivers=#{@rivers.size} mines=#{@mines.size}"
  end

  def set_futures(futures)
    @futures = {}
    futures.each do |future|
      @futures[future['source']] = future['target']
    end
  end

  def search_paths(from, pid)
    scores = []
    queue = [[from, 0]]
    until queue.empty?
      sid, distance = queue.shift
      next if scores[sid]
      scores[sid] = distance
      @site_to_rivers[sid].each do |river|
        next if pid && river.pid != pid
        nsid = river.another(sid)
        queue.push([nsid, distance + 1])
      end
    end
    scores
  end

  def construct_score_map
    return if @score_map

    @site_to_rivers = []
    @rivers.each do |st, river|
      @site_to_rivers[st[0]] = [] if !@site_to_rivers[st[0]]
      @site_to_rivers[st[0]] << river
      @site_to_rivers[st[1]] = [] if !@site_to_rivers[st[1]]
      @site_to_rivers[st[1]] << river
    end

    @score_map = {}
    @mines.each do |mine|
      @score_map[mine] = search_paths(mine, nil)
    end

    seen = {}
    q = @mines.dup
    until q.empty?
      sid = q.shift
      next if seen[sid]
      seen[sid] = true
      @sites[sid].is_mine_connected = true

      @site_to_rivers[sid].each do |river|
        if river.pid == @pid
          q.push river.another(sid)
        end
      end
    end
  end

  def calc_score_impl(pid, futures)
    construct_score_map
    score = 0
    fscore = 0
    if futures
      futures.each do |mine, to|
        len = @score_map[mine][to]
        fscore -= len ** 3
      end
    end
    @mines.each do |mine|
      search_paths(mine, pid).each_with_index do |d, to|
        if d
          len = @score_map[mine][to]
          score += len ** 2
          if futures && futures[mine] == to
            fscore += len ** 3 * 2
          end
        end
      end
    end
    [score, fscore]
  end

  def calc_score(pid)
    score, fscore = calc_score_impl(pid, pid == @pid ? @futures : nil)
    score + fscore
  end

  def handle_claim(claim)
    pid = claim['punter']
    raise "What? #{claim.inspect}" if !pid
    s = claim['source']
    raise "What? #{claim.inspect}" if !s
    t = claim['target']
    raise "What? #{claim.inspect}" if !t

    pid = pid.to_i
    s = s.to_i
    t = t.to_i
    raise 'Broken!' if @rivers[[s, t]].pid
    @rivers[[s, t]].pid = pid
  end

  def handle_splurge(claim)
    pid = claim['punter']
    raise "What? #{claim.inspect}" if !pid
    r = claim['route']
    raise "What? #{claim.inspect}" if !t

    pid = pid.to_i
    (r.size-1).times{|i|
      s = r[i].to_i
      t = r[i+1].to_i
      raise 'Broken!' if @rivers[[s, t]].pid
      @rivers[[s, t]].pid = pid
    }
  end

  def handle_moves(m)
    return if m['timeout']
    moves = if m['stop']
              @done = true
              @scores = m['stop']['scores']
              m['stop']['moves']
            elsif m['move']
              m['move']['moves']
            else
              raise if !m['moves']
              m['moves']
            end
    moves.each do |move|
      if claim = move['claim']
        handle_claim(claim)
      elsif claim = move['option']
        handle_claim(claim)
      elsif claim = move['splurge']
        handle_splurge(claim)
      elsif move['pass']
      else
        raise "What? #{move.inspect}"
      end
    end
  end

  def search_cost(source, target)
    construct_score_map
    seen = {}
    cost_queue = [[0, source]]
    best_cost = @rivers.size
    until cost_queue.empty?
      cost, sid = cost_queue.shift
      if sid == target
        best_cost = cost
        break
      end
      next if seen[sid]
      seen[sid] = cost

      @site_to_rivers[sid].each do |river|
        nid = river.another(sid)
        if river.pid == @pid
          cost_queue.unshift [cost, nid]
        elsif !river.pid
          cost_queue << [cost + 1, nid]
        end
      end
      #cost_queue.sort!
    end

    best_cost
  end

  def calc_future_cost
    if !@futures
      return 0
    end

    total_cost = 0
    @futures.each do |source, target|
      cost = search_cost(source, target)
      #STDERR.puts "cost #{source}=>#{target}: #{cost}" if @pid == 0
      total_cost += cost
    end
    total_cost
  end

  def choose(pid)
    if @mode == :head
      return choose_conn(pid)
    elsif @mode == :value
      return choose_impl(pid, false, true)
    elsif @mode == :prefer_choice
      return choose_impl(pid, true)
    else
      return choose_impl(pid)
    end
  end

  def gen_cost_map(source, pid)
    cost_queue = [[0, [source]]]
    seen_pats = {}
    until cost_queue.empty?
      cost, route = cost_queue.shift
      sid = route[-1]
      if seen_pats[sid]
        seen_pats[sid][1] += route.size
        next
      end
      seen_pats[sid] = [cost, 0, route]

      @site_to_rivers[sid].each do |river|
        nid = river.another(sid)
        nr = route.dup
        nr << nid
        if river.pid == pid
          cost_queue.unshift [cost, nr]
        elsif !river.pid
          cost_queue << [cost + 1, nr]
        end
      end
    end
    seen_pats
  end

  def get_river(s1, s2)
    @rivers[[s1,s2]] || @rivers[[s2,s1]] || (
      raise "hmm #{s1} #{s2}"
    )
  end

  def choose_conn(pid)
    construct_score_map

    best_cost_map = nil
    best_pair = nil
    best_cp = [1e100, 0]
    @mines.each do |mine|
      cost_map = gen_cost_map(mine, pid)
      @mines.each do |m2|
        next if mine == m2 || !cost_map[m2]
        cp = cost_map[m2]
        cp[1] = -cp[1]
        if best_cp[0] > best_cp[1].size
          best_cp = cp
          best_cost_map = cost_map
          best_pair = [mine, m2]
        end
      end
    end

    if !best_cost_map || best_cp[0] == 0
      STDERR.puts "fall back to normal mode"
      return choose_impl(pid)
    end

    route = best_cp[2]
    cands = []
    (route.size-1).times do |i|
      river = get_river(route[i], route[i+1])
      if river.pid
        raise "xxx" if river.pid != pid
        next
      end
      cands << river
    end

    choose_impl_cands(pid, cands)
  end

  def choose_impl(pid, prefer_choice=false, use_value=false)
    construct_score_map

    if use_value
      estimate_value
    end

    cands = []
    @rivers.each do |_, river|
      if !river.pid
        score = 0
        river.st.each do |f|
          if @sites[f].is_mine
            score += 1000
          end
          @site_to_rivers[f].each do |r|
            if r.pid == pid
              score += 200
            end
          end
          if @futures && @futures[f]
            score += 10000
          end
        end
        cands << [score, river]
      end
    end
    cands = cands.sort_by{|s,_|-s}.map{|_, cand|cand}

    choose_impl_cands(pid, cands, prefer_choice, use_value)
  end

  def choose_impl_cands(pid, cands, prefer_choice=false, use_value=false)
    start_time = Time.now

    best_river = nil
    best_score = -1e100
    cands.each do |river|
      if Time.now - start_time > 0.9
        STDERR.puts "timeout!"
        break
      end

      raise if river.pid
      river.pid = pid

      score = calc_score(pid) * 100.0
      #STDERR.puts "#{river.st}" if @pid == 0
      score -= calc_future_cost * 10000.0

      if use_value
        score += Math.sqrt(river.value)
      end

      river.st.each do |sid|
        if @sites[sid].is_mine
          score += 1000.0
        elsif (prefer_choice && @sites[sid].is_my_mine &&
               !@sites[river.st.another(sid)].is_my_mine)
          score += 11.0 * @sites[river.st.another(sid)].rivers.size
        end
      end

      @mines.each do |mine|
        river.st.each do |v|
          d = @score_map[mine][v]
          # TODO: really?
          next if !d
          score += 300.0 / (d + 1)
        end
      end

      if best_score < score
        best_score = score
        best_river = river
      end
      river.pid = nil
    end
    [best_river, best_score]
  end

  def decide_move
    start_time = Time.now
    chosen, best_score = choose(@pid)
    elapsed = Time.now - start_time
    if elapsed > 0.5
      STDERR.puts "*** SLOW!!!!! ***"
    end
    STDERR.puts "best_score=#{best_score} elapsed=#{elapsed}"

    #chosen = cands[rand(cands.size)]

    {
      'claim' => {
        'punter' => @pid,
        'source' => chosen.st[0],
        'target' => chosen.st[1],
      }
    }
  end

  def myrand(*n)
    if @use_rand
      rand(*n)
    else
      0
    end
  end

  def decide_futures
    construct_score_map

    if @mode == :head
      return nil
    end

    num_moves = @rivers.size / @npt
    #future_len = num_moves / 4
    future_len = Math.sqrt(num_moves)
    if future_len < 2
      future_len = 2
    end

    STDERR.puts "future_len=#{future_len}"

    best_pair = nil
    best_score = 1e100
    @mines.each do |m1|
      @mines.each do |m2|
        next if m1 == m2
        len = @score_map[m1][m2]
        #STDERR.puts "m1=#{m1} m2=#{m2} len=#{len}"
        score = (len - future_len) ** 2 + myrand * future_len
        if best_score > score
          best_score = score
          best_pair = [m1, m2]
        end
      end
    end

    return [] if !best_pair

    futures = []
    [best_pair, best_pair.reverse].each do |m1, m2|
      best_target = nil
      best_score = 1e100
      @site_to_rivers[m2].each do |river|
        m3 = river.another(m2)
        next if @sites[m3].is_mine
        len = @score_map[m1][m3]
        score = (len - future_len) ** 2
        if best_score > score
          best_score = score
          best_target = m3
        end

      end

      if best_target
        STDERR.puts "future: #{m1}=>#{best_target} #{@score_map[m1][best_target]}"
        futures << {
          "source" => m1,
          "target" => best_target,
        }
      end
    end

    set_futures(futures)

    futures
  end

  def summary(futures=nil)
    scores = []
    @npt.times do |pid|
      f = if futures
            futures[pid]
          else
            pid == @pid ? @futures : nil
          end
      score, fscore = calc_score_impl(pid, f)
      ss = ''
      if f
        ss = "#{score+fscore}(#{fscore})"
      else
        ss = "#{score+fscore}"
      end
      if pid == @pid
        ss = "*#{ss}"
      end
      scores << ss
    end
    scores * ' '
  end

  def usable_rivers_from(sid)
    r = []
    @site_to_rivers[sid].each do |river|
      if !river.pid || river.pid == @pid
        r << river
      end
    end
  end

  def estimate_value_step
    total_mine_value = 0
    @mines.each do |mine|
      site = @sites[mine]
    #@sites.each do |_, site|
      total_mine_value += site.value
      rivers = usable_rivers_from(site.id)
      next if rivers.empty?
      value = site.value / rivers.size
      rivers.each do |river|
        river.value += value
      end
    end

    @rivers.each do |_, river|
      river.add_value = 0
    end

    @rivers.each do |_, river|
      value = river.value / 2
      river.st.each do |sid|
        #nrs = @site_to_rivers[sid]
        nrs = usable_rivers_from(sid)
        next if nrs.empty?
        v = value / nrs.size
        nrs.each do |nr|
          nr.add_value += v
        end
      end
    end

    total_add_value = 0
    @rivers.each do |_, river|
      total_add_value += river.add_value
    end

    @rivers.each do |_, river|
      river.value += river.add_value / total_add_value * total_mine_value * 0.5
      river.add_value = 0
    end

  end

  def estimate_value_init
    construct_score_map
    @rivers.each do |_, river|
      river.value = 0
    end

    # @sites.each do |_, site|
    #   site.value = @site_to_rivers[site.id].size ** 2 * 10
    # end

    @mines.each do |mine|
      v = 0
      @sites.each do |_, site|
        v += @score_map[mine][site.id] if @score_map[mine][site.id]
      end
      site = @sites[mine]
      site.value += v.to_f
      STDERR.puts "mine: #{site.value} x=#{site.x} y=#{site.y}"
    end
  end

  def estimate_value
    estimate_value_init
    @rivers.size.times{
      estimate_value_step
    }
  end

end

class Visualizer
  attr_accessor :show_value

  def initialize(st)
    require 'sdl'

    xs = []
    ys = []
    st.sites.each do |_, site|
      xs << site.x
      ys << site.y
    end
    @min_x = xs.min
    @max_x = xs.max
    @min_y = ys.min
    @max_y = ys.max

    SDL.init(SDL::INIT_VIDEO)

    @w = 1000
    @h = 1000
    @scr = SDL.set_video_mode(@w, @h, 32, SDL::SWSURFACE)
  end

  def show(st)
    conv_x = proc{|x|
      (x - @min_x) * (@w - 40) / (@max_x - @min_x) + 20
    }
    conv_y = proc{|y|
      (y - @min_y) * (@h - 40) / (@max_y - @min_y) + 20
    }

    st.futures.each do |s, t|
      color = [255,255,0]
      @scr.draw_line(conv_x[st.sites[s].x]+2,
                     conv_y[st.sites[s].y]+2,
                     conv_x[st.sites[t].x]+2,
                     conv_y[st.sites[t].y]+2,
                     color)
    end if st.futures

    if @show_value
      values = []
      st.rivers.each do |_, river|
        values << [river.value, river]
      end
      #p values.map{|v,_|v}
      values = values.sort_by{|v,_|v}.reverse

      values.each_with_index do |vr, i|
        vr[1].value_rank = i
      end
    end


    st.rivers.each do |_, river|
      s, t = river.st
      color = if river.pid == st.pid
                [0,255,0]
              elsif river.pid
                v = river.pid / st.npt.to_f
                [v*255,0,(1-v)*255]
              else
                [255,255,255]
              end

      if @show_value
        if river.value_rank.to_f < 10
          STDERR.puts "river rank: #{river.value_rank} #{river.value}"
          v = river.value_rank.to_f / 3
          color = [(1-v)*255, 128+v*127, 0]
        else
          v = river.value_rank.to_f / st.rivers.size
          color = [(1-v)*255, 0, v*255]
        end
      end

      @scr.draw_line(conv_x[st.sites[s].x],
                     conv_y[st.sites[s].y],
                     conv_x[st.sites[t].x],
                     conv_y[st.sites[t].y],
                     color)
    end

    st.sites.each do |_, site|
      color = site.is_mine ? [255,0,0] : [255,255,255]
      @scr.draw_circle(conv_x[site.x], conv_y[site.y], 3, color)
    end

    @scr.flip
  end

end

def send_impl(fd, j)
  j = JSON.dump(j)
  STDERR.puts "=> #{j} =>"
  msg = "#{j.size}:#{j}"
  fd.print msg
  fd.flush
end

def recv_impl(fd)
  r = ''
  loop {
    c = fd.getc
    break if c == ':'
    r += c
  }
  j = fd.read(r.to_i)
  STDERR.puts "<= #{j} <="
  JSON.load(j)
end

def handshake(send, recv)
  send[{'me' => NAME}]
  r = recv[]
  if r['you'] != NAME
    raise "What? #{r}"
  end
end

def wait_key
  while true
    ev = SDL::Event2.wait
    case ev
    when SDL::Event2::KeyDown
      case ev.sym
      when SDL::Key::ESCAPE
        exit
      end
      break
    end
  end
end

if ARGV[0] =~ /\.json$/
  map_to_npt = {}
  %w(sample).each{|n|map_to_npt[n] = 2}
  %w(Sierpinski-triangle).each{|n|map_to_npt[n] = 3}
  %w(lambda circle randomMedium randomSparse).each{|n|map_to_npt[n] = 4}
  %w(boston-sparse tube).each{|n|map_to_npt[n] = 8}
  %w(edinburgh-sparse nara-sparse oxford-sparse gothenburg-sparse).each{|n|
    map_to_npt[n] = 16
  }
  name = File.basename($`)
  npt = map_to_npt[name]
  map = JSON.parse(File.read(ARGV[0]))

  states = []
  npt.times do |pid|
    state = State.new
    if pid != 0
      state.mode = :light
    end
    state.use_rand = true
    setup = {
      'punter' => pid,
      'punters' => npt,
      'map' => map,
    }
    state.setup(setup)
    state.decide_futures
    states << state
  end

  viz = Visualizer.new(states[0])

  if ARGV[1] == 'value'
    state = states[0]
    state.estimate_value_init

    viz.show_value = true
    viz.show(state)
    wait_key

    state.rivers.size.times do |t|
      STDERR.puts "#{t}/#{state.rivers.size}"
      state.estimate_value_step
      viz.show(state)
      wait_key
    end
    exit
  end

  pid = 0
  states[0].rivers.size.times do |turn|
    river, best_score = states[pid].choose(pid)

    states.each do |st|
      st.rivers[river.st].pid = pid
    end

    futures = {}
    states.each do |st|
      futures[st.pid] = st.futures
    end
    STDERR.puts states[pid].summary(futures)
    viz.show(states[0])

    wait_key

    pid = (pid + 1) % states[0].npt
  end

elsif !ARGV[0]
  send = proc {|j| send_impl(STDOUT, j) }
  recv = proc { recv_impl(STDIN) }
  handshake(send, recv)

  msg = recv[]
  if msg['map']
    state = State.new
    state.setup(msg)

    settings = msg['settings']
    if settings && settings['futures']
      futures = state.decide_futures
    end

    msg['moves'] = []
    msg.delete('state')
    msg['futures'] = futures if futures
    reply = {
      'ready' => state.pid,
      'state' => msg,
    }
    reply['futures'] = futures if futures
    send[reply]
  elsif msg['stop']
    # nothing to do.
  else
    state_msg = msg['state']
    state = State.new
    state.setup(state_msg)
    state.handle_moves(state_msg)
    state.handle_moves(msg)

    move = state.decide_move
    state_msg['moves'] += msg['move']['moves']

    state_msg.delete('state')
    reply = move
    reply['state'] = state_msg
    send[reply]
  end

elsif ARGV[0] =~ /^\d+$/
  require 'socket'
  sock = TCPSocket.new(SERV, ARGV[0].to_i)
  send = proc {|j| send_impl(sock, j) }
  recv = proc { recv_impl(sock) }
  handshake(send, recv)

  setup = recv[]
  state = State.new
  state.setup(setup)

  settings = setup['settings']
  if settings && settings['futures']
    futures = state.decide_futures
  end
  msg = {'ready' => state.pid}
  msg['futures'] = futures if futures
  send[msg]

  move = nil
  loop {
    STDERR.puts state.summary
    moves = recv[]
    state.handle_moves(moves)
    if state.done
      break
    end
    move = state.decide_move
    send[move]
  }

  state.handle_claim(move['claim'])
  STDERR.puts state.summary

elsif ARGV[0]
  lines = File.readlines(ARGV[0])

  states = []
  state = nil
  last_claim = nil
  lines.each do |line|
    j = if line =~ /^(<=|=>)(.*)\1/ || line =~ /^(<=|=>)(.*)$/
          JSON.load($2)
        end
    next if !j

    req = $1 == '=>'

    if j['ready'] && j['futures']
      state.set_futures(j['futures'])
    elsif j['map']
      state = State.new
      state.setup(j)
      states.push(state)
    elsif j['claim']
      last_claim = j['claim']
    elsif (j['move'] || j['stop']) && !req
      nstate = State.new
      nstate.clone(state)
      nstate.handle_moves(j)
      if j['stop']
        if last_claim
          nstate.handle_claim(last_claim)
        end
      end
      state = nstate
      states.push(state)
    end
  end

  viz = Visualizer.new(states[0])
  n = 0
  was_down = false
  state_changed = true

  while true
    st = states[n]
    if state_changed
      state_changed = false
      summary = st.summary
      STDERR.puts "#{n}/#{states.size}"
      STDERR.puts summary
    end

    viz.show(st)

    ev = SDL::Event2.wait
    case ev
    when SDL::Event2::Quit
      exit
    when SDL::Event2::KeyDown
      if !was_down
        was_down = true
        case ev.sym
        when SDL::Key::N
          n += 1
          if states[n]
            state_changed = true
          else
            n -= 1
          end
        when SDL::Key::P
          n -= 1
          if n >= 0
            state_changed = true
          else
            n += 1
          end
        when SDL::Key::ESCAPE
          exit
        end
      end
    when SDL::Event2::KeyUp
      was_down = false
    end
  end

end

Fix...

Index: life.rb
===================================================================
--- life.rb     (revision 9508)
+++ life.rb     (working copy)
@@ -231,6 +231,7 @@
     pid = pid.to_i
     s = s.to_i
     t = t.to_i
+    s, t = t, s if !@rivers[[s, t]]
     raise 'Broken!' if @rivers[[s, t]].pid
     @rivers[[s, t]].pid = pid
   end
@@ -245,6 +246,7 @@
     (r.size-1).times{|i|
       s = r[i].to_i
       t = r[i+1].to_i
+      s, t = t, s if !@rivers[[s, t]]
       raise 'Broken!' if @rivers[[s, t]].pid
       @rivers[[s, t]].pid = pid
     }