無人島で直角三角形の角度をかなりアバウト(誤差20%以内)に計りたい時に使えるかもしれない簡単な計算式

おそらく、無人島の先生がこの直角三角形のアバウトな角度出しなさいという問題に答える生徒しか使わない気がしますが一応書いておきます。

無人島で直角三角形ABCの角度をアバウトに図りたい時は

角度　＝　６０　＊　高さ　／　底辺

を計算します。計算した角度から大まかな誤差を求めます。

誤差は
４０°で約２０%
２０°で約１０％
１０°で約５％
となります。

この誤差をみて使えるか使えないか判断するとよいでしょう。
誤差が大きい場合は別の手法を使いましょう。

この数式の背景にあるもの：

x が 0 に限りなく近い時以下が成り立ちます。
x = tan(x)

私の疑問として、

• x が 0 に近くないときも使ってみたとしたら誤差がどれくらいになるのか、
• 計算を簡単にするため円周率を3.14ではなく3にしてみたらどれくらいになるのか

というのがあり、それを計算機で計算し誤差を求めた結果、上記数式が使えない使えることを発見しました。

検証は以下のコードでで行いました。

import numpy as np
import matplotlib.pyplot as plt

def rad_to_degree(rad):
    return rad * 60

end_degree = 45
xdegree = np.linspace(0.000000000000001,end_degree,100)
xrad = np.pi * 2 * xdegree / 360
guess_degree = rad_to_degree(np.tan(xrad))
true_degree = xdegree
diff = guess_degree - true_degree

fig = plt.figure()

ax = fig.add_subplot(111)
ax.set_xlabel("x [Degree]", fontsize=14, fontweight='bold')
ax.set_ylabel("gosa [%]", fontsize=14, fontweight='bold')
ax.plot(xdegree, abs(diff)/true_degree*100)

plt.show()

以上です。

二値画像にk-meansを適用し、細線化？してみる

前回の続きです。今度は二値画像にk-meansを適用し、細線化？してみます。
二値画像においてk-meansが細線化や情報削減に利用できるのではないかと思えるような結果になりました。今回は、scipyのkmeans2を使用し、代表点の初期配置を領域内に収めることで、細線化？を実現します。

ソース：
（関係のないモジュールをimportしまくってますが無視してください。）

# -*- coding: utf-8 -*-
from itertools import combinations
from itertools import product
import random
import re
import numpy as np
from numpy import arange
import matplotlib.pyplot as plt
from scipy.ndimage import zoom
from scipy.fftpack import fft, ifft
from scipy.signal import resample
from scipy.spatial import Delaunay
import matplotlib.tri as tri
from scipy.cluster.vq import kmeans,vq
from scipy.cluster.vq import kmeans2,vq

def rawObjectToMatrix(ro):
    ret = []
    lines = ro.splitlines()
    for line in lines:
        if line.strip()=="":
            continue
        ret.append(map(lambda x: 0 if x == " " else 1, line))
    whiteRow = [[0 for _ in xrange(len(ret[0]))]]
    return whiteRow + ret + whiteRow

def pb(lst2d):
    ret = ""
    for lst in lst2d:
        lst = map(abs, lst)
        ret += "".join(map(str, lst)) + "\n"
    print ""
    print ret

def readMyData():
    with open("a.txt", 'r') as fp:
        text = fp.read()
    objectRawDataList = re.split(r"\n\n", text)
    objectRawDataList = filter(lambda x: x != "", objectRawDataList)
    return map(lambda ro: rawObjectToMatrix(ro), objectRawDataList)

lst = readMyData()

sampleMatrix = zoom(np.array(lst[5]), 1.5)
pb(sampleMatrix)

height = sampleMatrix.shape[0]
width = sampleMatrix.shape[1]

mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn + 1, cn] == 1:
            mat[rn, cn] = 0

out = mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[(height - 1) - rn, cn] == 1 and mat[(height - 1) - rn - 1, cn] == 1:
            mat[(height - 1) - rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn, cn + 1] == 1:
            mat[rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, (width - 1) - cn] == 1 and mat[rn, (width - 1) - cn - 1] == 1:
            mat[rn, (width - 1) - cn] = 0

out |= mat  

firstPosFlat = out.flatten().argmax()
pos = firstPosFlat / width, firstPosFlat % width
startPos = pos
code = []
while True:
    if   out[pos[0] - 1, pos[1]    ] == 1:
        out[pos[0] - 1, pos[1]    ] = 2
        pos = pos[0] - 1, pos[1]
        code.append((-1, 0))
    elif out[pos[0] - 1, pos[1] + 1] == 1:
        out[pos[0] - 1, pos[1] + 1] = 2
        pos = pos[0] - 1, pos[1] + 1
        code.append((-1, 1))
    elif out[pos[0]    , pos[1] + 1] == 1:
        out[pos[0]    , pos[1] + 1] = 2
        pos = pos[0]    , pos[1] + 1
        code.append((0, 1))
    elif out[pos[0] + 1, pos[1] + 1] == 1:
        out[pos[0] + 1, pos[1] + 1] = 2
        pos = pos[0] + 1, pos[1] + 1
        code.append((1, 1))
    elif out[pos[0] + 1, pos[1]    ] == 1:
        out[pos[0] + 1, pos[1]    ] = 2
        pos = pos[0] + 1, pos[1]    
        code.append((1, 0))
    elif out[pos[0] + 1, pos[1] - 1] == 1:
        out[pos[0] + 1, pos[1] - 1] = 2
        pos = pos[0] + 1, pos[1] - 1
        code.append((1, -1))
    elif out[pos[0]    , pos[1] - 1] == 1:
        out[pos[0]    , pos[1] - 1] = 2
        pos = pos[0]    , pos[1] - 1
        code.append((0, -1))
    elif out[pos[0] - 1, pos[1] - 1] == 1:
        out[pos[0] - 1, pos[1] - 1] = 2
        pos = pos[0] - 1, pos[1] - 1
        code.append((-1, -1))
    if pos == startPos:
        break

pr = startPos[0]
pc = startPos[1]
prlst = []
pclst = []
p = []
for n, c in enumerate(code):
    dr, dc = c
    pr += dr
    pc += dc
    prlst.append(pr)
    pclst.append(pc)
    p.append((pr, pc))

prlst = np.array(prlst)
pclst = np.array(pclst)

fig, ax = plt.subplots(1)
ax.plot(pclst, prlst)

numOfCentroids = 10
k = np.array(random.sample(zip(*np.where(sampleMatrix == 1)), numOfCentroids), dtype=np.float)
observation = np.array(zip(*np.where(sampleMatrix==1)), dtype=np.float)

# computing K-Means with K = 2 (2 clusters)
centroids,_ = kmeans2(observation, k, minit="point")

# assign each sample to a cluster
idx,_ = vq(observation,centroids)

centroidsRow, centroidsCol = centroids.T
centroidsRow = map(lambda x: int(round(x)), centroidsRow)
centroidsCol = map(lambda x: int(round(x)), centroidsCol)

sampleMatrixDummy = sampleMatrix.copy()
sampleMatrixDummy[centroidsRow, centroidsCol] = 5
pb(sampleMatrixDummy)

ax.plot(centroids[:,1], centroids[:,0], "sm")
fig.savefig("/Users/kei/Desktop/saisenka.png")

出力結果：

赤い点が周辺領域の代表点になります。形状の情報をよく表しているのではないかと思います。k-meansは形状の情報削減、圧縮、細線化などに使えそうなことがわかると思います。

抽出した輪郭を間引いてみる

昨日はオブジェクトから輪郭を抽出する処理を書きました。今日は、
輪郭を等間隔に間引いたものの形状がどうなるか見てみます。前処理としてオリジナルデータのオブジェクト領域が小さかったのでscipyのzoom関数で２倍に拡大してから処理に入っています。あと、符号化もしてます。等間隔に間引くだけなら符号化する必要はないかもしれませんが、あとで何かに使えるかもしれないので、符号化してみました。

# -*- coding: utf-8 -*-
import random
import re
import numpy as np
from numpy import arange
import matplotlib.pyplot as plt
from scipy.ndimage import zoom

def rawObjectToMatrix(ro):
    ret = []
    lines = ro.splitlines()
    for line in lines:
        if line.strip()=="":
            continue
        ret.append(map(lambda x: 0 if x == " " else 1, line))
    whiteRow = [[0 for _ in xrange(len(ret[0]))]]
    return whiteRow + ret + whiteRow

def pb(lst2d):
    ret = ""
    for lst in lst2d:
        lst = map(abs, lst)
        ret += "".join(map(str, lst)) + "\n"
    print ""
    print ret

def readMyData():
    with open("a.txt", 'r') as fp:
        text = fp.read()
    objectRawDataList = re.split(r"\n\n", text)
    objectRawDataList = filter(lambda x: x != "", objectRawDataList)
    return map(lambda ro: rawObjectToMatrix(ro), objectRawDataList)

lst = readMyData()

sampleMatrix = zoom(np.array(lst[5]), 1.5)
pb(sampleMatrix)

height = sampleMatrix.shape[0]
width = sampleMatrix.shape[1]

mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn + 1, cn] == 1:
            mat[rn, cn] = 0

out = mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[(height - 1) - rn, cn] == 1 and mat[(height - 1) - rn - 1, cn] == 1:
            mat[(height - 1) - rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn, cn + 1] == 1:
            mat[rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, (width - 1) - cn] == 1 and mat[rn, (width - 1) - cn - 1] == 1:
            mat[rn, (width - 1) - cn] = 0

out |= mat  
pb(out)

firstPosFlat = out.flatten().argmax()
pos = firstPosFlat / width, firstPosFlat % width
startPos = pos
code = []
while True:
    if   out[pos[0] - 1, pos[1]    ] == 1:
        out[pos[0] - 1, pos[1]    ] = 2
        pos = pos[0] - 1, pos[1]
        code.append((-1, 0))
    elif out[pos[0] - 1, pos[1] + 1] == 1:
        out[pos[0] - 1, pos[1] + 1] = 2
        pos = pos[0] - 1, pos[1] + 1
        code.append((-1, 1))
    elif out[pos[0]    , pos[1] + 1] == 1:
        out[pos[0]    , pos[1] + 1] = 2
        pos = pos[0]    , pos[1] + 1
        code.append((0, 1))
    elif out[pos[0] + 1, pos[1] + 1] == 1:
        out[pos[0] + 1, pos[1] + 1] = 2
        pos = pos[0] + 1, pos[1] + 1
        code.append((1, 1))
    elif out[pos[0] + 1, pos[1]    ] == 1:
        out[pos[0] + 1, pos[1]    ] = 2
        pos = pos[0] + 1, pos[1]    
        code.append((1, 0))
    elif out[pos[0] + 1, pos[1] - 1] == 1:
        out[pos[0] + 1, pos[1] - 1] = 2
        pos = pos[0] + 1, pos[1] - 1
        code.append((1, -1))
    elif out[pos[0]    , pos[1] - 1] == 1:
        out[pos[0]    , pos[1] - 1] = 2
        pos = pos[0]    , pos[1] - 1
        code.append((0, -1))
    elif out[pos[0] - 1, pos[1] - 1] == 1:
        out[pos[0] - 1, pos[1] - 1] = 2
        pos = pos[0] - 1, pos[1] - 1
        code.append((-1, -1))
    if pos == startPos:
        break

pb(out)


mabiki = [1, 2, 4, 8, 16, 32]
for m in mabiki:
    pr = 0
    pc = 0
    p = []
    for n, c in enumerate(code):
        dr, dc = c
        pr += dr
        pc += dc
        if n % m == 0:
            p.append((pr, pc))

    x = map(lambda x: x[1], p)
    y = map(lambda x: x[0], p)
    x += [0]
    y += [0]
    fig, ax = plt.subplots(1)
    ax.plot(x, y)
    fig.savefig("/Users/kei/Desktop/mabiki%d.png"%m)

出力(上から順に、オリジナル, 2, 4, 8, 16, 32ステップごとにサンプルをとった場合の集合)：

輪郭抽出

いきなりですが、輪郭抽出をPythonで実装しました。
ここでいう輪郭抽出とは画像にフィルタを適用する話ではありません。二値画像のオブジェクトの輪郭を綺麗に抽出したいのです。

すでに、このアルゴリズムがあるかは知りませんが、アルゴリズムのイメージだけ説明すると、上下左右の４方向から光をてらして光が当たる部分だけ取り出すという感じです。実際にはひたすら「連続する(1,1)を消していく」を４方向分行うだけです。

境界値処理は行っていません。以下のように入力データを加工したので、境界値の問題は発生しませんでした。

00000 < はじめと終わりの行データが非オブジェクト(0)である
00100 < 左端と右端の列データが非オブジェクト(0)である
01110
00100
00000

以下に、冗長だがよみやすいソースコードを記載していることを望みます。

# -*- coding: utf-8 -*-
import random
import re
import numpy as np
from numpy import arange

def rawObjectToMatrix(ro):
    ret = []
    lines = ro.splitlines()
    for line in lines:
        if line.strip()=="":
            continue
        ret.append(map(lambda x: 0 if x == " " else 1, line))
    whiteRow = [[0 for _ in xrange(len(ret[0]))]]
    return whiteRow + ret + whiteRow

def pb(lst2d):
    ret = ""
    for lst in lst2d:
        lst = map(abs, lst)
        ret += "".join(map(str, lst)) + "\n"
    print ""
    print ret

def readMyData():
    with open("a.txt", 'r') as fp:
        text = fp.read()
    objectRawDataList = re.split(r"\n\n", text)
    objectRawDataList = filter(lambda x: x != "", objectRawDataList)
    return map(lambda ro: rawObjectToMatrix(ro), objectRawDataList)

lst = readMyData()

sampleMatrix = np.array(lst[5])
pb(sampleMatrix)

height = sampleMatrix.shape[0]
width = sampleMatrix.shape[1]

mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn + 1, cn] == 1:
            mat[rn, cn] = 0

out = mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[(height - 1) - rn, cn] == 1 and mat[(height - 1) - rn - 1, cn] == 1:
            mat[(height - 1) - rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn, cn + 1] == 1:
            mat[rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, (width - 1) - cn] == 1 and mat[rn, (width - 1) - cn - 1] == 1:
            mat[rn, (width - 1) - cn] = 0

out |= mat  
pb(out)

a.txtのデータはこちらになります。

   @@            
   @@@@          
   @@@@@@        
   @@@@@@@       
     @@@@@@      
       @@@@@@    
         @@@@    



            @@@@@@@ 
      @@@@@@@@@@@@  
   @@@@@@@@@@@@     
  @@@@@@@@@@@@      
  @@@@@@@           
  @@@@@             
  @@@               



                              
                    @@@@@@@@  
               @@@@@@@@@@@@@  
             @@@@@@@@@@@@@@@  
          @@@@@@@@@@@@@@@     
        @@@@@@@@@@@@@@@@      
      @@@@@@@@@@@@@@@         
    @@@@@@@@@@@@@@            
    @@@@@@@@@@@               
     @@@@@                    



                           @@@@       
                           @@@@@@@    
                            @@@@@@@   
                            @@@@@@@@  
                            @@@@@@@@  
                           @@@@@@@@@  
                           @@@@@@@@@  
  @@@@@                    @@@@@@@@@  
 @@@@@@@@                 @@@@@@@@@@  
 @@@@@@@@               @@@@@@@@@@@@  
 @@@@@@@@             @@@@@@@@@@@@@@  
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     
  @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@      
   @@@@@@@@@@@@@@@@@@@@@@@@@@@@       
      @@@@@@@@@@@@@@@@@@@@@@@         
            @@@@@@@@@@@@@@@@          



                                      @@@@@@@@@    
                                  @@@@@@@@@@@@@@@  
                              @@@@@@@@@@@@@@@@@@@  
                           @@@@@@@@@@@@@@@@@@@@@@  
                        @@@@@@@@@@@@@@@@@@@@@@@@@  
                      @@@@@@@@@@@@@@@@@@@@@@@@@@   
                    @@@@@@@@@@@@@@@@@@@@@@@@@@     
                  @@@@@@@@@@@@@@@@@@@@@@@@@@@      
               @@@@@@@@@@@@@@@@@@@@@@@@@@@@        
             @@@@@@@@@@@@@@@@@@@@@@@@@@@@          
           @@@@@@@@@@@@@@@@@@@@@@@@@@@             
          @@@@@@@@@@@@@@@@@@@@@@@@@                
         @@@@@@@@@@@@@@@@@@@@@@@                   
         @@@@@@@@@@@@@@@@@@@@@                     
          @@@@@@@@@@@@@@@@                         
           @@@@@@@@@@@                             




                                @@@@@@@@@              
                            @@@@@@@@@@@@@@@@           
                         @@@@@@@@@@@@@@@@@@@@@@        
                       @@@@@@@@@@@      @@@@@@@@@      
                     @@@@@@@@@            @@@@@@@@     
                     @@@@                    @@@@@     
                                             @@@@@@    
                                             @@@@@@    
                                             @@@@@@    
                   @@                       @@@@@@@    
                  @@@@                     @@@@@@@     
                  @@@@@@                  @@@@@@@@     
                   @@@@@@@@          @@@@@@@@@@@@      
                     @@@@@@@@@@@@@@@@@@@@@@@@@@@       
                        @@@@@@@@@@@@@@@@@@@@@@         
                             @@@@@@ @@@@@@@            

実行結果

0000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011111111100000000000000
0000000000000000000000000000111111111111111100000000000
0000000000000000000000000111111111111111111111100000000
0000000000000000000000011111111111000000111111111000000
0000000000000000000001111111110000000000001111111100000
0000000000000000000001111000000000000000000001111100000
0000000000000000000000000000000000000000000001111110000
0000000000000000000000000000000000000000000001111110000
0000000000000000000000000000000000000000000001111110000
0000000000000000000110000000000000000000000011111110000
0000000000000000001111000000000000000000000111111100000
0000000000000000001111110000000000000000001111111100000
0000000000000000000111111110000000000111111111111000000
0000000000000000000001111111111111111111111111110000000
0000000000000000000000001111111111111111111111000000000
0000000000000000000000000000011111101111111000000000000
0000000000000000000000000000000000000000000000000000000


0000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011111111100000000000000
0000000000000000000000000000111100000000011100000000000
0000000000000000000000000111000000111111000011100000000
0000000000000000000000011000001111000000110000011000000
0000000000000000000001100111110000000000001110000100000
0000000000000000000001111000000000000000000001000100000
0000000000000000000000000000000000000000000001000010000
0000000000000000000000000000000000000000000001000010000
0000000000000000000000000000000000000000000001000010000
0000000000000000000110000000000000000000000010000010000
0000000000000000001001000000000000000000000100000100000
0000000000000000001000110000000000000000001000000100000
0000000000000000000110001110000000000111110000001000000
0000000000000000000001110001111111111000000000110000000
0000000000000000000000001111100000010000000111000000000
0000000000000000000000000000011111101111111000000000000
0000000000000000000000000000000000000000000000000000000

これを見ると、ガタガタじゃないかと思われるが、人間の目には"1"の領域の輪郭がしっかり把握できるのは、"1"という文字を符号としてみているのではなく、画像としてみているー数百ドットではなく数万ドットやそれ以上として認識されているーからだと思います。

備忘録、Raspberry Piにシリアル接続する方法

１年くらいに購入したラズベリーパイ、Macでシリアル接続してみた。
結果、Arduino書き込みのために購入した、USB-シリアル変換ケーブルでシリアル接続できた。
配線は以下のとおり。

※ラズパイが3.3VなのでUSB-シリアル変換ケーブルも3.3Vに合わせる。

この状態で以下のコマンドを実行。

idとパスワードを入力

以上。

再帰を走らせた時の道筋

再帰を走らせた時の道筋が知りたくなったため、考察してみました。
具体的には、以下のPythonコードで表される再帰を考えます。

# -*- coding: utf-8 -*-
def recShow(n):
    if n == 5:
        return
    else:
        recShow(n + 1)
        recShow(n + 1)

recShow(1)

これが、どのような道筋をたどるのかを知りたかったため、
試行錯誤し、以下のようにしてみました。

# -*- coding: utf-8 -*-
def recShow(n, lst):
    if n == 5:
        lst.append("ret")
        return
    else:
        newlst = lst[:]
        newlst.append("a%d"%n)
        recShow(n + 1, newlst)
        newlst.append("b%d"%n)
        recShow(n + 1, newlst)
        print newlst
        
print ""
lst = []
recShow(1, lst)

出力は以下のようになります。

['a1', 'a2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'a3', 'b3']
['a1', 'a2', 'b2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'b2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'b2', 'a3', 'b3']
['a1', 'a2', 'b2']
['a1', 'b1', 'a2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'a3', 'b3']
['a1', 'b1', 'a2', 'b2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'b2', 'a3', 'b3']
['a1', 'b1', 'a2', 'b2']
['a1', 'b1']

最深層まで行ったら戻って、また行けるところまでいくというようなイメージはつかめました。
あと、aの次はb、そのbの次はa、というような、グローバルな視点で眺めるとaとbを行き交うことがわかりました。

絶対解けるマインスイーパのようなパズル「宝探し」の6x6の問題を作成した

表題の通り、「宝探し」の6x6をつくりました。頭の体操にどうぞ。

			2
	2
	4			2
		2	3
	4	2	3		3
	2			2	1

2	3				2
3			3	1
2	3
	3	2	1
2			1

		2
2
				2
3		3		3	2
2	3		3		1
1			2

		1	1	2
		1	2
2		3			2
	2			2
2		3		2

	2
2		3	3	2
	3			3
	4			2
2		2
1		2

			2
			3
2			2
	3	3	4		2
	3	2
	2		3	2

		2	2
		4		4
		4
2	2	3	4	4
		2
	2	2

		2	3		3
3	4	4
				3	2
2					2
	2
2					2

		1	1
2	3
			2	3	3
4		5	5
					3
2			4

	2	2
			4		2
3				3
2			2
2					1
1	1				1

2	2			2
			3		3
					3
	2		4
	3
1	2		3	2

2					2
3			2	3
2
2	4
					2
2		2	2		2

	2				2
	2		3		3
3		2	3		3
			4	3
				3
			2

		2	2		2
	2	2		3
2	3
1
1	2		2
		1

		2	2		3
2			4
	2				2
		4	4	3	2
			2
	2

1	2	2			2
	4
		3		4	3
		4		3
2		3
2

	2	2	2
3
	2		2		1
		1	2
2		1	2
			2

				2	2
		2	4
1	2			2
1	2	2	3		2
1

		2			2
		3	3		2
			3		2
	2	2			1
1	1	2

1		2
				2
	4	2	3
2		2	4
2	4				2
1

2	2		2		2
					4
	2	3	3	4
1				2
	1		3

		2		2	1
			4	3
				3
	2				2
1	2	2	3	2