Let's write β

プログラミング中にできたことか、思ったこととか

CodeIQのナムドット問題。僕の回答

結城先生がCodeIQに定期的に出題なさっているのですが、今回のナムドット問題をやってみました。
挑戦者求む!【アルゴリズム】古代文献を復元しよう! by The Essence of Programming 結城 浩│CodeIQ

問題の出力に着目してみると、ドットでくぎられている数字は1区切り区間中では昇順になっているのがわかります。だから、単純な数字のシャッフルではないと考えられます。
となると数字をいくつかの集合に分割しているのだと考えられます。

となると集合を部分集合に分割する方法を列挙するアルゴリズムが考えられます。
そこで、そのアルゴリズムを試してみたところ、無事正解らしき出力がえられたのでまずはそれを僕の回答としました。

最初はCで実装していたのですが、リストの最大値を得る処理などもうすこし高級な言語ならその処理そのものが実装されていると考えられる物がいくつかあったので、Rubyで実装しなおす事にしました。
元々ワンライナーは嫌いなので、ワンライナーにならない元のアルゴリズムの実装が見てとれる範囲で圧縮しようとおもい試行錯誤しました。特に出力についてはどの数字がどのグループに属するのかという処理をして出力するコードが3行ほど食っていたので、標準ライブラリなら利用して問題ないだろうという事で利用しました。