CodeIQの言語総選挙の予選でcodegolf

Golf Ruby CommonLisp

先月開催されたCodeIQの言語総選挙の問題の予選ルールがショートコーディング入門によさ気で面白かったのです。 出題者がショートーコーディング本の著者のOzyさんという事もあり、これは解説でゴルフコードの紹介なんかもあるんでないかなーと期待して気合を入れて短くしたコードを投稿したのですが、全く触れられていなくて無念…

というわけで、ここで短くして行った過程を解説してみようと思います。 私の回答はCommonLispで書いて提出したのですが、折角なので1位を取ったRubyで書きなおしてみました。

問題

問題も解説もCodeIQにログインしないと見れないので簡単に説明。

教室に席が格子状に並んでおり、出席者をO、欠席者をXで表した表が標準入力から与えられる。 生徒たちが前後or左右の隣りの生徒と2人1組のグループを作る時、余りが出ない配置の場合はyes、どう組んでも余る生徒が出てしまう場合はnoと出力せよ、という問題。

(例)

OOOOO
OOOXO
OOOOO

上図の場合、ペアを数字で表すと

11223
445X3
66577

のように組めるのでyesと出力する。

OOO
OOX
OOO

だと

122
13X
O3O

のようにペアを作れない生徒が出てしまうのでno。

入力データの条件として以下の制限があります。

席の列数をW, 行数をH, 欠席者の数をXとした時
予選 : 2≦W*H≦30, 0≦X≦1
本選 : 1≦W≦10, 1≦H≦10, 0≦X≦W*H

素朴な深さ優先探索で予選も本選も用意されたテストケースは全て通ってしまうようですが、予選の条件では後に解説するように簡単に判別する方法がありました。

以下予選の条件で解法を考えていきます。

方針1. 塗り分け&数え上げ

まずCodeIQの解説にあったやり方。 下図のように各席を市松模様のように塗り分けて考えます。

f:id:youz:20141013174136p:plain

ペアは必ずA席とB席の生徒で組まれるので、出席者のうちA席の生徒とB席の生徒をそれぞれ数え上げて同数なら余りが出ない、という考え方です。 欠席者が複数になるとAB同数でも余りが出る場合がありますが、欠席者が最大1名の予選ルールならこの数え上げだけで解が出ます。

というわけで最初のコード

def solve(input)
  map = input.split(/\n/)
  w = map[0].length
  h = map.length
  counts = [0, 0]   # A席,B席の生徒数を記録する配列
  h.times do |y|
    w.times do |x|
      if map[y][x] == "O"
        counts[(x+y)%2] += 1
      end
    end
  end
  counts[0]==counts[1]
end

puts solve($<.read) ? "yes" : "no"

一番左上の席の座標を(x,y) = (0,0)として、x+yが偶数だったらA席、奇数だったらB席と判定しています。

変数名を短くするだとか空白・改行を削るだとかの作業は一番最後にやるとして、まずアルゴリズムの簡素化をしていきます。

1重ループ化

とりあえず2重ループを1重にできないかなと考えます。 幅が奇数の場合は、下図のように改行を取っ払って1行にしてしまっても数え上げはうまく行きます。

ABA
BAB → ABABABABA
ABA

左端を0番目として、偶数番目がA席で奇数番目がB席。よって2重ループの部分は

map = input.delete("\n")
map.length.times do |i|
  if map[i] == "O"
    counts[i%2] += 1
  end
end

と短く出来ます。

幅が偶数の場合は改行を取っ払ってしまうと

ABAB
BABA → ABABBABAABAB
ABAB

のようになってしまってABの判別が面倒な事になります。 しかし幅が偶数ということは欠席者のいない行は必ずAの数=Bの数なので、欠席者のいる行だけ考えればよろしい。 そうすると先の奇数幅用のコードでも結果的には問題ないことがわかります。ちょっと気持ち悪いけど。

というわけで全体としてはこんな感じに。

def solve(input)
  map = input.delete("\n")
  counts = [0, 0]
  map.length.times do |i|
    if map[i] == "O"
      counts[i%2] += 1
    end
  end
  counts[0] == counts[1]
end

puts solve($<.read) ? "yes" : "no"

数え上げの工夫

配列を使って数え上げてるのがイケてない気がするのでなんとかしたいと考えた所、数え上げ用変数を1つだけ用意して、偶数番目だったらデクリメント・奇数番目だったらインクリメントして最終的に0になっていればOkとする方法がありました。

def solve(input)
  map = input.delete("\n")
  c = 0
  map.length.times do |i|
    if map[i] == "O"
      c += i%2*2-1
    end
  end
  c == 0
end

数え上げの所はc += i%2-0.5として0.5ずつ増減させる方法もアリ。

この時点でアルゴリズム上の工夫はこれ以上思いつかなくなってしまったので、一旦畳んでスコア(コード長)を測ってみます。

c=0
(m=$<.read.delete("\n")).length.times{|i|m[i]=="O"&&c+=i%2*2-1}
puts c==0?"yes":"no"

89バイトになりました。 とりあえずこの方針はここで一旦保留。

方針2. 欠席者の位置から判断

W*Hが偶数の場合は欠席者の有無、奇数の時はA席の生徒が欠席しているかどうかで判断できるのだから数え上げるまでもないですよね、という考え。

要するにこう。

  • W*H が偶数
    • 欠席者ナシ → yes
    • 欠席者アリ → no
  • W*H が奇数
    • 欠席者ナシ → no
    • 欠席者はA席 → yes
    • 欠席者はB席 → no

という訳で最初のコードがこちら

def solve(input)
  map = input.split("\n")
  w = map[0].length
  h = map.length
  if (w*h).even?
    # 偶数なら欠席者がいなければ"yes"
    input !~ /X/
  else
    # 奇数の場合
    h.times do |y|
      w.times do |x|
        if map[y][x] == "X"
          # 欠席者が見つかったらA席かどうかを返して終了
          return (x+y).even? 
        end
      end
    end
    # 欠席者が見つからなかったら"no"
    false
  end
end

puts solve($<.read) ? "yes" : "no"

方針1に比べて大分長い所からスタートする感じですが頑張って短くして行きましょう。

まず奇数の場合は方針1で使った1重ループ化の考え方が問題なく使える & 改行取っ払ってしまえば偶奇判定も楽という事で

def solve(input)
  map = input.delete("\n")
  l = map.length
  if l.even?
    input !~ /X/
  else
    l.times do |i|
      if m[i] == "X"
        return i.even?
      end
    end
    false
  end
end

っと、ループの所、文字列の探索ならindexメソッドで十分ですね。

def solve(input)
  map = input.delete("\n")
  if map.length.even?
    input !~ /X/
  else
    pos = map.index("X")
    !pos.nil? && pos.even?
  end
end

大分スッキリしましたが、偶数の場合奇数の場合それぞれでXを検索してるのが気になる所。 とりあえずposの取得を前に持ってきてみる。

def solve(input)
  map = input.delete("\n")
  pos = map.index("X")
  if map.length.even?
    pos.nil?
  else
    !pos.nil? && pos.even?
  end
end

この時点では畳んでもなんとか100を切れる程度。 全体長の偶奇で処理分けてるのコスト高いよなー何とかしたい、と風呂で考えてたら良いアイデアが降ってきました。

def solve(input)
  input.delete("\n").split("X").all?{|l|l.length.even?}
end

入力から改行を取っ払った上でXの位置で分割してしまえ、というアイデア。どうなるかいうと

  • W*H が偶数
    • 欠席者アリ(no) → 分割すると["OOOO", "O"]のように、長さが奇数の文字列と長さが偶数の文字列を要素に持つ配列になる
    • 欠席者ナシ(yes) → 分割されないので、偶数長の文字列1つを要素に持つ配列になる
  • W*H が奇数
    • 欠席者ナシ(no) → 奇数長の文字列1つを要素に持つ配列になる
    • 欠席者はA席(yes) → ["OO", "OOOOOO"]のように、偶数長の文字列2つを要素に持つ配列になる
    • 欠席者はB席(no) → ["OOO", "OOOOO"]のように、奇数長の文字列2つを要素に持つ配列になる

つまり、分割した結果、偶数長の文字列だけを持つ配列になる場合にyesとすれば良い訳です。

分割して、断片の長さの偶奇を測る、たったこれだけの作業ならアレで一発ですよねーという訳で

def solve(input)
  input.delete("\n") =~ /^(OO)*X?(OO)*$/
end

正規表現のマッチング1回で済んでしまいました。 畳んで全体を書くと

puts $<.read.delete("\n")=~/^(OO)*X?(OO)*$/?"yes":"no"

54バイトに。これだけ単純になると文法上のハックはほとんど必要ないですね。

保留にしておいた方針1でこれを超えるのは無理でしょう(多分)、という事でこれが私の回答の最終形。

二次元的な情報を全部捨ててしまっていて、一見するとこれは(用意されているテストケースだけ通る)cheatコードでしょーと 思ってしまいそうな回答ですが、ちゃんとどんなパターンにも対応できているっていうのが面白いです。

おまけで、予選落ちとなってしまったCommonLispのコードの供養。

予選用

(princ(if(regexp:match"^\\(OO\\)*X\\?\\(OO\\)*$"(format()"~{~A~}"(loop
while(listen)collect(read))))"yes""no"))

本選用

探索の前に

  • AB塗り分けによる枝刈り
  • 組む相手が1人しかいない箇所を予め埋めておく
  • 探索が早く収束するように、全体を4分割して欠席者が最も多いブロックから探索を開始する

といった工夫を入れた所、extracaseにも全て対応できました。