TS's memorandom

Google Developer Day 2011:DevQuiz解答晒し大会(6)

分野別問題(5) 一人ゲーム

当初、変なヒューリスティクスを入れたコードで2度ほど失敗。最後は簡単な方針でコードを作成して解いた。まずは擬似コード

procedure 一人ゲーム(q)
  if (qが空である) return 0
  if (∀n[n∈q, nが5の倍数]) return 1
  count ← 0
  while (∃n[n∈q, nが5の倍数])
    q ← div2(q)
    count ← count+1
  end
  return count+1+min(一人ゲーム(elim5(q)), 一人ゲーム(div2(q)))
end

実際のコード(rubyで書いた)

module Solver

  module_function

  def solve(question)

    count = 0

    if (question.length == 0)
      return 0
    end

    if (only_fives?(question))
      return 1
    end

    q = question.dup

    while (not_exists_fives?(q))
        q.map! { |n| n/2 } 
        count = count + 1
    end

    q1 = q.dup.delete_if { |n| n%5 == 0 }
    count1 = count + 1 + solve(q1)
    q.map! { |n| n/2 }
    count2 = count + 1 + solve(q)

    (count1<count2)?count1:count2

  end

  def not_exists_fives?(question)
    question.each { |n| 
      return false if (n%5 == 0)
    }
    return true
  end

  def only_fives?(question)
    question.each { |n|
      return false if (n%5 != 0)
    }
    return true
  end

end

open("question.txt", "r") do |f|
  number = f.gets.to_i
  count = 0
  while (count < number)
    size = f.gets.to_i
    question = f.gets.chomp.split(' ').map { |n| n.to_i }
    if (size == question.size) then
      puts Solver.solve(question)
    else
      puts 0
    end
    count = count + 1
  end
end

スライドパズルは項を改めて。