やってみた

makeplex salon：あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ
3時間でできなければ優秀でないことが証明されてしまうことで一部で話題になっている問題をやってみた。
結果は...

“ほぼ確実に”優秀ではない！orz

とりあえずコード晒しとく。Rubyで書いたのにやけに長い。
真面目にアルゴリズムの勉強しないとだめだなぁ。

Kotsu = 1
Shuntsu = 2
Any = 3
class Array
    def Array.deepcopy(arr)
        Marshal.load(Marshal.dump(arr))
    end

    def top
        self[self.length - 1]
    end

    def car
        if self.length > 0
            self[0]
        else
            nil
        end
    end

    def cdr
        new_a = Array.deepcopy(self)
        new_a.shift
        new_a
    end

    def rest(i)
        new_a = Array.deepcopy(self)
        new_a.delete_at(i)
        new_a
    end
end

class Machi
    def initialize
        @machi = nil
        @atama = nil
        @triple = []
    end
    attr_accessor :machi, :atama, :triple

    def eql?(m)
        self.hash == m.hash
    end

    def hash
        str = @triple.sort.join
        str += @atama.join if @atama
        str += @machi.join if @machi
        str.hash
    end

    def print
        @triple.sort!
        @triple.each{|t|
            STDOUT.print "(#{t.join})"
        }
        STDOUT.print "(#{@atama.join})" if @atama && @atama.length > 0
        STDOUT.print "[#{@machi.join}]" if @machi
        STDOUT.print "\n"
    end

    def deepcopy
        new_machi = Machi.new
        new_machi.machi = Array.deepcopy(self.machi)
        new_machi.atama = Array.deepcopy(self.atama)
        new_machi.triple = Array.deepcopy(self.triple)
        new_machi
    end
end

def check_four_tiles(n)
    $four_tiles.each{|t| return true if t == n}
    return false
end

def search_same(temp, rest)
    return {} if temp.length == 0
    v = temp[0]
    for i in 0...rest.length
        if v == rest[i]
            return {v => rest.rest(i)}
        end
    end
    return {}
end

def search_forward_backword(temp, rest)
    return {} if temp.length == 0
    if temp.length == 2
        return {} if temp[1] - temp[0] != 1
    end
    forward = temp.first - 1
    backward = temp.last + 1
    result = {}
    for i in 0...rest.length
        if rest[i] == forward || rest[i] == backward
            if !result.key?(rest[i])
                result[rest[i]] = rest.rest(i)
            end
        end
    end
    return result
end

def search_aida_machi(temp, rest)
    return {} if temp.length != 1
    forward = temp.first - 2
    backward = temp.last + 2
    result = {}
    for i in 0...rest.length
        if rest[i] == forward || rest[i] == backward
            if !result.key?(rest[i])
                result[rest[i]] = rest.rest(i)
            end
        end
    end
    return result
end

def get_machi(shuntsu2)
    return [] if shuntsu2.length != 2
    case shuntsu2[1] - shuntsu2[0]
    when 1
        ret = []
        ret << shuntsu2[0] - 1 if shuntsu2[0] > 1
        ret << shuntsu2[1] + 1 if shuntsu2[1] < 9
        return ret
    when 2
        return [shuntsu2[1] - 1]
    else
        return []
    end
end

def search(type, rest, temp, result)
    if rest.length == 0 && temp.length == 0
        $final_result << result
        return
    end
    case type
    when Kotsu
        search_same(temp, rest).each{|num, new_rest|
            new_result = result.deepcopy
            new_result.triple << (temp + [num])
            search(Any, new_rest, [], new_result)
        }
    when Shuntsu
        search_forward_backword(temp, rest).each{|num, new_rest|
            new_result = result.deepcopy
            new_result.triple << (temp + [num]).sort
            search(Any, new_rest, [], new_result)
        }
    when Any
        if temp.length == 0
            search(Any, rest.cdr, temp + [rest.car], result.deepcopy)
            if !result.atama && !result.machi && !check_four_tiles(rest.car) #一個待ちパターン
                new_result = result.deepcopy
                new_result.machi = [rest.car]
                new_result.atama = []
                search(Any, rest.cdr, [], new_result)
            end
        elsif temp.length == 1
            search_same(temp, rest).each{|num, new_rest|
                search(Kotsu, new_rest, temp + [num], result.deepcopy)
                if !result.atama #頭パターン
                    new_result = result.deepcopy
                    new_result.atama = temp + [num]
                    search(Any, new_rest, [], new_result)
                end
                if !result.machi && !check_four_tiles(num) #刻子待ちパターン
                    new_result = result.deepcopy
                    new_result.machi = temp + [num]
                    search(Any, new_rest, [], new_result)
                end
            }
            search_forward_backword(temp, rest).each{|num, new_rest|
                search(Shuntsu, new_rest, (temp + [num]).sort, result.deepcopy)
                exist_machi = false
                get_machi((temp + [num]).sort) .map{|m| !check_four_tiles(m)} .each{|m| exist_machi |= m}
                if !result.machi && exist_machi #順子待ちパターン
                    new_result = result.deepcopy
                    new_result.machi = (temp + [num]).sort
                    search(Any, new_rest, [], new_result)
                end
            }
            if !result.machi
                search_aida_machi(temp, rest).each{|num, new_rest|
                    exist_machi = false
                    get_machi((temp + [num]).sort) .map{|m| !check_four_tiles(m)} .each{|m| exist_machi |= m}
                    if exist_machi
                        new_result = result.deepcopy
                        new_result.machi = (temp + [num]).sort
                        search(Any, new_rest, [], new_result)
                    end
                }
            end
        end
    end
end

def check_number_of_every_tile(tiles)
    arr = []
    ret = []
    arr.fill(0, 1..9)
    tiles.each{|t| arr[t.to_i] += 1}
    for i in 1..9
        ret << i if arr[i] == 4
    end
    ret
end

$final_result = []
$four_tiles = []
input = [
    "1112224588899",
    "1122335556799",
    "1112223335559",
    "1223344888999",
    "1112345678999",
    "1113335558888",
    "1222233456788",
    "1223567789789"
]

input.each{|i|
    $final_result.clear
    $four_tiles.clear
    puts i
    nums = i.split(//).map{|n| n.to_i}.sort
    $four_tiles = check_number_of_every_tile(nums)
    search(Any, nums, [], Machi.new)
    $final_result.uniq.each{|r| r.print}
    puts
}