CodeHew 2016 (Qualification Round)

_README.md

Writeup: https://www.facebook.com/notes/thai-pangsakulyanont/%E0%B8%9A%E0%B8%B1%E0%B8%99%E0%B8%97%E0%B8%B6%E0%B8%81%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%81%E0%B8%82%E0%B9%88%E0%B8%87%E0%B8%82%E0%B8%B1%E0%B8%99-codehew-2016-%E0%B8%A3%E0%B8%AD%E0%B8%9A%E0%B8%84%E0%B8%B1%E0%B8%94%E0%B9%80%E0%B8%A5%E0%B8%B7%E0%B8%AD%E0%B8%81%E0%B8%AD%E0%B8%AD%E0%B8%99%E0%B9%84%E0%B8%A5%E0%B8%99%E0%B9%8C/10153771619659088

day1_problem1_tooeasy.rb

puts gets.to_i.times.map { gets.to_i }.map { |n| n % 3 == 0 || n % 7 == 0 ? "hard" : "t#{'o' * n} easy" }

day1_problem2_deal.rb

# utility
class NewDate < Struct.new(:year, :month, :date)
  def day_count
    [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31][month - 1] + (year % 4 == 0 ? 1 : 0)
  end
  def succ
    return next_month if date == day_count
    NewDate.new(year, month, date + 1)
  end
  def next_year
    NewDate.new(year + 1, 1, 1)
  end
  def next_month
    return next_year if month == 12
    NewDate.new(year, month + 1, 1)
  end
  def diff other
    current = self
    count = 1
    while current != other; count += 1; current = current.succ; end
    count
  end
end

# unit test
raise unless NewDate.new(3000, 01, 01).succ == NewDate.new(3000, 01, 02)
raise unless NewDate.new(3000, 01, 31).succ == NewDate.new(3000, 01, 32)
raise unless NewDate.new(3000, 01, 32).succ == NewDate.new(3000, 02, 01)
raise unless NewDate.new(3000, 12, 32).succ == NewDate.new(3001, 01, 01)
raise unless NewDate.new(3001, 01, 31).succ == NewDate.new(3001, 02, 01)
raise unless NewDate.new(3001, 02, 28).succ == NewDate.new(3001, 03, 01)

# main logic
puts gets.to_i.times
.map { gets.split.map(&:to_i) }
.map { |a, b, c, d, e, f| [NewDate.new(a, b, c), NewDate.new(d, e, f)]}
.map { |x, y| x.diff y }

day1_problem3_influencer.rb

require 'set'
gets.to_i.times do
  m, n = gets.split.map(&:to_i)
  sets = m.times.map { Set[*gets.split.map(&:to_i)[0..-2]] }
  puts (1..m).find { |c| sets.combination(c).any? { |a| a.reduce(&:|).length == n } }
end

day2_problem1_review.rb

def cont? x, y
  if x.is_a? Range
    y == x.end + 1
  else
    y == x + 1
  end
end

def succ x, y
  if x.is_a? Range
    (x.begin..y)
  else
    (x..y)
  end
end

gets.to_i.times do
  data = gets.split[1..-1].map(&:to_i).sort
  out = [ ]
  data.each do |x|
    if out.length > 0 && cont?(out[-1], x)
      out[-1] = succ(out[-1], x)
    else
      out << x
    end
  end
  puts out.map { |x| x.is_a?(Range) ? "#{x.begin}->#{x.end}" : x }.join(',')
end

day2_problem1_review2_refactored.rb

# NOTE: Refactored version
#       Uses Array#reduce instead of imperative code and
#       always use a Range in the reduction array.

def cont? x, y
  y == x.end + 1
end

def succ x, y
  (x.begin..y)
end

gets.to_i.times do
  data = gets.split[1..-1].map(&:to_i).sort
  out = data.reduce [ ] do |a, x|
    if !a.empty? && cont?(a.last, x)
      [*a[0...-1], succ(a.last, x)]
    else
      [*a, x..x]
    end
  end
  puts out.map { |x| x.size > 1 ? "#{x.begin}->#{x.end}" : x.begin }.join(',')
end

day2_problem2_startup.rb

require 'set'

teams_count, employees_count = gets.split.map(&:to_i)
links = { }
teams_count.times do
  gets.to_i.times do
    a, _, *bs = gets.split.map(&:to_i)
    bs.each do |b|
      (links[a] ||= Set.new) << b
    end
  end
end

def bfs links, a, b
  fringe = [ a ]
  length = { a => -1 }
  visited = Set[a]
  until fringe.empty?
    front = fringe.shift
    next unless links[front]
    links[front].each do |t|
      next if visited.include?(t)
      visited << t
      fringe << t
      length[t] = length[front] + 1
    end
  end
  raise if length[b] == -1
  length[b]
end

gets.to_i.times do
  a, b = gets.split.map(&:to_i)
  r = bfs(links, a, b)
  if r.nil?
    puts "no"
  else
    puts r
  end
end

day2_problem2_startup2_with_rgl.rb

# NOTE: Refactored version
#       Uses RGL so that I don't have to write the graph algorithms myself.

require 'rgl/adjacency'
require 'rgl/traversal'

teams_count, _ = gets.split.map(&:to_i)
graph = RGL::DirectedAdjacencyGraph[]
teams_count.times do
  gets.to_i.times do
    a, _, *bs = gets.split.map(&:to_i)
    bs.each { |b| graph.add_edge(a, b) }
  end
end

gets.to_i.times do
  a, b = gets.split.map(&:to_i)
  bfs = graph.bfs_iterator(a).attach_distance_map
  if bfs.include?(b)
    puts bfs.distance_to_root(b) - 2
  else
    puts "no"
  end
end

day2_problem3_interstellar.rb

class Knapsack
  def initialize(values, weights, max_weight)
    @values, @weights = values, weights
    @max_weight = max_weight
    @cache = { }
  end
  def max_value
    max_value_given(@values.length - 1, @max_weight)
  end
  def max_value_given(choice_index, max_weight)
    @cache[[choice_index, max_weight]] ||= begin
      return 0 if choice_index < 0
      choices = [ ]
      weight = @weights[choice_index]
      if weight <= max_weight
        choices << max_value_given(choice_index - 1, max_weight - weight) + @values[choice_index]
      end
      choices << max_value_given(choice_index - 1, max_weight)
      choices.max
    end
  end
end

gets.to_i.times do
  n, l = gets.split.map(&:to_i)
  people = gets.split.map(&:to_i)
  delay = gets.split.map(&:to_i)
  overhead = n + 1
  max_weight = l - overhead
  c = Knapsack.new(people, delay, max_weight)
  p c.max_value
end