Idiom: Partial Sorting

書庫から久しぶりに取り出したEffective STLをパラパラめくっていて、std::partial_sortのうまい用法を学びました(第31項「ソートの選択肢を知っておこう」)。昇順に整列して初めから20番目の要素までの合計を取りたいときにはstd::sortを使うより、std::partial_sortを使ったほうが効率的であるようです。

std::vector<int> a;

// ...aを更新する

std::partial_sort(std::begin(a),
                  std::begin(a) + 20,
                  std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

イテレータを3つ取る関数には苦手意識がありましたが、この用法は覚えやすいですし、手軽な定数倍高速化として重宝するかもしれません。計算量は面白く、

$$ O({}(\mathrm{last} - \mathrm{first})\log(\mathrm{middle} - \mathrm{first}){}) $$

だそうです。線形の項が配列全体の要素数なので劇的に計算量が減るわけではなさそうですが、以下のように一定の効果は期待できそうです。

$$ \begin{array}{cccc} \mathrm{first} & \mathrm{middle} & \mathrm{last} & \text{Complexity}\\ \hline 0 & 10 & 1000 & 1000 \times 3.322\\ 0 & 100 & 1000 & 1000 \times 6.644\\ 0 & 500 & 1000 & 1000 \times 8.966\\ 0 & 1000 & 1000 & 1000 \times 9.966\\ \end{array} $$

よしよし、一つ賢くなったぞ...と喜んでいたのも束の間、合計を取りたいのであればstd::nth_elementで十分であることに気づきました。std::nth_elementはstd::partial_sortと書式がほとんど一緒ですが、std::partial_sortが先頭から20要素までに上位20個の要素を整列して格納するのに比べ、先頭から20要素までに上位20個の要素を格納する、とのこと。

std::vector<int> a;

// ...aを更新する

std::nth_element(std::begin(a),
                 std::begin(a) + 20,
                 std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

(この用途では1)計算量はstd::parital_sortに比べとても効率的で、\(O(\mathrm{last} - \mathrm{first})\)だそうです。\(\log\)が落ちてしまうんですね。


  1. C++17から追加されたstd::nth_elementの計算量は少々複雑であるようです

Multi-start Breadth First Search

先日参加したコンテストで以下のような問題が出題されました1

シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。ただし、頂点の最大数は\(10^{5}\)である。

この問題、コンテスト中には全く手が出ませんでした。それぞれの頂点から幅優先探索を行なって任意のグループに属する頂点に出会う度に記録すれば、目的はまあ達成です。ですが、計算量は軽く見積もっても\(O(N^{2})\)。\(10^{10}\)を超えてしまいます。これは駄目です。

また、制約から考えると、\(10^{5} \times 100\)のテーブルを用意して記録していけばよいように思うのですが、うまく埋めていくことができませんでした。

このときは次のように考えていました。

  • 各頂点から幅優先探索を行う。訪れた頂点のグループ情報を得る。そのグループに初めて訪れているなら、距離を最短距離として記録する(全てのグループに出会ったらその頂点に関しての探索は終了する)

さてコンテスト終了後に色々考えても計算量が落とせなかったので他のコンテスタントの実装を読んでみました。皆幅優先探索を実装しているようですが、探索をグループの数分しか行なっていません...はて?

ポイントは以下でした。

  • 幅優先探索の開始点はグループに属する全頂点とする(!)
  • 幅優先探索を行う。先ほどのようにグループ情報を集めるのではなく、開始点のグループ情報を伝搬するようにする

なるほど、これなら計算量も\(O(MN)\)に落とすことができます。「多点開始幅探索」、とでも呼称できそうな技法です。

以下のような盤面を考えてみます。ここで、グループは4色の色として表しています。また、グラフは表示されているよりも広く存在しています。

f:id:agw:20180604152628p:plain:w350:h350

単点開始幅優先探索では以下のように探索を行います。この緑色の頂点はすぐに、青色と紫色の点を見つけることができますが、赤色の頂点にたどり着くまでには3ステップかかっていることが分かります。

f:id:agw:20180604152739p:plain

赤色の頂点にたどり着いた時点で自分が属する色以外の3色の頂点にたどり着いたのでここで探索を打ち切ることはできますが、最悪\(O(N)\)の探索を\(N\)回繰り返さなければならないので、計算量は依然\(O(N^{2})\)と考えたほうがよいでしょう。

では多点開始幅探索を見て見ましょう。探索は以下のようになされているようです。先ほどの単開始点から行う幅優先探索に比べて、ほとんどの頂点をすぐ網羅することも注目しましょう。

f:id:agw:20180604153135p:plain

一回の探索で訪れる頂点の数は単点開始でも多点開始でも\(N\)ですが、探索を全体で\(N\)回(最大\(10^{5}\)回)やらなければいけないか、\(M\)回(最大100回)でいいのかで総合的な計算量は大きく変わります。ぜひ覚えておきたい技法です。


  1. 少し簡潔な問題としています

Idiom: Enumerate ranges that decrease(but not strictly)

コンテストに参加していると、数列の部分的に降順になっている区間を列挙することを求められることがままあるのですが、苦手意識がありました。図でいえば、[4, 9]、[18, 21]、[23, 24]を列挙することです。

f:id:agw:20180215092113p:plain

この小問題、自分にはなかなか難しいものでした。特に初めの区間のように、単調に減少しないものを処理しなければならない場合は無駄に複雑な実装をして時間を浪費することが多かったように思います(この問題を見るたびに「隣り合う値から微分を検出すれば書けるのでは?」と考えてしまうのが敗因です)。

今日参加したコンテストでも同じように迷い、しゃくとりを使えば簡潔に書けることにやっと気づきました。

for (int i = 1; i <= N; )
  if (a[i] <= a[i + 1]) {
    i ++;
  }
  else {
    for ( ; i <= N && a[i] >= a[i + 1]; i ++)
      ;

    ranges.emplace_back(i, j);  // 区間はinclusive。[i, j]
  } 

しゃくとり以外に工夫していることといえば、処理を簡潔にするために最初と最後に番兵を入れていることでしょうか(実際には先頭の番兵を\(-\infty\)、最後の番兵は\(\infty\)としています)。

f:id:agw:20180215092108p:plain

隣り合う値から微分を検出しようとしてうまく行かなかったのですが、番兵のアイデアはそのときに微分を確実に取れるように、と思いついたものです(この問題設定だと先頭はなくてもよい)。面白いですね。

これからは迷うことなく書くことができそうです。

Finding Distance Between Two Nodes of a Binary Tree

yambe2002さんの記事に面白い問題が掲載されていたことをふと思い出して、考えてみました。

バイナリツリーの2ノード間の距離を求めるメソッドを作成せよ

こちらは所謂「ホワイトボードコーディング」で出題された問題だそうです。つまり、面接の問題です。

木が二分木ではない場合、ダブリングを伴ったLCAを答えることが選択肢の一つではないか、と考えました。計算量は\(O(Q\log{}N)\)です。しかし二分木であること、また電話面接だったとのことですので1、おそらく20分以内で簡潔な解法を説明することを要求されているのではないかと感じました。解法はおそらくとてもシンプルなものなのでしょう。

根の番号を1とした二分木では、頂点の番号をiとした場合に

  • \(\lfloor{}i / 2\rfloor\)として親の頂点の番号を取得することができる

という性質があります。この性質をうまく使う問題ではないかと思い、考えてみました。

f:id:agw:20171206082249p:plain

まず\(O(Q\log{}N)\)の解法をすぐ思いつきました。頂点数をN、クエリ数をQとしています。二分木なので想定して、頂点数Nはたかだか\(2^d - 1\)です(dは1以上の整数で、木の深さ)。例えば木の深さが60までだとすると、取りうるNは高々1、3、7、...、1,152,921,504,606,846,975となります。木の深さは\(\log{}N\)です。

さて、一般的な木での\(O(QN)\)の解法は以下のようなものになると思います。

  • 2つの頂点の深さを合わせる(この回数を\(c_1\)回とします)
  • 共通の頂点にたどり着くまで、親をたどる(この回数を\(c_2\)回とします。両方の頂点の移動量は\(2c_2\)となります)

図示すると以下のようになるでしょうか。黒い矢印が深さを合わせるフェーズで、灰色の矢印が共通の親を探すフェーズを表します。

f:id:agw:20171206082406p:plain

\(c_1\)と\(c_2\)から二つの頂点の距離は\(c_1 + 2c_2\)と計算することができます。

頂点の深さを求めるにはどうしたらよいでしょう? 一般的な木の場合はDFS等で事前に記録しなければならなさそうですが、こちらも完全二分木ならではの求め方がありそうです。これは各頂点の番号を二進数として表すことで規則性が見えてきました。

f:id:agw:20171206082442p:plain

つまり、同じ深さの頂点は高位の1のビットが現れる位置が同じであるわけです。これを行うには何らかのビット演算を行う必要があるように思いました。おそらく効率のよろしくないであろう実装を書き始めることも出来そうですが、後に回すことにしました。

深さが合っていれば、共通の頂点にたどり着くまで親をさかのぼればよいです。この回数を\(c_2\)として数えます。

f:id:agw:20171206082549p:plain

実装はおそらく以下のようなものになるのではないでしょうか(ここから全編を通して\(x \le y\)であるものとしています)。

  // ゴニョゴニョした結果、xとyの深さは揃っているものとする

  int c2 = 0;

  for ( ; x != y; c2 ++, x /= 2, y /= 2)
    ;

  return c1 + c2 * 2;

これで\(O(Q\log{}N)\)の実装は完成です。

こう考えると、予め深さの調整をせずとも単純に深い方の頂点を上に持ってきてもいい気がします。

  int c = 0;

  for ( ; x != y; c ++)
    (x > y ? x : y) /= 2;

  return c;

より簡潔に書けました。追いかけっこをしているようなので、そのように名付けます(追いかけ)。深さを合わせる実装も必要なくなってしまいました。めでたしめでたし。

...さて、時間が余ってしまいました。ここで面接官が世間話をしてくることはおそらくないでしょう。次の問題を出題するかもしれません。また、計算量を\(O(Q\log{}N)\)から下げる方法はないか検討することを求めてくるかもしれません

ここで先ほどの図をよく眺めてみます。親の親の頂点番号は場号を右側に2つシフトしたものとなっていますね。これは利用できないでしょうか?

同様に、n個上の親の頂点の番号はx >> nで算出することができそうです。二つの頂点の深さが等しければ、ビットシフトを利用して二分探索をすることができそうです。

f:id:agw:20171206082629p:plain

  // ゴニョゴニョした結果、xとyの深さは揃っているものとする

  int l = -1, u = 66;

  while (u - l > 1) {
    int m = (l + u) / 2;

    ((x >> m) == (y >> m) ? u : l) = m;
  }

  return c1 + 2 * u;

この実装の計算量は\(O(Q\log\log{}N)\)となります。計測してみると、確かに速い。\(O(Q\log{}N)\)のものに比べて10倍速い結果となりました。

さて、おざなりにしていた深さを揃える実装を考えてみます。以下のように頂点の高さを揃えたいのです。

f:id:agw:20171206082536p:plain

試しに書いてみたのですが、どうもどんくさい。

  int c1 = 0, c2 = 0;

  long long s = (xのビットをゴニョゴニョする), t = (yのビットをゴニョゴニョする);

  for ( ; s != t; t /= 2, y /= 2, c1 ++)    // 深さを揃える
    ;
                     :

どうもうまく書けない。そこでnaoya_t氏にご登場願いました。この話の背景、\(O(Q\log{}N)\)、\(O(Q\log\log{}N)\)の実装アイデア、深さを揃えるところをうまく書けていない...10分ほど会話をしたでしょうか。

1時間ほど経ってnaoya_t氏から一報が届きました。実装含め、完了したとのこと。内容は目を疑うようなものでした2

  int c = __builtin_clzll(x) - __builtin_clzll(y);

  return c + (64 - __builtin_clzll(x ^ (y >> c))) * 2;

結局のところ、二分探索も必要なく3先頭からの0のビットの数を数えること(clz / Count Leading Zero)とビット演算だけで求めることができる、とのことでした。びっくり4

まず双方の番号のclzを取得して、大きい方の番号をclzの差の分だけ右側にシフトします。これで深さが揃います。以下の例の場合、\(5 - 4 = 1\)ビットだけ右側にずらしてやります。

f:id:agw:20171207100732p:plain

さらに、排他的論理和を取って二つの数のビットが異なる初めてのビットまでの位置をclzで取得します。このビット以降をなくしてしまえば、それは共通の祖先の頂点であると言えそうです。またその距離は右側からこのビットまでのビット数(bsr / Bit Scan Reverse)です。つまり総ビット長(実装では64、図では8)からclzを引いた分が共通の頂点までの距離となります。この距離は2倍しなければならないことに注意してください。

f:id:agw:20171207100716p:plain

さて、計測です。\(O(Q\log\log{}N)\)のものに比べてさらに10倍速い。clzは大抵CPUで用意されているので当然と言えば当然です。clzの計算量を\(O(1)\)とすると、全体の計算量は\(O(Q)\)です。

ちょっとしたあとがき

このブログはnico_shindanninさんが主宰するCompetitive Programming Advent Calendar 2017 - Adventarの飛び込みエントリとして書いてみました。氏は多忙であるにも関わらずコミュニティのアクティビティに貢献し続けています。いつも本当にありがとうございます(就寝するときはシンガポールに足を向けないようにしています :))。遅筆なところ急ぎ書き起こしたため、読み辛い部分が多いと思います。ごめんなさい。

最近ありがたいことに人付き合いに恵まれ、コンテスト以外でのアクティビティが充実しています。と言っても、解けた問題のレビューをしたり、解けなかった問題を教わったり。競技プログラミングのみならず、オンラインコースでの勉強、英会話などなど。大変充実した時間を過ごしています。

アルゴリズムの勉強方法にも少しずつ工夫を取り入れています。あまり派手ではありませんが、レートもジワジワ上がってきていて効果を実感してきています(Codeforcesで100くらい、ですかね)。

  • コンテスト終了時に取り組んでいた問題をコンテスト終了直後にリマインダーに突っ込み、復習する
  • 自分が実現したい不明なテクニックがあった場合、コンテスト中でもリマインダーに突っ込む
  • コンテストに参加できなかった知人に良問だと思った問題をリコメンドする(また、知人のレベルではやらなくてよい問題も伝える)
  • 良問についてダラダラ語る

問題について議論することが相当効いているようです。本文にご登場いただいたnaoya_t氏の発想は自力ではなかなかたどり着けませんし、また氏曰く、自分が考えていた追いかけや二分探索の発想はまずしなかったそうです(ビット演算系がうまく行かなかった後の選択肢なんでしょう)。もちろんコンテスト終了後のTLによる感想戦でもこのような知見に出会えるのですが。コンテストからしばらく経ったあとでも議論したりしているとことがいいんでしょうか。

さて、面接で求められていたのはどの程度なんでしょうかね。気になるところではあります。題材として引用することを快諾くださったyambe2002さん、どうもありがとうございました。

ちょっとした追記

「ビットをゴニョゴニョする」のに、最高位のビットだけ残すことを考えていました。つまり、2の冪での床関数です。分岐なしで\(O(log{}N)\)の実装なので、これはこれで大変高速です(これだけ命令があってclzの倍程度)。

inline long long bfloor(long long x)
{
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x |= x >> 32;
  return x - (x >> 1);
}

例えば\(0010\ 1011\)を渡すと\(0010\ 0000\)を返します。


  1. コラボレート可能なエディタにコーディングするよう指示されたそうです

  2. naoya_t氏の実装を元に筆者の好みで改訂しています(スンマセン)

  3. おそらくclzのCPU内での実装は\(O(\log{}N)\)のビット演算です。分岐不要な二分探索として実装されているものも多いようです

  4. 実際のところ、__builtin_clzは引数に0を取った場合の返り値が未定義となりますので、long long z = x ^ (y >> c); return z ? c + (64 - __builtin_clzll(z)) * 2 : c;等としなければなりません

Idiom: Cumulative Summation Summary

累積和を実装するとき、いつもインデックスの扱いに悩んでしまいます。これが結構時間を喰うので 、しっかりイディオムとしてまとめようと思いました。

例えば0-indexの配列、\(a_i\)があるとします。

$$ \begin{array}{c|ccccc} i & 0 & 1 & 2 & 3 & 4 & 5\\\hline a_i & 1 & 2 & 3 & -4 & -2 & 1 \end{array} $$

目的はO(1)で\(s_{[i,j)}\)を求めることです(準備にはO(N)かかります)。例えば、\(s_{[0,1)}\)は1、\(s_{[0,3)}\)は6、\(s_{[1,3)}\)は5といった具合です。

これを行うには累積和をテーブルとして用意するのが常套手段です。これを\(\mathit{acc}_i\)とします。\(\mathit{acc}_{i+1} = a_i + \mathit{acc}_i\)とします。また、\(\mathit{acc}_0\)は0です。つまり、

$$ \begin{cases} \mathit{acc}_0 = 0\\ \mathit{acc}_{i+1} = a_i + \mathit{acc}_i\ \text{where}\ 0 \leq i < \mathit{size}\\ \end{cases} $$

作成された累積和テーブルは以下のようになります。

$$ \begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\hline \mathit{acc}_i & 0 & 1 & 3 & 6 & 2 & 0 & 1 \end{array} $$

ここで添字がずれるのが混乱の元なんですね。しっかり式を立てておきましょう。

$$ s_{[i, j)} = \mathit{acc}_j - \mathit{acc}_i $$

ポイントは、

  • 半開区間とすること(\(s_{[i,i)}\)は空集合なので0)
  • i、jは配列\(a_i\)のものをそのまま使う

となります。結果は以下のようになります。

$$ \begin{array}{c|c} s_{[0,1)} = \mathit{acc}_1 - \mathit{acc}_0 = 1 - 0 = 1\\ s_{[0,3)} = \mathit{acc}_3 - \mathit{acc}_0 = 6 - 0 = 6\\ s_{[1,3)} = \mathit{acc}_3 - \mathit{acc}_1 = 6 - 1 = 5\\ \end{array} $$

さて、1-indexの配列の場合にはどうしたらよいでしょう?

$$ \begin{array}{c|ccccc} i & 1 & 2 & 3 & 4 & 5 & 6\\\hline a_i & 1 & 2 & 3 & -4 & -2 & 1 \end{array} $$

\(a_0\)を0とおけば-0indexの場合と同様に扱うことができそうです。

$$ \begin{array}{c|ccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\hline a_i & 0 & 1 & 2 & 3 & -4 & -2 & 1 \end{array} $$

累積和テーブルは一つずれますが、0-indexと同じ考え方で扱うことができそうです。累積和テーブルの先頭の2つの要素を0で初期化しておかなければならないので注意が必要です。

$$ \begin{cases} \mathit{acc}_0 = 0\\ \mathit{acc}_1 = 0\\ \mathit{acc}_{i+1} = a_i + \mathit{acc}_i\ \text{where}\ 1 \leq i \leq \mathit{size}\\ \end{cases} $$

作成された累積和テーブルは以下のようになります。

$$ \begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline \mathit{acc}_i & 0 & 0 & 1 & 3 & 6 & 2 & 0 & 1 \end{array} $$

\(s_{[i,j)}\)は以下のように算出することができます。

$$ s_{[i, j)} = \mathit{acc}_j - \mathit{acc}_i $$

もう一つ気になることといえば、配列は要素数 + 1、また累積和は要素数 + 2分確保しなければならないことでしょうか。

では累積和を一つずらすことを考えてみましょう。この場合の累積和は要素数 + 1分確保すればよいです。

$$ \begin{cases} \mathit{acc}_0 = 0\\ \mathit{acc}_{i} = a_i + \mathit{acc}_{i-1}\ \text{where}\ 1 \leq i \leq \mathit{size}\\ \end{cases} $$

作成された累積和テーブルは0-indexのときと変わりません。

$$ \begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\hline \mathit{acc}_i & 0 & 1 & 3 & 6 & 2 & 0 & 1 \end{array} $$

これは0-indexのときの累積和と全く同じです。\(s_{[i, j)}\)を計算するときは、以下とします。

$$ s_{[i,j)} = \mathit{acc}_{j-1} - \mathit{acc}_{i-1} $$

書き出したことで頭がスッキリしてきました。特に、0-indexのときの悩みはなくなりそうです。1-indexのときはどうしたらいいんでしょうか。もう少し経験を積んでから考えたほうがよさそうです。

Idiom: Check if given string starts with some string

std::stringとして与えられた文字列がある特定の文字列から始まるかどうかを記述するのは簡単なことのように思えます。これが自分にとっては意外に難しく、いつも時間を割いてしまうのです。先日、コードリーディングをしていた際にうまい方法を見つけたため、イディオムとして記載しておこうと思います。

先日(またもや)やってしまった実装は以下のようなものでした。

  const std::string s("abc");   // abcから始まる文字を探したい

  const int size = s.size();

  const std::string a[] = {
    "abcdef",
    "defabc",
    "abcabc",
    "a"
  };

  for (const auto& i : a)
    if (i.size() >= size)               // 文字列の長さが十分かどうかチェックする
      if (i.substr(0, size) == s)       // 先頭の文字列を切り出して比較する
        // 文字列iはsから始まっている!
};

この実装は色々と無駄があるだけではなく、自分にとっては注意すべき点が多く手早く書けないのです。

  • 文字列iのサイズを検証する -> この際等号を入れるべきだろうか?
  • 文字列iの先頭size文字をstd::stringとして生成する -> この際使うべきsubstrメソッドには引数を1つ与えるべきか。それとも2つ与えるべきか?

そもそもsubstrメソッドは末尾のサイズを適切にチェックしてくれるはずです。

  for (const auto& i : a)
    // if (i.size() >= size)            // サイズのチェックはしなくてよい
      if (i.substr(0, size) == s)
        // 文字列iはsから始まっている!

これでも悪くはないのですが、やはりsubstrの引数の数は悩んでしまいそうです。どうもあれだなあ、とコードリーディングをしていた際に、以下のイディオムを見つけました。

  for (const auto& i : a)
    if (i.find(s) == 0)
      // 文字列iはsから始まっている!

なるほど簡潔で覚えやすそうです。次回からはこのイディオムを使おうと思います。

もう少しだけ

findメソッドを使ったこのイディオムは簡潔でよいのですが、先頭から指定して文字列で始まっていない場合、無駄に探索を行ってしまいます(例えば文字列が"xyzxyzxyzxyzxyzxyzxyz"の場合)。これが無駄に思える場合はstrncmpを使った方がいいかもしれません。

  for (const auto& i : a)
    if (strncmp(i.c_str(), s.c_str(), size) == 0)
      // 文字列iはsから始まっている!

Redirecting Contents of File to Standard Input

1行シェルスクリプトEmacsで極力物事を済ます方針になって久しいのですが、コンテスト中は時間がないので多少のスクリプトを用意しています。先日コンテスト中にこんなスクリプトがあったらいいなあ、と考えついたので早速作成しました。

  1. Emacsでテキストを加工する。具体的には「入力」「空行」「出力」「空行」...という形式とする
  2. コマンドを適用すると、「入力」「出力」がsample1.txt、answer1.txt、...と出力される

例えば以下のようなファイルを用意します。

3 2
1 2 3
1 2
3 2

5

4 3
1 2 3 4
1 2
3 4
3 4

8

これにコマンドを適用すると、以下のようにファイルに格納されるようにしたいのです。

sample1.txt:
3 2
1 2 3
1 2
3 2

answer1.txt:
5

sample2.txt:
4 3
1 2 3 4
1 2
3 4
3 4

answer2.txt:
8

こういう処理はシェルスクリプトでさっさと書いてしまいましょう。

unpack.sh:

#!/bin/sh

i=1

bodyname="sample"

test -f "$bodyname$i.txt" && rm -f "$bodyname$i.txt"

while read l; do
  if ! echo "$l" | grep '^ *$' > /dev/null; then
    echo $l >> "$bodyname$i.txt"
  else
    if [ "$bodyname" == "sample" ]; then
      bodyname="answer"
    else
      bodyname="sample"

      i=`expr $i + 1`
    fi

    test -f "$bodyname$i.txt" && rm -f "$bodyname$i.txt"
  fi
done

早速テストして...いい感じですね。内容もよいようです。

> ls
a.txt
> unpack.sh < a.txt
> ls
a.txt       answer2.txt sample1.txt sample3.txt
answer1.txt answer3.txt sample2.txt

さて、これを自分の環境にリリースしたのですが、どうも自分の操作と相性が合わないのです。どうしてだろう? と観察してみたのですが、Emacs diredから!でファイル操作ができないのが原因でした。Emacs diredから!とするにはシェルスクリプトがファイル名を引数として得て処理できなければなりません。

これを解決するのは簡単で、以下の1行を代入するだけでした。

           :
test -f "$bodyname$i.txt" && rm -f "$bodyname$i.txt"

test -f "$1" && exec <"$1"   # この行を挿入

while read l; do
           :

つまるところ、引数としてファイルが与えられていた場合、ファイルの内容を標準入力にリダイレクトしてしまえばよいのです。

さて、これでEmacs diredから快適にコマンドを使うことができるようになりました。今から使う機会が楽しみです。

少しばかりの続き

さて、このスクリプトであると空行が2つ以上続くとよくない結果となります。

> ls
a.txt
> cat a.txt
1  # sample1.txtに書き込まれるはず

2  # answer1.txtに書き込まれるはず


3  # sample2.txtに書き込まれるはず

4  # answer2.txtに書き込まれるはず
> unpack < a.txt
> ls # sample2.txtがない? sample3.txtがある??
a.txt       answer1.txt answer2.txt sample1.txt sample3.txt

空白毎に出力するファイルを更新しているのが原因です。これを防ぐために、予めsedを適用して調整しています。

           :
test -f "$1" && exec <"$1"

sed -ne '
s/^  *$//
H
$ {
  g
  s/^\n*//g
  s/\n*$//g
  s/\(\n\n\)\n*/\1/g
  p
}
' | while read l; do
           :

このsedスクリプトも面白いので興味があれば是非処理を追ってみてください。具体的には、「全て読み込んでから連続する改行を取り除く。ただし、各行が空白を含む空行であればこれも処理する」といったことをしています。また、最新のスクリプトこのGistで管理しています。