さえぴ の めも

色んなアウトプットする。

【Python3】Project Eulerをワンライナーで解く

1年くらい前にちまちま解いていたProject Eulerワンライナーで解いていこうと思います。
有志の方が日本語に訳したサイトはこちら:Project Euler - PukiWiki


個人で勝手に決めたワンライナーのルールです⬇︎

  1. Python3で書かれたスクリプトである
  2. コマンドラインで実行した時、答えを出力するスクリプトである
  3. 1行のスクリプトである
  4. exec使用禁止
  5. 問題で与えられた数値はスクリプト外で演算しないこと
  6. 標準ライブラリ・numpy・sympyのみ使用可能

増え次第この記事に追加していこうと思います。
githubはこちらにアップします→(https://github.com/sae-py/oneliner_euler

・problem1 - 10
・problem11 - 20


■ problem1 - 10
■ problem1

print(sum(i for i in range(1,1000) if i % 3 == 0 or i % 5 == 0))

■ problem4

print((max(map(int, filter(lambda x: x == x[::-1], map(str,[x*y for x in range(900,1000) for y in range(900,1000)]))))))

■ problem6

print(int((100*101 / 2)**2 - 100*(100+1)*(200+1)/6))

■ problem8

print(max([__import__("functools").reduce( lambda x, y: int(x) * int (y), [c for c in ("7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"[i : i + 5])] ) for i in range( len("7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450")-5)]))

■ problem9

print([a * b * (1000 - a - b) for a in range(1, 1000 + 1) for b in range(a + 1, 1000 + 1) if a * a + b * b == (1000 - a - b) * (1000 - a - b)][0])


■ problem11 - 20

■ problem11

print(max([max([max([__import__("functools").reduce( lambda x,y: x*y, r) for r in zip(*[ row[i:-(4-i)] for i in range(4)])] ) for row in [[8,0o2,22,97,38,15,00,40,00,75,0o4,0o5,0o7,78,52,12,50,77,91,8],[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,0o4,56,62,00],[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,0o3,49,13,36,65],[52,70,95,23,0o4,60,11,42,69,24,68,56,0o1,32,56,71,37,0o2,36,91],[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],[24,47,32,60,99,0o3,45,0o2,44,75,33,53,78,36,84,20,35,17,12,50],[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],[67,26,20,68,0o2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],[24,55,58,0o5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],[21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],[78,17,53,28,22,75,31,67,15,94,0o3,80,0o4,62,16,14,9,53,56,92],[16,39,0o5,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],[86,56,00,48,35,71,89,0o7,0o5,44,44,37,44,60,21,58,51,54,17,58],[19,80,81,68,0o5,94,47,69,28,73,92,13,86,52,17,77,0o4,89,55,40],[0o4,52,8,83,97,35,99,16,0o7,97,57,32,16,26,26,79,33,27,98,66],[88,36,68,87,57,62,20,72,0o3,46,33,67,46,55,12,32,63,93,53,69],[0o4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,0o4,36,16],[20,73,35,29,78,31,90,0o1,74,31,49,71,48,86,81,16,23,57,0o5,54],[1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,0o1,89,19,67,48]]]),max([max([__import__("functools").reduce( lambda x,y: x*y, r)for r in zip(*[ row[i:-(4-i)] for i in range(4)])])  for row in zip(*[[8,0o2,22,97,38,15,00,40,00,75,0o4,0o5,0o7,78,52,12,50,77,91,8],[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,0o4,56,62,00],[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,0o3,49,13,36,65],[52,70,95,23,0o4,60,11,42,69,24,68,56,0o1,32,56,71,37,0o2,36,91],[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],[24,47,32,60,99,0o3,45,0o2,44,75,33,53,78,36,84,20,35,17,12,50],[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],[67,26,20,68,0o2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],[24,55,58,0o5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],[21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],[78,17,53,28,22,75,31,67,15,94,0o3,80,0o4,62,16,14,9,53,56,92],[16,39,0o5,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],[86,56,00,48,35,71,89,0o7,0o5,44,44,37,44,60,21,58,51,54,17,58],[19,80,81,68,0o5,94,47,69,28,73,92,13,86,52,17,77,0o4,89,55,40],[0o4,52,8,83,97,35,99,16,0o7,97,57,32,16,26,26,79,33,27,98,66],[88,36,68,87,57,62,20,72,0o3,46,33,67,46,55,12,32,63,93,53,69],[0o4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,0o4,36,16],[20,73,35,29,78,31,90,0o1,74,31,49,71,48,86,81,16,23,57,0o5,54],[1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,0o1,89,19,67,48]])]),max([max([__import__("functools").reduce( lambda x,y: x*y, n) for n in zip(row[0][:-4], row[1][1:-3], row[2][2:-2], row[3][3:-1]) ]) for row in zip(*[[[8,0o2,22,97,38,15,00,40,00,75,0o4,0o5,0o7,78,52,12,50,77,91,8],[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,0o4,56,62,00],[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,0o3,49,13,36,65],[52,70,95,23,0o4,60,11,42,69,24,68,56,0o1,32,56,71,37,0o2,36,91],[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],[24,47,32,60,99,0o3,45,0o2,44,75,33,53,78,36,84,20,35,17,12,50],[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],[67,26,20,68,0o2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],[24,55,58,0o5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],[21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],[78,17,53,28,22,75,31,67,15,94,0o3,80,0o4,62,16,14,9,53,56,92],[16,39,0o5,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],[86,56,00,48,35,71,89,0o7,0o5,44,44,37,44,60,21,58,51,54,17,58],[19,80,81,68,0o5,94,47,69,28,73,92,13,86,52,17,77,0o4,89,55,40],[0o4,52,8,83,97,35,99,16,0o7,97,57,32,16,26,26,79,33,27,98,66],[88,36,68,87,57,62,20,72,0o3,46,33,67,46,55,12,32,63,93,53,69],[0o4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,0o4,36,16],[20,73,35,29,78,31,90,0o1,74,31,49,71,48,86,81,16,23,57,0o5,54],[1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,0o1,89,19,67,48]][i:-(4-i)] for i in range(4)])]),max([max([__import__("functools").reduce( lambda x,y: x*y, n) for n in zip(row[3][:-4], row[2][1:-3], row[1][2:-2], row[0][3:-1]) ]) for row in zip(*[ [[8,0o2,22,97,38,15,00,40,00,75,0o4,0o5,0o7,78,52,12,50,77,91,8],[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,0o4,56,62,00],[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,0o3,49,13,36,65],[52,70,95,23,0o4,60,11,42,69,24,68,56,0o1,32,56,71,37,0o2,36,91],[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],[24,47,32,60,99,0o3,45,0o2,44,75,33,53,78,36,84,20,35,17,12,50],[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],[67,26,20,68,0o2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],[24,55,58,0o5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],[21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],[78,17,53,28,22,75,31,67,15,94,0o3,80,0o4,62,16,14,9,53,56,92],[16,39,0o5,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],[86,56,00,48,35,71,89,0o7,0o5,44,44,37,44,60,21,58,51,54,17,58],[19,80,81,68,0o5,94,47,69,28,73,92,13,86,52,17,77,0o4,89,55,40],[0o4,52,8,83,97,35,99,16,0o7,97,57,32,16,26,26,79,33,27,98,66],[88,36,68,87,57,62,20,72,0o3,46,33,67,46,55,12,32,63,93,53,69],[0o4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,0o4,36,16],[20,73,35,29,78,31,90,0o1,74,31,49,71,48,86,81,16,23,57,0o5,54],[1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,0o1,89,19,67,48]][i:-(4-i)] for i in range(4)])])]))

■ problem12

print([int(i * (i+1) / 2) for i in range(1,15000)  if __import__("sympy").divisor_count(int(i * (i+1) / 2)) > 500][0])

■ problem13

print(str(sum([37107287533902102798797998220837590246510135740250,46376937677490009712648124896970078050417018260538,74324986199524741059474233309513058123726617309629,91942213363574161572522430563301811072406154908250,23067588207539346171171980310421047513778063246676,89261670696623633820136378418383684178734361726757,28112879812849979408065481931592621691275889832738,44274228917432520321923589422876796487670272189318,47451445736001306439091167216856844588711603153276,70386486105843025439939619828917593665686757934951,62176457141856560629502157223196586755079324193331,64906352462741904929101432445813822663347944758178,92575867718337217661963751590579239728245598838407,58203565325359399008402633568948830189458628227828,80181199384826282014278194139940567587151170094390,35398664372827112653829987240784473053190104293586,86515506006295864861532075273371959191420517255829,71693888707715466499115593487603532921714970056938,54370070576826684624621495650076471787294438377604,53282654108756828443191190634694037855217779295145,36123272525000296071075082563815656710885258350721,45876576172410976447339110607218265236877223636045,17423706905851860660448207621209813287860733969412,81142660418086830619328460811191061556940512689692,51934325451728388641918047049293215058642563049483,62467221648435076201727918039944693004732956340691,15732444386908125794514089057706229429197107928209,55037687525678773091862540744969844508330393682126,18336384825330154686196124348767681297534375946515,80386287592878490201521685554828717201219257766954,78182833757993103614740356856449095527097864797581,16726320100436897842553539920931837441497806860984,48403098129077791799088218795327364475675590848030,87086987551392711854517078544161852424320693150332,59959406895756536782107074926966537676326235447210,69793950679652694742597709739166693763042633987085,41052684708299085211399427365734116182760315001271,65378607361501080857009149939512557028198746004375,35829035317434717326932123578154982629742552737307,94953759765105305946966067683156574377167401875275,88902802571733229619176668713819931811048770190271,25267680276078003013678680992525463401061632866526,36270218540497705585629946580636237993140746255962,24074486908231174977792365466257246923322810917141,91430288197103288597806669760892938638285025333403,34413065578016127815921815005561868836468420090470,23053081172816430487623791969842487255036638784583,11487696932154902810424020138335124462181441773470,63783299490636259666498587618221225225512486764533,67720186971698544312419572409913959008952310058822,95548255300263520781532296796249481641953868218774,76085327132285723110424803456124867697064507995236,37774242535411291684276865538926205024910326572967,23701913275725675285653248258265463092207058596522,29798860272258331913126375147341994889534765745501,18495701454879288984856827726077713721403798879715,38298203783031473527721580348144513491373226651381,34829543829199918180278916522431027392251122869539,40957953066405232632538044100059654939159879593635,29746152185502371307642255121183693803580388584903,41698116222072977186158236678424689157993532961922,62467957194401269043877107275048102390895523597457,23189706772547915061505504953922979530901129967519,86188088225875314529584099251203829009407770775672,11306739708304724483816533873502340845647058077308,82959174767140363198008187129011875491310547126581,97623331044818386269515456334926366572897563400500,42846280183517070527831839425882145521227251250327,55121603546981200581762165212827652751691296897789,32238195734329339946437501907836945765883352399886,75506164965184775180738168837861091527357929701337,62177842752192623401942399639168044983993173312731,32924185707147349566916674687634660915035914677504,99518671430235219628894890102423325116913619626622,73267460800591547471830798392868535206946944540724,76841822524674417161514036427982273348055556214818,97142617910342598647204516893989422179826088076852,87783646182799346313767754307809363333018982642090,10848802521674670883215120185883543223812876952786,71329612474782464538636993009049310363619763878039,62184073572399794223406235393808339651327408011116,66627891981488087797941876876144230030984490851411,60661826293682836764744779239180335110989069790714,85786944089552990653640447425576083659976645795096,66024396409905389607120198219976047599490197230297,64913982680032973156037120041377903785566085089252,16730939319872750275468906903707539413042652315011,94809377245048795150954100921645863754710598436791,78639167021187492431995700641917969777599028300699,15368713711936614952811305876380278410754449733078,40789923115535562561142322423255033685442488917353,44889911501440648020369068063960672322193204149535,41503128880339536053299340368006977710650566631954,81234880673210146739058568557934581403627822703280,82616570773948327592232845941706525094512325230608,22918802058777319719839450180888072429661980811197,77158542502016545090413245809786882778948721859617,72107838435069186155435662884062257473692284509516,20849603980134001723930671666823555245252804609722,53503534226472524250874054075591789781264330331690]))[:10])

第九回 CTF for GIRLS 参加した #ctf4g

第九回 CTF for GIRLS ワークショップに参加してきました。
こちらです:CTF4G - 第九回 CTF for GIRLS (ワークショップ) 開催のご案内

ctf4gは初めての参加だったので緊張しましたが、とっても楽しかった〜〜!


演習のCTFはなんとか全部解けた!全完は3人。
今回はweb脆弱性の回ということで、web問苦手な私としては非常に大変だった・・・

f:id:saemero:20180623063623j:plain
⬆︎2位でした


スコアサーバはfbctfでした。やっぱかっこいいですね。

演習環境はVM(windows7)で配られ、xamppでlocalhostに環境が構築されていました。

運営の方が詳細な解説をされていたので、覚え書き程度の超ざっくりwriteup。



① 初級問題1
正しいパスワードを教えてもらえるが、プルダウンの選択肢にないので送れない。
なのでパスワードを書き換えた。


② 初級問題2
ディレクトリトラバーサルの問題。
xamppなので3階層上がったあとtest/flag.txtでflagをもらえる。


③ 初級問題3
最初はguestとしてログインしていて、adminに切り替えればflagをもらえる。
当然adminと入力してボタン押すだけでは弾かれた。
cookieのisadminをTrueにしたらflagゲット。


④ 中級問題1
スマートフォンからアクセスしてくださいと怒られるので、User-Agentを書き換える。
スマホだと思ってもらえたのでflagを出してもらえた。


⑤ 中級問題2
5万回クリックするとflagがもらえる。
htmlをデベロッパーツールで編集→valueの50000を1にした。
クリックしたらflagをもらえた。


⑥ 上級問題1
cookie「ID」に「victim」を設定すればいいらしい。
ヘッダインジェクションを使ってみましょう!とのこと。
Set-Cookie: ID=victimでflag。


⑦ 上級問題2
OSコマンドインジェクション、perl、open…ウッ頭が!
みたいな問題。
ファイル確認して、secret.plのソースを頼りに操作するとflagをもらえた。



楽しいワークショップでした!
8月に学生向けのctf4gがあるとのことなので、ぜひ参加したいと思います。

google foo.bar終わりました

学校の先輩に招待いただいたfoo.bar、先日level5解き終わりました!ワーーーーーイ!

f:id:saemero:20180610181314p:plain
⬆︎頑張って逃したBunny


解き終えた後、status画面でメッセージももらった。
1人1人違うようで、どうやらユーザー名(googleアカウント名)がキーになっているっぽい。
暗号化されたメッセージをbase64でデコードし、その結果とユーザー名のXORとっていったら解読できた。
Python3でコード書きました。

import base64

txt = "NUIFEBEPBB0XCREKS0oTPAAXEVVAQUkHQV1cDgwTOwBRRUhMRgsXWlRVBggQaUlWQhcKBwEWWkIXS1dUaQwYBgAJBQcGQlQXR01TLwYeDBcaBAMBQEUXS1dUaRAYCR0PCgsACR0QTB8VLAcfEQFLQVRECUJRDQhTYkVRAx0DRk5eDhZHAgNVaRg="
key = "my username"

message = ""

m = list(base64.b64decode(txt).decode())

for i in range(len(m)):
    a = int((key[i % len(key)]).encode("utf-8").hex(),16)
    b = int(m[i].encode("utf-8").hex(),16)
    message += chr(a ^ b)
    
print(message)

いや〜本当に嬉しいです。
楽しかった!!

Python3でtracerouteとwhoisを一気にやるスクリプト作った

ネットワークの授業でひたすらtraceroute(winだとtracertらしい)をしました。楽しかったです。
さらに、そこで可視化されたIPアドレスwhoisドメイン/IPアドレス サーチ 【whois情報検索】)で検索して国や持ち主を調べるといったことをしました。


ネットワーク超初心者の私としては楽しかったのですが、いかんせんIPアドレスをコピペして検索して…とやるのがすんごく面倒くさい。
なのでネットワークの勉強も兼ねて、traceroute → whoisで検索して国・会社を表示までPython3で一気にできるようにしました。



環境

mac OS sierra 10.12.4



作りたいもの

コマンドラインから実行するPython3のスクリプト
・入力したアドレスまでtracerouteして、whoisで取得した国・会社名とともに表示する



traceroute

まずはPython3でtracerouteを実装してみる。
書いた:traceroute/traceroute.py at master · sae-py/traceroute · GitHub



具体的にいうと、dest_name,port,max_hopsを与えてtracerouteを行う関数です。
なんでもかんでも手動で指定すると面倒くさいので、あらかじめmain関数で

port = 33434
max_hops = 30

を宣言しておきます。
2つともUNIX系のUDPtracerouteのデフォルト値です。

Traceroute - Wikipediaによると、UDPtracerouteが使用するポート番号の範囲は

On Unix-like operating systems, traceroute sends, by default, a sequence of User Datagram Protocol (UDP) packets, with destination port numbers ranging from 33434 to 33534;

だそうなので、その辺空けておいてランダムに使ってもいいかもしれない。
dest_nameはinput()で取得します。



ipwhois

ipwhois · PyPI こちらを使って、IPアドレスの管理者情報を取得するコードを書きます。
書いた:traceroute/whois.py at master · sae-py/traceroute · GitHub


ipwhoisは

pip install ipwhois

で入れられますが、私の環境の場合これでインストールすると

AttributeError: 'IPWhois' object has no attribute 'lookup'

のエラーが出てしまったので

pip install ipwhois==0.10.3

でインストールし直しました。ピタッとエラーなくなりました。
参考:[SOLVED] Cannot use python IPWhois: IPWhois instance has no attribute 'lookup_rws'

whoisの情報は辞書型で返ってきますが、

{'query': '24.24.24.24', 'nets': [{'cidr': '24.24.0.0/14, 24.28.0.0/15', 'name': 'ROAD-RUNNER-1', 'handle': 'NET-24-24-0-0-1', 'range': '24.24.0.0 - 24.29.255.255', 'description': 'Time Warner Cable Internet LLC', 'country': 'US', 'state': 'CO', 'city': 'Greenwood Village', 'address': '6399 S Fiddlers Green Circle', 'postal_code': '80111', 'abuse_emails': 'abuse@rr.com', 'tech_emails': 'ipaddressing@chartercom.com', 'misc_emails': None, 'created': '2000-06-08T00:00:00', 'updated': '2011-07-06T00:00:00'}], 'raw': None, 'referral': None, 'raw_referral': None, 'asn_registry': 'arin', 'asn': '11351', 'asn_cidr': '24.24.0.0/18', 'asn_country_code': 'US', 'asn_date': '2000-06-09'}

こんな感じで、返ってきた辞書型whoの中にさらに辞書型の要素['nets']が入っています。
なので、who['nets']をnetsに代入し、netsの要素['description']['country']を取り出しています。


合わせてみた

上記2つを合わせたスクリプトを書きます。
書いた:traceroute/trace_whois.py at master · sae-py/traceroute · GitHub


tracerouteは自分のローカル環境から任意のアドレスまでの道筋を追ってくれますが、whoisローカルアドレスを取得できないため、エラーとなります。

なので

from ipwhois.ipwhois import IPDefinedError

try:
	obj = IPWhois(curr_addr)
except IPDefinedError as e:
	print("local host")
else:
	who = obj.lookup()
	nets = who['nets']
	country = nets[0]['country']
	company = nets[0]['description']
	print("country:{0} company:{1}\n".format(country,company))

でエラーをキャッチするようにしました。

参考:IPDefinedError import is missing · Issue #9 · ChrisTruncer/Just-Metadata · GitHub

あとは素直にtracerouteのループの中にwhoisをぶち込めば完成です。わーい。



参考

PythonでUDPトレースルート(traceroute)〜ネットワーク経路調査 - ServersMan@VPS(CentOS)でお気楽サーバー運営 (^^♪ (忘れっぽいので個人メモ用)
TracerouteをPython3で実装
whoisの情報から必要なところだけを抜き出してくれるようにしてみた。 - KITA Eng.

Python3でスタック&キュー

タイトルママです。
アルゴリズムの勉強も兼ねて、10分くらいで書いてみました。


スタック

class Stack:
	def __init__(self):
		self.stack = [0,0,0,0,0]
		self.p = 0

	def push(self,obj):
		self.stack[self.p] = obj
		self.p += 1

	def pop(self):
		del self.stack[self.p-1]
		self.p -= 1

	def disp(self):
		print(self.stack)

if __name__ == "__main__":
	stack = Stack()
	data = [2,4,6,8,10]
	for i in range(len(data)):
		stack.push(data[i])
	stack.disp()
	for i in range(len(data)):
		stack.pop()
		stack.disp()

キュー

class Queue:
	def __init__(self):
		self.queue = [0,0,0,0,0]
		self.p = 0

	def enqueue(self,obj):
		self.queue[self.p] = obj
		self.p += 1

	def dequeue(self):
		del self.queue[0]
		self.p -= 1

	def disp(self):
		print(self.queue)

if __name__ == "__main__":
	queue = Queue()
	data = [2,4,6,8,10]
	for i in range(len(data)):
		queue.enqueue(data[i])
	queue.disp()
	for i in range(len(data)):
		queue.dequeue()
		queue.disp()

オーバーしちゃった時の処理などを入れていないので、まだ色々手直ししないといけないです。
githubGitHub - sae-py/stack_and_queue

Python3でハッシュ探索

前回の記事(Python3で構造体っぽいことをしてみる - さえぴ の めも)にて、Python3で構造体っぽいものを作り、さらにその要素をリニアサーチ&バイナリサーチで探索するという課題のコードを載せました。

今週の授業ではさらにハッシュ探索の実装が追加されたので、Python3でのハッシュ探索を書きました。というわけでこまめにアウトプットします(あんまりできてない)

ハッシュ探索とは

  • 配列の要素を一定の規則でハッシュ化し、そのハッシュ値を使って探索を行う。
  • ハッシュ値に従っての格納さえ済んでいれば、探索の計算量は常にO(1)

というウルトラスーパー早い探索アルゴリズムです。
ただ格納の際に時間がかかるので、探索したいデータが小さい場合はかえって効率が悪いこともあります。


簡単なコードを書くと、

import hashlib

# ハッシュ関数
def get_hash(n):
	hash = hashlib.md5(n.encode('utf-8')).hexdigest()
	hash = int(hash,16) % 61
	return hash

# ハッシュ探索
def hash_search(list,target):
	index = get_hash(target)
	if list[index] == "":
		print("見つかりませんでした")
	else:
		print("見つかりました")

# 探索したいリスト
ary = ["あ","い","う","え","お","か"]
# 格納先のリスト
hash_list = []
for i in range(61):
	hash_list.append("")

# ハッシュに基づいて格納
for i in range(len(ary)):
	index = get_hash(ary[i])
	hash_list[index] = ary[i]

# あを探す
hash_search(hash_list,"あ")
# きを探す
hash_search(hash_list,"き")

こんな感じになります。

探索したい配列aryの中身をハッシュ関数でハッシュ化し、格納先のリストの要素数素数、この場合は61)で割って格納します。
今回は簡単なハッシュかですが、衝突を考えなければいけないので実際は対策が必要です。

そして、ハッシュはユニークなものなので、格納先リストのハッシュ番目をのぞけば探したい数字があるかないかわかるという寸法です。


このハッシュ探索を前回のコード(空クラスを使用した構造体もどき)に盛り込んでみました。
github.com