#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# @file robot_steps_calculator.py
# @author kaka_ace
# @date Mar 27 2015
# @breif
#
import copy
class RobotBrain(object):
CACHE_INIT = {
1: [['1']],
2: [['1', '1'], ['2']],
3: [['1', '1' ,'1'], ['1', '2'], ['2', '1'], ['3']],
}
CACHE_KEY_MAP_INIT = dict()
for k, v in CACHE_INIT.items():
for l in v:
s = "".join(l)
CACHE_KEY_MAP_INIT[s] = True
def __init__(self):
self.cache = copy.deepcopy(self.CACHE_INIT)
self.cache_key_map = copy.deepcopy(self.CACHE_KEY_MAP_INIT)
def output_solution(self, n: "total length, positive number") -> None:
if n <= 3:
print(RobotBrain._ouput_result(self.cache[n]))
return
i = 4
while i <= n:
"""
f(i) = 1 + f(i-1)
= 2 + f(i-2)
= 3 + f(i-3)
= f(i-1) + 1
= f(i-2) + 2
= f(i-3) + 3
we need to remove duplicates
"""
self.cache[i] = []
for step in range(1, 4):
self._add_to_cache(1, i, True)
self._add_to_cache(2, i, True)
self._add_to_cache(3, i, True)
self._add_to_cache(1, i, False)
self._add_to_cache(2, i, False)
self._add_to_cache(3, i, False)
i += 1
self._ouput_result(self.cache[n])
def _add_to_cache(self, delta: int, i: int, reverse: bool) -> None:
for sl in self.cache[i-delta]:
s = ''.join(sl)
delta_str = str(delta)
if reverse is True:
# delta + f(i - delta)
new_key = delta_str + s
else:
# f(i - delta) + delta
new_key = s + delta_str
if new_key not in self.cache_key_map:
self.cache_key_map[new_key] = True
self.cache[i].append([delta_str] + sl)
@staticmethod
def _ouput_result(cache_list: list) -> None:
for cache_result in cache_list:
print(",".join([i+"m" for i in cache_result]))
if __name__ == "__main__":
r = RobotBrain()
r.output_solution(5)
