ランダムなFizzBuzz列をクイックソートで並べ替える

はじめに
---
前回クイックソートを学んだ。
懸念点は、大小比較が多いのでどうしようかという点であった。
http://qiita.com/cof/items/7b94aac6794d12ae020f

解決策
---
1. FizzBuzzと数値とを対応付けるクラスを作り、そのクラスで演算子のオーバロードを行う。
2. ランダム列の要素を上記クラスのインスタンスで置き換える。
3. 置き換えた後のランダム列をクイックソートする。

一度完全に数値化してクイックソートして後でFizzBuzzに置き換えるほうが早いけど、演算子のオーバロードの練習ということで、FizzBuzzと数値とを対応付けるクラスを作ってみた。
参考：
http://docs.python.jp/2/reference/datamodel.html#customization

演算子のオーバロード
---

文字列等(key)に対応付けられた数値（value）の演算を行い、結果のkeyに相当する文字列等を返すコード。 

```py
def fizzbuzz(n):
  if (n%15) == 0: return 'FizzBuzz'
  elif (n%5) == 0: return 'Buzz'
  elif (n%3) == 0: return 'Fizz'
  else: return n

class FizzBuzzNumber:
  def __init__(self, value):
    self.key = fizzbuzz(value)
    self.value = value

  def __call__(self):
    return self.key

  def __add__(self, other) :
    return fizzbuzz(self.value + other.value)

  def __sub__(self, other):
    return fizzbuzz(self.value - other.value)

  def __mul__(self, other):
    return fizzbuzz(self.value * other.value)

  def __div__(self, other):
    return fizzbuzz(self.value // other.value)

  def __mod__(self, other):
    return fizzbuzz(self.value % other.value)

  def __pow__(self, other):
    return fizzbuzz(self.value ** other.value)

  def __cmp__(self, other):
    return cmp(self.value, other.value)

  def __lt__(self, other):
    return cmp(self.value, other.value) == -1

  def __le__(self, other):
    return cmp(self.value, other.value) in (-1, 0)

  def __eq__(self, other):
    return cmp(self.value, other.value) == 0

  def __ne__(self, other):
    return cmp(self.value, other.value) != 0

  def __gt__(self, other):
    return cmp(self.value, other.value) == 1

  def __ge__(self, other):
    return cmp(self.value, other.value) in (1, 0)

  def __iadd__(self, other) :
    self.value += other.value
    self.key = fizzbuzz(self.value)
    return self

  def __isub__(self, other) :
    self.value -= other.value
    self.key = fizzbuzz(self.value)
    return self

  def __imul__(self, other) :
    self.value *= other.value
    self.key = fizzbuzz(self.value)
    return self

  def __imod__(self, other) :
    self.value %= other.value
    self.key = fizzbuzz(self.value)
    return self

  def __idiv__(self, other) :
    self.value /= other.value
    self.key = fizzbuzz(self.value)
    return self

  def __ipow__(self, other) :
    self.value **= other.value
    self.key = fizzbuzz(self.value)
    return self
```

下記コードを実行すると、

```py
fizz = FizzBuzzNumber(3)
buzz = FizzBuzzNumber(5)
print 'fizz + buzz = ', fizz + buzz
print 'fizz - buzz = ', fizz - buzz
print 'fizz * buzz = ',  fizz * buzz
print 'fizz / buzz = ', fizz / buzz
print 'fizz % buzz = ', fizz % buzz
print 'fizz ** buzz = ', fizz ** buzz
print 'fizz > buzz: ', fizz > buzz
print 'fizz < buzz: ', fizz < buzz
print 'fizz == buzz: ', fizz == buzz
print 'fizz != buzz: ', fizz != buzz
print 'fizz <= buzz: ', fizz <= buzz
print 'fizz >= buzz: ', fizz >= buzz
print 'fizz():', fizz()
fizz += buzz
print 'fizz += buzz => fizz() = ' , fizz()
fizz -= buzz
print 'fizz -= buzz => fizz() = ' , fizz()
fizz *= buzz
print 'fizz *= buzz => fizz() = ' , fizz()
fizz /= buzz
print 'fizz /= buzz => fizz() = ' , fizz()
fizz %= buzz
print 'fizz %= buzz => fizz() = ', fizz()
fizz **= buzz
print 'fizz **= buzz => fizz() = ', fizz()
```

以下のような結果が出力される。

```py
fizz + buzz =  8
fizz - buzz =  -2
fizz * buzz =  FizzBuzz
fizz / buzz =  FizzBuzz
fizz % buzz =  Fizz
fizz ** buzz =  Fizz
fizz > buzz =  False
fizz < buzz =  True
fizz == buzz:  False
fizz != buzz:  True
fizz <= buzz:  True
fizz >= buzz:  False
fizz(): Fizz
fizz += buzz => fizz() =  8
fizz -= buzz => fizz() =  Fizz
fizz *= buzz => fizz() =  FizzBuzz
fizz /= buzz => fizz() =  Fizz
fizz %= buzz => fizz() =  Fizz
fizz **= buzz => fizz() =  Fizz
```

数値化する関数
---
後はランダム列に出てきたFizzBuzzを数値化するためのクラスを作ってみた。

```py
class FizzBuzzCounter:
  def __init__(self, f_start, b_start, fb_start):
    self.f = f_start
    self.b = b_start
    self.fb = fb_start

  def get_value(self, s):
    if s == 'FizzBuzz': 
      return self.fb
    elif s == 'Buzz': 
      return self.b
    elif s == 'Fizz': 
      return self.f
    else: 
      return s

  def next(self, s):
    if s == 'FizzBuzz': 
      self.fb += 15
    elif s == 'Buzz': 
      if (self.b % 15) == 10:
         self.b += 10
      else:
         self.b += 5
    elif s == 'Fizz': 
      if (self.f % 15) == 12:
         self.f += 6
      else:
         self.f += 3
    else: 
      pass
```

FizzBuzz列を置き換える関数
---
上記2クラスを使って、与えられたFizzBuzz列の要素をFizzBuzzNumberクラスのインスタンスに置き換えた列を作る関数を作った。

```py
def recreate_fizzbuzz_seq(seq):
  counter = FizzBuzzCounter(3,5,15)
  ret = []
  for e in seq:
   ret.append(FizzBuzzNumber(counter.get_value(e)))
   counter.next(e)
  return ret
```

後は前回つくったクイックソート関数に上記新たな列を与えるだけ。

前回作ったクイックソート関数
---
```py
def pivot(target, i, j):
  k = i + 1
  while k <= j and target[i] == target[k]: k += 1
  if k > j: return -1
  if target[i] >= target[k]: 
    return i
  else:
    return k

def partition(target, i, j, x):
  l, r = i, j
  while l <= r:
    while l <= j and target[l] < x: l += 1
    while r >= i and target[r] >= x: r -= 1
    if l > r: break
    target[l], target[r] = target[r], target[l]
    l, r = l + 1, r - 1
  return l

def quick_sort(target,i ,j):
  if i == j: return 
  p = pivot(target, i, j)
  if p != -1:
    k = partition(target, i, j, target[p])
    quick_sort(target, i, k-1)
    quick_sort(target, k, j)
```

ランダムなFizzBuzz列を作る関数
---
```py
def make_random_fizzbuzz(start=1,finish=100):
  seq = range(start,finish+1)
  random_fizzbuzz = []
  while seq:
    random_fizzbuzz.append(fizzbuzz(seq.pop(random.randint(0,len(seq)-1))))
  return random_fizzbuzz
```


メイン関数
---
与えられたFizzBuzz列をrecreate_fizzbuzz_seq()に与えて新たな列を作り、新たな列をクイックソートに与える関数

```py
def fizzbuzz_sort(target):
  newtarget = recreate_fizzbuzz_seq(target)
  quick_sort(newtarget,0,len(newtarget)-1)
  return newtarget
```

起動は次のように行う。

```
fizzbuzz_sort(make_random_fizzbuzz())
```

感想
---
こんなくだらないことをやっている俺はあほや。あと`__add__()`等が返すのは新たなFizzBuzzNumberのインスタンスのほうがよかったかな。