Skip to content

Instantly share code, notes, and snippets.

@Kuniwak Kuniwak/codeiq_q684.md
Last active Aug 29, 2015

Embed
What would you like to do?
結城さんの問題の解答。王女様の宝石パターンを見つけよう! by The Essence of Programming【https://codeiq.jp/ace/yuki_hiroshi/q684

ポイント

次のルール従って、宝石を配置していく。ただし、素直に解こうとすると計算量が爆発するので、メモ化するなどして計算量を抑える工夫が必要。

ルール

  1. 未配置の宝石があるときは、そのなかで最も小さい(aが最小)アルファベット を順に配置していく。
  2. 未配置の宝石がなくなったら、未配置の宝石の中に、取り除いた後の末尾よりも 大きいアルファベットの宝石が含まれるようになるまで末尾を取り除く。次に、 配置済の宝石の末尾より大きいアルファベットをもつ宝石のうち、もっとも アルファベットが小さい宝石を、配置済の宝石の末尾と置き換える。
  3. 未配置の宝石がなく、かつルール2で置き換えられる宝石が無くなったら終了

メモ化

ルール2で置き換えた後の配置済の宝石の種類の組が、以前計算したものと同じであれば計算結果を再利用できる。 たとえば、問題文中図2の並びの12〜20日と38〜46日をみると、4つめ以降の宝石の並びが同じになっている。 つまり、38〜46日の方は、以前の結果を再利用できる。

日: 帯の宝石
12: aab|
13: aab|a
14: aab|ac
15: aab|acc
16: aab|c
17: aab|ca
18: aab|cac
19: aab|cc
20: aab|cca

38: aba|
39: aba|a
40: aba|ac
41: aba|acc
42: aba|c
43: aba|ca
44: aba|cac
45: aba|cc
46: aba|cca

コード

import bisect
import logging


class QueensGemSolverError(Exception):
    pass


class QueensGemSolver:
    class TransitionError(QueensGemSolverError):
        def __init__(self, transit_from, transit_to):
            self.transit_from = transit_from
            self.transit_to = transit_to

        def __str__(self):
            return 'Cannot transit to {0} from {1}'.format(self.transit_to,
                                                           self.transit_from)

    def __init__(self, gems=[]):
        self.unallocated = sorted(gems)
        self.gem_count = len(gems)
        self.allocated = []
        self.history = {}
        self.depth_history = []

    def allocate_gem(self, gem=None, idx=None):
        if gem is None:
            will_be_allocated = self.unallocated.pop(0)
        else:
            self.unallocated.remove(gem)
            will_be_allocated = gem

        if idx is None:
            self.allocated.append(will_be_allocated)
        else:
            self.allocated.insert(idx, will_be_allocated)

    def unallocate_gem(self, idx):
        unallocated = self.allocated.pop(idx)
        bisect.insort(self.unallocated, unallocated)
        return unallocated

    def unallocate_last_gems(self, start=0):
        will_be_unallocated = []
        for idx in range(0, len(self.allocated) - start):
            will_be_unallocated.append(self.unallocate_gem(start))

        return will_be_unallocated

    def get_greatest_transitable_gem_index(self):
        for pivot_gem_idx in reversed(range(0, len(self.allocated))):
            assumed_unallocated = set(self.unallocated + self.allocated[pivot_gem_idx + 1:])
            pivot_gem = self.allocated[pivot_gem_idx]
            for gem in assumed_unallocated:
                if pivot_gem < gem:
                    return pivot_gem_idx

        return None

    def transit_gem(self, idx):
        transit_from = self.unallocate_gem(idx)
        transit_to = None
        for gem in sorted(self.unallocated, reverse=True):
            if gem > transit_from:
                transit_to = gem
            else:
                break

        if transit_to is None:
            raise QueensGemSolver.TransitionError(transit_from, transit_to)

        self.allocate_gem(transit_to, idx)

    def add_depth_history(self):
        depth = len(self.allocated) - 1
        if len(self.depth_history) <= depth:
            self.depth_history.append(self.day)
        else:
            self.depth_history[depth] = self.day

    def add_history(self, idx):
        history_key = ''.join(sorted(self.allocated[0:idx + 1]))
        self.history[history_key] = self.day - self.depth_history[idx]

    def pivot(self, idx):
        self.unallocate_last_gems(idx + 1)
        self.transit_gem(idx)

    def log(self):
        logging.debug('{0} | {1} | {2}'.format(
            str(self.day).rjust(10),
            ''.join(self.allocated).ljust(10),
            ''.join(self.unallocated).ljust(10)))

    def solve(self, gem_list):
        self.day = 0
        while True:
            self.day += 1

            if len(self.unallocated) > 0:
                history_key = ''.join(sorted(self.allocated))

                # 探索している宝石がスキップ対象の中に含まれているかどうかを判定
                match = [self.allocated[idx] == gem_list[idx]
                         for idx in range(0, min(len(self.allocated), len(gem_list)))]

                if history_key in self.history and not all(match):
                    # 履歴に残っていれば計算したことにしてpivotへ
                    skipped_day = self.history[history_key] - 1
                    self.day += skipped_day

                    logging.debug('Hit history: {0} in {1}, skipping {2}'.format(
                        history_key,
                        ''.join(self.allocated),
                        skipped_day))
                else:
                    # 履歴に残っていなければ実際に計算
                    # または探索している宝石がスキップ対象に含まれている場合も実際に計算
                    self.allocate_gem()

                    self.add_depth_history()
                    self.log()
                    if self.allocated == gem_list:
                        return self.day
                    continue

            pivot_gem_idx = self.get_greatest_transitable_gem_index()
            if pivot_gem_idx is None:
                break

            self.add_history(pivot_gem_idx)
            self.pivot(pivot_gem_idx)

            self.add_depth_history()
            self.log()
            if self.allocated == gem_list:
                return self.day

        return None

if __name__ == '__main__':
    logging.basicConfig(level=logging.DEBUG, format='[%(levelname)s] %(message)s')
    solver = QueensGemSolver([char for char in 'abbbbcddddeefggg'])
    print(solver.solve([char for char in 'eagcdfbe']))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.