CodeIQ：外周の折り目
私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「外周の折り目」（CodeIQ）を参照してください。
問題の概要
【概要】
紙を折り重ねた後、元の通りに開きます。
そのとき、紙の外周についた折り目がどうなっているのかを調べるプログラムを書いてください。
【入出力】
入力は
LBR
のような感じです。
折り方を示す記号が区切り文字なしで並んでいます。
記号の意味は下表の通りです：
記号 意味 図 L 左側半分を右側に折る。 R 右側半分を左側に折る。 T 上側半分を下側に折る。 B 下側半分を上側に折る。
出力は、外周についた折り目を、左上隅から時計回りに答えてください。
谷折りがvで、山折りがmです。先ほど示した入力LBRは下図のような折り目を作るので、
mvvvmvvm
が出力できれば正解です。
【例】
入力 出力 LBR mvvvmvvm TT mvvvvm
【補足】
不正な入力に対処する必要はありません。
紙を折る回数は1回以上、7回以下です。
私のプログラム
Rubyで解答しています。
#!/usr/bin/ruby
class Paper
attr_reader :folds
def initialize(before="LT", folds=[], left_top=true, grids=[1,1])
@before = before
@folds = folds
@left_top = left_top
@grids = grids
end
def foldBack(top_face, size)
face = top_face
folds = []
for _ in 0...size
if face then folds << "v"
else folds << "m"
end
face = !face
end
return folds
end
def foldT()
folds = []
folds << foldBack(@left_top, @grids[0])
folds << foldBack(@grids[1] == 1 ? @left_top : !@left_top, @grids[0])
turn = {
"LT" => [true, "LB"],
"LB" => [false, "LB"],
"RT" => [true, "RB"],
"RB" => [false, "RB"],
}
left_top = (turn[@before][0] ? !@left_top : @left_top)
return Paper.new(turn[@before][1], folds, left_top, [2*@grids[0], @grids[1]])
end
def foldB()
folds = []
folds << foldBack(@left_top, @grids[0])
folds << foldBack(@grids[1] == 1 ? @left_top : !@left_top, @grids[0])
turn = {
"LT" => [false, "LT"],
"LB" => [true, "LT"],
"RT" => [false, "RT"],
"RB" => [true, "RT"],
}
left_top = (turn[@before][0] ? !@left_top : @left_top)
return Paper.new(turn[@before][1], folds, left_top, [2*@grids[0], @grids[1]])
end
def foldL()
folds = []
folds << foldBack(@left_top, @grids[1])
folds << foldBack(@grids[0] == 1 ? @left_top : !@left_top, @grids[1])
turn = {
"LT" => [true, "RT"],
"LB" => [true, "RB"],
"RT" => [false, "RT"],
"RB" => [false, "RB"],
}
left_top = (turn[@before][0] ? !@left_top : @left_top)
return Paper.new(turn[@before][1], folds, left_top, [@grids[0], 2*@grids[1]])
end
def foldR()
folds = []
folds << foldBack(@left_top, @grids[1])
folds << foldBack(@grids[0] == 1 ? @left_top : !@left_top, @grids[1])
turn = {
"LT" => [false, "LT"],
"LB" => [false, "LB"],
"RT" => [true, "LT"],
"RB" => [true, "LB"],
}
left_top = (turn[@before][0] ? !@left_top : @left_top)
return Paper.new(turn[@before][1], folds, left_top, [@grids[0], 2*@grids[1]])
end
def fold(to)
ret = nil
case to
when "T"
ret = foldT()
when "B"
ret = foldB()
when "L"
ret = foldL()
when "R"
ret = foldR()
end
return ret
end
end
def addResult(before, current)
ret = []
for i in 0...current.size
bef = before[i]
cur = current[i]
sz = bef.size + cur.size
nxt = Array.new(sz)
bef.each_with_index{|b, j|
nxt[2*j+1] = b
}
cur.each_with_index{|c, k|
nxt[2*k] = c
}
ret << nxt
end
return ret
end
def getResultString(rows, cols)
if rows.empty? then
arr = cols[0] + cols[1].reverse[1..-1]
elsif cols.empty? then
arr = rows[0] + rows[1].reverse[1..-1]
else
arr = rows[0] + cols[1] + rows[1].reverse + cols[0].reverse
end
return arr.join("")
end
def solve(line)
paper = Paper.new()
folds_row = [[],[]]
folds_col = [[],[]]
line.chars{|c|
paper = paper.fold(c)
# p paper
if c == "T" || c == "B" then
folds_col = addResult(folds_col, paper.folds)
else
folds_row = addResult(folds_row, paper.folds)
end
}
# p folds_row
# p folds_col
return getResultString(folds_row, folds_col)
end
# main
while line = gets
line.strip!
if line.empty? then next end
puts solve(line)
end
解説
かなり難しいと思います。
ギブアップしようかと思っては少し考え、またギブアップを何回か繰り返してやっとできました。
考え方
まず、谷折りと山折りになる条件です。
折り紙を折る前に上を向いている面を表、反対側を裏とします。
折り重なった折り紙を上から見た時に表になっている場所についた折り目が「谷」、裏になっている場所についた折り目が「山」になります。
なので、n回目に折った時にできる折り目はn-1回目にできた区画（折り目と辺で囲めれた場所）が折り重なった折り紙を上から見た時に表か裏かが分かれば判定できることがわかります。
次に重要な性質ですが、折り紙を折った場合、互いに辺で繋がる区画は一方が表、他方が裏になります。図示すると次のようになります。
つまり、ある時点で左上が表か裏かが分かればそれを起点として全ての区画の表裏がわかります。
もうひとつ重要な性質ですが、ある区画を折った時にできる折り目と新たな区画は他の区画に依存しない、ということです。わかりやすく説明するのが難しいですが、折り目に沿って切り離してしまい、新たな1枚の紙として考えても問題ないということです。
このことから問題の答えを求める上では上下左右の辺の部分だけを考えればよくて、中央の状態は関係ないことがわかります。
最後に紙を折った時に新しくできる区画の表裏が、折る前の区画に対して裏返しになるか、表裏は変化しないかの法則です。
これは左上の角が折り返し前に左上、右上、左下、右下のどの場所にあったかと、折る方向でわかります。例えば、折る前に左上にあった場合、BとRの方向に折っても基準となる角を含む区画の表裏は変わりませんが、BとLの方向に折った場合は反転します。
| 元 | T | B | L | R | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
以上の考え方を総合すると問題を解くことができます。
main
入力値を solve()に渡します。
solve()が結果を返すのでそれを印字して終わります。
solve(line)
答えを計算します。
折り紙の状態はPaperクラスのインスタンスで管理します。変数paperは1回も折っていない状態の折り紙でインスタンスを作成しておきます。
folds_rowは上辺と下辺にできた折り目を保持する領域で、上辺が要素0、下辺が要素1です。上辺下辺とも左から右に向かって折り目を保持しています。
folds_colは左辺と右辺にできた折り目を保持する領域で、左辺が要素0、右辺が要素1です。左辺右辺とも上から下に向かって折り目を保持しています。
入力値を1文字ずつ取り出し、Paper#fold()で指定された方向に折った紙の状態を取得します。
インスタンス変数paper#foldsには新たにできた折り目のリストが入っているので、addResult()でその折り目をそれまでの折り目に追加します。
最後にgetResultString()で折り目情報を文字列にして返却します。
Paperクラス
折り紙の状態を管理するクラスです。
メンバ変数は次の通りです。
@before：左上角が現在どこにあるか（"LT"：左上、"LB"：左下、"RT"：右上、"RB"：右下）
@folds：最新の折り目リスト。[[上辺], [下辺]]か[[左辺, 右辺]]。
@left_top：左上の区画が表（true）か裏（false）か。
@grids：区画の数。[行数, 列数]
Paper#fold(to)
引数toの方向への折り曲げ処理をします。
引数によってfoldT()、foldB()、foldL()、foldR()のどれを呼ぶかを判断するだけです。
折り曲げた結果の状態を表すPaperクラスのインスタンスを返します。
Paper#foldT()、foldB()、foldL()、foldR()
各方向への折り曲げを処理します。
処理の実態はPaper#foldBack()で、この関数に渡すパラメータと折った後の状態を表すインスタンス作成のためのパラメータを作るのが仕事です。
4つのメソッドの仕事はだいたい同じなのでfoldT()だけを説明します。
変数foldsは新たにできる折り目のリストを保持する領域です。
30行目のfoldBack()で左辺、31行目で右辺の折り目を求めます（foldL()、foldR()は上辺、下辺になる）。
左辺の各区画の表裏は@left_topを基準にすれば良いのでfoldBack()の第一引数にそのまま渡します。第二引数は区画の数です。
右辺は少しややこしく、1列しかない場合と2列以上の場合で右辺の先頭の区画の表裏が変わります。1列しかない場合（1回もLかR方向に折られていない場合）は左辺と右辺の区別がありませんので基準となる区画の表裏は左辺の場合と同じですが、2列以上ある場合は反転します。これを考慮して31行目で右辺の折り目を求めます。
定数turnは折った時に基準となる区画の表裏が変わるか（true：変わる、変わらない：false）、左上角がどの場所に移動するかを現在の左上角の場所から求めるためのものです。
39行目で折った後の基準区画の表裏を計算しています。
41行目で折った後の状態でPaperのインスタンスを新規に作成して返します。
Paper#foldBack(top_face, size)
折り紙を折った時に新たにできる折り目を求めます。
引数top_faceは基準となる区画の表裏で、sizeは区画数です。
faceは現在の区画の表裏で初期値はtop_faceと同じです。
foldsは折り目のリストです。
区画の数だけ折り目を作ります（17〜23行目）。
区画が表なら谷折り"v"、裏なら山折り"m"をfoldsに追加します。
隣の区画は必ず表裏反転するので1区画終わるごとにfaceを反転します。
折り目のリストを返却します。
addResult(before, current)
それまでの折り目リストに新しい折り目リストを追加します。
引数beforeは上辺下辺か左辺右辺のそれまでの折り目リストです。
引数currentは上辺下辺か左辺右辺の新たな折り目リストです。
上辺と下辺、左辺と右辺があるのでその分ループします（112〜128行目）。
befは1辺のこれまでの折り目リスト、curは1辺の新たな折り目リストです。
新しい折り目リストのサイズはbefとcurのサイズの合計になるのでそれだけの領域を確保します。
新たな折り目を追加した時、元の折り目は奇数番号の位置に移り、新たな折り目は偶数番号の位置に配置されます。わかりにくいので図示します（元の折り目を小文字、新たな折り目を大文字で区別しています）。
| 元 |
|
|||||||
|---|---|---|---|---|---|---|---|---|
| 新 |
|
|||||||
| 合計 |
|
この処理の元の折り目部分の処理を119〜121行目、新たな折り目部分の処理を123〜126行目でやっています。
結果は上辺下辺か左辺右辺のセットなのでそれを返却します。
getResultString(rows, cols)
結果文字列を作ります。
LR方向だけ、TB方向だけに折り返された場合とそれ以外で処理が変わります。
LR方向だけ、TB方向だけに折り返された場合は要素のある折り目リストだけを連結します（下辺、右辺は反転します）。ただし、連結部分の折り目が重複するのでそれを無視します。
縦横両方に折られた場合は全ての辺に折り目があるのでそれを連結します。外周なので上辺、左辺、下辺、右辺の順に連結します（下辺、右辺は反転します）。
結果を文字列にして返却します。
雑感
非常に苦労しました。私の頭だと3回以上頭の中で折り紙を折ることはできません。実際に紙を折ってみても4回くらいで折り目がはっきりしなくて（見えなくて）嫌になります。
折り紙を折った時に区画の表裏が交互に現れることは調べてわかりました。これはかなり大きなブレイクスルーで全体を管理しなくて良くなる上、扱いが単純になるので助かりました。また、これによって上下左右の辺だけを調べれば良いことに気づいたのも大きいです。
左上の区画の表裏と上下左右の辺にできた折り目だけを管理すれば答えには十分というのは割とすぐにたどり着いたのですがそこから結構苦労しました。