AOJ（問題集）4

AIZU ONLINE JUDGE: Programming Challenge
　

0031 Weight

def measure(object, weight, result = [])
  return result.join(" ") if weight.zero?
  result.unshift(weight) if (object / weight).nonzero?
  measure(object % weight, weight / 2, result)
end

$<.readlines.map(&:to_i).each {|ob| puts measure(ob, 512)}

0032 Plastic Board

rectangle = lozenge = 0

$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |a, b, c|
  rectangle += 1 if a * a + b * b == c * c
  lozenge   += 1 if a == b
end
puts rectangle, lozenge

0033 Ball

def try(balls, b ,c)
  return 1 if balls.empty?
  nxt = balls.first
  bl = balls.drop(1)
  if nxt > b and nxt > c
    try(bl, nxt, c) + try(bl, b, nxt)
  elsif nxt > b
    try(bl, nxt, c)
  elsif nxt > c
    try(bl, b, nxt)
  else
    0
  end
end

$<.gets.to_i.times do
  balls = $<.gets.split.map(&:to_i)
  puts try(balls.drop(1), balls.first, 0).nonzero? ? "YES" : "NO"
end

読み込みに readlines を使ったらエラーが出る。gets を使ったコードに替えたら正解になった。非本質的なところで延々と悩まされた。
　

0034 Railway Lines

$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |given|
  ls = given.first(10)
  v1, v2 = given.last(2)
  s = Rational(v1 * ls.sum, v1 + v2)
  l = 0
  ls.each_with_index do |ln, i|
    next if s > (l += ln)
    puts i + 1
    break
  end
end

0035 Is it Convex?

$<.readlines.map {|l| l.split(",").map(&:to_r)}.each do |given|
  f = (given + given.first(4)).each_slice(2).each_cons(3).map do |a, b, c|
    (c[0] - a[0]) * (b[1] - a[1]) - (c[1] - a[1]) * (b[0] - a[0]) > 0
  end
  puts((f.all? or f.none?) ? "YES" : "NO")
end

0036 A Figure on Surface

L = 8
table = [["11", "11"], ["1", "1", "1", "1"], ["1111"], ["01", "11", "10"],
         ["110", "011"], ["10", "11", "01"], ["011", "110"]]
table.map! {|pt| [pt.size, l = pt.first.length, pt.join("0" * (L - l))]}

$<.readlines.chunk {|l| !!l.match(/^\d/) || nil}
  .map {|a| a.last.map(&:chomp).join}.each do |field|
  table.each_with_index do |ary, k|
    y, n, pt = ary
    (L + 1 - y).times do |i|
      (L + 1 - n).times do |j|
        puts "ABCDEFG"[k] if field[i * L + j, pt.length] == pt
      end
    end
  end
end

0037 Path on a Grid

given = $<.readlines.map {|l| l.chomp.chars.map(&:to_i)}
yoko = 0.step(8, 2).map {|i| given[i]}
tate = 1.step(8, 2).map {|i| given[i]}.transpose
dirs = "LRUD"
go = nil
route = ""
f = false

get_yoko = ->(x, y, dir) {
  if dir == 0
    if tate[x][y] == 1
      go.(x, y, 3)
    elsif x > 0 and yoko[y][x - 1] == 1
      go.(x, y, 0)
    elsif y > 0 and tate[x][y - 1] == 1
      go.(x, y, 2)
    else
     go.(x, y, 1)
    end
  else
    if y > 0 and tate[x][y - 1] == 1
      go.(x, y, 2)
    elsif x <= 3 and yoko[y][x] == 1
      go.(x, y, 1)
    elsif tate[x][y] == 1
      go.(x, y, 3)
    else
      go.(x, y, 0)
    end
  end
}

get_tate = ->(x, y, dir) {
  if dir == 2
    if x > 0 and yoko[y][x - 1] == 1
      go.(x, y, 0)
    elsif y > 0 and tate[x][y - 1] == 1
      go.(x, y, 2)
    elsif yoko[y][x] == 1
      go.(x, y, 1)
    else
      go.(x, y, 3)
    end
  else
    if x <= 3 and yoko[y][x] == 1
      go.(x, y, 1)
    elsif y <= 3 and tate[x][y] == 1
      go.(x, y, 3)
    elsif x > 0 and yoko[y][x - 1] == 1
      go.(x, y, 0)
    else
      go.(x, y, 2)
    end
  end
}

go = ->(x, y, dir) {
  return if x.zero? and y.zero? and f
  f = true
  route += dirs[dir]
  if dir <= 1
    get_yoko.(x + dir * 2 - 1, y, dir)
  else
    get_tate.(x, y + dir * 2 - 5, dir)
  end
}

go.(0, 0, 1)
puts route

何だか全然よくないコード。もっと考えたい。
　

0038 Poker Hand

def same_numbers(ary, result = [])
  return result.sort if ary.empty?
  a = ary.first
  co = ary.count(a)
  result << co if co > 1
  same_numbers(ary - [a], result)
end

$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |hand|
  puts case same_numbers(hand)
  when [4]    then "four card"
  when [2, 3] then "full house"
  when [3]    then "three card"
  when [2, 2] then "two pair"
  when [2]    then "one pair"
  else
    hand.sort!
    if hand.sum == (hand.first + 2) * 5 or hand == [1, 10, 11, 12, 13]
      "straight"
    else
      "null"
    end
  end
end

0039 Roman Figure

table = {I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000, nil => 0}

count = ->(roman, number = 0) {
  return number if roman.empty?
  a, b = table[roman.first], table[roman[1]]
  number += if a >= b
    r = roman.drop(1)
    a
  else
    r = roman.drop(2)
    b - a
  end
  count.(r, number)
}

$<.readlines.map(&:chomp).each {|roman| puts count.(roman.chars.map(&:to_sym))}

0040 Affine Cipher

def decode(word, a, b)
  g = (0..25).map {|i| [[*"a".."z"][(a * i + b) % 26], i]}.to_h
  word.chars.map {|st| (g[st] + 97).chr}.join
end

e = Enumerator.new do |y|
  generate = ->(n) {
    a, b = n, 0
    n.times do
      y << [a, b]
      a -= 1
      b += 1
    end
    generate.(n + 1)
  }
  generate.(1)
end

$<.readlines.drop(1).map {|a| a.split}.each do |sentence|
  loop do
    a, b = e.next
    dsr = (1..a).select {|i| (a % i).zero?}
    next if dsr.include?(2) or dsr.include?(13) or dsr.include?(26)
    f = sentence.select {|w| w.length == 4}.map do |word|
      st = decode(word, a, b)
      st == "that" or st == "this"
    end.any?
    next unless f
    puts sentence.map {|word| decode(word, a, b)}.join(" ")
    break
  end
end

アフィン暗号の解読にはここを参考にした。

うーん、あんまりひどいタイムなので、他の人のコードを参考にした。すごい。

cl = [*"a".."z"]
table_a = (1..26).select {|i| 26.gcd(i) == 1}
b = nil

$<.readlines.drop(1).each do |str|
  a = table_a.find do |i|
    b = (0..26).find do |j|
      nominees = str.split.select {|w| w.length == 4}
      ["that", "this"].map do |x|
        nominees.include?(x.chars.map {|c| cl[(i * cl.index(c) + j) % 26]}.join)
      end.any?
    end
  end
  table = (0..25).map {|i| (a * i + b) % 26}
  puts str.chomp.chars.map {|c| (c == " ") ? c : cl[table.index(cl.index(c))]}.join
end