SHIINBLOG

エンジニアを説明上手にする本を読んだ

エンジニアを説明上手にする本 を読んだ.

わかりやすく説明するために,
分類してラベルをつけて説明する.
使う用語や関心についてターゲットを分析することなどが説明されていた.

プレゼンテーションについても触れており,
ジェスチャーは3秒キープすることや間についての説明などもある.

情報を構造化するパターンについても説明があった.

言っていることはとても分かる.凄く説明が上手くいきそうだと思った.
悪くない.悪くないんだけど…
日本語が頭に入ってこない…

3度くらい読むの挫折しそうになった.

YAPC::Tokyo に参加しました!

目次

  1. なぜ参加しようと思ったか
  2. 当日
    1. 2019年冬のPerl
    2. Perl to Go
    3. ランチ
    4. Perl5の静的解析入門 機械と人間双方の歩み寄りによる平和編
    5. PerlプログラムでPerlプログラムを修正する方法
    6. レガシーPerlビルド 〜現代に蘇るPerl[1..5].0とPerl6〜
  3. その後

なぜ参加しようと思ったか

実は Perl ほとんど知りませんでした.

Perl 入学式に参加したノリでそのまま行ってみるか〜って気分になったのが理由ですね.
Perl 入学式の記事は こちら




当日

寝坊してしまって,オープニングを見逃してしまいました…
着いたのは, 11:40 を超えていたので, 2019年冬のPerl から見始めました.


2019年冬のPerl

Comma IDE の辺りから聞きました.
Perl 6用の IDE が開発進んでるんですね.
Perl 知らないけど, Perl 6 面白そうだなぁとか思っています.

最後の方しか聞けなかったのが残念だったんですが,
紹介にあった Learning Perl 6 を読んでみたいなと思っています.

次は何を見るか迷ったんですが, Golang ほんの少し触った事があったので,
そのまま Perl to Go を見ることにしました.



Perl to Go

Golang は書いたことがあったのですが,
Web API を書いたこともなかったので,あんまり追いつけなかったのが正直なところです…

net/http が便利そうだなぁと思ったので,今度触ってみたいなぁと

「ここにコードを書く と書いてますが書いてませんね」とかあったり,結構笑いました.



ランチ

ランチは,学生支援ということで企業の方の発表を聞き,お話しさせていただきました.
県外の大学生の方ともお話できたので,楽しかったです.



Perl5の静的解析入門 機械と人間双方の歩み寄りによる平和編

静的解析という言葉に惹かれて見に行きました.
Perl 5 での,静的解析ツールはいくつかあるそうなんですが,
Pattern-based Perl Recognizer の紹介をしていました.

なるほど完全に理解したって感じでした.
Perl を書いてみて,使ってみたいなぁという気分になりました.

「これだから Perl は!」 からの
コードの迷いは思考の迷い 一呼吸おいて,もう少し考えようというのは,
面白かったです.



PerlプログラムでPerlプログラムを修正する方法

次もタイトルに惹かれて,このお話を聞きました.
が,当日かなり体調が悪くあまり覚えていません…

「会社にはクソコードいっぱいある」というセリフだけは覚えています.



レガシーPerlビルド 〜現代に蘇るPerl[1..5].0とPerl6〜

学校の後輩ということもありましたが,体調不良の惰性でそのまま聞きました.
Perl って古い方がビルドしやすいのかぁって感じでした.

なぜか Perl 1.0 がメンテされていて,テスト通過率 100% のバージョンが存在するという事実に笑いました.

Perl 1.0 のソース見てみたいなぁと.




その後

本当は懇親会まで参加するつもりだったんですが,
座っているのも辛かったので,帰ってしまいました…

ホテルに戻って体温計を借りたら, 39度近くあったので,そのまま寝ました.

本当に残念だったので,次回にはちゃんと参加したい!
まずは,普段のスクリプトPerl で書いてみようかなぁと思っています.

最後になりますが, YAPC::Tokyo の運営ありがとうございました.
また,学生支援本当にありがとうございました.

次回までには YAPC を 100% 楽しめるように勉強します.

Perl入学式 に 中途入学しました

Perl入学式in沖縄 第4回 〜サブルーチン/正規表現編〜 に参加しました.


あるツールのインターフェースが Perl で書かれていて,読めなかったのと,
いろいろあって少し興味があったので参加してみました.


一応,1回〜3回までの資料を見ながら復習(?)はして行きました.


第4回は,ちょうど分からなかった,@_ の説明とかがあって, 良かったです.


メモ程度にまとめておく(:3」∠)

  • @_ は,サブルーチンの引数がまとめて入った配列
  • $x = shift @_ とか ($x, $y) = @_ したら取り出せる
  • ($x, $y, @array) = @_ とかして 2つはスカラー,後は配列みたいにできる

全体としてはこんな感じ…?

sub func {
    my $x = shift @_;
    print "$x\n";
}

func(10);


これでインターフェースの Perl スクリプト読めるぞ〜

CADDi 2018 for Beginners

CADDi 2018 for Beginners に参加しました.

またもや気付いたら始まっていた…
まぁ,言い訳は置いといて,



結果的には全部解けました.
A → B → D → C の順で解いた.

A - 12/22

問題文はこちら

4桁の整数が与えられて, '2' が何個現れるか求めるもの.

C++ で解いたので, string で受けて,単純に'2'の数を数えた.

#include <iostream>
#include <string>

using namespace std;

int count_char(string s,char x) {
    int count;
    for (auto c : s) {
        if ( c == x ) {
            count++;
        }
    }
    return count;
}

int main(){
    string s;
    cin >> s;
    cout << count_char(s,'2') << endl;
}



B - AtCoder Alloy

問題文
hight と width が与えられて,それ以上の金属板はいくつあるかみたいな問題.

これもすぐに書き終わったかな.

#include <iostream>

using namespace std;

int main(void) {
    int n,h,w;
    int count;

    cin >> n;  cin >> h;  cin >> w;
    for(int i=0; i<n; i++) {
        int a,b;
        cin >> a; cin >> b;
        if( h <= a && w <= b ) {
            count++;
        }
    }
    cout << count << endl;
}



D - Harlequin

一応解いた順番にD問題から.
問題文

交互にリンゴを食べていって,最後のリンゴを食べるのはどちらかっていう問題.


問題を眺めながら紙に書いてたら何か神が降りてきて,

2 で割った余りが全部 0 なら second の人が勝つのでは?
と思って実装してみたら合ってた.

#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int n;
    string winner = "second";
    cin >> n;
    

    for(int i=0; i<n; i++) {
        int a;
        cin >> a;
        if ( a % 2 != 0 ) {
            winner = "first";
        }
    }
    cout << winner << endl;
} 

よく見たら, winner = "first" としている部分で break した方が良いのでは…?



C - Product and GCD

問題文

D 問題解く前に1度見て,ぱっと見思いつかなかったので,一旦放置した問題.

なんとなく素因数分解使えそうだな〜と考えていて,

n個に分解するんだから,素因数分解したときの素数がn個以上あれば,それが最大公約数に含まれるじゃん!
と気付いた.


それで,最初書いたのだけれど,
2*n個以上ある場合を考えていなかったので,
問題によっては,WA(間違い)になってしまった.

全然間違っている理由が分からなくて,
いろいろ変えて提出したので間違いだらけになってしまった.
intlong long にしてみたりとか)

#include <iostream>
#include <unordered_map> 

using namespace std;

std::unordered_map<long long,long long> c;

void decompositPrime(long long n)
{
    long long a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            n /= a;
            c[a] += 1;
        } else {
            a++;
        }
    }
    c[n]++;
}

int main(void) {
    long long n;
    long long p;
    long long ans=1;
    cin >> n;  cin >> p;
    decompositPrime(p);
    
    for (auto itr = c.begin(); itr != c.end(); itr++) {
        // if ( itr->second >= n ) {
        while ( itr->second >= n ) {
            itr->second -= n;
            ans *= itr->first;
        }
    }
    cout << ans << endl;
}



今回は, Beginners だけど, 267位だったので,
40分ほど遅れてスタートした割りには良い方なんじゃないだろうか.

初めての競プロ

本日初めて AtCoder Grand Contest 029 に参加しました.

なんだかんだで初めての競プロです.

大学入ってすぐに,何ヶ所か競プロのサイトに登録していたのに
1回も参加した事が無かった…

気付いたときには始まっててちょっと焦った


結果は惨敗でした.
Grand じゃなくて Beginners に参加したかった…


不慣れということと,1回目でタイムアウトが出てしまってとても焦ってしまった.
結局時間内に1問も解けなかった.



落ち込んでいても仕方が無いので,
次のためのお勉強をし(他の人が出した物を読み解き)ます.



A - Irreversible operation

問題文はこちら

「黒白 の並びならひっくり返す」を繰り返して何回ひっくり返せるかという問題.

最初は,1週 「黒白」 をひっくり返しつつ探して,というのを繰り返すプログラムを書いた.
(時間制限が 2sec だったから無理な気はしていた)


次に, string.h の strstr を使ったら早いんじゃないかと使ってみた.
結果は タイムアウト 変わらず…


最後らへんに 「黒白」を見つけたときに,その前の黒を数えたら良いのではないかと考えた.
「黒黒白」 なら 2回ひっくり返せるみたいな.

これ実装して提出したら,いくつか不正解に. タイムアウト ではなくなったものの,何が間違ってるのか分からなくて,
悩んでる間に終了してしまった.


ということで,一番最初に解いていた方のソースコードを参考にする.

まず,準備具合が違いますね.

#define sqr(x) ((x)*(x))

とか

#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)

とか用意している.

求解のアルゴリズム的には, 黒 ならカウントの変数をインクリメントして,白が来たらそれを解用の変数に足すもの.

僕のアルゴリズムの上位互換みたいな感じがする…


確かに 黒 が連続の後に 白 が来た場合,1つずれるだけなので,ひっくり返せる回数は増えていく.


僕が最後に考えていたアルゴリズムは,
黒 を数えつつ 白 に 変えていったけど,最後の 黒 1つだけを 白 にすれば良くて,
ルールを表現できていなかったみたい.



ということで書き直してみたのだけど,これを提出しても タイムアウト

#include <stdlib.h>
#include <stdio.h>

#define BUF_SIZE 200010
int main(void){
    unsigned long long count = 0;
    char s[BUF_SIZE];
    int i;
    int j;
    fgets(s, BUF_SIZE, stdin);
    for(i=0; i<BUF_SIZE; i++) {
        if( s[i] == '\n' || s[i] == '\0') {
            break;
        }
        
        if( s[i] == 'B' && s[i+1] ==  'W' ){
            count++;
            
            for( j = 1;  (i-j) >= 0; j++) {
                if( s[i-j] == 'B') {
                    count++;
                } else {
                    s[i-j+1] = 'W';
                    break;
                }
            }
            
            if( j == 1) {
                s[i] = 'W';
            }
            s[i+1] = 'B';
        }
    }
    printf("%llu",count);
}

やっぱり,こっちアルゴリズムを考えつく必要がありそうだ


次までに,今回の AGC029 の別な問題とか,前の大会の問題を解いて高速に求解できるようにならないといけないなぁと実感した.

楽しい楽しい SAT符号化

琉大情報工学科(知能情報コース) Advent Calendar 2018 10日目の記事です.

SAT 符号化についてまとめているところが無くて,とても苦労したのでまとめておく.

SAT符号化とは,制約充足問題や制約最適化問題などを SAT 問題(充足可能性問題:Satisfiability Problem)に変換することである.

近年, SAT問題を解く SATソルバーは高速になっている.
そのため,制約充足問題専用のソルバーを使用するより, SAT符号化を行い SATソルバー*1を使用した方が高速に解くことができる場合がある.
まず, SAT問題について説明する.

SAT問題

SAT問題(Satisfiability)は,与えられた命題論理式または関数が充足可能(SAT)であえるか,充足不能(UNSAT)であるかを判定する問題である.

充足可能とは,命題論理式の命題変数に対し,T または F を割り当てて,式全体が T となる割り当てが少なくとも1つ存在することを言う.

例えば,f=( A ∨ B) ∧ (¬ A ∨ B) ∧ (A ∨ ¬ B) という関数は,以下に示すように A = TB = T の時に関数f が真となる.つまり,関数f は充足可能である.

A B f
T T T
T F F
F T F
F F F

充足不能な例は, A ∧ ¬A などである.A ∧ ¬A は,A に T,F どちらを割り当てても式全体は F となる.


ハードウェアやソフトウェアの検証,制約充足問題,スケジューリング問題などの問題を SAT問題に置き換えることができる.そのため, SAT問題を解くアルゴリズムが研究されてきた. それにより,近年 SATソルバーの性能が向上し非常に高速に SAT問題が解けるようになった.

そこで,制約充足問題などを SAT問題へ符号化し, SATソルバーで解を求める SAT符号化の研究もされるようになった.

SAT問題は,連言標準形(Conjunctive Normal Form: CNF)の論理式を与えられることが多い. CNF は,節の連言(∧)であり,節はリテラル(命題変数またはその否定)の選言(∨)である. 具体例としては,上で出てくる ( A ∨ B) ∧ (¬ A ∨ B) ∧ (A ∨ ¬ B) などである.

これ以降は,連言を省略して節を並べて表記する.


SAT符号化

SAT符号化は,直接符号化法順序符号化法,対数符号化法 などが提案されている*2



直接符号化法

x = 0 を表す命題変数p(x=0) を導入する.

x が 0 から 4 の範囲を取る場合(x ∈ [0,4]),
p(x=0) から p(x=4) までを導入する. x は 0 から 4 のどれかの値を取るため,次のような式をたてる.

p(x=0) ∨ p(x=1) ∨ p(x=2) ∨ p(x=3) ∨ p(x=4)

これで,0 から 4 のどれかであるという命題変数が真となる必要がある. at-least-one 節と呼ばれるもの.少なくとも1つを満たす必要がある.

また,0 から 4 が同時に成り立つことは無いため,排他になるようにする.

¬p(x=0) ∨ ¬p(x=1)
¬p(x=0) ∨ ¬p(x=2)
¬p(x=0) ∨ ¬p(x=3)
        ⋮
¬p(x=2) ∨ ¬p(x=3)
¬p(x=2) ∨ ¬p(x=4)
¬p(x=3) ∨ ¬p(x=4)

こんな感じ これは,A → B(A ならば B) の変形 ¬A ∨ B と考えることができる. p(x=0) ならば ¬p(x=1) である.
これが, at-most-one 節と呼ばれるもの.最大で1つのみが真となる.


他に x ≦ 2 などの制約がある場合,その制約に違反する点をあげる.

¬p(x=3)
¬p(x=4)

となる.

x ∈ [0,4] と x ≦ 2 を符号化したものを全て SATソルバーに与えると, SAT であるという答えと一緒に

p(x=0) ¬p(x=1) ¬p(x=2) ¬p(x=3) ¬p(x=4)

など SAT な解の1つを返してくれる.

x+1 ≦ y なども,違反点をあげていけば符号化できる.

¬p(y=1) ∨ ¬p(x=1)
¬p(y=1) ∨ ¬p(x=2)
       ⋮

という感じ. p(y=1) ならば ¬p(x=1) (y=1 のとき, x=1 なら x+1 ≦ y が成り立たないので) y=2 のときなども全部違反点を上げるため節がとても多くなる…



順序符号化法

x ≦ 0 を表す命題変数p(x≦0) を導入する.

同じように x ∈ [0,4] を表すと,

¬p(x≦0) ∨ p(x≦1)
¬p(x≦1) ∨ p(x≦2)
¬p(x≦2) ∨ p(x≦3)

という感じ. p(x≦4) は常に真となるので,不要.

この命題変数の真理値表を書くと,数が表現できていることが分かる.

p(x≦0) p(x≦1) p(x≦2) p(x≦3) x
F F F F 4
F F F T 3
F F T T 2
F T T T 1
T T T T 0

命題変数の組み合わせは上の表しかなく, x の値を判断できる.

こちらは,直接符号化法の at-least-one 節や, at-most-one 節は,不要で, 節数も少なく表現できる.


x ≦ 2 などは違反する範囲をあげれば良い.

¬p(x≦3)

直接符号化法は違反点をあげるのに対し,順序符号化法は違反範囲をあげるため, 線形制約は簡単に符号化ができる.


x+1 ≦ y は少しだけ複雑になる.

y=1 のとき,p(y≦0) が偽,p(y≦1) が真となるので,
y=1 は, ¬p(y≦0) ∧ p(y≦1) である.

つまり,(¬p(y≦0) ∧ p(y≦1))→ p(x≦0)(y=1 ならば, x は 0 以下である)という形になって,
A→B = ¬A ∨ B の変形とド・モルガンを適用して変形すると,p(y≦0) ∨ ¬p(y≦1) ∨ p(x≦0) となる.

y=1 のときは,恩恵が微妙だけど, y=3 のときなどは,
p(y≦2) ∨ ¬p(y≦3) ∨ p(x≦2) だけで違反する範囲をあげることができるので,
少ない節数で表現できる.



対数符号化法

x や y などの変数を2進表記で考える符号化である.
{ \displaystyle
x = (x_2, x_1,x_0)_2
} として表現する.

x ∈ [0,4] は,違反するビットを否定する.
¬{ \displaystyle x_2} ∨ ¬{ \displaystyle x_0}
¬{ \displaystyle x_2} ∨ ¬{ \displaystyle x_1}

こんな感じで, 5(101)や6(110),7(111)が現れないようにする.

全て偽の場合は,0 となるので,こちらも at-least-one 節や, at-most-one 節と呼ばれるものはない.


x ≦ 2 なんかは,上と同じように違反するビットを否定すれば良い.
¬{ \displaystyle x_2}
¬{ \displaystyle x_1} ∨ ¬{ \displaystyle x_0}



この程度なら良いのだけど,
( x+5 ≦ y ) ∨ ( y+8 ≦ x) みたいなやつがたくさんあると,
対数符号化法 上手くいかない…
辛い…


誰かこの記事見て面白いと思った人一緒に考えてくれ〜〜〜 @e145755 リプライ待ってます_(:3」∠)_

論理学も勉強中なので,一緒に勉強してくれる人居たら声かけて_(:3」∠)_

親知らず4本 一気に抜歯した

人生初めての入院・全身麻酔が親知らずの抜歯だった.

9/6 くらいに歯茎が腫れて?
噛み合わせると歯に挟まれて痛い状態に…

歯肉炎…?

歯医者さんに行ってみると,

「親知らずのせいで歯茎が腫れてますね〜
 ここでは抜けないので口腔外科行ってくださいね」
とのこと.

3本抜いた方が良いかもと言われた.

口腔外科に行ってみると
「4本ありますが全部抜きますか?」
って言われて,3本じゃ無いのか…って思った.


上下左右に1本ずつ.
下の歯が水平に生えていて,神経もわりと近いらしい
さらに上の歯の片方は上顎洞に貫通しているみたい.

相談した結果
入院して全身麻酔で抜くことになった.
「時間あるなら一気に行った方が楽ですよ〜
 難易度高いので抜く方も全身麻酔の方が気が楽ですし」
って

手術日が 9/26 に決まり,
前日から入院した.


手術自体は,気付いたら終わっていた.

手術室からベッドごと病室に運ばれて,
顔も上がらないし周りも見えない状況で
「抜いた歯こんな感じですよ」って見せられた

僕は「(いや,見えないし…なんなら少し顔上げるのも辛いんだけど…)」って感じだった.

その後は,ひたすら寝ていた.


次の日の朝食は,お粥とか柔らかいものが出てきたけど,
痛い…

血は出ていなかったので,我慢して食べた…

そして,そのままお昼後に退院
状態が悪ければ延びたかもしれないけど, 2泊3日で退院することができた.


家では,お粥とか白和えとか,茶碗蒸しとか食べて生活した.

今日10/6 手術の10日後抜糸をした.


順調に回復しているようで一安心.

だけど,(削ったであろう)アゴがとても痛いので,
しばらくは堅めなもの食べられ無さそうだ…