Sum with level

Posted on Tue 28 March 2017 in Puzzles

In [1]:
class SumLv:
    def __init__(self, depth):
        self.depth=depth
        self.lv=self.depth
        self.s=0
    def __call__(self, *args):
        '''
        Empty call to return value
        Non-empty call to add values
        '''
        if args:
            self.s+=sum(args)
            self.lv-=len(args)
            if self …

Continue reading

Next Permutation

Posted on Fri 24 March 2017 in Puzzles

Aim: Find a larger permutation

We must move a larger number forward. So we should go from the tail to find any new number is smaller than a number behind it. If no next permutation, reverse list.

In [ ]:
def next_permutation(l):
    '''Give out the next permutation of list l
    >>> next_permutation …

Continue reading

24 Game Solver

Posted on Wed 01 March 2017 in Puzzles

24 game is an arithmetic game with a simple rule: Given 4 numbers and use + - * / to get 24.

  • A simple example is 1, 2, 3, 4, and you find 1*2*3*4=24
  • A more difficult one is 5, 5, 5, 1, the answer is 5*(5-(1/5 …

Continue reading

最大子序列和系列问题

Posted on Tue 01 November 2016 in Puzzles

In [2]:
def maxsum(l):
    '''最大子序列和问题'''
    m=s=0
    for i in l:
        s=max(s, 0)
        s+=i
        m=max(m, s)
    return m
In [3]:
def maxprod(l):
    '''最大子序列积问题'''
    m=pos=0
    neg=0
    for i in l:
        pos=max(1, pos)*i
        neg=neg*i
        if i …

Continue reading

拼图游戏之打乱拼图

Posted on Sat 07 March 2015 in Puzzles

线性时间计算排列的奇偶性

计算交换次数(鸠占鹊巢)

扫描所有的鸟,命名为鸠(Dove):

  • 鸠现在占着鹊(Magpie)巢
  • 鸠的巢(nest)被麻雀(sparrow)占领
  • 鸠和麻雀换巢:鸠回到自己的巢,麻雀挪到鹊的巢
In [2]:
def rev_index(l):
    '''Construct nest<->bird reversed index'''
    rev=empty_like(l)
    for i, j in enumerate(l):
        rev[j]=i
    return rev
def count_swap(nest2bird, bird2nest):
    '''Count swaps needed …

Continue reading

拼图游戏之可解性条件

Posted on Fri 06 March 2015 in Puzzles

可解的必要条件

游戏中只能由不断的空块和相邻的块做交换完成。而可解性也由交换数的奇偶性决定,交换数定义为通过交换任意块使得其恢复原状需要的次数。

考虑包含空块在内的交换数:空格子移动一步的时候,进行了一次交换,交换数的奇偶性发生改变。显然最后的奇偶性取决于空格移动步数的奇偶性。而移动步数奇偶性不依赖于具体路径,只依赖于初末位置。我们可以找一条最简单的路径的长度(曼哈顿距离)的奇偶性来判断可解性。

必要条件 移动步数奇偶性必须等于排列数/交换数的奇偶性

充分性

三元轮换与聚合

我们考虑三元置换的可行性。首先如果我们有$ABC$和空格聚在一起,那么显然很容易将$ABC$做轮换$R$

A  B     C  A     B  C
     -->      --> 
C  O     B  O     A  O

对于大于$(2,2)$显然是容易聚在一起的,而且方块越多,自由度越大,越容易聚在一起。所以这里我们仅考虑$(3 …


Continue reading