end0tknr's kipple - 新web写経開発

http://d.hatena.ne.jp/end0tknr/ から移転しました

状態遷移図 / 状態遷移表によるメールアドレスのチェック

GoFのステートパターンは以前のエントリで記載していますが、 次のurlで、状態遷移図 / 状態遷移表 の実装があった為、写経。

日経ソフトウエア 2020年3月号|日経ソフトウエア

状態遷移図 と 状態遷移表

まぁ、記載している通りです f:id:end0tknr:20200126201554p:plain

現在の状態 / 外部からの入力 英数字 ドット 末尾
初期状態 (State_0) State_1 State_7 State_7 State_7 State_7
≠ドット in ローカル部 (State_1) State_1 State_2 State_3 State_7 State_7
=ドット in ローカル部 (State_2) State_1 State_2 State_3 State_7 State_7
@(State_3) State_4 State_7 State_7 State_7 State_7
≠ドット in ドメイン部 (State_4) State_4 State_5 State_7 State_7 State_6
=ドット in ドメイン部 (State_5) State_4 State_7 State_7 State_7 State_7
=メールアドレス (State_6) State_8 State_8 State_8 State_8 State_8
≠メールアドレス (State_6) State_8 State_8 State_8 State_8 State_8
完了 (State_8)

状態遷移表によるメールアドレスのチェック

上記の状態遷移表をpythonで実装すると、以下の通り

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-

def main():
    string = input("文字列を入力下さい-->")
    if is_email(string):
        print("これはメールアドレスです。")
    else:
        print("これはメールアドレスではありません。")


def is_alphanum(char):
    if "0" <= char <= "9" or "A" <= char <= "Z" or "a" <= char <= "z":
        return True
    return False

def is_dot(char):
    if char == ".":
        return True
    return False

def is_atmark(char):
    if char == "@":
        return True
    return False

def is_end(char):
    if char == "$":
        return True
    return False

def is_email(str):
    str += "$"  # 文字列に末尾を意味する$を付加

    # 状態遷移表
    table = [ [1, 7, 7, 7, 7],
              [1, 2, 3, 7, 7] ,
              [1, 7, 7, 7, 7],
              [4, 7, 7, 7, 7],
              [4, 5, 7, 7, 6],
              [4, 7, 7, 7, 7],
              [8, 8, 8, 8, 8],
              [8, 8, 8, 8, 8] ]

    state = 0   # 0 = 初期状態
    
    for char in str:    # 文字列から1文字ずつ取り出し状態遷移
        if is_alphanum(char):
            col = 0
        elif is_dot(char):
            col = 1
        elif is_atmark(char):
            col = 2
        elif is_end(char):
            col = 4
        else:
            col = 3
        
        state = table[state][col]
        
        if state == 6 or state == 7:    # OK or NGなら終了
            break

    if state == 6:
        return True
    return False

if __name__ == '__main__':
    main()

windowsにおいて、丸やゼロで変換される ○ , ◯ , 〇 , ❍

excelで記入されたアンケートを集計したら、 同じ丸(まる、マル)でも複数の文字コードがあり、少々、手間取りました。

特に「ゼロ」で変換すると、漢数字の「〇」が表示されることは、すっかり忘れていました。

以下は、複数の「丸」の文字コードをurl encodingにより表示するものです。

linux odコマンドでも同様のことができますが、私の場合、perlで対応しました。

#!/usr/local/bin/perl
use utf8;
use strict;
use warnings;
use Encode;
use Data::Dumper;

main( @ARGV );

sub main {
    my @chars =
        ('○',    # 丸
         '◯',    # 大きな丸
         '〇',    # 漢数字のゼロ
         '❍',    # 丸    <機種依存文字>
         '⭕',    # 絵文字<機種依存文字>
         '⚪',    # 絵文字<機種依存文字>
        );

    my $i = 0;
    for my $char ( @chars ){
        $i++;
        my $char_utf8 = Encode::encode('utf8',$char);
        my $char_url = url_encode($char_utf8);
        print "$i : $char_utf8 -> $char_url\n";
    }
}

sub url_encode {
    my ($str) = @_;
    $str =~ s/(\W)/'%' . unpack('H2', $1)/ego;
    return $str;
}

sub url_decode {
    my ($str) = @_;
    $str =~ s/%([0-9A-F][0-9A-F])/pack('H2', $1)/egoi;
    return $str;
}

↑こう書くと、↓こう表示されます。

$ ./foo.pl
1 : ○ -> %e2%97%8b
2 : ◯ -> %e2%97%af
3 : 〇 -> %e3%80%87
4 : ❍ -> %e2%9d%8d
5 : ⭕ -> %e2%ad%95
6 : ⚪ -> %e2%9a%aa

kanren for python による論理プログラミング (パズルの解法)

https://www.oreilly.co.jp/books/9784873118727/

またまた、上記url の 6章の写経の続き。

「パズル」と言っても、歯抜けの条件群を定義した上で、 ウサギの飼い主を求めます。

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-
from kanren import * 

    
def main():
    
    people = var()

    rules = lall(
        # people は4個の変数(人)を持つ
        (eq,      (var(),    var(),    var(),  var()      ),people),
        # Steveは青い車を持っており、peopleのメンバー
        (membero, ('Steve',  var(),    'blue', var()      ),people),
        # 猫を飼って、Canadaに住むメンバーがいる
        (membero, (var(),    'cat',    var(),  'Canada'   ),people),
        # MattherはUSAに住んでおり、peopleのメンバー
        (membero, ('Matthew',var(),    var(),  'USA'      ),people),
        # 黒い車を持っている人はAustraliaに住んでいるメンバーがいる
        (membero, (var(),    var(),    'black','Australia'),people),
        # Jachは猫を飼っており、peopleのメンバー
        (membero, ('Jack',   'cat',    var(),  var()      ),people),
        # AlfredはAustraliaに住んでおり、peopleのメンバー
        (membero, ('Alfred', var(),    var(),  'Australia'),people),
        # 犬を飼ってFranceに住んでいるメンバーがいる
        (membero, (var(),    'dog',    var(),  'France'   ),people),
        
        # ウサギを飼っているメンバーがいる
        (membero, (var(),    'rabbit', var(),  var()      ),people)
    )
  
    solutions = run(0, people, rules)

    # ウサギの飼い主は?
    output = [house for house in solutions[0] if 'rabbit' in house][0][0]
    print(output + ' is the owner of the rabbit')


    # ルール一覧の出力
    print('Here are all the details:') 
    attribs = ['Name', 'Pet', 'Color', 'Country'] 
    print('\n' + '\t\t'.join(attribs)) 
    print('=' * 57) 

    for item in solutions[0]: 
        print('\t\t'.join([str(x) for x in item])) 

    
if __name__ == '__main__':
    main()

↑こう書くと、↓こう表示されます

$ ./foo.py 
Matthew is the owner of the rabbit
Here are all the details:

Name            Pet             Color           Country
=========================================================
Steve           dog             blue            France
Jack            cat             ~_9             Canada
Matthew         rabbit          ~_11            USA
Alfred          ~_13            black           Australia

kanren for python による論理プログラミング (家系図の解析)

https://www.oreilly.co.jp/books/9784873118727/

上記url の 6章の写経の続き。

以下の家系図を定義し、「John」の父親(≠義父)を求めます

                           John─Megan
                            │                  
      ┌──────────┼─────────────┐
 William─Emma             David─Olivia                Adam─Lily
  ┌─┤            ┌─┬─┴─┬──┬──┐          │
Cris Stephanie    Wayne Tiffany Julie Neil Peter        Sopia
#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-
import json
import kanren
from kanren import Relation, facts, run, conde, var, eq 

relation = \
    {"father": [{"John": "William"},
                {"John": "David"},
                {"John": "Adam"},
                {"William": "Chris"},
                {"William": "Stephanie"},
                {"David": "Wayne"},
                {"David": "Tiffany"},
                {"David": "Julie"},
                {"David": "Neil"},
                {"David": "Peter"},
                {"Adam": "Sophia"} ],
     "mother": [{"Megan": "William"},
                {"Megan": "David"},
                {"Megan": "Adam"},
                {"Emma": "Stephanie"},
                {"Emma": "Chris"},
                {"Olivia": "Tiffany"},
                {"Olivia": "Julie"},
                {"Olivia": "Neil"},
                {"Olivia": "Peter"},
                {"Lily": "Sophia"}
     ]
    }

    
def parent(x, y):
    return kanren.conde((father(x, y),), (mother(x, y),))

def grandparent(x, y):
    temp = var() 
    return kanren.conde((parent(x, temp), parent(temp, y))) 

def sibling(x, y): # 兄弟
    temp = var()
    return kanren.conde((parent(temp, x), parent(temp, y))) 

def uncle(x, y):
    temp = kanren.var()
    return kanren.conde((father(temp, x), grandparent(temp, y))) 
#    return conde((sibling(temp, x), parent(temp, y)))


def main():
#    with open('relationships.json') as f:
#        d = json.loads(f.read())
    d = relation

    father = kanren.Relation()
    mother = kanren.Relation()

    for item in d['father']:
        kanren.facts(father, (list(item.keys())[0], list(item.values())[0])) 

    for item in d['mother']: 
        kanren.facts(mother, (list(item.keys())[0], list(item.values())[0])) 

    x = var()
    output = run(0, x, (father, 'John', x))
    for item in output:
        print(item)


if __name__ == '__main__':
    main()

↑こう書くと、↓こう表示されます

$ ./foo.py 
Adam
David
William

kanren for python による論理プログラミング (素数の判定)

https://www.oreilly.co.jp/books/9784873118727/

上記url の 6章の写経の続き。

「23, 4, 27, 17, 13, 10, 21, 29, 3, 32, 11, 19」から素数を抽出します。

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-
import itertools  # イテレータ関数群
import kanren
from kanren.core import success, fail
import sympy


def main():
    x = kanren.var()

    list_nums = (23, 4, 27, 17, 13, 10, 21, 29, 3, 32, 11, 19)

    print( 'List of primes in the list:' )
    
    # 「membero, x, list_nums」= xに対するlist_numsの要素判定
    # 「check_prime, x」= xに対する素数判定
    # 多分「run(0, ...)」は解を無限に収集し,「run(7, ...)」は解を7個、収集する
    print(
        set(
            kanren.run(0, x, (kanren.membero, x, list_nums), (check_prime, x))
        )
    )


# 素数判定
def check_prime(x):

    if kanren.isvar(x):
        print("X0:",x)
        # 以下の condeseq() により
        # [eq(x,2)] or [eq(x,3)] or [eq(x,5)] or [eq(x,7)] or ...
        # が生成
        # - sympy.ntheory.generate.prime(i)= i番目の素数を算出
        # - it.count(1) = 開始値=1の無限イテレータ
        return kanren.core.condeseq([kanren.eq(x, p)] \
                    for p in map(sympy.ntheory.generate.prime,
                                 itertools.count(1) ))
    print("X1:",x)

    if sympy.ntheory.generate.isprime(x): # 素数判定
        return success
    return fail


if __name__ == '__main__':
    main()

↑こう書くと、↓こう出力されます

$ ./foo.py 
List of primes in the list:
X0: ~_1
X1: 23
X1: 4
X1: 27
X1: 17
X1: 13
X1: 10
X1: 21
X1: 29
X1: 3
X1: 32
X1: 11
X1: 19
{3, 11, 13, 17, 19, 23, 29}

ただ、「if kanren.isvar(x)」内を殆ど通らない点が、気になります。

kanren for python による論理プログラミング (数式の照合)

https://www.oreilly.co.jp/books/9784873118727/

上記url の 6章の写経。

「数式の照合」として、数式の変数(a,b,c)の値を算出します。

論理プログラミングというと、prologの方が記述しやすいと思いますが、 pythonの場合、算出後のデータ加工等が容易な為、 今回、 kanren for python を使用しています。

ただ、複雑な論理プログラミングは、prolog の方が良い気がします。

kanren for python は日本語の情報も少ないようですので

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-
from kanren import run, var, fact   # https://pypi.org/project/kanren/
import kanren.assoccomm as la


def main():
    add = 'addition' 
    mul = 'multiplication'

    # 交換法則(commutative)と結合法則(associative)の事実を定義
    
    ## 交換法則 : 2x4=4x2 のように順番を交換可
    fact(la.commutative, mul)
    fact(la.commutative, add)
    ## 結合法則 : (3×6)×2=3×(6×2) のように、()をどこにつけても結果は同じ
    fact(la.associative, mul)
    fact(la.associative, add)

    # 変数を定義
    a, b, c = var('a'), var('b'), var('c')

    # 0) ↓ 3x(-2) + (1+2+3) x (-1)
    expression_orig = (add, (mul, 3, -2), (mul, (add, 1, (mul, 2, 3)), -1))

    # 1) ↓ (1+2xa) x b + 3xc
    expression1 = (add, (mul, (add, 1, (mul, 2, a)), b), (mul, 3, c))
    # 2) ↓ cx3 x b x (2xa+1)
    expression2 = (add, (mul, c, 3), (mul, b, (add, (mul, 2, a), 1))) 
    # 3) ↓ (((2xa) x b) + b) + 3xc
    expression3 = (add, (add, (mul, (mul, 2, a), b), b), (mul, 3, c)) 

    # 数式の照合
    print(run(0, (a, b, c), la.eq_assoccomm(expression1, expression_orig)))
    print(run(0, (a, b, c), la.eq_assoccomm(expression2, expression_orig)))
    print(run(0, (a, b, c), la.eq_assoccomm(expression3, expression_orig)))

    
if __name__ == '__main__':
    main()

上記のように書くと、上記の式0と式1-3を比較し、同一式である場合、 変数a,b,cの値が算出されます。

$ ./foo.py 
((3, -1, -2),)
((3, -1, -2),)
()

python の module を src から ( not pip ) install

普段、pip ばかりでは、忘れてしまうので

https://pypi.org/project/kanren

上記 kanren を例にすると、以下の通り

$ wget https://files.pythonhosted.org/packages/f7/28/????/kanren-0.2.3.tar.gz
$ tar -xvf kanren-0.2.3
$ sudo /usr/local/python3/bin/python3 setup.py install

おまけで、tox による testを実施する場合、以下の通り

$ sudo /usr/local/python3/bin/pip3 install tox
$ sudo /usr/local/python3/bin/tox
GLOB sdist-make: /home/end0tknr/tmp/kanren-0.2.3/setup.py
python create: /home/end0tknr/tmp/kanren-0.2.3/.tox/python
python inst: /home/end0tknr/tmp/kanren-0.2.3/.tox/.tmp/package/1/kanren-0.2.3.zip
python installed: kanren==0.2.3,multipledispatch==0.6.0,six==1.13.0,toolz==0.10.0,unification==0.2.2
python run-test-pre: PYTHONHASHSEED='2241079051'

python: commands succeeded
  congratulations :)

aws s3 の static website hosting で、独自ドメインを利用する場合、「バケット名 = ドメイン名」 とする

ポイントは

バケット名 = ドメイン名 とする

以下の通り

f:id:end0tknr:20200105101806p:plain

jsonで記載するバケットポリシー

{ "Version":"2012-10-17", // AWSから指定されている文字列(not任意)
  "Statement":[
    { "Sid":"TestAwsS3WebHosting", // 任意の文字列
      "Effect":"Allow",
      "Principal": "*",
      "Action":["s3:GetObject"],
      "Resource":["arn:aws:s3:::バケット名/*"] }
  ]
}

pythonによる経路探索 ( 深さ優先 or 幅優先 )

1) pgRouting を使用した 幾何学図形に対する経路探索 - end0tknr's kipple - 新web写経開発

2) 最短経路探索アルゴリズムの A* (A-STAR)を perlで試す - end0tknr's kipple - 新web写経開発

3) Algorithms with Python / 集合, グラフ, 経路の探索

経路探索は、過去1),2)で何度か書いた(写経)ことがありますが、 改めて? 上記3)を pythonにて写経し、少々、修正。

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-

# http://www.nct9.ne.jp/m_hiroi/light/pyalgo05.html
#       B(1)──D(3)──F(5)
#     / │     │      │
#  A(0)  │     │      │
#     \ │     │      │
#       C(2)──E(4)──G(6)
adjacent = ((1, 2),    # A
            (0, 2, 3), # B
            (0, 1, 4), # C
            (1, 4, 5), # D
            (2, 3, 6), # E
            (3,),      # F
            (1,))      # G

def main():
    print("#### 深さ優先探索 ####")
    search(6, [0])

    print("#### 幅優先探索 ####")
    bf_search(0, 6)


# 深さ優先探索 (最初に見つかる経路が最短経路とは限らない)
def search(goal, path):
    n = path[len(path) - 1]
    
    if n == goal:
        print("GOAL REACHED!", path )
        return path

    for x in adjacent[n]:
        # 既に通過した経路に設定xが含まれない場合
        # これを追加(path+[x])し、再帰探索
        if x not in path:
            search(goal, path+[x] )
    return None


# 幅優先探索
def bf_search(start, goal):
    q = [[start]]  # 「q」には探索中の経路が複数含まれます
    while len(q) > 0:
        # dequeu
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            print("GOAL REACHED!", path )
        else:
            for x in adjacent[n]:
                if x not in path:
                    q.append( path+[x])


if __name__ == '__main__':
    main()

↑こう書くと、↓こう表示されます

C:\home\end0tknr\tmp\PYTHON>python foo.py
#### 深さ優先探索 ####
GOAL REACHED! [0, 1, 2, 4, 6]
GOAL REACHED! [0, 1, 3, 4, 6]
GOAL REACHED! [0, 2, 1, 3, 4, 6]
GOAL REACHED! [0, 2, 4, 6]
#### 幅優先探索 ####
GOAL REACHED! [0, 2, 4, 6]
GOAL REACHED! [0, 1, 2, 4, 6]
GOAL REACHED! [0, 1, 3, 4, 6]
GOAL REACHED! [0, 2, 1, 3, 4, 6]

swi-prolog + clpfd による ナップザック問題 (knapsack)

http://www.nct9.ne.jp/m_hiroi/prolog/clp02.html

上記urlには、swi-prolog + clpfd による様々な制約プログラミングが、 分かりやすく記載されています。

その中に swi-prolog + clpfd による ナップザック問題もありますが、 流石 prolog という程、簡潔に記載されています。

他の言語では、ここまで簡潔にはなりませんよね。

use_module(library(clpfd)).

solver :-
    Ws = [3, 4, 5, 7, 9],
    Ps = [4, 5, 6, 8, 10],
    Bs = [A, B, C, D, E],
    Bs ins 0..1,
    scalar_product(Ws, Bs, #=<, 15),
    scalar_product(Ps, Bs, #=, V),
    labeling([max(V)], [A, B, C, D, E, V]), 
    writeln(V),
    writeln(Bs).
use_module(library(clpfd)).

solver(W) :-
    % 単価
    % A: 30.3, B: 30.0, C: 30.5, D: 31.0
    Price = [91, 120, 610, 930],
    Size = [3, 4, 20, 30],
    Vars = [A, B, C, D],
    maplist(#=<(0), Vars),
    scalar_product(Size, Vars, #=<, W),
    scalar_product(Price, Vars, #=, Value),
    labeling([down, max(Value)], [D, C, A, B, Value]),
    writeln(Value),
    writeln(Vars).

はてなブログの code hilightが、prologに対応していることも驚きです

perlとpythonで範囲指定による配列(list)作成 - 「..」in perl 「range()」in python3

以下の通り、その他の注意点としては同じ「1 ~ 9」で範囲指定しても pythonでは「8」までしか表示されません

perl

#!/usr/local/bin/perl
use strict;
use warnings;
use Data::Dumper;

main();

sub main {
    print "a" x 5 ,"\n";

    for my $int ( 1 .. 9 ){
        print $int,"\n";
    }

}

python3

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-

def main():
    print("a" * 5 );

    for int  in range( 1, 9 ):
        print(int)

    
    
if __name__ == '__main__':
    main()

perlとpythonにおける同一文字列の連続(繰り返し)出力 - 「"a" x 5」in perl 「"a" * 5」in python3

perl

#!/usr/local/bin/perl
use strict;
use warnings;
use Data::Dumper;

main();

sub main {
    print "a" x 5 ,"\n";
}

python3

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-

def main():
    print("a" * 5 );

    
if __name__ == '__main__':
    main()
    

python 3.7 における多重sort - 「lambda x:(-x[0],x[1])」と「key=cmp_to_key(cmpstr)」

ちょっと迷ったのでメモ。

lambda x:(-x[0],x[1]) による方法

以下は、2次元配列の 第1要素で降順 & 第2要素で昇順 sort します。

seisan_date_candidates_tmp = \
    sorted(seisan_date_candidates, key=lambda x:(-x[0],x[1]))
seisan_date_str = seisan_date_candidates_tmp[0][1]

key=cmp_to_key(cmpstr) による方法

更に複雑な条件での多重sortには、key=cmp_to_key() を用いると良いと思います。

def cmp_func(a, b):
    if a[0] == b[0]:
        cmp_func_2(a, b)

    if a[0] < b[0] :
        return -1 
    else :
        return 1 

def cmp_func_2(a, b):
    if a[1] == b[1]: return 0

    if a[1] < b[1] :
        return -1 
    else :
        return 1 

def main():
    xs = [[3, 4], [0, 6], [5, 7], [8, 9]]
    print(sorted(xs, key=cmp_to_key(cmp_func)))

openpyxl for python による excel 読み込みを高速化 - wsheet.iter_rows()

xlrd for python で excel (xlsx) を読む - end0tknr's kipple - 新web写経開発

上記エントリに倣い openpyxl for pythonexcel (xlsx)を読むと速度が遅く、 特にレコード数の多い excelデータではこれが致命的。

どうやら

cell = wsheet.cell(row=row,column=col)

のように、ワークシートから座標指定で、各セルを取り出していることが原因らしい。

なので、wsheet.iter_rows() を用いることで、かなりの高速化になります。

for cells in wsheet.iter_rows(min_row=2): # min_row: 読取り開始行
    cell = cells[0]
    shukka_date = datetime.datetime.strptime(str(cell.value), '%Y-%m-%d %H:%M:%S')
    shukka_date_str = shukka_date.strftime('%Y-%m-%d')

    col = 1
    while col < len( cells ):
        factory = factories[col-1]
        units_waku = cells[col].value
        fact_shukka_mst[factory][shukka_date_str] = units_waku
        col += 1
     :
  • iter_rows()は上記のmin_row以外に min_row max_row min_col max_col を指定できます
  • iter_rows()の他、iter_cols() もあります