第46回シェル芸勉強会に参加しました
参加しました 今回は午後のみ。毎度「死にます」と宣言されるので戦場かなんかだと思ってます。
問題と解答はここです。
Q1
データを幹葉表現に変換する問題。
$ cat vol.46/data|fmt -1|sed 's/^[0-9]/+&/g'|sed 's/+\|-/& /g'|awk '{k=$1int($2/10);b[k]=b[k]""$2%10}END{for(x in b)print x,b[x]}'|tr + ' ' 0 39 1 98 2 245 -0 44 -1 24 3 242 4 2
10の位をキーに1の位を連想配列に入れています。このとき気をつけるのは正負の情報も必要だということです。PowerShellでもやってみます。
$ $(cat .\vol.46\data).Split()|%{$_/10 -replace "^([0-9])","+`$1"}|% -begin{$$=@{}} -end{$$} {$$[$_[0..1] -join ""]+=$_[-1]} Name Value ---- ----- +4 2 -0 44 -1 24 +2 245 +0 39 +1 98 +3 242
Q2
パリティチェックをして異常のあった行数を出力する問題。シェルでパリティチェックしたいですよね。したい
$ cat Sh*/*.46/data2|awk -F '' '{for(i=1;i<=NF-2;i++)a[$i]++;if(a[0]%2!=$(NF-1)||a[1]%2!=$NF)print NR;a[0]=a[1]=0}' 4
特に云うこともないawkゴリゴリ。解答例ではgsub
がマッチ数を返すというのを利用する超賢いやつでした。PowerShellでもやるよ。
$ cat .\vol.46\data2|% -begin{$NR=1}{$_=($_ -split " ");$$=($_[0].ToCharArray()|group);if($_[1][0] -ne ""+$$[0].Count%2 -or $_[1][1] -ne ""+$$[1].Count%2){$NR};$NR++} 4
PowerShell版ではGroup-Object
を使いました。このコマンドレットはコレクションに対してGroupByをおこない、GroupInfoオブジェクトを返します。ここに個数を示すCountプロパティがあるので、それをみてパリティチェックをしています。
Q3
行列の掛け算をする問題。そうそう、CLI上でやりたいことあるよね
Rの使い方を調べている間に時間が終わってしまったのでここではそれに再チャレンジします。
$ cat Sh*/*46/matrix|awk -v OFS=, '{for(i=1;i<=NF;i++)b[(NR-1)*NF+i]=$i}END{print "rbind(c("b[1],b[2],b[3]"),c("b[7],b[8],b[9]"),c("b[13],b[14],b[15]"))%*%rbind(c("b[4],b[5],b[6]"),c("b[10],b[11],b[12]"),c("b[16],b[17],b[18]"))"}'|R --no-save --silent > rbind(c(3,4,-2),c(3,-1,2),c(2,5,6))%*%rbind(c(1,-9,4),c(3,-2,-8),c(0,2,-3)) [,1] [,2] [,3] [1,] 15 -39 -14 [2,] 0 -21 14 [3,] 17 -16 -50
awk
でRのソースコードを組み立ててRに評価させています。コレに関してはPowerShellでやること変わらないので無しで。
Q4
4人を2つにグループ分けするときの全パターンを列挙する問題。グループに区別はない。時間中に解けたんだけど、コピペのときにミスってたみたい。
$ echo {a,A}{b,B}{c,C}{d,D}|fmt -1|xargs -I@ bash -c 'paste <(echo @|grep -oP "[a-z]"|tr -d \\n) <(echo @|grep -oP "[A-Z]"|tr -d \\n)'|awk 'NF==2'|sed 's/.\+/\U&/'|awk '{if(b[$1]||b[$2])print $0;b[$1]=b[$2]=1}' BCD A BC AD BD AC B ACD CD AB C ABD D ABC
echo {a,A}{b,B}{c,C}{d,D}
の出力をみてみます。
$ echo {a,A}{b,B}{c,C}{d,D}|fmt -1 abcd abcD abCd abCD aBcd aBcD aBCd aBCD Abcd AbcD AbCd AbCD ABcd ABcD ABCd ABCD
ここで大文字小文字に注目すると、グループが区別されているときの全パターンが列挙されることがわかります。ここからいらないところを抜いてやれば良さそうです。とりあえず加工しやすいように左右に大文字小文字を分割します
$ echo {a,A}{b,B}{c,C}{d,D}|fmt -1|xargs -I@ bash -c 'paste <(echo @|grep -oP "[a-z]"|tr -d \\n) <(echo @|grep -oP "[A-Z]"|tr -d \\n)' abcd abc D abd C ab CD acd B ac BD ad BC a BCD bcd A bc AD bd AC b ACD cd AB c ABD d ABC ABCD
あとは、sed
で大文字変換、awk
で重複チェックするとほしい結果が得られますね。
PowerShellもやってみます
$ 1111..2222|?{$_ -match "[1-2]{4}"}|%{$$=@{};(""+$_).ToCharArray()|% -begin{${@}=[int][char]'A'}{$$[$_]+=[char]${@}++};$$[[char]'1']+","+$$[[char]'2']}|sls - NotMatch ",$|^,"|%{$_=($_ -split ",");if($_[0] -match "^A"){$_[0]+" "+$_[1]}else{$_[1]+" "+$_[0]}}|Sort-Object -Unique A BCD AB CD ABC D ABD C AC BD ACD B AD BC
ブレース展開が無いのでグループの列挙に 1111..2222
を使います。これは1111から2222までの数値を列挙するものです。そこから [1-2]{4}
にマッチするものだけを通します。
$ 1111..2222|?{$_ -match "[1-2]{4}"} 1111 1112 1121 1122 1211 1212 1221 1222 2111 2112 2121 2122 2211 2212 2221 2222
一行ごとに、この数値をキーにして連想配列にABCDを詰めていきます。後は整形、Aの含まれるグループを先に出力し重複を消して終わりですね。
Q5
パスカルの三角形を出力する問題。なんだこれ
$ awk 'BEGIN{b[0,0]=1;for(i=0;i<10;i++){for(j=0;j<i+2;j++){b[i+1,j]=b[i,j-1]+b[i,j];printf b[i,j]" "};print}}'|align center 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
awk
でパスカルの三角形を二次元配列に生成し、出力。あとは align
コマンドへ渡して終わりです。コレ便利なのでおすすめです。
$ $($$=@(@{1=1},@{},@{},@{},@{},@{},@{},@{},@{},@{},@{},@{}); for($i=0;$i -lt 11;$i++){for($j=0;$j -lt $i+2;$j++){$$[$i+1][$j]=$$[$i][$j-1]+$$[$i][$j];$L+=" " +($$[$i][$j])}$L;$L=""})|Select-Object -Skip 1|align.exe center 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
最初に連想配列の配列の初期化をしています。なんかもっといい方法がほしいところではありますね。アルゴリズムは同じなのでそこの説明はしません。
Q6
ある10桁の数値 K
の i
桁目の数値を K[i]
としたとき、K[i]*i + K[i+1]*(i+1) + K[i+2]*(i+2) + ... + K[10]*10
を計算、さらに行の結果について最大公約数を計算する問題。競プロみある。最近やってないけど
$ echo -n "#include <iostream>\n#include <numeric>\nusing namespace std;int main(){long x,y;cin>>x;while(cin>>y)x=gcd(x,y); cout<<x<<endl;}"|g++ -x c++ - -std=c++17 && cat Sh*/*46/isbn|awk -F '' '{for(i=1;i<=NF;i++){sum+=$i*(10-i+1)}print sum;sum=0}'|./a.out 11
C++じゃねーか!!!!!!!!!
この問題はどのライブラリを使ってGCDするか、という問題っぽいのでまぁなんでもいいんですが、解答例とかを見ているとpythonでmath.gcdするのが楽そうですね。PowerShellでもやってみましょう。
$ cat .\vol.46\isbn|%{($_.ToCharArray()|% -begin{$x=10} {$x*([int]$_-[int][char]'0');$x--}|measure -sum).Sum} 176 264 231 242 330 286
とりあえず合計から。Measure-Object -Sum
でコレクションの合計値を計算しています。
$ cat .\vol.46\isbn|%{($_.ToCharArray()|% -begin{$x=10} {$x*([int]$_-[int][char]'0');$x--}|measure -sum).Sum}|% -begin{$$=0} {if($$ -eq 0){$$=$_}else{$$=[System.Numerics.BigInteger]::GreatestCommonDivisor($$,$_)}} -end{$$} 11
[System.Numerics.BigInteger]
のStaticメソッドにGCDがあるのでそれを利用すればOKですね。
Q7
円形に41人を並べ、それぞれに番号を割り振る。3人ごとに排除していき、最後に残る二人の番号を求めるという問題。ヨセフスの問題というらしい。
時間中に解けなかったのでここで解いてみる。
$ shq clear;seq 41|xargs -n1 shq push;while true; do shq push $(shq pop);shq push $(shq pop);shq pop > /dev/null; [[ "$(shq show|fmt -1|wc -l)" == "2" ]] && break;done; shq show ["16", "31"]
この問題を解くためだけに shq
というコマンドを作りました。Rust製です。Rust難しい
文字列を扱うDeque(双方向キュー)を提供するコマンドです。これを使えばジョブキューみたいなのもできるんじゃないですかね。多分
インストールは手順とかを記載してるんですけど、まだちょっと気軽に試せる感じじゃないのでその辺の整備もしたいですね。
Q8
以下の文字列の各アルファベットに0-9の数値を割り当てて、式を完成させる問題。ただし、0-9が重複してはいけない。
SEND + MORE = MONEY
この問題は全探索をするのですが、全パターンを試しているとめちゃめちゃ時間がかかるので、なんとか探索範囲を削っていきたいところ。
まず桁数に注目すると、4桁+4桁=5桁で、最上位桁で繰り上がりがあることがわかります。1桁同士の足し算だと繰り上がりは1しか無いので M
が1であることがわかります。
次に S
について考えます。 M
が 1
のとき、繰り上がりしないとダメなので、 S
は 9
になります。 次に O
です。O
の取りうる値は 0
か 1
です。ここで重複を許さないという制約から O
が 0
であることがわかります。
ここまでの式を見てみると、 9END + 10RE = 10NEY
となりました。ここまで削れば全探索できそうです。
$ seq 22222 88888|grep -vE "0|1|9"|grep -vE "(.).*\1"|awk -F "" '{print 9$1$2$3,10$4$1,10$2$1$5}'|awk '$1+$2==$3' 9567 1085 10652
seq
を使って全パターンを列挙しますが、 0,1,9 はすでに決定されているので、これが含まれるパターンは除外しし、重複が含まれるパターンも除外します。
あとはawk
で計算式を作り、その次のawk
で条件に合うものだけ出力して終わりです。
PowerShellでもやってみましょう。
$ 22222..88888|?{$_ -match "[2-8]{5}"}|?{((""+$_).ToCharArray()|group).Count -eq 5}|%{$_=""+$_;"9$($_[0..2] -join '') 10$($_[3])$($_[0]) 10$($_[1])$($_[0])$($_[4])"}|?{$_=($_ -split " "|%{[int]$_});$_[0]+$_[1] -eq $_[2]} 9567 1085 10652
できました。
LT
今回はしませんでした。何もネタが思いつかなかった…。
終わり
今回もとても楽しかったです!企画・運営の皆様!ありがとうございました!
$ owari kanban --giko --author xztaityozx | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄| | 終 | | 制作・著作 | |  ̄ ̄ ̄ ̄ ̄ ̄ ̄ | | xztaityozx | |_________| ∧∧ || ( ゚д゚)|| / づΦ