プログラミング問題解答-正方形を谷に詰める(yhpg-r0)

はじめに

久しぶりに「どう書く(yhpg)」の問題が出たため、Rubyで実装してみました。
問題については、オフラインリアルタイムどう書く問題作成リハビリ #0 の問題をご覧ください。

解説

コードおよび実行結果

今回はRubyで実装しました。残念ながらBrainf**kでの実装は断念しております。
ソースコードについてはgithub上のリポジトリに挙げています。
問題ページからダウンロードできる data.json ファイルに基づき実行および答え合わせする作りとなっており、次のように55ケース全てパスしています。
※なお、手元での実行時間は全部で1秒弱です。

実行結果

angel:r00$ ruby solve.rb
0: ok
  in:  27,17,8,36,16,12,11,13,25,23,10,6,2,9
  out: 2,8,9,10,13,23,27
  exp: 2,8,9,10,13,23,27

1: ok
  in:  1,2,3
  out: 2
  exp: 2
(略)
54: ok
  in:  73,147,153,172,171,70,97,20,124,64,44,17,60,45,131,26,43,173,111,172,25,84,147,52,68,19,40,48,38,37
  out: 26,37,38,48,172
  exp: 26,37,38,48,172

ok: 55 / 55

方針

まず、データをどう取り扱うかについてですが、次の図のように右上方向・左上方向のx軸・y軸を設けて xy座標として管理することにしました。そうすると、正方形の辺が全てどちらかの軸に平行になって分かり易いためです。

この座標系のもとでは、「できるだけ下に置く」は「x+yがなるべく小さくなるように頂点を選ぶ」、同じ低さにあるもの同士での「できるだけ左に置く」は「xがなるべく小さくなるように頂点を選ぶ」と読み替えることができます。
※注: 純粋な「左」という意味では「x-yがなるべく小さく」ですが、既に「できるだけ下に」での抽出が終わっている段階を想定しているので x の1パラメータのみでの判定にしています。

そうして、正方形については、下の頂点の座標(x,y)と一辺の長さwの3つの整数値の組で管理します。例えば上図の36の正方形であれば、(27,8,36) という組み合わせになります。

では、肝心の正方形の配置の選択ですが、頂点の座標は配置済み正方形のいずれかの辺とx座標・y座標が一致することになることに注目します。
例えば、上の図のケースで36の正方形の配置を考える(27,17,8が配置済みの)時点では、x座標が 0,17,27,35、y座標が 0,8,27,44 の4通りずつが候補、頂点の座標は2乗した16通りが候補となっています。
もちろん、この中には明らかに使えない座標もあるのですが、素直に全部の座標から「配置済みの正方形と重ならないかどうか」をチェックして探すことにしました。
そのため、計算量としては正方形の数 n に対し、$O(n^4)$ です。正方形が数百個とかになるとちょっと厳しくなってきますが、今回の問題規模であれば十分かと思います。

詳細

では、コード内のソルバー部分についてです。
…が、正直、コメントで書いてあること以上にほとんど追加はありません。

なお、ソルバーとは別に Square という正方形情報を管理するクラスを定義しており、メソッド pos は Square 同士の位置関係を判定するものです。2つの Square が重なっていれば -1、接していれば 0、離れていれば 1 を返します。
そのため、「配置済みの正方形と重ならない」であれば squares.all?{|sq| sq.pos(newsq)>=0 } のように -1 を除外するような判定を、「最大の正方形に接している」であれば squares.select{|sq| sq.pos(biggest)==0 }.map(&:w).sort*?, のように 0 を抽出するような判定を行います。
※1頂点のみの共有は「離れている」という判定になります。

ソルバー部分

# ソルバー本体
def solve(src)
  # src: 正方形の幅のリスト
  # return: 回答の文字列
  #  ※最大の正方形に隣接する正方形の幅の昇順リストをカンマ区切り結合

  # 正方形の頂点のx座標、y座標の候補のリスト
  xvals = [0]
  yvals = [0]
  # 正方形の配置情報リスト
  squares = []

  # 配置する正方形の幅に対してループ
  src.each{|w|
    # 頂点の候補リストを優先度順にソートした状態で作成
    xylist = xvals.product(yvals).sort_by{|(x,y)| (x+y)**2+x }
    # 配置済みの正方形と重ならないように頂点を探索
    x,y = xylist.find{|(x,y)|
      newsq = Square.new(x,y,w)
      squares.all?{|sq| sq.pos(newsq)>=0 }
    }
    # 正方形情報および、次回以降のx,y座標候補を追加
    sq = Square.new(x,y,w)
    squares.push(sq)
    xvals.push(x+w)
    yvals.push(y+w)
  }
  # 最大の正方形および隣接する正方形情報を探索し、解を生成
  biggest = squares.max_by(&:w)
  squares.select{|sq| sq.pos(biggest)==0 }.map(&:w).sort*?,
end

補足:正方形の重なり判定

一応 Square クラスの実装部分のコードも挙げておきます。
posメソッドが位置関係の判定になるわけですが、Rubyの <=> 演算子を使えば割とそのままです。rhx, rhy がそれぞれ x軸、y軸方向での重なりあり(-1)、接している(0)、離れている(1) を判定した結果になっています。

Squareクラス実装

# 正方形の位置情報を扱うクラス
Square = Struct.new(:x,:y,:w) do
  # x,y,w → (x,y)が下の頂点、wが一辺の長さ

  # 正方形同士の位置関係の判定
  def pos(sq)
    # -1: intersect, 0: tangent, 1: far 
    rhx = (x<=>sq.x+sq.w)*(x+w<=>sq.x)
    rhy = (y<=>sq.y+sq.w)*(y+w<=>sq.y)
    rhx==-1 ? rhy : rhy==-1 ? rhx : 1
  end
end

追加実装

後日、速度を改善した高速版を同じくRubyで実装しました。ソースコードもgithub上のリポジトリに挙げています。

方針としては、従来のコードで正方形の頂点を馬鹿正直に全配置済み正方形のx,y座標から全検索していたのを、「現実的に正方形を置ける場所」を管理することで検索の手間を抑えようというものです。

この「置ける場所」についても、配置済みの正方形と同じように正方形のリストとして管理します。ただし「幾らでも大きな正方形を置ける」という状況については、仮想的に「幅無限大の正方形」として扱います。

例えば、テストケース1の 27→17→8→36→… と配置していく状況だと、8 を配置した時点では下図左側のように4つの幅無限大の正方形が「配置可能」分を表しています。

そこから 36 を追加配置すると、それまでの配置可能分は一部消えたり幅が制限されたり、それ以外には追加配置された正方形の屋根に乗っかるかたちで、配置可能正方形が追加されたりで、配置可能分のリストを更新することができます。
そのようにリストを持っておくことで、候補の数を大幅に減らすことができるという寸法です。

なお、配置可能な正方形を追加する場合は、配置済みの正方形の屋根の部分の線分情報をリストとして持っておいて、「屋根に乗っかるような正方形」を探していくことになります。
下図のように、追加された正方形の位置から段々と手前に探していき、矢印の終端のように既存の線分とぶつかる地点で探索を終了させれば十分です。( それより手前に「配置可能」は増えないため )

なお、この図が示す探索はあくまで配置可能な正方形の頂点を探すものであって、配置可能な幅は配置済みの正方形全てと照らし合わせて決定します。
そのため、ここがボトルネックになる可能性があり計算量は最悪で$O(n^3)$です。しかし実際にはそれほど配置可能な正方形が増えることは考えにくく、ほぼ$O(n^2)$で計算できることが期待できます。いずれにせよ、従来実装の$O(n^4)$よりは格段に速くなっています。

以下、ソルバー部分のコードです。まあ、実装内容はコメントの通りです。
従来の実装と違って、頂点を表すのに Vertex というクラスを導入していたり、線分の管理用に Line というクラスを追加していたりとありますが、そういった細部はリポジトリ上のコードをご覧ください。

高速版ソルバー部分

# ソルバー本体
def solve(src)
  # 頂点候補を作るための線分のリスト
  # vlsがy軸方向の線分用 ( p:x座標の降順にソート )
  # hlsがx軸方向の線分用 ( p:y座標の降順にソート )
  vls = [ Line.new(0,0,Float::INFINITY) ]
  hls = [ Line.new(0,0,Float::INFINITY) ]
  # 頂点候補毎に配置できる最大サイズの正方形のリスト
  # 「頂点の優先順位」の昇順にソート
  caps = [ Square.new(Vertex.new(0,0),Float::INFINITY) ]
  # 配置済み正方形のリスト
  squares = []

  src.each{|w|
    # 配置できる正方形のうち、サイズに収まる最優先のものを選出
    vn = caps.find{|c| c.w>=w }.v
    # 新たに配置する正方形をfix
    sq_a = Square.new(vn,w)
    # 新たに配置した正方形により、配置できる正方形のサイズをそれぞれ修正
    # ※サイズ0=配置できなくなったものは削除
    caps_upd = caps.map{|c|
      Square.new(c.v,[c.w,sq_a.wlimit(c.v)].min)
    }.reject(&:zero?)

    # 新たに配置した正方形の「屋根」にあたる辺に沿って、新たに配置可能となった
    # 情報を整理する

    # まずは頂点候補の選出
    vs_add = []
    # 鉛直、水平でxy座標の順が違うだけなので同じループで処理
    [ [vls,true], [hls,false] ].each{|(ls,xy_order)|
      # 屋根にあたる部分のLine(新規追加用)のパラメータ
      pn,sn = *xy_order ? [vn.x+w,vn.y] : [vn.y+w,vn.x]
      en = sn+w
      # vls/hls にLineを追加する場合のインデクス
      l_i=nil
      ls.each_with_index{|l,i|
        # 後ろ(無限遠方向)にある線分は無関係なので飛ばす
        next if l.p>pn
        # Lineのリストの降順を保つようにインデクスを決定
        l_i=i unless l_i
        # 頂点候補ができないケースは飛ばす
        next if l.e<=en
        # 頂点候補の追加
        vs_add.push(xy_order ? Vertex.new(l.p,en) : Vertex.new(en,l.p))
        # 屋根の射線が遮られる場合、これ以上候補ができないので終了
        break if l.s<=en
      }
      ls.insert(l_i,Line.new(pn,sn,en))
    }

    # 頂点候補を元に、配置済みの正方形と照らし合わせて
    # 追加分の「配置できる正方形」を決定
    caps_add = vs_add.map{|v|
      # 正方形の最大サイズは、配置済み正方形全てと突き合わせて最小値を採用
      wlim_min = squares.map{|sq_e| sq_e.wlimit(v) }.min || Float::INFINITY
      Square.new(v,wlim_min)
    }.reject(&:zero?)

    # 配置可能な正方形のリストと、配置済み正方形のリストを更新
    caps = merge(caps_upd,caps_add.sort)
    squares.push(sq_a)
  }
  # 最大の正方形および隣接する正方形情報を探索し、解を生成
  biggest = squares.max_by(&:w)
  squares.select{|sq| sq.pos(biggest)==0 }.map(&:w).sort*?,
end

おわりに

以前にyhpgに参加していた時は、変数名はほぼ1～2文字だったはずなのに、長い変数名を使ったりコメントを書いたり、独自クラスを整備したり。歳のせいか随分丸くなった気がします。…は置いておいて。
もう少し計算量のオーダーを下げたかったのですが、あんまりいいアイデアも思いつかなかったので、とにかく「素直さ」を重視しました。参考になれば幸いです。