たいちょーの雑記

ぼくが3日に一度くらい雑記をかくところ

第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

やっていることはbash/zsh版と同じです。

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 コマンドへ渡して終わりです。コレ便利なのでおすすめです。

github.com

$ $($$=@(@{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桁の数値 Ki 桁目の数値を 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難しい

github.com

文字列を扱うDeque(双方向キュー)を提供するコマンドです。これを使えばジョブキューみたいなのもできるんじゃないですかね。多分

インストールは手順とかを記載してるんですけど、まだちょっと気軽に試せる感じじゃないのでその辺の整備もしたいですね。

Q8

以下の文字列の各アルファベットに0-9の数値を割り当てて、式を完成させる問題。ただし、0-9が重複してはいけない。

SEND + MORE = MONEY

この問題は全探索をするのですが、全パターンを試しているとめちゃめちゃ時間がかかるので、なんとか探索範囲を削っていきたいところ。

まず桁数に注目すると、4桁+4桁=5桁で、最上位桁で繰り上がりがあることがわかります。1桁同士の足し算だと繰り上がりは1しか無いので M が1であることがわかります。
次に S について考えます。 M1 のとき、繰り上がりしないとダメなので、 S9 になります。 次に O です。O の取りうる値は 01 です。ここで重複を許さないという制約から O0 であることがわかります。

ここまでの式を見てみると、 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    |
|_________|
    ∧∧ ||     
   ( ゚д゚)||    
    /   づΦ