問題文

概要

ssh接続先で作業しているとき暇になった。
しかし、何のアプリを開いているか上司に監視されているため、コンソールしか遊ぶものがない。
ちょうどいいことに、接続先の環境がubuntu22.04であることに気がついた。
ソースコードを残すと遊んでいたことがバレてしまうため、一行のbashコマンドのみで動作を終わらせる必要がある。

ここで、ICTSCでは問題にランダムのアルファベット3文字のIDが振られているを思い出した。
せっかくなので、アルファベット3文字のIDを偏りなく生成するようなワンライナーで作成してみよう。

そうそう、ワンライナーというからにはなるべく短くしてほしい。

前提条件

• OSが提供する乱数や乱数依存のもの(/dev/random や $RANDOM など)が十分無作為であることを仮定してよい
• 明示的にファイルを作成してはならない

初期状態

• user ユーザーのディレクトリ、~/tester.sh に制作したワンライナーのスクリプトを簡易的に判定するスクリプトテスターが配置されており、それを実行して使用することができる
  • テスターは、スクリプトのコード長の計測、出力されたIDの数がちょうど20個であることと、出力されたすべてのIDがユニークであることのみを判定するだけである
    • つまり、テスターのテストをパスしても、判定としては不正解となる場合がある
  • 使用方法は./tester.sh 'あなたのワンライナースクリプト'である

終了状態

• bash及びOSの標準コマンドを用いて次を満たすbashのスクリプトをワンライナーで作成する
  • 実行すると各行にランダムのラテン大文字アルファベット3文字IDを1つずつ、20行に分けて出力する
    • 後にスクリプトの出力例が記述されている
  • 各行のIDはすべてユニークである
  • 出現するIDは順番によって偏ってはならない
  • スクリプトの実行で明確にファイルを作成した場合、スクリプト実行終了時にそのファイルを残してはならない
    • 実行中に一時的に作成し、削除するのは問題ない
    • 任意の読み取り書き込みが可能なディレクトリ上で実行しても条件を満たすスクリプトであること
• 十分高確率で上記を達成すること。具体的には、スクリプトを読むとは別に、提出されたスクリプトを、点時に実際に1万回テストで実行し、以下の事項とともに正誤判定を行う
  • いずれかのテストの実行で、IDのユニーク性や出力数を満たさない場合は不正解となる
  • テスト完遂後、各アルファベットの出現数をもとにIDの偏りが無いかを判定する
  • ただし、スクリプトテスト時間が長く、採点時間までに間に合わないと判断された場合、採点者がスクリプトを読むことのみで条件を満たしているかの判断を行う
• 条件を満たす、なるべく短いワンライナーのbashスクリプトを提出する
• 提出されたスクリプトが条件を満たしていると判断された場合、正解と判定される。具体的な採点は以下の通りである
  • 64 bytes 未満 なら 満点
  • 64 bytes 以上 96 bytes 未満 なら 満点の70%
  • 96 bytes 以上 128 bytes 未満 なら 満点の50%
  • 128 bytes 以上 なら 満点の30%
• なお、問題製作者の最短記録は 29bytes である。

スクリプトの出力例

LJR
ZRI
WWN
DOI
RSF
BDK
GIO
MRT
ZPW
NNT
MIY
PHW
MEX
NIP
WSL
LAA
QSM
AFT
UTY
DUN

解説

様々な解答が考えられますが、特に運営が用意した２つの解答について紹介します。

１つ目は、ランダムに文字列を生成し、3文字区切りで改行し、そこから重複なく20個のID選ぶ方法です。
まず、cat /dev/random | tr -dc 'A-Z'などを使うことでランダムなアルファベットのみの無限長の文字列を生成することができます。
続いて、fold -3 を使い、3文字ごとに改行を割り込ませ、これにより条件を満たすIDを各行に生成できます。
しかし、このままではダブりが生じる可能性がありますので、如何にダブりを回避するかが問題となります。
回避の一般的な手法として sort | uniq があります。これを用いることで、ダブリを消すことができますが、そのまま適用することはできません（無限長の出力をソートすることはできないため）。
そのため、head -n 25 などをして一旦25個くらいの候補を取り、そこから sort | uniq などでダブリを削除し、さらに shuf | head -n 20 で指定の数を選ぶようにすると良いでしょう。
これの失敗率は 0.00000000000056% （約 180兆分の1） で、1万回実行しても全体の失敗率は 0.00000000056% （約 180億分の1） に抑えられますので概ね問題無いと判断してよいです。（これでも心配ならば、候補の数を99個にするなども良いです。その場合一回あたりの失敗率は指数表記を用いると 7.5e-231 です。）
まとめると、スクリプトは

cat /dev/random | tr -dc 'A-Z' | fold -3 | head -n 25 | sort | uniq | shuf | head -n 20

となります。
これをコマンドオプションを使ったりや余分な空白を消したりして短くすると、

tr -dc A-Z</dev/random|fold -3|head -25|sort -uR|head -20

で 57bytes となり、このアプローチにおいてはこれが最短だと考えられます。（各オプションについては、それらコマンドのマニュアルを参照）

２つ目の解答は、まずすべてのIDを生成し、そこから20個ランダムに選ぶ方法です。
bashにおいては、{A..Z}　と記すれば、A B C … Z までアルファベット26文字がすべて空白区切りで展開されます。
更に、{A..Z}{A..Z} と記すれば、AA AB AC … ZY ZZ まで、AからZの2文字の順列がすべて表れます。
よって、{A..Z}{A..Z}{A..Z}を用いることで、要件のIDをすべて書き出すことができます。
あとは、これを echo などで文字列として出力させ、trで空白を改行に変え、 shuf -n20 を使うことで、目的を達成できます。
この時点でのスクリプトは

echo {A..Z}{A..Z}{A..Z}|tr ' ' '\n'|shuf -n20

となります。(45bytes)
さらに、shuf の -e オプションを用いると、入力の代わりに引数をシャッフルし、-nオプションを用いると、その中から選ぶ（最大の）数を指定できます。
よって echo などが不要となり、最終的には

shuf -en20 {A..Z}{A..Z}{A..Z}

と、外部コマンドや実行ファイルを用いない場合（shufコマンドだけなのでワンライナーと言ってよいか怪しいですが）これが想定していた最短の解答です。(29bytes)

ほかにも、awkの連想配列を用いた解法や、egrep などを用いた解法が存在しました。

採点基準

• 題意を満たさない スクリプト 0点
• 題意を満たす スクリプト であり、かつ
  • 64 bytes 未満 なら 150点（満点）
  • 64 bytes 以上 96 bytes 未満 なら 105点(70%)
  • 96 bytes 以上 128 bytes 未満 なら 75点(50%)
  • 128 bytes 以上 なら 45点(30%)

講評

想定誤答に、以下のようにソート後にシャッフルをせずに先頭から取ってしまい、行によって偏りが生じてしまうようなものがありました

cat /dev/random | tr -dc 'A-Z' | fold -3 | head -n 25 | sort | uniq | head -n 20

確かにダブりは回避できますが、先頭ほど辞書順で早いIDが出やすいという不具合を抱えています。

他に、以下の想定していた誤答がありました

• sort せずに uniq をしてしまい、「連続したダブり」しか取り除けていない解答
• 20個選んでからダブりを消してしまったため、約 1.07% の確率で要求数が20を切る解答
  • その場合、1万回すべて正当な出力をする確率は 1.9e-47 で、まず通りません。
• 無限長の要素を sort してしまい、処理が終わらない解答

ダブりの不具合に関しては低確率で生じることもあり、正当なコードを作るには実験的な方法だけでなく確率論的なアプローチ力も求められるような問題となりました。