Software Designの2017-12月号を今頃読んでいるのですが、数学の話の中で「アナグラムファインダー」の話題が出ていました。
文中ではpythonとsortコマンドを使って解く方法が紹介されていたのですが、Unixのコマンドだけでできないものか考えていました。
その中で、文字 (cba) を (abc)のようにならべかえる必要があったのですが、その方法がなかなか上手くいかなかったのでコツを紹介します。
## 文字をソートする
```bash
`gutter:false;
$ echo "helloworld" | perl -pe 's/\r\n//' | fold -w1 | sort -s | paste -s -d '\0' -
dehllloorw
```
1文字だけソートする場合は良いのですが、複数文字行った時に、上手くソートできませんでした。
foldに流す前に改行コードを削除するのがコツでした。
fold -w1で文字をバラバラにして、sortコマンドでソートした後pasteコマンドで1行に戻しています。
## アナグラムファインダーを解く
アナグラムファインダーをワンライナーで解く方法ですが、文字をアルファベット順に並び替えてからソートして最後に順番に表示していくのですが文字をソートするのに時間がかかってしまい、実用的でありませんでした。
```bash
`gutter:false;
cat words_alpha.txt | xargs -n 1 -I {} sh -c "echo {} | perl -pe 's/\r\n//' | fold -w1 | sort -s | paste -s -d '\0' - | perl -pe 's/\n$/ /g'; echo {}" | sort | awk 'BEGIN{a="";result="";}{if (a != $1){print(result); a = $1; result = $2; next;} result = result " " $2; } END{print result}'
```
words_alpha.txtはGithubの[ここ](https://github.com/dwyl/english-words.git)から取得しました。
abcd cabd の様に文字列をソートした物とオリジナルと並べる必要があるのですが、その部分の処理に時間がかかってしまい実用的でありませんでした。
その部分のみpythonで解くと3秒程度で問題を解くことができました。
今後高速化する方法がわかったら再度チャレンジしてみたいと思います。
高速化バージョンはこっち
```bash
`gutter:false;
./map.py < english-words/words_alpha.txt | sort | awk 'BEGIN{a="";result="";}{if (a != $1){print(result); a = $1; result = $2; next;} result = result " " $2; } END{print result}'
```
0 件のコメント :
コメントを投稿