题目

The observed PIN

观察到的PIN

描述

Alright, detective, one of our colleagues successfully observed our target person, Robby the robber. We followed him to a secret warehouse, where we assume to find all the stolen stuff. The door to this warehouse is secured by an electronic combination lock. Unfortunately our spy isn't sure about the PIN he saw, when Robby entered it.

好的，侦探，我们的一位同事成功地观察到了我们的目标人，抢劫犯罗比。我们跟着他到了一个秘密仓库，我们假设在那里找到了所有被盗的东西。这个仓库的门由电子组合锁固定。不幸的是，当罗比进入时，我们的间谍不确定他看到的PIN。

The keypad has the following layout:

键盘具有以下布局：

┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │ 6 │
├───┼───┼───┤
│ 7 │ 8 │ 9 │
└───┼───┼───┘
    │ 0 │
    └───┘

He noted the PIN 1357, but he also said, it is possible that each of the digits he saw could actually be another adjacent digit (horizontally or vertically, but not diagonally). E.g. instead of the 1 it could also be the 2 or 4. And instead of the 5 it could also be the 2, 4, 6 or 8.

他注意到了插脚1357，但他也说，他看到的每个数字可能实际上都是另一个相邻的数字（水平或垂直，但不是对角线）。例如，它也可以是2或4，而不是1。而不是5，它也可以是2，4，6或8。

He also mentioned, he knows this kind of locks. You can enter an unlimited amount of wrong PINs, they never finally lock the system or sound the alarm. That's why we can try out all possible (*) variations.

他还提到，他知道这种锁。您可以输入无限数量的错误PIN，它们不会最终锁定系统或发出警报。这就是为什么我们可以尝试所有可能的（*）变体。

possible in sense of: the observed PIN itself and all variations considering the adjacent digits

可能的含义：观察到的引脚本身以及考虑到相邻数字的所有变化

Can you help us to find all those variations? It would be nice to have a function, that returns an array (or a list in Java/Kotlin and C#) of all variations for an observed PIN with a length of 1 to 8 digits. We could name the function getPINs (get_pins in python, GetPINs in C#). But please note that all PINs, the observed one and also the results, must be strings, because of potentially leading '0's. We already prepared some test cases for you.

你能帮我们找到所有这些变化吗？最好有一个函数，返回一个数组（或Java/Kotlin和C#中的列表），该数组包含观察到的长度为1到8位的管脚的所有变化。我们可以将函数命名为getPINs（python中的get_pins，C中的getPINs）。但请注意，所有管脚（观察到的管脚以及结果）都必须是字符串，因为可能是前导“0”。我们已经为您准备了一些测试用例。

Detective, we are counting on you!

侦探，我们全靠你了！

例子

test.describe('example tests')
expectations = [('8', ['5','7','8','9','0']),
                ('11',["11", "22", "44", "12", "21", "14", "41", "24", "42"]),
                ('369', ["339","366","399","658","636","258","268","669","668","266","369","398","256","296","259","368","638","396","238","356","659","639","666","359","336","299","338","696","269","358","656","698","699","298","236","239"])]

for tup in expectations:
  test.assert_equals(sorted(get_pins(tup[0])), sorted(tup[1]), 'PIN: ' + tup[0])

思路

首先，看到这个题就要明白这是一个排列问题，不要看这个描述就被吓到了，我们从例子中可以很明显的看出，就是排列，但是呢，本题的重点就是找到符合条件的排列数。

怎么找到符合条件的排列数呢？题目已经给了我们键盘的布局，以及规则（上下左右相邻，不包含对角线），那我们对着键盘布局找规律就好。

所以本题首先需要计算的就是，符合要求的排列数，其实很简单，我们一个一个的来即可，遍历obserd，找到每个数的符合要求的按键，所以我们分成五个部分来处理，这样直观并且明显：

0的处理，因为0的特殊性，我们需要单独拿出来

# 对于0的处理
# 本身就是0
if val == 0:
    keys[i].append(8)
    continue
# 相邻
if val == 8:
    keys[i].append(0)

上相邻，根据键盘排布，对于一个数的上相邻，我们只要减3即可，但是我们需要考虑边界问题，如果本身就是上边界，那么就上相邻，我们分了两种处理边界的方法，看下面会明白
```
# 上相邻
temp = val - 3
# 边界，对于上边界，一定是要大于0的，否则，超出边界
if temp > 0:
    keys[i].append(temp)
```
下相邻，对于一个下相邻，我们只要加+3即可，同样也要考虑边界问题
```
# 下相邻
temp = val + 3 
if temp <= 9:
    keys[i].append(temp)
```

左相邻，对一个数的左相邻，我们只要减1即可，如果本身已经是左边界了，那么也就必然没有左相邻

# 左相邻
# 如果本身已经是左边界了，那么也就必然没有左相邻
if val not in [1,4,7]:
    temp = val - 1
    if temp > 0:
        keys[i].append(temp)

右相邻，对于一个数的右相邻，我们只要加1即可，如果本身已经是右边界了，那么也就必然没有右相邻

# 右相邻
# 如果本身已经是右边界了，那么也就必然没有右相邻
if val not in [3,6,9]:
    temp = val + 1 
    if temp <= 9:
        keys[i].append(temp)

通过上面的处理，我们就找到了observed的每个数的符合条件的值，并且保存到列表keys中
observed = "11",keys = [[1,2,4],[1,2,4]]

然后就是排列，通过例子我们可以看出，排列是有顺序的，observed的第一个数的符合条件的值，只能放在排列的第一个位置，第二个数的符合条件的值，只能放在排列的第二个位置，依次类推

看到上面我们肯定想到了循环，循环keys，但是如果只是两个列表还好，但是如果是10个或者更多呢，我们总不可能写10个for吧，看到这里，我们有经验，应该就能想到使用递归，因为每次做的事情都是一样的，把上一个循环的值和本次循环的值组合起来。

def backtracking(keys,startindex,path):
    # 终止条件
    if len(path) == len(observed):
        # 保存结果
        result.append(''.join(path))
        return 
    # 遍历
    for i in range(len(keys[startindex])):
        # 保存结果
        path.append(str(keys[startindex][i]))
        # 递归
        backtracking(keys,startindex + 1,path)
        # 回溯
        path.pop()

完整代码

def get_pins(observed):
    # 保存所有可能密码按键
    keys = [[] for _ in range(len(observed))]
    # 全排列
    # 首先要将传入的值，拆分，然后找到每个值的相邻的值
    for i in range(len(observed)):
        # 转换成数字
        val = int(observed[i])
        # 处理相邻的数，包含自己，根据题意，这是个类似9宫格的图形，0特殊处理
        # 添加自身
        keys[i].append(val)
        # 对于0的处理
        # 本身就是0
        if val == 0:
            keys[i].append(8)
            continue
        # 相邻
        if val == 8:
            keys[i].append(0)
        # 上相邻
        temp = val - 3
        # 边界，对于上边界，一定是要大于0的，否则，超出边界
        if temp > 0:
            keys[i].append(temp)
        # 下相邻
        temp = val + 3 
        if temp <= 9:
            keys[i].append(temp)
        # 左相邻
        # 如果本身已经是左边界了，那么也就必然没有左相邻
        if val not in [1,4,7]:
            temp = val - 1
            if temp > 0:
                keys[i].append(temp)
        # 右相邻
        # 如果本身已经是右边界了，那么也就必然没有右相邻
        if val not in [3,6,9]:
            temp = val + 1 
            if temp <= 9:
                keys[i].append(temp)

    # 回溯
    # 保存符合条件的结果
    path = []
    # 保存结果
    result = []
    def backtracking(keys,startindex,path):
        # 终止条件
        if len(path) == len(observed):
            # 保存结果
            result.append(''.join(path))
            return 
        # 遍历
        for i in range(len(keys[startindex])):
            # 保存结果
            path.append(str(keys[startindex][i]))
            # 递归
            backtracking(keys,startindex + 1,path)
            # 回溯
            path.pop()

    backtracking(keys,0,path)
    return result