【自習】「第44回シェル芸勉強会」の解答例【AWK】

問題および出題者による解答例:
- 【問題のみ】jus共催第44回シェル芸7周年で変態化が進みすぎなので実用的な問題しか出さないぞと宣言しておく勉強会（無保証） | 上田ブログ
- 【問題と解答】jus共催第44回シェル芸7周年で変態化が進みすぎなので実用的な問題しか出さないぞと宣言しておく勉強会（無保証） | 上田ブログ
参考リンク:
- jus共催第44回シェル芸勉強会リンク集 | 上田ブログ

ちなみに、タイトルにある「無保証」とは、「無」を保証するという意味らしいです……

A1:

$ awk -F '' '{for(i=1;i<=NF;i++)print NR-1,i-1,int((i-1)/3)+int((NR-1)/3)*3,$i}' sudoku > a.A1
$ head a.A1
0 0 0 5
0 1 0 3
0 2 0 *
0 3 1 *
0 4 1 7
0 5 1 *
0 6 2 *
0 7 2 *
0 8 2 *
1 0 0 6
# 答え合わせ
$ diff -qs a a.A1
ファイル a と a.A1 は同一です

第3フィールドの値を生成するint((i-1)/3)+int((NR-1)/3)*3を思いつくのに苦労しました。

A2:

# 前半のAWKワンライナー: 入らない数字を取得
# 後半のAWKワンライナー: 入らない数字の重複を除去
$ awk 'FNR==1{l++}{if(l==1&&$4!="*"){r[$1]=r[$1]" "$4;c[$2]=c[$2]" "$4;s[$3]=s[$3]" "$4}if(l==2){printf $0;if($4=="*"){printf r[$1]""c[$2]""s[$3]}printf "\n"}}' a a | awk 'NF==4{print}NF>4{printf $1" "$2" "$3" "$4;for(i=5;i<=NF;i++)n[$i]=$i;for(u in n)printf " "n[u];printf "\n";delete n}' > b.A2
$ head b.A2
0 0 0 5
0 1 0 3
0 2 0 * 3 5 6 7 8 9
0 3 1 * 1 3 4 5 7 8 9
0 4 1 7
0 5 1 * 1 3 5 7 9
0 6 2 * 2 3 5 6 7
0 7 2 * 3 5 6 7 8
0 8 2 * 1 3 5 6 7 9
1 0 0 6
# ファイルbに対しても入らない数字の重複を除去
$ awk 'NF==4{print}NF>4{printf $1" "$2" "$3" "$4;for(i=5;i<=NF;i++)n[$i]=$i;for(u in n)printf " "n[u];printf "\n";delete n}' b > b.uniq
# 答え合わせ
$ diff -qs b.uniq b.A2
ファイル b.uniq と b.A2 は同一です

1巡目で入らない数字をリストアップし、2巡目でリストアップされた数字を題意に沿うように出力するため、ファイルaを2回読み込んでいます。

後半のAWKワンライナーはあくまでも個人の好みです。

A3:

$ awk 'NF==4{print}NF>4{printf $1" "$2" "$3" "$4;for(i=1;i<=9;i++)n[i]=i;for(i=5;i<=NF;i++)delete n[$i];for(i in n)printf " "n[i];printf "\n"}' b > c.A3
$ head c.A3
0 0 0 5
0 1 0 3
0 2 0 * 1 2 4
0 3 1 * 2 6
0 4 1 7
0 5 1 * 2 4 6 8
0 6 2 * 1 4 8 9
0 7 2 * 1 2 4 9
0 8 2 * 2 4 8
1 0 0 6
# 答え合わせ
$ diff -qs c c.A3
ファイル c と c.A3 は同一です

配列も連想配列も区別なく連想配列として扱うAWKならではの解答になりました。

A4:

$ awk '{print $1+1,$2+1,$4}' c | awk '{d[$1][$2]=$3}END{for(r=1;r<=9;r++){for(c=1;c<=9;c++){printf d[r][c]}printf "\n"}}' > sudoku_1
$ cat sudoku_1
53**7****
6**195***
*98****6*
8***6***3
4**8*3**1
7***2***6
*6****28*
***419**5
****8**79

二次元配列を使うと(Q1〜Q3に比べると)比較的簡単に解くことができました。

A4の付録:

# AWKで書かれた数独のソルバーに丸投げ
$ sed 's/\*/0/g;s/./& /g' sudoku_1 | awk -f <(curl -s https://www.thegeekstuff.com/scripts/solve.awk) | sed '/^$\|#/d' | tr -d ' '
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

数独のソルバーがAWK製とは……素晴らしい。

なお、curlで取得したスクリプト類の直接実行はセキュリティ上、本来は行わないほうが良いと思います。

A5:

$ Rscript -e 'options(digits=16);f<-function(x){log(cos(x))};integrate(f,0,0.5)'
-0.02138053681540822 with absolute error < 2.4e-16

よわよわシェル芸人なので、Rに積分の計算を丸投げしてみました。

A6:

$ awk 'BEGIN{i=1;j=1}FILENAME=="speech2"{l[i]=$0;i++}FILENAME=="speech"{if(!$0){print l[j];j++}else{print}}' speech2 speech
このうんこを作った
のは誰だあっ!!う
んこも休み休み言え
春はあけぼの。夏は
夜。秋は夕暮れ。冬
はうんこハァ　テレ
ビも無ェ、うんこも
無ェ、生まれてこの
かた見だごとア無ェ
やつはとんでもない
ものを盗んでいきま
した。あなたのうん
こですお前それうん
こでも同じ事言えん
の？疲れからか、

現在の入力ファイル名を格納しているAWKの特殊変数FILENAMEを利用することで簡単に解くことができました。

ラスボスのQ7と戦う前に一休み、といった感じの問題でしょうか。

A7:

小問1:

# `-M`オプションでMPFR拡張による任意精度演算を可能にする
$ awk -M '{for(i=1;i<=NF;i++)$i=$i^200%437;print}' message
35 308 26 282 399 87 349 55 308 55 85

小問2:

# 総当りで復号化を試みる
$ awk -M '{for(i=1;i<=1000;i++){printf i": ";for(j=1;j<=NF;j++)printf "%c",$j^i%437;printf "\n"}}' message | grep -Pa '^\d+: [[:ascii:]]+$'
unko_jyanai
unko_jyanai
unko_jyanai
unko_jyanai
unko_jyanai

小問3:

# RSA暗号らしきものを愚直に実装して復号化
$ awk -M 'function gcd(m,n, t){while(n!=0){t=m;m=n;n=t%n}return m}function lcm(m,n, r){if(m==0||n==0)return 0;r=m*n/gcd(m,n);return r<0?-r:r}BEGIN{N=437;"factor "N | getline;split($0,pq," ");L=lcm(pq[2]-1,pq[3]-1);for(i=2;i<=L;i++){E=i;if(gcd(i,L)==1)break};for(i=2;i<=L;i++){D=i;if((E*i)%L==1)break}}{for(i=1;i<=NF;i++)printf "%c",$i^D%N;printf "\n"}' message
unko_jyanai

小問3の付録:

# 小問3が復号化ということで暗号化してみた
$ printf unko_jyanai | grep -o . | while read l; do printf '%d\n' \'$l; done | awk -M 'function gcd(m,n, t){while(n!=0){t=m;m=n;n=t%n}return m}function lcm(m,n, r){if(m==0||n==0)return 0;r=m*n/gcd(m,n);return r<0?-r:r}BEGIN{N=437;"factor "N | getline;split($0,pq," ");L=lcm(pq[2]-1,pq[3]-1);for(i=2;i<=L;i++){E=i;if(gcd(i,L)==1)break}}{printf (NR==1?"%d":" %d"),$1^E%N}END{printf "\n"}'
262 325 122 80 266 406 163 89 325 89 326

RSA暗号にまつわる問題とのことです。小問1と小問2はまだ楽だったのですが、小問3の解答がなかなか思い浮かばなくて苦労しました。

非常に難しい問題でしたが、情報セキュリティを支える暗号技術を身近に感じることができ、解いていて楽しかったです。

みなさんもぜひ、ワンライナーでRSA暗号を楽しんでみてください。

今回はAWKで解くことを前提とした問題が多かったこともありますが、AWKは地味ながらもかなり使える言語(なお、ゲームも作成可)であることを再確認することができました。

母親の認知症の進行にともない、自由時間が一日で一時間に満たないような日が近頃多いですが、できる範囲でシェル芸に触れ続けていこうと思います。

Written on December 2, 2019