あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定
Pythonで解きました。所要時間は１時間ぐらいだと思います（時間を測るのを忘れました）。
#encoding:shift-jis from __future__ import division, print_function __metaclass__ = type import re from itertools import permutations, combinations def removed(alist, x): alist = list(alist) alist.remove(x) return alist def combinations2(iterable, r): """ combinations2('ABCD', 2) --> (AB,CD) (AC,BD) (AD,BC) (BC,AD) (BD,AC) (AB,CD) >>> from itertools import combinations >>> i2 = s.combinations2("ABCDE", 2) >>> i1 = s.combinations("ABCDE", 2) >>> all(x == y for x, (y, _) in zip(i1, i2)) True """ pool = tuple(iterable) n = len(pool) for indices in permutations(range(n), r): if sorted(indices) == list(indices): comb = tuple(pool[i] for i in indices) rest = tuple(pool[i] for i in xrange(n) if i not in indices) yield comb, rest def is_pair(tiles): assert len(tiles) == 2 return len(set(tiles)) == 1 def is_triple(tiles): assert len(tiles) == 3 return len(set(tiles)) == 1 def is_seq(tiles): assert len(tiles) == 3 tiles = sorted(tiles) return tiles[0] == (tiles[1] - 1) == (tiles[2] - 2) def pop_body(tiles): """ パイの中から、『体』になりうる３枚組を全て見つけ、 ３枚組みとそれ以外を返します。 """ for comb, rest in combinations2(tiles, 3): if is_triple(comb) or is_seq(comb): yield comb, rest def pop_head(tiles): """ パイの中から、『頭』になりうる２枚組を全て見つけ、 ２枚組みとそれ以外を返します。 """ for comb, rest in combinations2(tiles, 2): if is_pair(comb): yield comb, rest def stuple(iterable, *a, **kw): return tuple(sorted(iterable, *a, **kw)) def split_tiles_3(tiles): """ 13 - 1 = 12 枚のパイを 3, 3, 3, 3 の体4つに分解する仕方を返します """ bodies = set() add = bodies.add for t1, r1 in pop_body(tiles): for t2, r2 in pop_body(r1): for t3, r3 in pop_body(r2): for t4, r4 in pop_body(r3): add(stuple([t1, t2, t3, t4])) return bodies def split_tiles_2_3(tiles): """ 13 - 2 = 11 枚のパイを 2, 3, 3, 3 の頭1つと体4つに分解する仕方を返します """ bodies = set() add = bodies.add for t1, r1 in pop_head(tiles): for t2, r2 in pop_body(r1): for t3, r3 in pop_body(r2): for t4, r4 in pop_body(r3): add(stuple([t1, t2, t3, t4])) return bodies def solv_1(tiles): """ 13枚の牌から「待ちの部分」が1枚になる、待ちを探します。 """ tiles = sorted(int(t) for t in tiles) for t in set(tiles): tiles1 = removed(tiles, t) for body in split_tiles_3(tiles1): yield (body, (t,)) def is_wait2(t): """ 「待ちの部分」になりうる２枚か判定します。 すなわち、アンコかシュンツを作りうるか判定します。 """ assert len(t) == 2 return (t[0] - t[1]) in [-2, -1, 0, 1, 2] def solv_2(tiles): """ 13枚の牌から「待ちの部分」が2枚になる、待ちを探します。 """ tiles = sorted(int(t) for t in tiles) for t in set(combinations(tiles, 2)): if not is_wait2(t): continue tiles1 = removed(removed(tiles, t[0]), t[1]) for body in split_tiles_2_3(tiles1): yield (body, t) def solv(tiles): """すべての待ちをタプルで返す""" tiles = [int(t) for t in tiles] answers = [] answers.extend(solv_1(tiles)) answers.extend(solv_2(tiles)) return answers def solv_s(s): """回答を文字列で返す""" return [ans_to_str(ans) for ans in solv(s)] def ans_to_str(ans): body, w = ans body = ["".join(map(str, t)) for t in body] w = "".join(map(str, w)) return "({0[0]})({0[1]})({0[2]})({0[3]})[{1}]".format(body, w) def str_to_ans(s): m = re.match("\((\d{2,3})\)\((\d{2,3})\)\((\d{2,3})\)\((\d{2,3})\)\[(\d{1,2})\]", s) bodies = stuple(stuple(int(d) for d in m.group(i)) for i in [1, 2,3,4]) wait = stuple(int(d) for d in m.group(5)) return (bodies, wait) def answer_eq(ans1, ans2): return stuple(str_to_ans(ans) for ans in ans1) == stuple(str_to_ans(ans) for ans in ans2) def test(): assert answer_eq(solv_s("1112224588899"), ["(111)(222)(888)(99)[45]"]) assert answer_eq(solv_s("1122335556799"), [ "(123)(123)(555)(99)[67]", "(123)(123)(55)(567)[99]", "(123)(123)(99)(567)[55]", ]) assert answer_eq(solv_s("1112223335559"), [ "(123)(123)(123)(555)[9]", "(111)(222)(333)(555)[9]", ]) assert len(solv_s("1223344888999")) == 3 from pprint import pprint #九蓮宝燈は、すべての待ちを数えられなかったので、出力のみ pprint((solv_s("1112345678999"))) def main(): test() if "__main__" == __name__: main()
パソコンが修理中だったので、Pythonは久しぶりだったのですが、
一時HaskellやClojureの勉強をしたせいか、
listを非破壊的に操作する関数が無いことが窮屈に感じました。
上のコードで言えば、removedのような関数が標準で用意されていて欲しいです。
並行処理うんぬんのような、難しい意味では無くて、
単にリストを複製する必要がなくなり、コードが短くなるという意味ですが。
