DevCon Code Challenge Cup Solutions

team_x_prob_a.rb

def trunc(x)
  (x * 100.0).floor / 100.0
end

output = File.open("bestfit2.txt", "w")

count, point_count, points, = nil, nil, nil

IO.readlines("bestfit.txt").each do |line|

  if count.nil?
    count = line.strip.to_i
  elsif point_count.nil?
    point_count = line.strip.to_i
    points = []
  else
    points << line.strip.split.map { |d| d.to_f }
    point_count -= 1
  end

  if point_count == 0

    # perform simple linear regression 
    # see http://en.wikipedia.org/wiki/Simple_linear_regression#Numerical_example   
    sum_x = points.map { |d| d[0] }.reduce(:+)
    sum_y = points.map { |d| d[1] }.reduce(:+)
    sum_xx = points.map { |d| d[0] * d[0] }.reduce(:+)
    sum_xy = points.map { |d| d[0] * d[1] }.reduce(:+)
    sum_yy = points.map { |d| d[1] * d[1] }.reduce(:+)
    n = points.size.to_f

    a = (n * sum_xy - sum_x * sum_y) / (n * sum_xx - sum_x * sum_x)
    b = (sum_y / n) - (a * sum_x / n)

    output.puts "#{trunc(a)} #{trunc(b)}"

    count -= 1
    point_count, points = nil, nil
  end

  break if count == 0
end

team_x_prob_b.rb

output = File.open("ripley2.txt", "w")

count, alphabet, word_count, words = nil, nil, nil, nil

IO.readlines("ripley.txt").each do |line|

  if count.nil?
    count = line.strip.to_i
  elsif alphabet.nil?
    alphabet = line.strip
  elsif word_count.nil?
    word_count = line.strip.to_i
    words = []
  else
    words << line.strip
    word_count -= 1
  end

  if word_count == 0
    translation_table = Hash[*alphabet.split(//).zip('A'..'Z').flatten]
    word_pairs = words.map do |word|
      # convert to ripley alphabet
      [word, word.split(//).map { |c| translation_table[c] }.join]
    end

    word_pairs.sort_by { |pair| pair[1] }.each { |pair| output.puts pair[0] }

    output.puts("*")

    count -= 1
    alphabet, word_count, words = nil, nil, nil
  end

  break if count == 0
end

team_x_prob_c.rb

output = File.open("leon2.txt", "w")

count, edge_count, edges, districts = nil, nil, nil, nil

IO.readlines("leon.txt").each do |line|

  if count.nil?
    count = line.strip.to_i
  elsif edge_count.nil?
    edge_count = line.strip.to_i
    edges, districts = [], []
  else
    edges << line.strip.split
    districts += line.strip.split
    edge_count -= 1
  end

  if edge_count == 0

    districts.uniq!

    major = []
    districts.each do |excluded|
      new_edges = edges.reject { |pair| pair[0] == excluded or pair[1] == excluded }
      map = (districts - [excluded]).reduce({}) do |hash, district|
        hash[district] = hash.size
        hash
      end
      dist_count = districts.count - 1

      # Warshall's Algorithm
      # http://en.wikipedia.org/wiki/Stephen_Warshall#Warshall.27s_algorithm
      adj_mat = Array.new(dist_count) { Array.new(dist_count) { false } }
      new_edges.each do |pair|
        adj_mat[map[pair[0]]][map[pair[1]]] = true
        adj_mat[map[pair[1]]][map[pair[0]]] = true
      end

      (0...dist_count).each do |k|
        (0...dist_count).each do |i|
          (0...dist_count).each do |j|
            adj_mat[i][j] = (adj_mat[i][j] or (adj_mat[i][k] and adj_mat[k][j]))
          end
        end
      end
      major << excluded if adj_mat.flatten.include?(false)
    end
    if major.empty?
      output.puts "None"
    else
      major.sort.each { |district| output.puts district }
    end
    
    output.puts "*"

    count -= 1
    edge_count, edges, districts = nil, nil, nil
  end

  break if count == 0
end

team_x_prob_d.rb

def has_islands?(map)
  map.flatten.include?("*")
end

def find_island_tip(map)
  map.each_with_index do |row, row_id|
    return row_id, row.index("*") if row.include? "*"
  end
end

def delete_island(row, col, map)
  map[row][col] = "~"
  if col > 0
    delete_island(row, col - 1, map) if map[row][col - 1] == "*"
  end
  if col < map[0].size - 1
    delete_island(row, col + 1, map) if map[row][col + 1] == "*"
  end
  if row > 0
    delete_island(row - 1, col, map) if map[row - 1][col] == "*"
  end
  if row < map.size - 1
    delete_island(row + 1, col, map) if map[row + 1][col] == "*"
  end
end

output = File.open("island2.txt", "w")

map = []
height, width = nil, nil
IO.readlines("island.txt").each do |line|
  if height.nil?
    height, width = line.strip.split.map { |x| x.to_i }
  elsif height != 0
    map << line.strip.split(//)
    height -= 1
  end

  if height == 0
    island_count = 0
    while has_islands?(map)
      island_count += 1
      row, col = find_island_tip(map)
      delete_island(row, col, map)
    end
    output.puts island_count
  end
end

team_x_prob_e.rb

output = File.open("basket2.txt", "w")
IO.readlines("basket.txt").each do |line|
  player, stats_str = line.strip.split
  stats = stats_str.split(//)
  output.puts "PLAYER #{player}"
  output.puts "Points #{stats.reduce(0) { |sum, x| sum + x.to_i }}"

  made1 = stats.count("1") 
  total1 = stats.count("0") + made1

  output.puts "     Freethrows    #{made1}/#{total1}  = #{(total1 == 0 ? 0 : (made1 * 100.0/total1).round)}%"

  made2 = stats.count("2")
  total2 = stats.count("X") + made2

  output.puts "     2-point shots #{made2}/#{total2}  = #{(total2 == 0 ? 0 : (made2 * 100.0/total2).round)}%"

  made3 = stats.count("3")
  total3 = stats.count("Y") + made3

  output.puts "     3-point shots #{made3}/#{total3}  = #{(total3 == 0 ? 0 : (made3 * 100.0/total3).round)}%"

  output.puts "Assists #{stats.count("A")}"
  output.puts "Rebounds #{stats.count("R")}"
  output.puts "Turnovers #{stats.count("T")}"
  output.puts ""
end

team_x_prob_f.rb

output = File.open("utility2.txt", "w")

count, data_count, data = nil, nil, nil

IO.readlines("utility.txt").each do |line|
  if count.nil?
    count = line.strip.to_i
  elsif data_count.nil?
    data_count = line.strip.to_i
    data = []
  elsif data_count > 0
    data << line.strip.split.map { |d| d.to_f }
    data_count -= 1
  else
    income = line.strip.to_i
    total_subst = data.map { |d| d[0] }.reduce(:+)
    data.each do |pair|
      output.puts (100.0 * pair[0] * income / (total_subst * pair[1])).floor / 100.0
    end
    output.puts "*"

    count -= 1
    data_count, data = nil, nil
  end
  break if count == 0
end

team_x_prob_g.rb

output = File.open("export2.txt", "w")

nodes = []
edges = {}
start, finish = nil, nil
IO.readlines("export.txt").each do |line|
  if start.nil?
    start, finish = line.strip.split
  else
    edge1, edge2, weight = line.strip.split
    nodes << edge1
    nodes << edge2

    edges[edge1] = {} if edges[edge1].nil?
    edges[edge1][edge2] = weight.to_f
    edges[edge2] = {} if edges[edge2].nil?
    edges[edge2][edge1] = weight.to_f
  end
end

nodes.uniq!

# Dijkstra's Algorithm http://en.wikipedia.org/wiki/Dijkstra's_algorithm
probability = Hash[*nodes.map { |n| [n, 0] }.flatten]
probability[start] = 1

visited = [start]
unvisited = nodes - visited

prev = {}
while visited.last != finish
  current = visited.last
  connected = edges[current]
  connected.each_pair do |target, weight|
    if unvisited.include?(target) and  probability[target] < probability[current] * weight
      probability[target] = probability[current] * weight
      prev[target] = current
    end
  end
  next_node = unvisited.sort_by { |node| probability[node] }.last
  visited << next_node
  unvisited.delete next_node
end

path = [finish]
current = finish
while current != start
  current = prev[current]
  path << current
end
path.reverse.each { |node| output.puts node }

team_x_prob_h.rb

def coprime_count(n)
  (1...n).count { |x| x.gcd(n) == 1 }
end

output = File.open("euler2.txt", "w")
IO.readlines("euler.txt").each do |line|
  output.puts( coprime_count(line.strip.to_i) )
end

team_x_prob_i.rb

output = File.open("jugs2.txt", "w")
IO.readlines("jugs.txt").each do |line|
  jug1, jug2, target = line.strip.split.map { |x| x.to_i }

  queue = [[0, 0]]
  idx = 0
  info = {}
  while target != 0
    current = queue[idx]
    # fill A
    unless queue.include? [jug1, current[1]]
      queue << [jug1, current[1]]
      info[([jug1, current[1]])] = { prev: current, action: "fill A" }
    end
    # fill B
    unless queue.include? [current[0], jug2]
      queue << [current[0], jug2]
      info[([current[0], jug2])] = { prev: current, action: "fill B" }
      break if jug2 == target
    end

    # empty A
    unless queue.include? [0, current[1]]
      queue << [0, current[1]]
      info[([0, current[1]])] = { prev: current, action: "empty A" }
    end
    # empty B
    unless queue.include? [current[0], 0]
      queue << [current[0], 0]
      info[([current[0], 0])] = { prev: current, action: "empty B" }
    end

    # pour A B
    pourAB = [0, current[0] + current[1]]
    pourAB = [pourAB[1] - jug2, jug2] if pourAB[1] > jug2

    unless queue.include? pourAB
      queue << pourAB
      info[pourAB] = { prev: current, action: "pour A B" }
      break if pourAB[1] == target
    end

    # pour B A
    pourBA = [current[0] + current[1], 0]
    pourBA = [jug1, pourBA[0] - jug1] if pourBA[0] > jug1

    unless queue.include? pourBA
      queue << pourBA
      info[pourBA] = { prev: current, action: "pour B A" }
      break if pourBA[1] == target
    end
    idx += 1
  end
  steps = []
  current = queue.last
  while current != [0, 0]
    steps << info[current][:action]
    current = info[current][:prev]
  end
  steps.reverse.each { |action| output.puts action }
  output.puts "success"
end

team_x_prob_j.rb

output = File.open("facts2.txt", "w")
IO.readlines("facts.txt").each do |line|
  n = line.strip.to_i
  output.puts( "#{"% 5d" % n } -> #{ (1..n).reduce(:*).to_s.gsub("0", "")[-1] }")
end