サルベジオン問題の参考プログラムです。

solve.rb

#! /usr/bin/ruby

require 'open-uri'

SLEEP_SEC = 1

API_URL = "http://salvageon.textfile.org/"

def puts_output(db, index)
  output = URI("#{API_URL}?db=#{db}&index=#{index}").read
  puts output
  sleep(SLEEP_SEC)

  h = nil
  if output == '?'
    h = {
      :output => output
    }
  else
    if output.match(/^(\d+) (\d+) (\S+) (\S+) (\d+)/)
      h = {
        :output => output,
        :db => $1.to_i,
        :index => $2.to_i,
        :key => $3,
        :value => $4,
        :size => $5.to_i,
      }
    else
      abort(%Q(Invalid output = "#{output}"))
    end
  end
  h
end

def puts_many(db, start_index, count)
  count.times do |k|
    puts_output(db, start_index + k)
  end
end

def search_linear(db, search_key)
  index = 0
  count = 1
  loop do
    print "\##{count}: "
    h = puts_output(db, index)
    if h[:key] == search_key
      puts "Found! key = #{h[:key]}, value = #{h[:value]}"
      return
    end
    index += 1
    if h[:size] <= index
      puts "Not found..."
      return
    end
    count += 1
  end
end

def search_binary(db, search_key)
  count = 1
  index = 0
  print "#{count}: "
  h = puts_output(db, index)
  count += 1
  size = h[:size]
  left = 0
  right = size
  loop do
    index = (left + right) / 2
    print "#{count}: "
    h = puts_output(db, index)
    search_key_i = search_key.sub(/K/, "").to_i
    key_i = h[:key].sub(/K/, "").to_i
    case key_i <=> search_key_i
    when 0
      puts "Found! key = #{h[:key]}, value = #{h[:value]}"
      return
    when 1
      right = index
    when -1
      left = index + 1
    end
    count += 1
    if right <= left
      puts "Not found... key = #{h[:key]}"
      return
    end
  end
end

def search_heap(db, search_key)
  count = 1
  index = 1
  loop do
    print "#{count}: "
    h = puts_output(db, index)
    size = h[:size]
    search_key_i = search_key.sub(/K/, "").to_i
    key_i = h[:key].sub(/K/, "").to_i
    if size <= index
      puts "Invalid search_key. size=#{size}, index = #{index}"
      return
    end
    case key_i <=> search_key_i
    when 0
      puts "Found! key = #{h[:key]}, value = #{h[:value]}"
      return
    when 1
      index = index * 2
    when -1
      index = index * 2 + 1
    end
    count += 1
  end
end

puts
puts "== DB1 first 5 =="
puts_many(1, 0, 5)

puts
puts "== DB1 last 5 =="
puts_many(1, 1267650600228229401496703205376 - 5, 5)

puts
puts "== DB2 first 10 =="
puts_many(2, 0, 10)

puts
puts "== DB1 binary search =="
search_binary(1, "K208050656559285601386927895421059705239114932023754")

puts
puts "== DB2 binary search with heap =="
search_heap(2, "K2023636070998557444542586045")