乙Py先生のプログラミング教室
初学者のためのプログラミング学習サイト

プログラミング

はいどうもこんばんわ
乙pyです

さて、今回は
Googleの入社問題を解いてみたいと思います。

解説動画はこちら





さて、
どのような問題かというと

2 Eggs and 100 floor Google Classic question
100階建てのビルのある階から卵を落とします。
卵はある階よりも低ければ割れることはなく
ある階よりも高いと割れてしまう。

今、あなたは卵を2つ持っています。
卵が何階で割れるかを調べるもっとも効率のよい方法は何ですか?
そして、その方法で必要な卵を落とす回数は最大で何回ですか?

こんな問題です。

まずは素直に一回から落として行くと
最大でその階数分だけの試行回数になります。

なので100階まであるので
最大で100回でしょうね。

次に10階刻みで増やしていき
割れたら手前の階層に戻って1づつ増やして行く方法


これだと
10階 、 20階 ぺちゃる 
11,12,13,14 ペチャる 
14階で割れるとしたら6回落とした、となります。

さて、これを全階層分試行するには面倒くさいですよね
プログラムで一気に解いてしまいましょう。

def check_egg(x):
    c,n=0,10
    while True:
        c+=1
        if x<=n:
            break
        n+=10

    n = n-9
    while True:
        c+=1
        if x<=n or '{:02}'.format(n)[1]=='9':
            break
        n+=1
    return c,x

results = {}
for x in range(1,101):
    answer,key = check_egg(x)
    results[key] = answer

for k,v in results.items():
    print(k,v)

これで実行してみると
最大試行回数は99階と100階がそれぞれ
19回落とすことになります。

さて
もっと効率の良い方法はないでしょうか?

それは
刻む階層を減らして行くやり方です。

まず最初に刻む分をNとすると

N , N-1 , N-2 ・・・

という感じで
刻むのを減らせます。

そして、この刻みが100階を超えるには
Nが14であるということになります。

1 + 2 + 3 + 4 ・・・ で
100を超えるのは14の時ですね

さて刻み方がわかったら
これをプログラムにしてみましょう。

こんな感じですね

def check_egg(x):
    c=0
    steps=[14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100]
    for i,n in enumerate(steps):
        c+=1
        if x<=n:
            break

    n = steps[i-1]+1 if i!=0 else 1
    while True:
        if n in steps:
            break
        c+=1
        if x<=n:
            break
        n+=1
    return c,x

results = {}
for x in range(1,101):
    answer,key = check_egg(x)
    results[key] = answer

for k,v in results.items():
    print(k,v)

これで実行してみると
最大試行回数は
14回まで減らすことができます。

落とす時のイメージとしてはこんな感じ

1	2	3	4	5	6	7	8	9	10	11	12	13	14	
15	16	17	18	19	20	21	22	23	24	25	26	27	
28	29	30	31	32	33	34	35	36	37	38	39	
40	41	42	43	44	45	46	47	48	49	50	
51	52	53	54	55	56	57	58	59	60	
61	62	63	64	65	66	67	68	69	
70	71	72	73	74	75	76	77	
78	79	80	81	82	83	84	
85	86	87	88	89	90	
91	92	93	94	95	
96	97	98	99	
98	99	100	

どこでたまごが潰れても
最大で14回で答えにたどり着ける感じになってますね。


今回は
Googleの入社問題を考えてみました。

よく考えれば意外と
解けそうな問題ですね〜〜

入社できませんかねwwwwww

今回はこれまでです
それでは。






 

はいどうも
乙pyです。

今回はみんな大好き黒川先輩を
世界旅行に連れて行ってあげましょう
という企画です。

動画はこちら




さて今回は
OpenCVというのを使います。

OpenCVは画像加工のための
ライブラリでPython以外の言語にも
対応しているものです。

これを用いると
画像を使っていろいろ遊ぶことができます。

インストール方法は
pip install opencv-python

でインストールすることができます。

Pythonでの使い方:

まずはじめにライブラリを読み込みます。
import cv2
import numpy as np 
import matplotlib.pyplot as plt
%matplotlib inline

これでライブラリを使う準備は完了です。

画像をうまく合成するには
1.背景画像
2.上に載せる画像
3.載せる画像のマスク画像

この3つが必要になります。

背景は良いとして
マスク画像というのは
kurochan6

こんな感じで、載せたい部分を白
それ以外の部分を黒く塗りつぶした画像を
マスク画像として使えます。

マスク画像なしでも
画像を合成することはできますが
スムーズな合成をするには
マスク画像が必要です。

コードはこんな感じになります。

file_dir = 'img/'
kurochan = 'kurochan.jpg'
bg_name = 'roma.jpg'
msk_name = 'kurochan6.png'
src = cv2.imread(file_dir + kurochan)
dst = cv2.imread(file_dir + bg_name)
msk = cv2.imread(file_dir + msk_name)

size_rate = 0.8
src2 = cv2.resize(src , (int(src.shape[1]*size_rate), int(src.shape[0]*size_rate)))

r_msk = cv2.resize(msk , (int(msk.shape[0]*size_rate), int(msk.shape[1]*size_rate)))

output = cv2.seamlessClone(src2, dst, r_msk, 
(src2.shape[0]//2,dst.shape[0]-src2.shape[0]//2), cv2.NORMAL_CLONE)

fig = plt.figure(figsize=(16,9))
plt.imshow(cv2.cvtColor(output, cv2.COLOR_BGR2RGB))
plt.show()

合成する画像をsrc
背景をdst
マスク画像をmsk
として読み込み
outputを生成しています。

cv2.seamlessCloneメソッドで
合成ができます。


さて合成してみると
こんな感じになります。

96

マスクの白い部分だけが合成に用いられ
黒い部分は背景とうまく合うように演算処理され
画像が合成される仕組みになっているようです。

cv2.seamlessCloneメソッドで
配置も決めるので
画像の大きさを超えるような場所に指定すると
エラーになります。

雑な合成ですが
元の画像とマスクの調整をうまくやれば
それっぽい画像ができるのではないかと思います。

これを用いると
まるで旅行に行ってきたような
画像を作ることができたりするので

アリバイ作りなんかも
できちゃったりするかもしれませんねwww


OpenCVは
他にもいろーーんなことができるので
また試していきたいと思います。

今回はここまでです。

それでは。


さて
今回は免許証番号のチェックデジットについての
お話になります。

動画はこちら




免許証番号にも法則性があり
必ず一定のルールに従った番号体系になっています。

もしそのルールに番号に沿っていなかったら
そこで偽造だとわかる事になります。

 まず最初に免許証番号のルールですが
こんな感じだそうです。

免許証番号は、県警察電算処理システムの電子計算機で管理し
新規免許登録時に付与されるが、 公安委員会コード
年号記号、交付番号及び再交付記号並びに
チェックデジットをもって構成する(12桁の数)。

例 309212345610

最初の2桁は公安委員会コード
続く2桁は発行年号(下2桁)
続く6桁が交付番号(発行番号)
その次1桁がチェックデジット
最後の1桁は再発行回数

menban


公安委員会コードは定められていて
こんな感じです。
北海道 北海道
10
函館
11
旭川
12
釧路
13
北見
14
           
東北 青森
20
岩手
21
宮城
22
秋田
23
山形
24
福島
25
         
関東甲信越 東京
30
茨城
40
栃木
41
群馬
42
埼玉
43
千葉
44
神奈川
45
新潟
46
山梨
47
長野
48
静岡
49
北陸・中部 富山
50
石川
51
福井
52
岐阜
53
愛知
54
三重
55
         
関西 滋賀
60
京都
61
大阪
62
兵庫
63
奈良
64
和歌山
65
         
中国 鳥取
70
島根
71
岡山
72
広島
73
山口
74
           
四国 徳島
80
香川
81
愛媛
82
高知
83
             
九州・沖縄 福岡
90
佐賀
91
長崎
92
熊本
93
大分
94
宮崎
95
鹿児島
96
沖縄
97
     
東京で取得したならば
30ということになります。

続く年号記号(3桁目と4桁目の数字)は
初めて免許を取得した年の西暦下2桁
になります。

例:
2019年に取得 → 19
1992年に取得 → 92

ということで
あまりにもかけ離れていた場合
(今25歳なのに99になっているとか)
その番号が偽りの番号であると
すぐにわかる仕組みです。

続く6桁は発行番号で
一意になるような番号体系です。


最後の12桁目は再交付記号

再交付記号「0」は、再発行がされた事がないのを示し

この数字は紛失・盗難などで再発行する度に増えていき

10回再発行された場合には「1」と記載される仕組みです

なのでほとんどの人は
再発行していないと思うので
「0」になっているのではないかと思います。


そして
11桁目がチェックデジットです。

免許証のチェックデジットの計算方法は
次のとおりになります。


左から10個の数字にそれぞれ、5,4,3,2,7,6,5,4,3,2をかけて合計する

例:「309212345690」のうちの「3092123456」

5×3+4×0+3×9+2×2+7×1+6×2+5×3+4×4+3×5+2×6=123

次に、これを11で割って余りを出す 123÷11=11 余り 2

さらに、11から余りを引く 11-2=9


計算式 :
上位10桁をabcdefghijとすると

(11 - (5a+4b+3c+2d+7e+6f+5g+4h+3i+2j) mod 11) mod 10

チェックデジットを計算する関数は次のようになります。

def check_menkyo_degit(t):
    a = 5*int(t[0])
    b = 4*int(t[1])
    c = 3*int(t[2])
    d = 2*int(t[3])
    e = 7*int(t[4])
    f = 6*int(t[5])
    g = 5*int(t[6])
    h = 4*int(t[7])
    i = 3*int(t[8])
    j = 2*int(t[9])
    degit  = a+b+c+d+e+f+g+h+i+j
    return (11 - degit%11)%10

check_menkyo_degit('309212345690')
9

免許証番号を引数に入れると
チェックデジットが出ます。


これを使って
免許証番号を生成してみましょう。

東京で1999年に取得
交付番号はランダム
再発行は無し
とすると

def make_menkyo(st=30,year=1999):
    t = str(st) + str(year)[2:4]
    t += '{0:06}'.format(random.randint(1,10000))
    cd = check_menkyo_degit(t)
    return t + str(cd) + '0'

make_menkyo()

309900219680

このような形で作ることができます。


このようにチェックデジットは
偽造の防止などに役立てられているので

この番号体系に合わないものは
すぐに弾ける仕組みとなっています。

ましWEBサービスを運営しているのであれば
こういった番号のチェックを行うことで
不正防止をすることができます。

皆様も
お手元に免許証があれば
ぜひ番号チェックをしてみてください

今回はこれまでです
それでは。







さて今回は
「チェックデジット」
というものについてのお話です。




動画はこちら

 



チェックデジットは
データの正確性を保つ為に使用される文字のことで
様々な分野のID番号などの使用されています。

工業用のコード
クレジットカード
免許証

いろんなチェックデジットが存在し
計算方法が違っています。

今回はクレジットカードの
チェックデジットを計算してみましょう。

クレジットカードの番号には法則があり
最初の6桁はカードの発行元
7-15桁目はカード番号
最後の1桁がチェックデジット
となっています。

また
日本で流通しているカード体系で
最初の1桁は金融機関などの業種を表します。

例えば
Visa 4xxxxx
Mastercard51xxxx - 55xxxx
Amex 34xxxx, 37xxxx
などです。

なので最初の6桁と
最後の1桁は必ず法則に従わないと
そのクレジットカード番号は
正しくない番号となります。

それでは
チェックデジットを計算してみましょう。

クレジットカードのチェックデジットの計算方法

元の番号 : 4417123456789113

奇数桁目を2倍に掛ける
8 2 2 6 10 14 18 2

偶数桁目はそのまま足す
4 7 2 4 6 8 1 3

2桁の数は十の位と1の位を足して1桁にする
(2桁の数になったら9を引けばいい)

8+4+2+7+2+2+6+4+1+0+
6+1+4+8+1+8+1+2+3 = 70

和が10で割れる数なら、そのクレジットカードは有効

こんなルールでカード番号が作られています。

お手元に
クレジットカードがある方は
実際に計算してみてはいかがでしょうか?


それでは
このクレジットカードが正しいのかどうかを
計算するプログラムを作っていきたいと思います。

これは至極簡単で数行で済みます。

カード番号をチェックする関数はコレ。
def check_digit(num):
    tmp1 = [int(num[i])*2 for i in range(len(num)) if i%2==0]
    tmp1 = [i-9 if i>9 else i for i in tmp1]
    tmp2 = [int(num[i]) for i in range(len(num)) if i%2==1]
    total = sum(tmp1+tmp2)
    return total%10==0

これを使ってカード番号をチェックしてみましょう。

例題の番号をそのまま使い
check_digit('4417123456789113')
True

カード番号が合っていればTrue
違っていればFalseになります。



それではこの関数を使って
クレジットカード番号を生成してみましょう。

クレジットカード番号を生成する関数はコレ。

import random
def make_card(head = '498003'):    
    num = str(head) + ''.join([str(random.choice([i for i in range(10)])) for i in range(9)])
    for i in range(10):
        if check_digit(num + str(i)):
            return num + str(i)
    return None

実際に使う場合は
make_card(head = '498003')
4980030390770041

このようになります。

最初の6桁は発行元の番号体系に
合わせる必要があります。

引数headの6桁の番号を変更していただければ
その番号で始まるカード番号になります。



さて
チェックデジットはいかがでしたでしょうか?

このように
カード番号などは
チェック機能があるので
デタラメな番号は弾かれるようになっています。

ECサイトなども同様で
正しい番号体系を入れなければ
成立しないようにチェックが働いています。

皆様も
サイト構築をしたりする際は
チェックデジットの仕組みを導入すると
不正防止に繋がりますので
いろいろ考えてみてくださいね

今回はここまでです
それでは。


日本で一番有名なマークである

安産祈願マークを
プログラムで作ってみましょう!!!


動画はこちら



さて
作り方は
numpyとmatplotlibを用いて
マークを描いていきます。

widgetも用いて
うねうね変形できるようにもします。

ソースはこちら
import numpy as np
import matplotlib.pyplot as plt
from ipywidgets import interact, FloatSlider, IntSlider,Select
%matplotlib inline

r = IntSlider(min=1, max=8, step=1, value=5)
t = FloatSlider(min=1.0, max=1.5, step=0.1, value=1.0)
c = Select(options=['black', 'red', 'blue','green'],
    value='black',description='coler : ',disabled=False)

@interact(r=r,t=t,c=c)
def plot_man(r,t,c):
    plt.figure(figsize=(10,9))
    plt.axes().set_aspect('equal', 'datalim')
    
    # circle 1
    x = [np.sin(np.radians(_x))*r for _x in np.linspace(-180,180,721)]
    y = [np.cos(np.radians(_y))*r*t for _y in np.linspace(-180,180,721)]
    plt.plot(x, y, c)
    
    # circle 2
    x2 = [i*0.7 for i in x]
    y2 = [i*0.7 for i in y]
    plt.plot(x2, y2, c)
    
    # line
    x3 = [0,0]
    y3 = [min(y)*1.25,max(y)*1.25]
    plt.plot(x3, y3, c)
    
    # lines
    x4 = [i*1.2 for i in x]
    y4 = [i*1.2 for i in y]
    for i in range(16):
        x5 = [x[i*45],x4[i*45]]
        y5 = [y[i*45],y4[i*45]]
        plt.plot(x5, y5, c)
    
    plt.xlim([-20,20])
    plt.ylim([-20,20])
    plt.show()



結果はこうなります。

スクリーンショット 2019-07-28 15.47.34


rで円の半径を変更
tで楕円の倍率を変更
colorで色を変更です。

楕円は
円の縦横方向を n 倍にすることで実現しています。

なので
縦方向であれば
xの値はそのままに
yの値の倍率を変えてあげると
縦方向の楕円になります。

今回のやり方では
まず半径を決めて円を用意します。
内側の円は1つめの円の倍率を変えただけです。

縦棒はxの値が0でyの値を変化させることで
実現させ、外側の棒たちは

大きな円を用意し
1つめの円から外側の円に向かう値で
描いています。

一応16本になるみたいなので
22.5度の角度になるような計算で
座標を求めています。

全部足すと
安産マークになります!!!!!!!




せっかくなので
GIFも作ってみましょう


matplotlibではアニメーション機能で
mp4やgifも作れますが
環境によっては動かないこともあり

今回は
画像をたくさん生成して
無理くりGIFに落とし込みます。


ソースはこちら
from PIL import Image, ImageDraw, ImageFont
import numpy as np
import matplotlib.pyplot as plt
from ipywidgets import interact, FloatSlider, IntSlider,Select
import os

data_dir = 'anzan_data/'
if not os.path.exists(data_dir):
    os.makedirs(data_dir)

for a in range(30):
    plt.figure(figsize=(3,3))
    plt.axes().set_aspect('equal', 'datalim')
    plt.tick_params(labelbottom=False,
                    labelleft=False,
                    labelright=False,
                    labeltop=False)
    plt.tick_params(bottom=False,
                    left=False,
                    right=False,
                    top=False)
    plt.xlim([-20,20])
    plt.ylim([-20,20])
    c ='black'
    n = (np.abs(np.sin(a))+1)
    # circle 1
    x = [np.sin(np.radians(_x))*8 for _x in np.linspace(-180,180,721)]
    y = [np.cos(np.radians(_y))*8*n for _y in np.linspace(-180,180,721)]
    plt.plot(x, y, c)

    # circle 2
    x2 = [i*0.7 for i in x]
    y2 = [i*0.7 for i in y]
    plt.plot(x2, y2, c)

    # line
    x3 = [0,0]
    y3 = [min(y)*1.25,max(y)*1.25]
    plt.plot(x3, y3, c)

    # lines
    x4 = [i*1.2 for i in x]
    y4 = [i*1.2 for i in y]
    for i in range(16):
        x5 = [x[i*45],x4[i*45]]
        y5 = [y[i*45],y4[i*45]]
        plt.plot(x5, y5, c)
    file_name = data_dir + 'tmp_{0:02}.png'.format(a)
    plt.savefig(file_name)

images = []
for a in range(30):
    file_name = data_dir + 'tmp_{0:02}.png'.format(a)
    img = Image.open(file_name)
    images.append(img)

gif_name = 'anzan.gif'
images[0].save(gif_name,save_all=True, append_images=images[1:], optimize=False, duration=2, loop=0)





結果はこうなります。


anzan
びろんびろん動くのが
気持ちいいですよねーーーー


はい
周りのに安産祈願の方がいたら
是非送ってあげましょう!!

きっと喜ばれること
間違いなし




今回はここまでです。

それでは


 

このページのトップヘ