次ログ

次ログ

プログラミング系の記事多め。GoやJavaFXで自作のツールを公開したり、イラストを配布してます。

第42回 シェル芸勉強会振り返り

まえがき

2019/06/15に「jus共催 第42回BLACK HOLEシェル芸勉強会」へ参加してきたのでその振り返り。 今回の名前は前回のブレース展開と違って普通の名前だった。

いわくここでいうBLACK HOLEは「アトランティスの謎 42th」を指すものだったらしい。 僕はアトランティスの謎というゲームを知らなかったけれど、ニコ動の何かの動画で 無限に落下するシーンを見たことはあった。

シェル芸の様子はこちら。

togetter.com

問題

Q1 正の整数の組(x, y, z)について、x + xy + xyz = 1234, x < y < zを満たす組み合わせを全て選んでください

競技プログラミング的な問題。普通に3重ループで実装したら計算量が 12343 になってとんでもないことになる。 例えば以下のような。(僕の回答)

for x in {1..1234}; do
  for y in {1..1234}; do
    for z in {1..1234}; do
      n=$((x + x*y + x*y*z))
      if [ $n -eq 1234 ]; then
        echo "x=$x y=$y z=$z"
      fi
    done
  done
done

一応この回答でも全然終了しないけれどそのうち計算は終了する。 けれど、それではこの問題を用意した意図に応えられていない。

x + xy + xyz == 1234 and ( x < y < z ) というこの問題、ぱっと問題を見た時ではわからなかったけれど、これは普通の数学の問題だった。

x + xy + xyz == 1234を式変形するとx(1 + y + yz) == 1234と等価になる。

これを更に式変形するとx(1 + y(1 + z))になる。

これはx * N == 1234と言い換えられるが、このNが何通り考えられるかを考える。 この1234を素因数分解すると、次のようになる。

% factor 1234
1234: 2 617

このことからxとNの組み合わせは次の通り考えられる。

  • x == 1 のとき N == 1234
  • x == 2 のとき N == 617
  • x == 617 のとき N == 2
  • x == 1234 のとき N == 1

しかし、前提条件として(x < y < z)が与えられているため、最終的に次のようになる。

  • x == 1 のとき N == 1234
  • x == 2 のとき N == 617

この時点で総計算量を比較してみる。

  • 1234 x 1234 x 1234 = 1879080904 (18億7908万)
  • 2 x 1234 x 1234 = 3045512 (304万)

304万オーダーならまぁ普通に計算できる計算量なので、僕の最初に考えたシェルは次のように修正できる。

for x in {1..2}; do
  for y in {1..1234}; do
    for z in {1..1234}; do
      n=$((x + x*y + x*y*z))
      if [ $n -eq 1234 ]; then
        echo "x=$x y=$y z=$z"
      fi
    done
  done
done

awkを使うともっと短くかける。

echo {1,2}" "{1..1234}" "{1..1234}"\n" | awk '$1 < $2 && $2 < $3 && $1 + $1 * $2 + $1 * $2 * $3 == 1234'

Q2 次のファイルの文章内の絵文字を全て💩に変えてください

$ cat oji
あれ(^_^;さのチャン、朝と夜間違えたのかな❗❓⁉俺はまだ起きてますよ〜😃 ちょっと電話できるかナ( ̄ー ̄?)⁉天気悪いと気分もよくないよね😱じゃあ今日は会社休んで俺とデートしヨウ💕ナンチャッテ🎵(笑)😘

僕のはじめの回答はこんなかんじ。あらゆる絵文字に対応できる方法が思いつかなくて、明らかに手抜きな回答になった。

cat /ShellGeiData/vol.42/oji | sed -E  "s@$(cat /ShellGeiData/vol.42/oji | grep -o . | sort | head -n 9 | tr '\n' '|')z@💩@g"

なにをやっているかというと、sed拡張正規表現の文字列を作っている。なんとなく sortして戦闘の文字列を確認したらいい感じに絵文字が先頭に偏っていたのでそれを9 文字決め打ちで取り出している。

% cat ShellGeiData/vol.42/oji | grep -o . | sort | head -n 20
❗
❓
⁉
⁉
😃
😱
💕
🎵
😘
 
(
;
?
^
^
_
、
 ̄
 ̄

これを正規表現のORでつなぐ。

% cat ShellGeiData/vol.42/oji | grep -o . | sort | head -n 9 | tr '\n' '|'
❗|❓|⁉|⁉|😃|😱|💕|🎵|😘|

すると正規表現の最後にORだけが残ってしまう。 めんどくさかったのでもとの文字列に出現していなかったzを付け足した。

% echo "s@$(cat ShellGeiData/vol.42/oji | grep -o . | sort | head -n 9 | tr '\n' '|')z@💩@g" 
s@❗|❓|⁉|⁉|😃|😱|💕|🎵|😘|z@💩@g

これをsed -Eに渡してやれば、絵文字をすべて💩に置換できる。 かなり雑だし問題しかない。 正しい回答はnkfawklength関数を使う方法。

上田先生のブログより引用。

$ grep -o . oji | LANG=C awk '{printf length($1)==4?"💩":$1}' | awk 4

Q3 (要約)素数のときに任意の値を出力してください

2: きつねうどん
3: ブラウンソース定食
4:
5: 鉄皿ブラウンソースハンバーグセット
6:
7: きつねうどん ミニプレミアムおろしポン酢牛めしセット
8:
9:
10:
11: 鉄皿ブラウンソースライス
12:
13: 担々うどん(プレミアム牛肉使用)
14:
15:
16:
17: とろたまうどん ミニポン酢ポン酢牛めしセット
18:
19: 豚カルビ丼
20:

僕の回答(ただしゴミが残ってるし、間違ってる)

% paste -d : <(seq 20) <(seq 20 | while read i; do factor $i | cut -d : -f 2- | awk -F " " '{print NF}'; done | sed -E 's@^1$@'"$(ojichat)"'@g')
1:0
2:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
3:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
4:2
5:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
6:2
7:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
8:3
9:2
10:2
11:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
12:3
13:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
14:2
15:2
16:4
17:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
18:3
19:吏花ちゃん、愛しいなぁモウ😘🎵(^з<)こんなに可愛く💕😄(^з<)なっちゃったら天使みたいでオジサン困っちゃウヨ(・_・;(^_^;
20:3

まず、ループしてfactorに引数としてわたして素因数分解する。

% seq 20 | while read i; do factor $i;done
1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5
11: 11
12: 2 2 3
13: 13
14: 2 7
15: 3 5
16: 2 2 2 2
17: 17
18: 2 3 3
19: 19
20: 2 2 5

この時、素数のものは:で区切られた右側の文字は1つしかないはず、と考えた。 よって、:で区切った2フィールド目の文字列のみを取得し、さらに空白区切るのフィールドの数を数えれば、素因数の数が取得できる。

% seq 20 | while read i; do factor $i | cut -d : -f 2- | awk -F " " '{print NF}'; done
0
1
1
2
1
2
1
3
2
2
1
3
1
2
2
4
1
3
1
3

あとは1だけをsedで置換すれば一応僕の回答にはなる。間違っているけれど。

% seq 20 | while read i; do factor $i | cut -d : -f 2- | awk -F " " '{print NF}'; done | sed -E 's@^1$@'"$(ojichat)"'@g'
0
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
2
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
2
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
3
2
2
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
3
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
2
2
4
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
3
えみこ、愛しいなぁもウ😃♥ (^o^)可愛すぎてボクお仕事に集中できなくなっちゃいそうだよ(◎ _◎;)どうしてくれるンダ😃✋
3

何が間違っているか、というと。

  1. 余計な数字が残っている
  2. ojichatの実行結果が毎回同じになっている。

この回答のだしかたが良くなかったのもあるけれど、この回答に会えて修正を入れるなら次のようにすればこの問題の解になる。

% paste -d : <(seq 20) <(seq 20 | while read i; do factor $i | cut -d : -f 2- | awk -F " " '{print NF}'; done | sed -E 's@^1$@ojichat@ge; s/^[0-9]+$//g')
1:
2:えいはチャン、可愛らしいネ😍😃♥ 可愛すぎてオジサンお仕事に集中できなくなっちゃいそうだよ(・_・;(T_T)(◎ _◎;)^^;どうしてくれるんダ😚(笑)❗
3:おはよー!チュッ(^з<)早く会いたいナ(^_^)😍❗
4:
5:センリチャン、お早う(^_^)😍😆センリチャンと一緒に今度ランチ、したいなァ(^o^)💗(^_^)風邪ひかないようにね😚(^_^)😆😘
6:
7:風邪ひかないようにね💕💗オイラはももきちゃん一筋だよ🤑✋
8:
9:
10:
11:美佐穂チャン、オッハー(^_^)(^o^)美佐穂チャンにとって素敵な1日になりますようニ😄
12:
13:今日も大変だったんだネ(-_-;)よく頑張ったね💕えらいえライ😄😃☀ 
14:
15:
16:
17:みゆきちゃん、可愛らしいね(^з<)(^_^)こんなに可愛く(^o^)😃♥ なっちゃったらお姫様みたいでオジサン困っちゃウヨ(・_・;(-_-;)😱( ̄Д ̄;;
18:
19:帆夏チャン、そっちも快晴なのかな😜⁉️水曜日は仕事〜❓( ̄ー ̄?)😜⁉️よく頑張ったね🎵(^_^)えらいえらイ(笑)😘
20:

修正したのはここ。

sed -E 's@^1$@ojichat@ge; s/^[0-9]+$//g'

いきなりojichatの実行結果をsedの置換式に埋め込むのではなく、ojichat自体を埋め込んでeで実行するようにした。 そのあと数字だけ残っている行を消す置換をすることで完成。

Q4 数字を打たずに3を出力してください

難読化シェル芸。僕の回答は下記。

echo $(( $(echo a | grep x)$? + $(echo a | grep x)$? + $(echo a | grep x)$? ))

grepで検索にマッチするものが存在しなかった時、終了コードは1になる。 それを$?で取得してbashの算術演算で加算している。

ただ他の方の回答ではより難読化しているものがあった。 面白かったのは以下。

% echo $(( $$/$$ + $$/$$ + $$/$$ )) 
3

$$はプロセスIDである。プロセスIDをプロセスIDで割ると当然1になる。あとはそれを加算している。

あとは僕が思いついたしょーもない回答。

$ unko.tower | wc | sed -E 's/|/ /g' | awk '{print $NF}'
3

なんなのかというとunko.towerの文字の数を数えたらたまたま一番最後の文字が3だったのでそれを取得している。 sedですべての文字を空白で区切り、awk$NFで一番最後の文字を取得した。

Q5 アルファベットを打たずにlsを実行してください

これも難読化。 パス補完の機能を使えばいいんだろうというのはわかったが、「アルファベットを使わずに」というのはわからなかった。 回答としてはこうなるらしい。

% echo /???/??
/bin/cp /bin/dd /bin/df /bin/ed /bin/ip /bin/ln /bin/ls /bin/mt /bin/mv /bin/nc /bin/ps /bin/rm /bin/sh /bin/ss /bin/su /dev/fd /etc/hp /etc/i3 /etc/pm /sys/fs


% __=(/???/??); ${__[7]}
oji

これはなるほど〜となった。 パス補完を配列として変数に追加して、決め打ちで配列のインデックスを指定して取得する、という。 lsが何番目に位置するかは環境によって変わるので、そこは適宜読み替える必要がある。

Q6 飛行機アイコンのみを左右反転させる

まさか僕が作ったtextimgというコマンドが問題の中で使われると思っていなくて驚いた。 なお問題は解けなかった。

問題の回答にのためにいろんな方がtextimgをインストールしようとして苦戦していたのが印象に残った。 インストールに時間がかかっていたようで、Go自体のインストールに時間がかかっていたのだと思われる。

あとは一応単体で動作する実行可能バイナリも配布していたが、絵文字とかの描画を可能にするにはさらに環境変数とかフォントを整える必要があるので おそらくそのあたりで躓いたのかなぁと考えている。

一応整備するべき環境変数についてはREADMEには書いておいたが、いきなりそれをやれというのはやはり難しいので 手軽に試せるDockerfileも用意しておこうと思った。 (Dockerを使えるようにするのが難しいとかはまた別の話)

Q7 素数の桁が変わる直前のところで改行を入れてください

$ seq 1000000 | factor | awk 'NF==2{print $2}' | tr \\n ' ' 
ここからパイプをつなげて、。つまり、桁数ごとに素数を1行に並べて出力してください。なお、awk、perl、rubyなどのプログラミングできるコマンドやbashのforやwhileなどの制御構文を用いて出力できた場合は、それらを使わずに出力してみてください。sedは可とします。

次のように確かめるとデバッグしやすいです。

$ seq 1000000 | factor | awk 'NF==2{print $2}' | (解答) | awk '{print $1,$NF}'
2 7
11 97
101 997
1009 9973
10007 99991
100003 999983

僕の回答は次の通り。数が決め打ちなので汚い。

$ seq 1000000 | factor | awk 'NF==2{print $2}' | tr \\n ' ' | sed -E 's/ ([0-9]{2}) ([0-9]{3})/ \1\n \2/g; s/ ([0-9]{3}) ([0-9]{4})/ \1\n \2/g; s/ ([0-9]{4}) ([0-9]{5})/ \1\n \2/g; s/ ([0-9]{5}) ([0-9]{6})/ \1\n \2/g' | awk '{print $1, $NF}'
2 97
101 997
1009 9973
10007 99991
100003 999983

ようは数字の連続する長さが切り替わるタイミングで改行を入れる、というアプローチ。 sedでいい感じにやる方法が思いつかなかった。

他の方の回答でgrepを使うのがすごくきれいでよかった。

seq 1000000 | factor | awk 'NF==2{print $2}' | tr \\n ' ' | grep -Eo -e'(([0-9]{'{1..6}'} )*)'

Q8 これをなるべく忠実に作ってみてください。

このあたりの画像系のシェル芸についていけてなくて遅れを感じている。

LT会

今回のLT会は名言の宝庫だった。 名言だと思ったもの。

  • くだしンス
  • ふつうの難読化
  • これはdateコマンドです
  • 難読化シェル芸のアンダーバー派
  • 好きなVimVim
  • Tab補完は軟派
  • 娘のChangeLog

まとめ

ということで今回の問題の僕の正答率は 3 / 8 。今回は難しかった。 今回は難読化、画像、数学とバリエーション豊かだったと感じた。

前回のsort系は得意なほうだった。 逆に今回は未知の問題ばかりだったので苦戦したが 解きほぐしてみればなるほどな、というものばかりだった。