两个极限编程大赛题解

引子

上周基友忽然问我，周六能不能帮他写写代码，说是参加什么比赛，可以多个人一起做题，赛程好像是24小时。

当时我感觉应该是比较麻烦的事情，准备不做的，不过后面一想，万一很有趣呢，哈哈。

到了周六，都差点忘了有这回事，被一个QQ消息提醒了，就开始做题了。后面才知道，这个活动叫“极限编程大赛”，会临场发布一些网上基本上搜不到的问题，给你解决，分数根据跑过的测试用例来计算。

我帮他做了两个题，都还算比较理想，也花了不少时间，但感觉颇有收获：）

由于问题都比较长，所以我用附件的形式附上英文原文，在下面的文字里面会简单的描述一下问题。

买不起刷子的油漆工Bob

问题

在美帝有一个叫做Bob的穷苦油漆工，因为太穷了，所以刷漆的刷子只有两个，他要刷一百面墙才能买得起一副刷子，但是一百面墙会让他用坏一个刷子（可怜的Bob大叔）。

所以他现在只有两个刷子。

那么问题来了，Bob大叔每次都要刷很多面墙，而且要用不同的油漆。

他只能把刷子洗了再重新染色，这时候他只能等待刷子干了才能重新上漆，所以在资本家要求Bob用给定的顺序刷漆的时候，Bob如何重新染刷子，才能降低总的等待时间呢？

接下来我们举两个栗子，说明一下究竟是怎么回事。我们假设一个数字就是一种颜色，不同的数字代表不同的颜色。

简单的例子

举个栗子，Bob现在要刷漆的序列是

7 7 2 11 7

Bob最少需要把刷子染色几次呢？

这个场景下，Bob大叔一下就想到怎么弄了：

因为7号颜色是会重复使用的，所以在需要染色2号颜色的时候，直接用另一个刷子，然后11号颜色也用这个刷子，七号颜色的刷子就不用改变颜色了。

这么计算下来，①号刷子一共要染色次数是 一次；②号刷子一共要染色的次数是两次。

所以Bob大叔需要染色三次，才能完成这次刷漆工作。

忽然出现了一个需求更加复杂的例子

复杂的例子

这次客户的需求更加复杂了。

需要刷漆的颜色序列如下：

9 1 7 6 9 9 8 7 6 7

卧槽，这次没有那么简单了，Bob大叔表示脑袋都想破了，也不知道该如何解决。

所以我们开始思考可以用程序来解决问题的方法吧: )

最原始的解法

没有经过算法训练的人，一开始很难想到合理的思路来解决这个问题，胡乱的写一些程序来尝试（说的就是我）。

最原始的办法，就是穷举出所有可能的染色组合，然后比较得出最小的次数的组合，解法获得！毕竟计算机的计算能力那么强，也不在乎你列出了这么多的组合的这点时间，是不是？

更好的办法

我注意到题设里面，有一个限制条件，颜色序列的长度在1-500之间，而颜色种类则是1-20，题目用python解出，时间限制是10s，也就是测试不能超过10s的运行时间，c++实现则是2s。

500 的序列长度，加上20种颜色，感觉上需要消耗很长的时间才能计算出来所有组合啊！（算法基础不牢暴露了！

不过虽然无法估计它的时间复杂度，但是我们可以考虑一下这个问题：每次我们在考虑选择下一个刷子要不要换颜色的时候，考虑的影响因素是什么。

实际上，我们在考虑，下个刷子要不要换颜色的时候，考虑的是，这个刷子的颜色被可重用的可能性。

把问题分解一下（分而治之）。

如果每次决定要重新染色哪个刷子的时候，我们都能选择接下来不能被重用的那个刷子，那么挨个这样选择下去，最后的解一定是最优的。

在这个例子中

9 1 7 6 9 9 8 7 6 7

首先初始化两个刷子：

刷子A染上颜色9，当前颜色决定进行到的index为1
因为刷子A后面没有紧邻的相同颜色，所以为了下一次染色不会造成重新染色，我们选择将刷子B染成1
此时两个刷子染上颜色了，这个时候染色的index到2了。
接下来，决定第3个刷子应该用哪个颜色来染色了。
我们的思路不变，要解决的问题是“当前哪个刷子的颜色接下来被重用的可能性越高，则重新染色另一个刷子”。
这个问题，可以转化为求下刷子的当前颜色到下一个相同颜色的距离问题。

• 首先看一下两个刷子的状态，刷子A是颜色9，刷子B是颜色1.
• 刷子A最近的颜色相同点是index 为5的位置，距离是2
• 刷子B颜色最近的相同点是不存在的，所以距离为∞
• 这一轮，刷子A获胜，刷子B被染成颜色7.
• 以此类推，可以计算出每一次刷子应该被染成哪个颜色更加划算。

代码实现

因为要处理标准输入输出，所以代码包含了一些额外的无用函数，可以自行查看原题的样例输入输出，然后查看结果：）

附上实现后的Python代码，里面包含了一些简单的优化，比如：

用一个哈希表统计每个颜色的数量，对于不存在相同的后续颜色的刷子，则不会遍历后面的颜色，省去了后面的计算。
这个颜色计数器，每次染色之后都会更新，来减少后续的遍历过程（总是能避免颜色穷尽之后的无用遍历），因为一次遍历的时间复杂度是O(n), 而如果颜色不存在后续了，则这次遍历的时间复杂度可以从原本的O(n)变成O(1)，因为你已经知道了后续相同颜色不存在，则不用继续通过遍历来计算距离了。
距离相同怎么办？那就把两个刷子染色后的情况再计算一下这次次染色之后到下一次染色的距离就好了，递归一下。

from collections import defaultdict


class Brush(object):
    def __init__(self):
        self.times = 0
        self.color = None

    def switch_color(self, new_color):
        if self.color != new_color:
            self.times += 1
        self.color = new_color


class BrushPainter(object):

    def __init__(self, input_list, elements_length):
        self.list = input_list
        self.count_registry = self._gen_count()
        self.length = elements_length
        self.current_index = 0
        self.brushes = {
            1: Brush(),
            2: Brush(),
        }

    def _gen_count(self):
        registry = defaultdict(lambda: 0)
        for ele in self.list:
            registry[ele] += 1
        return registry

    @property
    def times(self):
        return self.brushes[1].times + self.brushes[2].times

    def _get_count(self, number):
        return self.count_registry[number]

    def get_distance(self, start_index, brush_value):
        if self._get_count(self.list[start_index]) <= 0:
            return None
        _current_index = start_index
        while _current_index < self.length:
            element = self.list[_current_index]
            if element == brush_value:
                return _current_index - start_index
            _current_index += 1
        return None

    def should_replaced_brush(self, brush1_value, brush2_value, current_index):
        """
        return the brush index.
        """
        distance1 = self.get_distance(current_index, brush1_value)
        if distance1 == 0:
            return 1
        distance2 = self.get_distance(current_index, brush2_value)
        if distance2 == 0:
            return 2

        if (distance1 is None) and (distance1 is None):
            return 1
        elif distance1 is None:
            return 1
        elif distance2 is None:
            return 2

        if distance1 == distance2:
            brush1_value = self.list[current_index + distance1]
            brush2_value = self.list[current_index + distance2]
            current_index += 1
            return self.should_replaced_brush(brush1_value, brush2_value, current_index)
        elif distance1 > distance2:
            return 1
        else:
            return 2

    def init(self):
        self.brushes[1].switch_color(self.list[self.current_index])
        self.current_index += 1
        while self.brushes[1].color == self.list[self.current_index]:
            self.current_index += 1
        self.brushes[2].switch_color(self.list[self.current_index])
        self.current_index += 1
        return self.brushes

    def run(self):
        if self.length <= 2:
            self.brushes[1].times = self.length
            return
        self.init()
        while self.current_index < self.length:
            brush_index = self.should_replaced_brush(
                self.brushes[1].color, self.brushes[2].color, self.current_index
            )
            new_color = self.list[self.current_index]
            self.brushes[brush_index].switch_color(new_color)
            self.count_registry[new_color] -= 1
            self.current_index += 1


def _raw_input():
    return raw_input()


def get_list(list_str):
    color_sequence = list_str.strip().split()
    return color_sequence


def get_sequence():
    seq_len = int(_raw_input())
    seq = get_list(_raw_input())
    return seq, seq_len


def main_loop():
    _num_sequence = _raw_input()
    if not _num_sequence:
        return
    num_sequence = int(_num_sequence)
    if num_sequence <= 0:
        return
    seqs = []
    for i in range(num_sequence):
        seqs.append(get_sequence())

    for sample in seqs:
        obj = BrushPainter(sample[0], sample[1])
        obj.run()
        print("%s" % (obj.times, ))

main_loop()

LRU Cache和FIFO Cache优化效果比较

这个题的主要内容是比较在某种情况下，一个程序用LRU和FIFO的内存交换方式，哪种会带来性能提升。

题目没啥太大的难度，能理解清楚两个概念即可。

我直接把原题贴在这里lru-and-fifo

题解如下：

import math

YES = "yes"
NO = "no"


def get_page_index(address, page_size):
    if page_size == 0:
        page_size = 1
    page_index = math.floor(address/page_size)
    return page_index


class FIFOCache(object):
    def __init__(self, num_pages, page_size, access_seqs, access_times):
        self.cache = []
        self.max_pages = num_pages
        self.page_size = page_size
        self.replace_times = 0

        self.access_seqs = access_seqs
        self.access_times = access_times

    def _access(self, page_address):
        page_index = get_page_index(page_address, self.page_size)
        if page_index in self.cache:
            return
        if len(self.cache) >= self.max_pages:
            self._remove()
            self._add(page_index)
            self.replace_times += 1
        else:
            self._add(page_index)

    def _add(self, page_index):
        self.cache.append(page_index)

    def _remove(self):
        self.cache.pop(0)

    def run(self):
        for address in self.access_seqs:
            self._access(address)
        return self.replace_times


class LRUCache(object):

    def __init__(self, num_pages, page_size, access_seqs, access_times):
        self.cache = []
        self.max_pages = num_pages
        self.page_size = page_size
        self.replace_times = 0

        self.access_seqs = access_seqs
        self.access_times = access_times

    def _access(self, page_address):
        page_index = get_page_index(page_address, self.page_size)
        if page_index in self.cache:
            return self._move_lru(page_index)
        if len(self.cache) >= self.max_pages:
            self._remove()
            self._add(page_index)
            self.replace_times += 1
        else:
            self._add(page_index)

    def _move_lru(self, page_index):
        self.cache.remove(page_index)
        self._add(page_index)

    def _add(self, page_index):
        self.cache.append(page_index)

    def _remove(self):
        self.cache.pop(0)

    def run(self):
        for address in self.access_seqs:
            self._access(address)
        return self.replace_times


class Config(object):
    def __init__(self, num_pages, page_size, seqs, seq_len):
        self.num_pages = num_pages
        self.page_size = page_size
        self.seqs = seqs
        self.seq_len = seq_len

    def run_once(self):
        answer = NO
        fifo = FIFOCache(self.num_pages, self.page_size, self.seqs, self.seq_len).run()
        lru = LRUCache(self.num_pages, self.page_size, self.seqs, self.seq_len).run()
        if fifo > lru:
            answer = YES
        return answer, fifo, lru


def get_config():
    num_pages, page_size, seq_len = raw_input().strip().split()
    return int(num_pages), int(page_size), int(seq_len)


def get_test_seq(seq_len):
    seqs = []
    for i in range(seq_len):
        seqs.append(int(raw_input()))
    return seqs


def main_loop():
    config_seqs = []
    num_inputs = int(raw_input())
    for i in range(num_inputs):
        num_pages, page_size, seq_len = get_config()
        seqs = get_test_seq(seq_len)
        config_seqs.append(
            Config(
                num_pages,
                page_size,
                seqs,
                seq_len
            )
        )
    for config in config_seqs:
        print "%s %s %s" % config.run_once()

main_loop()