次のルール従って、宝石を配置していく。ただし、素直に解こうとすると計算量が爆発するので、メモ化するなどして計算量を抑える工夫が必要。
- 未配置の宝石があるときは、そのなかで最も小さい（aが最小）アルファベット を順に配置していく。
- 未配置の宝石がなくなったら、未配置の宝石の中に、取り除いた後の末尾よりも 大きいアルファベットの宝石が含まれるようになるまで末尾を取り除く。次に、 配置済の宝石の末尾より大きいアルファベットをもつ宝石のうち、もっとも アルファベットが小さい宝石を、配置済の宝石の末尾と置き換える。
- 未配置の宝石がなく、かつルール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']))