何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

Python Charity Talks in Japanに参加しました

去る2020年7月4日に行われたPython Charity Talks in Japanに参加した。

pyconjp.blogspot.com

pyconjp.connpass.com

www.youtube.com

チャリティの主旨は、Python Software Foundationへの寄付である。 Python Software Foundation(PSF)とはPythonの公式ドキュメントにある通り、 Python 2.1以降著作権を保持する独立の非営利組織であり、プログラミング言語Pythonの開発や利用を支援する団体である。 昨今のCOVID-19の影響でアメリカで開催予定であったPyCon US 2020がオンライン開催となり、活動の収益源を得ることができなくなってしまった。 苦境に立たされているPSFへの寄付がこのチャリティイベントの目的である。

今回、僕は2つの立場でチャリティイベントに参加した。 1つは個人パトロンとして、純粋にPSFへの寄付金を拠出するために参加する個人としての立場、もう1つは僕が所属する企業の役員や上司に働きかけてスポンサーになってもらうスポンサー企業の従業員としての立場である。

個人としての立場は単純明白である。 幸いなことに、僕はPythonでプログラミングをすることで生活ができている。 それを還元するだけである。

スポンサー企業の従業員としての立場は、まずこのようなイベントがあること、求人イベントも兼ねていることを伝え、PyCon JP 2020のスポンサーとの兼ね合いも含め社内で議論を行った。 今年はPyCon JPの社内主担当者ではないが、スポンサー枠が限られていることと、時間がそれほどなかったことからスポンサー決定まではできるだけ積極的に活動した。 幸い、すぐにスポンサーとなることが決定した。

イベントそのものは、所属企業のLTをハラハラしながら見ていた。 LTは5分で短いから簡単、とは過去言ってきたが、実際5分で言いたいことを伝えるのはそれなりに訓練が必要で実は難しいことを改めて感じた。

PSFへの寄付は140万円程となり、PyCon US 2020の1スポンサー枠程度の金額を集めることができたのではなかろうか。 Pythonの今後の発展や、スポンサーをした弊社の発展を願うばかりである。

Final Fantasy XII サブイベント「キャビンチーフ七姉妹」を効率的に攻略する

突然のゲーム攻略エントリ

だいぶ前にFinal Fantasy XII The Zodiac AgeのNintendo Switch版を購入し、先日ラスボスを撃破し、現在2周目をやっている。 FF12のサブイベントに「キャビンチーフ七姉妹」というものがあり、飛空艇定期便の「ゆったり飛空艇」の全航路にいるキャビンチーフのに話しかけるというイベントである。 全7航路あり、効率的にめぐる方法がないだろうか。 これは、グラフ理論の問題に落とし込めば解決できる。

オイラーグラフと準オイラーグラフ

あるグラフGがオイラーグラフであるとはGがオイラー閉路を持つことである。 オイラー閉路とはすべての辺を1回だけ通る閉路である。 また、あるグラフGが準オイラーグラフであるとは、Gがオイラー路を持つがオイラー閉路を持たないことをいう。 オイラーグラフは準オイラーグラフであるが逆は当然成立しない。

NetworkXで解く

御託はここまで、実際に都市を頂点、航路を辺とするグラフがオイラーグラフまたは準オイラーグラフであることをNetworkXで調べてみよう。

nodes = (
    "王都ラバナスタ",
    "ナルビナ城塞",
    "帝都アルケイディス",
    "港町バーフォンハイム",
    "空中都市ビュエルバ",
)
edges = (
    ("王都ラバナスタ", "ナルビナ城塞",),
    ("王都ラバナスタ", "帝都アルケイディス",),
    ("王都ラバナスタ", "空中都市ビュエルバ",),
    ("ナルビナ城塞", "帝都アルケイディス",),
    ("ナルビナ城塞", "港町バーフォンハイム",),
    ("帝都アルケイディス", "港町バーフォンハイム",),
    ("港町バーフォンハイム", "空中都市ビュエルバ",),
)

G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)

print(nx.is_eulerian(G))
print(nx.is_semieulerian(G))

結果は、

False
False

となる。 これは、空中都市ビュエルバ以外の頂点の次数がすべて奇数であり、オイラーグラフと準オイラーグラフの性質を満たさないから当然である。

俺達にはシュトラールがある

ところで、全航路たどれるタイミングではシュトラールが利用可能になっている。 つまり、辺を追加することで準オイラーグラフにすることができる。 ここで、王都ラバナスタと港町バーフォンハイムをシュトラールで移動することにする。

G.add_edge(*("王都ラバナスタ", "港町バーフォンハイム"))  # シュトラールで移動
print(nx.is_eulerian(G))
print(nx.is_semieulerian(G))

結果は

False
True

となり、準オイラーグラフとなった。

後は、オイラー路を求めれば所望の結果を得る。

for e in nx.eulerian_path(G):
    print(e)

結果は以下の通りである。

('帝都アルケイディス', '港町バーフォンハイム')
('港町バーフォンハイム', '空中都市ビュエルバ')
('空中都市ビュエルバ', '王都ラバナスタ')
('王都ラバナスタ', '港町バーフォンハイム')
('港町バーフォンハイム', 'ナルビナ城塞')
('ナルビナ城塞', '帝都アルケイディス')
('帝都アルケイディス', '王都ラバナスタ')
('王都ラバナスタ', 'ナルビナ城塞')

任意の都市間をシュトラールで移動できるからハミルトン閉路ではダメなのか?という疑問は、あくまでもすべての航路でキャビンチーフに話しかける必要があるのでハミルトン閉路ではなくオイラー閉路である必要があった。

『コンピュータ・システム』読書記録

図 2.4 のコード

オブジェクトのバイト表現を表示するコード。 ポインタのキャストを活用している。

#include <stdio.h>
#include <string.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len){
    size_t i;
    for (i = 0; i < len; i++){
        printf(" %.2x", start[i]);
    }
    printf("\n");
}

void show_int(int x){
    show_bytes((byte_pointer) &x, sizeof(int));
}

void show_float(float x){
    show_bytes((byte_pointer) &x, sizeof(float));
}

void show_pointer(void *x){
    show_bytes((byte_pointer)&x, sizeof(void *));
}

void show_strings(char *x){
    show_bytes((byte_pointer) x, strlen(x));
}

void test_show_bytes(int val){
    int ival = val;
    float fval = (float) ival;
    int *pval = &ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}

int main(){
    test_show_bytes(12345);
    char *s = "abcdef";
    show_strings(s);
    return 0;
}

問題2.11

ポインタ演算によるin-placeスワップと、配列を逆順にするコード。 全くもって見事に「ARR01-C. 配列のサイズを求めるときに sizeof 演算子をポインタに適用しない」に違反したコードを書いていた。 sizeofで配列の長さを計算しているのに...というバグをつぶそうと30分ぐらい時間をつぶした。

www.jpcert.or.jp

#include <stdio.h>

void inplace_swap(int *x, int*y){
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

void reverse_array(int a[], int cnt){
    int first, last;
    for (first = 0, last = cnt-1; first < last; first++, last--){
        inplace_swap(&a[first], &a[last]);
    }
}

void print_array(int a[], size_t len){
    int i;
    for (i=0; i < len; i++){
        printf("%d", a[i]);
    }
    printf("\n");

}

int main(){
    int b[5] = {1, 2, 3, 4, 5};
    print_array(b, sizeof(b) / sizeof(int));
    reverse_array(b, sizeof(b) / sizeof(int));
    print_array(b, sizeof(b) / sizeof(int));
    return 0;

}

問題2.13

VAXコンピュータには ANDとORの代わりにbisとbicという演算子があり…という件から始まる。

#include <stdio.h>

int bis(int x, int m){
    return x | m;
}

int bic(int x, int m){
    return x & (~m);
}

int bool_or(int x, int y){
    int result = bis(x, y);
    return result;
}

int bool_xor(int x, int y){
    int result = bis(bic(x, y), bic(y, x));
}

int main(){
    int x = 0x69;
    int y = 0x55;
    printf("%x | %x = %x\n", x, y, bool_or(x, y));
    printf("%x ^ %x = %x\n", x, y, bool_xor(x, y));
    return 0;

}

問題2.14

ビット演算と論理演算は別物ですよ、という問題

#include <stdio.h>

int main(){
    int x = 0x66;
    int y = 0x39;
    printf("%x & %x = %x\n", x, y, x & y);
    printf("%x | %x = %x\n", x, y, x | y);
    printf("~%x | ~%x = %x\n", x, y, ~x | ~y);
    printf("%x & !%x = %x\n", x, y, x & !y);
    printf("\n");
    printf("%x && %x = %x\n", x, y, x && y);
    printf("%x || %x = %x\n", x, y, x || y);
    printf("~%x || ~%x = %x\n", x, y, ~x || ~y);
    printf("%x && !%x = %x\n", x, y, x && !y);
}