CodeIQ ハサミを使うタイミング[https://codeiq.jp/ace/yuki_hiroshi/q172]のために書いたコード

main.py

class Counter:
  fmt = "%d, %d"
  def __init__(self):
    self.db = {}
  def count(self, w, h):
    n = 0
    assert(w < h)
    n = self.db.get(Counter.fmt % (w, h), None)
    if n: return n
    if h % w == 0:
      self.db[Counter.fmt % (w, h)] = 0
    else:
      self.db[Counter.fmt % (w, h)] = self.count(h % w, w) + 1
    return self.db[Counter.fmt % (w, h)]

def count(w):
  max_v = 0
  max_h = 0
  counter = Counter()
  for i in range(1, w):
    h = w + i
    v = counter.count(w, h)
    if max_v < v:
      max_v = v
      max_h = h
  return (max_v, max_h)

tests.py

#!/usr/bin/env python2.7
from test import test_support
import unittest
from main import *
class TestClass(unittest.TestCase):
  def test_method(self):
    self.assertEquals((0, 0), count(1))
    self.assertEquals((1, 3), count(2))
    self.assertEquals((2, 5), count(3))
    self.assertEquals((3, 8), count(5))
    self.assertEquals((4, 13), count(8))
test_support.run_unittest(TestClass)