Google Code Jam 2013 รอบคัดเลือก

ปีนี้สุดท้ายแล้วได้มา 80 คะแนนครับ อันดับอยู่ 8 พันกว่าๆ เนื่องจาก กว่าจะตื่นมาทำก็เที่ยงละ แล้วข้อสุดท้ายที่ทำได้ ก็เล่นเอาเกือบหมดเวลา (ตี 4 ของอีกวัน หมดเวลา 7 โมงเช้า)

ทรมานคนแข่งประเทศอื่น Google ก็คิดว่า Programmer ต้องนอนดึกเลยจัดแข่ง 11.00PM เวลาที่นู่น
ซึ่งเมืองไทยก็ 6 โมงไงครับ Programmer ที่นี่ บางทีพึ่งจะนอนหลับกัน (รึปล่าว ?)

ผมทำไปทั้งหมด 3 ข้อ

Problem A. Tic-Tac-Toe-Tomek

อันนี้ไม่มีอะไรครับ เป็น OX แบบ 4x4 ที่มีตัวพิเศษคือ T อยู่บนตาราง 1 ตัว (หรืออาจจะไม่มี) ซึ่ง T จะเป็นตัวพิเศษคือถ้ามี O หรือ X จำนวน 3 ตัวแล้วมี T ไม่ว่าจะแทรกอยู่หรือต่อท้าย เป็นว่าชนะ

Input ตารางเข้าไปแล้วให้หาว่า ใครชนะ เสมอ หรือเกมส์ยังไม่จบ
ตอนแรกคิดว่า T จะต้องต่อ XXX เท่านั้น แต่มาอ่านอีกที T เนี่ยแทรกอยู่ตรงไหนก็ได้
Algorithm ที่ผมใช้ เลยใช้ประโยชน์จากตัวภาษา แล้วนับจำนวนเลย

(ตอนแรกก็เขียน check แถวหลักธรรมดาแหละ แต่ Code ยาวไปยันเกือบ 120 บรรทัดมั้ง = =')

test = gets.chomp.to_i
def win_checker(symbol_list, symbol)
  symbol_list.count(symbol) == 4 or 
    (symbol_list.count(symbol) == 3 and symbol_list.count('T') == 1)
end

test = gets.chomp.to_i
test.times do |t|
  table = []
  n = 3
  4.times { table << gets.chomp }
  dummy = gets.chomp
  
  x_win = o_win = false
  
# vertical
  vertical_1, vertical_2, vertical_3, vertical_4 = [], [], [], []
  0.upto(3) do |i|
    vertical_1 << table[i][0]
    vertical_2 << table[i][1]
    vertical_3 << table[i][2]
    vertical_4 << table[i][3]
  end
  
  if win_checker(vertical_1, 'X') or 
      win_checker(vertical_2, 'X') or
        win_checker(vertical_3, 'X') or
          win_checker(vertical_4, 'X')
    x_win = true
  elsif win_checker(vertical_1, 'O') or 
          win_checker(vertical_2, 'O') or
            win_checker(vertical_3, 'O') or
              win_checker(vertical_4, 'O')
    o_win = true
  end
  
# horizontal
  horizontal_1, horizontal_2, horizontal_3, horizontal_4 = [], [], [], []
  0.upto(3) do |i|
   horizontal_1 << table[0][i]
   horizontal_2 << table[1][i]
   horizontal_3 << table[2][i]
   horizontal_4 << table[3][i]
  end
  
  if win_checker(horizontal_1, 'X') or 
      win_checker(horizontal_2, 'X') or
        win_checker(horizontal_3, 'X') or
          win_checker(horizontal_4, 'X')
    x_win = true
  elsif win_checker(horizontal_1, 'O') or 
          win_checker(horizontal_2, 'O') or
            win_checker(horizontal_3, 'O') or
              win_checker(horizontal_4, 'O')
    o_win = true
  end
       
# diagonal
  diagonal_right = []
  diagonal_left = []
  0.upto(3) do |i|
    0.upto(3) do |j|
      if i == j
        diagonal_right << table[i][j]
      elsif j == (n - i)
        diagonal_left << table[i][j]
      end
    end
  end
  
  if win_checker(diagonal_right, 'X') or
      win_checker(diagonal_left, 'X')
    x_win = true
  elsif win_checker(diagonal_right, 'O') or
          win_checker(diagonal_left, 'O')
    o_win = true
  end
      
  print "Case ##{t + 1}: "
  table_string = table.join
  
  if x_win
    print "X won\n"
  elsif o_win
    print "O won\n"
  elsif !x_win and !o_win
    print (table_string.count('.') != 0) ? "Game has not completed\n" : "Draw\n"
  end
end

Problem B. Lawnmower 

ข้อนี้ก็โจทย์ไถหญ้าครับ คือมีผัวเมียคู่หนึ่ง ไถหญ้าหน้าบ้านเป็น Pattern ทุกปี (ว่างสินะ) แต่พอดีว่ามีนวัตกรรมเครื่องไถหญ้าใหม่ออกขาย ... คือมันไถตรงไปข้างหน้าได้อย่างเดียว เลือกสักแถวแหละ มันไถเกรียนเท่ากันหมด (ทั้งในแนวแกน X, Y) ให้หาว่า ถ้าให้ Pattern แบบนี้มา จะไถได้หรือไม่ ? ข้อนี้เปลี่ยนมาใช้ Python เขียน ไม่รู้นึกอะไร เปลี่ยนบรรยากาศบ้าง :)

ข้อนี้แหละที่มา Submit ตอนก่อนหมดเวลา

import re

def check_game(lawn):
    row_maxes = [max(x) for x in lawn]
    cols = [[lawn[i][j] for i in range(len(lawn))] for j in range(len(lawn[0]))]
    col_maxes = [max(x) for x in cols]
    for i in range(len(lawn)):
        for j in range(len(lawn[i])):
            val = lawn[i][j]
            if val != row_maxes[i] and val != col_maxes[j]:
                return "NO"
    return "YES"

def read_input():
    dims = map(int, raw_input().split())
    x,y = int(dims[1]), int(dims[0])    
    lawn = []
    for i in range(y):
        line = raw_input()
        nums = [int(x.strip()) for x in re.split(" ",line)]
        lawn.append(nums)

    return lawn
    
if __name__ == "__main__":
    test = input()
    for i in xrange(test):
        lawn = read_input()
        result = check_game(lawn)
        print "Case #%d: %s" % (i + 1, result)

Problem C. Fair and Square

โจทย์ข้อนี้คือเมื่อให้ช่วงตัวเลข A - B มา ให้หาว่ามีเลขที่เป็น Palindrome และรากที่สองของตัวเลขนั้นยังคงเป็น Palindrome ด้วย ทั้งหมดกี่ตัว

โจทย์ข้อนี้ผมรันไม่ทันครับ ... ใน small problem มันกระจอกมาก ... Algorithm ที่ใช้เลยรันได้สบายๆ
แต่พอ Large นี่เดี้ยงทันที ... ให้ดูอันที่กากก่อนนะ :P

class Fixnum
  def is_palindrome
    self.to_s == self.to_s.reverse
  end
end

test = gets.chomp.to_i

test.times do |t|
  count = 0
  
  a, b = gets.chomp.split.map! { |e| e.to_i }
  (a).upto(b) do |i|
    if i.to_s.is_palindrome
      squared = Math.sqrt(i)
      if squared.to_s[squared.to_i.to_s.length + 1, 2] == "0" and 
          squared.to_s[0, squared.to_i.to_s.length].is_palindrome
        count += 1
      end
    end 
  end
  
  puts "Case ##{t + 1}: #{count}"
end

จากนั้นก็ได้ไปอ่าน Code ของหลายๆ คนที่ทำได้ครับ (@champjss, @neizod, @jittat) เลยกระจ่างว่าทำยังไง โดยมีอยู่ 2 วิธี ที่น่าสนใจและเข้าใจง่ายคงเป็นวิธี Dynamic Programming ของ @jittat ซึ่งผมแปลงมาเป็น Ruby ได้แบบนี้ครับ (อาจารย์ท่านเขียนด้วย C++)

class Fixnum
  def is_palindrome
    self.to_s == self.to_s.reverse
  end
  
  def square
    self * self
  end
  
  def between(a, b)
    a <= self and self <= b
  end
end

palindrome_list = []

def generate_palindrome_list
  1.upto(20000000) do |i|
    if i.is_palindrome
      squared_i = i.square
      if squared_i.is_palindrome
        palindrome_list << squared_i
      end
    end
  end
end

generate_palindrome_list
test = gets.chomp.to_i

test.times do |t|
  a, b = gets.chomp.split.map { |e| e.to_i }
  result_count = 0
  palindrome_list.each do |each|
    if each.between(a, b)
      result_count += 1
    end
  end
  
  puts "Case ##{t + 1}: #{result_count}"
end