[Algrothm] knight-dialer
- problem
- 思路
- 我的解法
- solution
[Review]
[Tip] python type hint
- what
- why
- how
[Share] 美团技术leader：写给工程师的十条精进原则

这是耗子叔发起的一个活动，每周为一个周期,需要完成以下内容

Algrothm: leetcode算法题目
Review: 阅读并且点评一篇英文技术文章
Tip/Techni: 学习一个技术技巧
Share: 分享一篇有观点和思考的技术文章

[Algrothm] knight-dialer

problem

https://leetcode.com/problems/knight-dialer/

A chess knight can move as indicated in the chess diagram below:

 .           

图片可以点击原链接查看 

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops.  Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example 1:

Input: 1
Output: 10
Example 2:

Input: 2
Output: 20
Example 3:

Input: 3
Output: 46
 
Note:

1 <= N <= 5000

思路

获取到状态转移的关系
这是一个典型的动态规划的问题，可以按照三个步骤的思路来处理(https://xionchen.github.io/2018/11/03/arts-001/#dp%E7%90%86%E8%A7%A3)
- 递归
- 存储
- 改为从头开始

我的解法

状态转移关系，用字典表示

      {1:[6,7],
       2:[7,9],
       3:[4,8],
       4:[3,9,0],
       5:[],
       6:[1,7,0],
       7:[2,6],
       8:[1,3],
       9:[2,4],
       0:[4,6]}

递归

   def knightDialer(self, N):
      """
      :type N: int
      :rtype: int
      """
      def move_to(now_number, n):
          key = '{}|{}'.format(n, now_number)

          if n == 1:
              if move_to_cache.get(key):
                  return move_to_cache.get(key)
              move_to_cache[key] = len(preview_numbers_of[now_number])
              return len(preview_numbers_of[now_number])
          else:
              if move_to_cache.get(key):
                  return move_to_cache.get(key)
              now = 0
              for number in preview_numbers_of[now_number]:
                  now += move_to(number, n-1)

              move_to_cache[key] = now
              return now

      preview_numbers_of = {1: [6, 8],
                            2: [7, 9],
                            3: [4, 8],
                            4: [3, 9, 0],
                            6: [1, 7, 0],
                            7: [2, 6],
                            8: [1, 3],
                            9: [2, 4],
                            0: [4, 6]}
      move_to_cache = {}

      if N == 1:
          return 10
      else:
          sum_num = 0
          for k, v in preview_numbers_of.items():
              sum_num += move_to(k, N-1)
          return sum_num   

显然这样效率非常低，可以profile以下看看，求N=10的情况下，move to被调用了6576次，显然其中有很多重复求解的情况

move_to	11643	3	3
<method 'items' of 'dict' objects>	1	0	0
<built-in method builtins.__build_class__>	1	0	0
<built-in method builtins.len>	6576	0	0
<built-in method builtins.print>	1	0	0
<module>	1	3	0
Solution	1	0	0
knightDialer	1	3	0

存储

  class Solution(object):
    def knightDialer(self, N):
        """
        :type N: int
        :rtype: int
        """
        def move_to(now_number, n):
            key = '{}|{}'.format(now_number,n)

            if n == 1:
                if move_to_cache.get(key):
                    return move_to_cache.get(key)
                move_to_cache[key] = len(preview_numbers_of[now_number])
                return len(preview_numbers_of[now_number])
            else:
                if move_to_cache.get(key):
                    return move_to_cache.get(key)
                now = 0
                for number in preview_numbers_of[now_number]:
                    now += move_to(number, n-1)

                move_to_cache[key] = now
                return now

        preview_numbers_of = {1: [6, 8],
                              2: [7, 9],
                              3: [4, 8],
                              4: [3, 9, 0],
                              6: [1, 7, 0],
                              7: [2, 6],
                              8: [1, 3],
                              9: [2, 4],
                              0: [4, 6]}
        move_to_cache = {}
        if N == 1:
            return 10
        else:
            sum_num = 0
            for k, v in preview_numbers_of.items():
                sum_num += move_to(k, N-1)
            return sum_num


if __name__ == '__main__':
    s = Solution()
    print(s.knightDialer(N=10))  

再profle一下看看

<method 'format' of 'str' objects>	169	0	0
<method 'get' of 'dict' objects>	257	0	0
<method 'items' of 'dict' objects>	1	0	0
<built-in method builtins.__build_class__>	1	0	0
<built-in method builtins.len>	18	0	0
<built-in method builtins.print>	1	0	0
<module>	1	0	0
move_to	169	0	0
Solution	1	0	0
knightDialer	1	0	0

结果显然好了不少

改为非递归，即动态规划的方式

    def knightDialer(self, N):
        preview_numbers_of = [ [4, 6],  [6, 8],  [7, 9],  [4, 8], [0, 3, 9], [], [0, 1, 7], [2, 6], [1, 3],
              [2, 4]]
        dp = [[0] * 10 for _ in range(N)]
        mod = 10 ** 9 + 7
        for i in range(10): dp[0][i] = 1

        for i in range(1, N):
            for j in range(10):
                for number in preview_numbers_of[j]:
                    dp[i][j] += dp[i - 1][number]
                dp[i][j] %= mod

        return sum(dp[N - 1]) % mod

其实改为非递归之后还是存在超时问题，后来修改了不少地方：

状态转移字典改为数组，减少了hash
列表推导改为了循环，使用inner操作
之前没注意还有mod 10 ** 9 +7 ，加上了
一样的代码要多跑几遍，leetcode的服务器有时候比较慢

最终才没有超时

solution

官反提供的solution基本与自己实现的一致，有一些小细节不一样。

class Solution(object):
    def knightDialer(self, N):
        MOD = 10**9 + 7
        moves = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],
                     [1,7,0],[2,6],[1,3],[2,4]]

        dp = [1] * 10
        for hops in xrange(N-1):
            dp2 = [0] * 10
            for node, count in enumerate(dp):
                for nei in moves[node]:
                    dp2[nei] += count
                    dp2[nei] %= MOD
            dp = dp2
        return sum(dp) % MOD

dp不是一次性生成的，是append出来的，这个看了python里面list的实现，基本与java一致，是数组，所以一次性生存可以防止频繁的resize。
使用了xrange，这个在python3中就没去别了，py2里面xrange比较快。
每一步都mod，参考了python里面加法的实现,这样确实能够减少运算。

[Review]

还是强化学习有关内容 https://github.com/wwxFromTju/awesome-reinforcement-learning-zh

内容比较多，并且独立完整，所有详细的内容记录在了这里 RL Course by David Silver

[Tip] python type hint

what

https://www.python.org/dev/peps/pep-0484/

这个特性我非常喜欢，正好最经用到了。其实就是python的类型提示，它有什么用呢？

why

python的优点在于灵活，缺点也在于灵活，所以这个语言的下限其实非常低，可以写出非常难以阅读的代码。类型提示在某种程度上可以有效的改善这种情况。

正如我在一篇博客里面提到，阅读源码的时间是你写代码时间的十倍以上。任何写起来爽的同时降低的代码可读性的操作都是一时之爽。

这点上有点类似mongodb一样，mongodb在易用性下了大功夫，但是在事务处理，安全方面却做的不是很好，维护成本非常高。这就导致了一个现象，大家一开始做poc或者创业公司很喜欢用mongodb。但是随着业务压力的上升，渐渐的都只能离开它(这种情况近几年有所改善)。

所以生孩子的效率固然重要，但是绝对不能忽视养孩子的成本。

说了这么多就是为了说明一件事，type hint用好了，真的很有用。它能有效的帮助代码最初的设计结构不被破坏，有效的提高代码可读性，而且还有一点，自动提升能更加准确和智能。

how

首先是官方的文档如果有一点python基础的话应该很快就能掌握。这里我只简单的写个例子。

from type import List
class Book:
    def __init__(self):
        ...

class BookService:
    def __init__(self):
       ...
       ...
    
    def get_books_by_type(type: str) -> List(Book):
       ...

这样就很明确，type是一个str类型，它会返回一个Book的list。

这样避免的type这个变量的模糊和返回类型的模糊，如果没有标注，有的人可能试图传入一个别的类型作为type，或者在修改代码的时候直接返回一个Book obj而不是Book 的list。

当然，这些都能写道函数的注释里，但是我的观点的代码的自解释性优先与注释。所以更推荐这种方式。

美团技术leader：写给工程师的十条精进原

这些都是进入职场的工程师必备的素质:

Owner意识
时间观念
以始为终
保持敬畏
事不过二
设计优先
P/PC平衡
善于提问
空杯心态

xionchen commented on Tue Jul 04 2017

哇,成功了
timchenxiaoyu commented on Fri Jan 05 2018

请问
mount --bind foo foo
有啥意义？
xionchen commented on Fri Jan 05 2018

@timchenxiaoyu
举个例子,可以通过这种方式来创造一个挂在点。
➜ ~ mkdir test_dir
➜ ~ sudo mount --bind test_dir test_dir
➜ ~ mount |grep test_dir
/dev/nvme0n1p6 on /home/xion/test_dir type ext4 (rw,relatime,errors=remount-ro,data=ordered)

这样就可以使用一些mount的属性，最简单的例子，例如：
sudo mount,ro --bind test_dir test_dir
可以让test_dir成为一个是read only的目录。无论改目录中的文件夹或者文件的权限是什么，这个文件夹都是只读的。
除此之外，mount有很多别的属性
yeweimian21 commented on Thu Mar 01 2018

您好，请问，我在用diskimage-builder制作镜像的时候，总是卡在一个地方执行不下去，不知道是哪里配置错了还是网络的原因。
下面是执行过程的输出：
2018-03-01 04:38:32.659 | Running hooks from /tmp/dib_build.cuv4VCZM/hooks/root.d
2018-03-01 04:38:32.671 | dib-run-parts Sourcing environment file /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/10-bootloader-default-cmdline
2018-03-01 04:38:32.673 | + source /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/10-bootloader-default-cmdline
2018-03-01 04:38:32.674 | ++ export 'DIB_BOOTLOADER_DEFAULT_CMDLINE=nofb nomodeset vga=normal'
2018-03-01 04:38:32.674 | ++ DIB_BOOTLOADER_DEFAULT_CMDLINE='nofb nomodeset vga=normal'
2018-03-01 04:38:32.674 | dib-run-parts Sourcing environment file /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/10-dib-init-system.bash
2018-03-01 04:38:32.676 | + source /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/10-dib-init-system.bash
2018-03-01 04:38:32.676 | ++++ dirname /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/10-dib-init-system.bash
2018-03-01 04:38:32.678 | +++ PATH=/root/dib-virtualenv/bin:/root/dib-virtualenv/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/..
2018-03-01 04:38:32.678 | +++ dib-init-system
2018-03-01 04:38:32.680 | ++ DIB_INIT_SYSTEM=upstart
2018-03-01 04:38:32.680 | ++ export DIB_INIT_SYSTEM
2018-03-01 04:38:32.680 | dib-run-parts Sourcing environment file /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/10-ubuntu-distro-name.bash
2018-03-01 04:38:32.682 | + source /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/10-ubuntu-distro-name.bash
2018-03-01 04:38:32.682 | ++ export DISTRO_NAME=ubuntu
2018-03-01 04:38:32.682 | ++ DISTRO_NAME=ubuntu
2018-03-01 04:38:32.682 | ++ export DIB_RELEASE=xenial
2018-03-01 04:38:32.682 | ++ DIB_RELEASE=xenial
2018-03-01 04:38:32.682 | dib-run-parts Sourcing environment file /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/14-manifests
2018-03-01 04:38:32.684 | + source /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/14-manifests
2018-03-01 04:38:32.684 | ++ export DIB_MANIFEST_IMAGE_DIR=/etc/dib-manifests
2018-03-01 04:38:32.684 | ++ DIB_MANIFEST_IMAGE_DIR=/etc/dib-manifests
2018-03-01 04:38:32.684 | ++ export DIB_MANIFEST_SAVE_DIR=image.d/
2018-03-01 04:38:32.684 | ++ DIB_MANIFEST_SAVE_DIR=image.d/
2018-03-01 04:38:32.685 | dib-run-parts Sourcing environment file /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/50-dib-python-version
2018-03-01 04:38:32.687 | + source /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/50-dib-python-version
2018-03-01 04:38:32.687 | ++ '[' -z '' ']'
2018-03-01 04:38:32.687 | ++ '[' ubuntu == ubuntu ']'
2018-03-01 04:38:32.687 | ++ '[' xenial == trusty ']'
2018-03-01 04:38:32.687 | ++ '[' -z '' ']'
2018-03-01 04:38:32.687 | ++ DIB_PYTHON_VERSION=3
2018-03-01 04:38:32.687 | ++ export DIB_PYTHON_VERSION
2018-03-01 04:38:32.687 | ++ export DIB_PYTHON=python3
2018-03-01 04:38:32.687 | ++ DIB_PYTHON=python3
2018-03-01 04:38:32.687 | dib-run-parts Sourcing environment file /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/99-cloud-init-datasources.bash
2018-03-01 04:38:32.689 | + source /tmp/dib_build.cuv4VCZM/hooks/root.d/../environment.d/99-cloud-init-datasources.bash
2018-03-01 04:38:32.689 | ++ export DIB_CLOUD_INIT_DATASOURCES=Ec2
2018-03-01 04:38:32.689 | ++ DIB_CLOUD_INIT_DATASOURCES=Ec2
2018-03-01 04:38:32.689 | dib-run-parts Running /tmp/dib_build.cuv4VCZM/hooks/root.d/10-cache-ubuntu-tarball
2018-03-01 04:38:32.694 | Getting /root/.cache/dib/lockfiles/xenial-server-cloudimg-amd64-root.tar.gz.lock: Thu Mar 1 12:38:32 CST 2018
2018-03-01 04:38:32.695 | Fetching Base Image
2018-03-01 04:38:32.714 | * Hostname was NOT found in DNS cache
2018-03-01 04:38:32.714 | % Total % Received % Xferd Average Speed Time Time Time Current
2018-03-01 04:38:32.714 | Dload Upload Total Spent Left Speed
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0* Trying 91.189.92.141...
2018-03-01 04:38:33.167 | * Trying 2001:67c:1360:8c01::8001...
2018-03-01 04:38:33.167 | * Immediate connect fail for 2001:67c:1360:8c01::8001: Network is unreachable
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0* Connected to cloud-images.ubuntu.com (91.189.92.141) port 443 (#0)
2018-03-01 04:38:33.222 | * successfully set certificate verify locations:
2018-03-01 04:38:33.222 | * CAfile: none
2018-03-01 04:38:33.222 | CApath: /etc/ssl/certs
2018-03-01 04:38:33.222 | * SSLv3, TLS handshake, Client hello (1):
2018-03-01 04:38:33.222 | } [data not shown]
2018-03-01 04:38:33.485 | * SSLv3, TLS handshake, Server hello (2):
2018-03-01 04:38:33.485 | { [data not shown]
0 0 0 0 0 0 0 0 --:--:-- 0:00:01 --:--:-- 0* SSLv3, TLS handshake, CERT (11):
2018-03-01 04:38:34.507 | { [data not shown]
2018-03-01 04:38:34.508 | * SSLv3, TLS handshake, Server key exchange (12):
2018-03-01 04:38:34.508 | { [data not shown]
2018-03-01 04:38:34.508 | * SSLv3, TLS handshake, Server finished (14):
2018-03-01 04:38:34.508 | { [data not shown]
2018-03-01 04:38:34.509 | * SSLv3, TLS handshake, Client key exchange (16):
2018-03-01 04:38:34.509 | } [data not shown]
2018-03-01 04:38:34.509 | * SSLv3, TLS change cipher, Client hello (1):
2018-03-01 04:38:34.509 | } [data not shown]
2018-03-01 04:38:34.509 | * SSLv3, TLS handshake, Finished (20):
2018-03-01 04:38:34.509 | } [data not shown]
2018-03-01 04:38:34.767 | * SSLv3, TLS change cipher, Client hello (1):
2018-03-01 04:38:34.767 | { [data not shown]
2018-03-01 04:38:34.767 | * SSLv3, TLS handshake, Finished (20):
2018-03-01 04:38:34.767 | { [data not shown]
2018-03-01 04:38:34.767 | * SSL connection using ECDHE-RSA-AES128-GCM-SHA256
2018-03-01 04:38:34.767 | * Server certificate:
2018-03-01 04:38:34.767 | * subject: C=GB; L=London; O=Canonical Group Ltd; OU=IS; CN=cloud-images.ubuntu.com
2018-03-01 04:38:34.767 | * start date: 2017-07-31 00:00:00 GMT
2018-03-01 04:38:34.767 | * expire date: 2018-08-23 12:00:00 GMT
2018-03-01 04:38:34.767 | * subjectAltName: cloud-images.ubuntu.com matched
2018-03-01 04:38:34.767 | * issuer: C=US; O=DigiCert Inc; CN=DigiCert SHA2 Secure Server CA
2018-03-01 04:38:34.767 | * SSL certificate verify ok.
2018-03-01 04:38:34.768 | > GET /xenial/current/SHA256SUMS HTTP/1.1
2018-03-01 04:38:34.768 | > User-Agent: curl/7.35.0
2018-03-01 04:38:34.768 | > Host: cloud-images.ubuntu.com
2018-03-01 04:38:34.768 | > Accept: /
2018-03-01 04:38:34.768 | > If-Modified-Since: Tue, 27 Feb 2018 07:45:32 GMT
2018-03-01 04:38:34.768 | >
2018-03-01 04:38:35.024 | < HTTP/1.1 200 OK
2018-03-01 04:38:35.024 | < Date: Thu, 01 Mar 2018 04:38:34 GMT
2018-03-01 04:38:35.024 | * Server Apache is not blacklisted
2018-03-01 04:38:35.024 | < Server: Apache
2018-03-01 04:38:35.024 | < Last-Modified: Wed, 28 Feb 2018 19:13:23 GMT
2018-03-01 04:38:35.024 | < ETag: "1492-5664a89703ac0"
2018-03-01 04:38:35.024 | < Accept-Ranges: bytes
2018-03-01 04:38:35.024 | < Content-Length: 5266
2018-03-01 04:38:35.024 | <
2018-03-01 04:38:35.279 | { [data not shown]
100 5266 100 5266 0 0 2052 0 0:00:02 0:00:02 --:--:-- 2052
2018-03-01 04:38:35.279 | * Connection #0 to host cloud-images.ubuntu.com left intact
2018-03-01 04:38:35.281 | Server copy has changed. Using server version of https://cloud-images.ubuntu.com/xenial/current/SHA256SUMS
2018-03-01 04:38:35.303 | * Hostname was NOT found in DNS cache
2018-03-01 04:38:35.303 | % Total % Received % Xferd Average Speed Time Time Time Current
2018-03-01 04:38:35.303 | Dload Upload Total Spent Left Speed
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0* Trying 91.189.92.141...
2018-03-01 04:38:35.756 | * Trying 2001:67c:1360:8c01::8001...
2018-03-01 04:38:35.756 | * Immediate connect fail for 2001:67c:1360:8c01::8001: Network is unreachable
2018-03-01 04:38:35.808 | * Connected to cloud-images.ubuntu.com (91.189.92.141) port 80 (#0)
2018-03-01 04:38:35.808 | > GET /xenial/current/xenial-server-cloudimg-amd64-root.tar.gz HTTP/1.1
2018-03-01 04:38:35.808 | > User-Agent: curl/7.35.0
2018-03-01 04:38:35.808 | > Host: cloud-images.ubuntu.com
2018-03-01 04:38:35.808 | > Accept: /
2018-03-01 04:38:35.808 | > If-Modified-Since: Tue, 13 Feb 2018 03:24:38 GMT
2018-03-01 04:38:35.808 | >
2018-03-01 04:38:36.064 | < HTTP/1.1 200 OK
2018-03-01 04:38:36.064 | < Date: Thu, 01 Mar 2018 04:38:35 GMT
2018-03-01 04:38:36.064 | * Server Apache is not blacklisted
2018-03-01 04:38:36.064 | < Server: Apache
2018-03-01 04:38:36.064 | < Last-Modified: Wed, 28 Feb 2018 15:48:30 GMT
2018-03-01 04:38:36.064 | < ETag: "c1f6071-56647acb7ef80"
2018-03-01 04:38:36.064 | < Accept-Ranges: bytes
2018-03-01 04:38:36.064 | < Content-Length: 203382897
2018-03-01 04:38:36.064 | < Content-Type: application/x-gzip
2018-03-01 04:38:36.064 | <
2018-03-01 04:38:36.064 | { [data not shown]

每次都是卡在这里不继续下去了，我看过程中有好多data not shown，是不是网络被墙了，下载不了镜像，还是别的原因。我是第一次用这个工具，有好多不明白的地方，请多指教，谢谢。
xionchen commented on Thu Mar 01 2018

@yeweimian21
出现了很多Hostname was NOT found in DNS cache错误，
建议检查DNS，

可以把DIB_DEBUG_TRACE打开，看详细日志。
不行的话可以下载好，用离线模式运行，DIB_OFFLINE 或者指定本地缓存镜像
参考此处源码
https://github.com/openstack/diskimage-builder/blob/master/diskimage_builder/elements/ubuntu/root.d/10-cache-ubuntu-tarball
yeweimian21 commented on Fri Mar 02 2018

您好，大神，我刚刚接触这个工具，平时可能有一些问题需要问您，方便加个QQ吗，我的QQ：1030060483，谢谢。同时祝您元宵节快乐🎉🎉
xionchen commented on Tue Mar 06 2018

@yeweimian21 现在基本不用qq了。。。有问题你可以直接留言或者发邮件。
能解答的基本都会解答
Sirius21c commented on Mon Jun 25 2018
你好，有两个问题想请教一下：
1. 我是在调研 openstack_octavia 的时候遇到 dib 的问题，跑 devstack 总是卡在了制作镜像处，为避免网络问题，已经换了国内的 ubuntu 源（阿里的），但还是出错：
  2018-06-25 02:51:45.639 | dib-run-parts Running /tmp/dib_build.shLTNvjU/hooks/root.d/50-build-with-http-cache
  2018-06-25 02:51:45.642 | dib-run-parts 50-build-with-http-cache completed
  2018-06-25 02:51:45.642 | dib-run-parts Running /tmp/dib_build.shLTNvjU/hooks/root.d/50-shared-apt-cache
  2018-06-25 02:51:45.653 | dib-run-parts 50-shared-apt-cache completed
  2018-06-25 02:51:45.653 | dib-run-parts Running /tmp/dib_build.shLTNvjU/hooks/root.d/50-trim-dpkg
  2018-06-25 02:51:45.669 | dib-run-parts 50-trim-dpkg completed
  2018-06-25 02:51:45.669 | dib-run-parts Running /tmp/dib_build.shLTNvjU/hooks/root.d/75-ubuntu-minimal-baseinstall
  2018-06-25 02:51:45.814 | Hit:1 http://mirrors.aliyun.com/ubuntu xenial InRelease
  2018-06-25 02:51:45.815 | Couldn't create tempfiles for splitting up /var/lib/apt/lists/mirrors.aliyun.com_ubuntu_dists_xenial_InReleaseErr:1 http://mirrors.aliyun.com/ubuntu xen
  ial InRelease
  2018-06-25 02:51:45.815 | Could not execute 'apt-key' to verify signature (is gnupg installed?)
  2018-06-25 02:51:45.877 | Get:2 http://mirrors.aliyun.com/ubuntu xenial-updates InRelease [109 kB]
  2018-06-25 02:51:45.983 | Couldn't create tempfiles for splitting up /var/lib/apt/lists/partial/mirrors.aliyun.com_ubuntu_dists_xenial-updates_InReleaseIgn:2 http://mirrors.aliyu
  n.com/ubuntu xenial-updates InRelease
  2018-06-25 02:51:46.015 | Get:3 http://mirrors.aliyun.com/ubuntu xenial-backports InRelease [107 kB]
  2018-06-25 02:51:46.092 | Couldn't create tempfiles for splitting up /var/lib/apt/lists/partial/mirrors.aliyun.com_ubuntu_dists_xenial-backports_InReleaseIgn:3 http://mirrors.ali
  yun.com/ubuntu xenial-backports InRelease
  2018-06-25 02:51:46.124 | Get:4 http://mirrors.aliyun.com/ubuntu xenial-security InRelease [107 kB]
  2018-06-25 02:51:46.635 | Couldn't create tempfiles for splitting up /var/lib/apt/lists/partial/mirrors.aliyun.com_ubuntu_dists_xenial-security_InReleaseGet:5 http://mirrors.aliy
  un.com/ubuntu xenial-updates/main amd64 Packages [796 kB]
  2018-06-25 02:51:46.638 | Ign:4 http://mirrors.aliyun.com/ubuntu xenial-security InRelease
  2018-06-25 02:51:47.524 | Get:6 http://mirrors.aliyun.com/ubuntu xenial-updates/universe amd64 Packages [636 kB]
  2018-06-25 02:51:47.694 | Get:7 http://mirrors.aliyun.com/ubuntu xenial-backports/main amd64 Packages [4844 B]
  2018-06-25 02:51:47.694 | Get:8 http://mirrors.aliyun.com/ubuntu xenial-backports/universe amd64 Packages [7400 B]
  2018-06-25 02:51:47.706 | Get:9 http://mirrors.aliyun.com/ubuntu xenial-security/main amd64 Packages [511 kB]
  2018-06-25 02:51:48.359 | Get:10 http://mirrors.aliyun.com/ubuntu xenial-security/universe amd64 Packages [355 kB]
  2018-06-25 02:51:48.876 | Fetched 2632 kB in 3s (832 kB/s)
  2018-06-25 02:51:49.605 | Reading package lists...
  2018-06-25 02:51:49.632 | W: An error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://mirro
  rs.aliyun.com/ubuntu xenial InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?)
  2018-06-25 02:51:49.632 | W: GPG error: http://mirrors.aliyun.com/ubuntu xenial-updates InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?)
  2018-06-25 02:51:49.632 | W: The repository 'http://mirrors.aliyun.com/ubuntu xenial-updates InRelease' is not signed.
  2018-06-25 02:51:49.632 | W: GPG error: http://mirrors.aliyun.com/ubuntu xenial-backports InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?)
  2018-06-25 02:51:49.632 | W: The repository 'http://mirrors.aliyun.com/ubuntu xenial-backports InRelease' is not signed.
  2018-06-25 02:51:49.632 | W: GPG error: http://mirrors.aliyun.com/ubuntu xenial-security InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?)
  2018-06-25 02:51:49.632 | W: The repository 'http://mirrors.aliyun.com/ubuntu xenial-security InRelease' is not signed.
  2018-06-25 02:51:49.632 | W: Failed to fetch http://mirrors.aliyun.com/ubuntu/dists/xenial/InRelease Could not execute 'apt-key' to verify signature (is gnupg installed?)
  2018-06-25 02:51:49.632 | W: Some index files failed to download. They have been ignored, or old ones used instead.
  2018-06-25 02:51:50.345 | Reading package lists...
  2018-06-25 02:51:50.504 | Building dependency tree...
  2018-06-25 02:51:50.576 | Calculating upgrade...
  2018-06-25 02:51:50.632 | The following packages will be upgraded:
  2018-06-25 02:51:50.632 | apt base-files bash bsdutils coreutils dpkg gcc-5-base gnupg gpgv grep init
  2018-06-25 02:51:50.632 | init-system-helpers libapparmor1 libapt-pkg5.0 libaudit-common libaudit1
  2018-06-25 02:51:50.634 | libblkid1 libc-bin libc6 libcryptsetup4 libdb5.3 libfdisk1 libgcrypt20
  2018-06-25 02:51:50.634 | libkmod2 libmount1 libpam-modules libpam-modules-bin libpam-runtime libpam0g
  2018-06-25 02:51:50.634 | libprocps4 libseccomp2 libsmartcols1 libstdc++6 libsystemd0 libudev1
  2018-06-25 02:51:50.634 | libuuid1 locales login lsb-base makedev mount multiarch-support passwd
  2018-06-25 02:51:50.634 | perl-base procps sensible-utils systemd systemd-sysv tar tzdata util-linux
  2018-06-25 02:51:50.634 | zlib1g
  2018-06-25 02:51:50.659 | 52 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
  2018-06-25 02:51:50.659 | Need to get 23.5 MB of archives.
  2018-06-25 02:51:50.659 | After this operation, 161 kB of additional disk space will be used.
  2018-06-25 02:51:50.659 | WARNING: The following packages cannot be authenticated!
  2018-06-25 02:51:50.659 | base-files bash bsdutils coreutils dpkg grep perl-base init-system-helpers
  2018-06-25 02:51:50.659 | init login libsystemd0 systemd libc6 libapparmor1 libaudit-common libaudit1
  2018-06-25 02:51:50.659 | libpam0g libpam-modules-bin libpam-modules passwd libuuid1 libblkid1
  2018-06-25 02:51:50.659 | libgcrypt20 libcryptsetup4 libkmod2 libmount1 libseccomp2 lsb-base
  2018-06-25 02:51:50.659 | util-linux mount tar locales libc-bin gcc-5-base libstdc++6 zlib1g
  2018-06-25 02:51:50.659 | libapt-pkg5.0 gpgv gnupg apt systemd-sysv libdb5.3 libfdisk1 libpam-runtime
  2018-06-25 02:51:50.659 | libsmartcols1 libudev1 multiarch-support sensible-utils libprocps4 makedev
  2018-06-25 02:51:50.659 | procps tzdata
  2018-06-25 02:51:50.662 | E: There were unauthenticated packages and -y was used without --allow-unauthenticated
  2018-06-25 02:51:51.261 | INFO diskimage_builder.block_device.blockdevice [-] State already cleaned - no way to do anything here
  2018-06-25 02:51:51.305 | Unmount /tmp/dib_build.shLTNvjU/mnt/var/cache/apt/archives
  2018-06-25 02:51:51.321 | Unmount /tmp/dib_build.shLTNvjU/mnt/tmp/pip
  2018-06-25 02:51:51.522 | +/opt/stack/octavia/devstack/plugin.sh:build_octavia_worker_image:1 exit_trap
  2018-06-25 02:51:51.527 | +./stack.sh:exit_trap:510 local r=1
  2018-06-25 02:51:51.533 | ++./stack.sh:exit_trap:511 jobs -p
  2018-06-25 02:51:51.538 | +./stack.sh:exit_trap:511 jobs=
  2018-06-25 02:51:51.543 | +./stack.sh:exit_trap:514 [[ -n '' ]]
  2018-06-25 02:51:51.548 | +./stack.sh:exit_trap:520 '[' -f /tmp/tmp.WQZcukSekU ']'
  2018-06-25 02:51:51.553 | +./stack.sh:exit_trap:521 rm /tmp/tmp.WQZcukSekU
  2018-06-25 02:51:51.559 | +./stack.sh:exit_trap:525 kill_spinner
  2018-06-25 02:51:51.565 | +./stack.sh:kill_spinner:424 '[' '!' -z '' ']'
  2018-06-25 02:51:51.569 | +./stack.sh:exit_trap:527 [[ 1 -ne 0 ]]
  2018-06-25 02:51:51.574 | +./stack.sh:exit_trap:528 echo 'Error on exit'
  2018-06-25 02:51:51.574 | Error on exit
  2018-06-25 02:51:51.579 | +./stack.sh:exit_trap:530 type -p generate-subunit
  2018-06-25 02:51:51.584 | +./stack.sh:exit_trap:531 generate-subunit 1529894031 1080 fail
  2018-06-25 02:51:52.004 | +./stack.sh:exit_trap:533 [[ -z /opt/stack/logs ]]
  2018-06-25 02:51:52.009 | +./stack.sh:exit_trap:536 /opt/stack/devstack/tools/worlddump.py -d /opt/stack/logs
  2018-06-25 02:51:52.991 | +./stack.sh:exit_trap:545 exit 1
2. 把 dib 的代码单独 clone 下来，按照blog直接使用命令disk-image-create vm ubuntu-minimal也出现问题，感觉是 ubuntu-minimal 依赖的 dpkg ebootstrap 都没有成功加载，但日志显示已经copy脚本
  2018-06-25 07:32:52.168 | Building elements: base vm ubuntu-minimal block-device-mbr
  2018-06-25 07:32:52.242 | Expanded element dependencies to: dib-python install-types install-bin block-device-mbr ubuntu-minimal ubuntu-common vm sysprep base pkg-map debootstrap dib-init-system bootloader manifests package-installs dpkg
  ......
  2018-06-25 07:32:53.731 | dib-run-parts Running /tmp/dib_build.vPtWj9sd/hooks/root.d/08-debootstrap
  2018-06-25 07:32:53.734 | /tmp/dib_build.vPtWj9sd/hooks/root.d/08-debootstrap: line 53: dpkg: command not found
  2018-06-25 07:32:53.734 | /tmp/dib_build.vPtWj9sd/hooks/root.d/08-debootstrap: line 53: [: !=: unary operator expected
  2018-06-25 07:32:53.741 | sh: debootstrap: command not found
  2018-06-25 07:32:53.999 | INFO diskimage_builder.block_device.blockdevice [-] State already cleaned - no way to do anything here
非常感谢！！！
xionchen commented on Thu Aug 02 2018

@Sirius21c 应该是缺少二进制依赖导致的，
可以clone dib的仓库
然后使用bindep安装二进制依赖。
适应diskimage-builder中的bindep.txt这个文件作为bindep的安装文件.
HF-CrisXu commented on Fri Nov 08 2019

2019-11-07 12:46:37.801 | + sudo udevadm settle
2019-11-07 12:46:37.807 | + sudo losetup -f
2019-11-07 12:46:37.811 | /dev/loop5
2019-11-07 12:46:37.812 | ++ sudo kpartx -av /tmp/tmp.JFLzt8mOgb/3cuH0l.raw
2019-11-07 12:46:37.812 | ++ awk '/loop[0-9]+p1/ {print $3}'
2019-11-07 12:46:37.818 | device-mapper: resume ioctl on loop5p1 failed: Invalid argument
2019-11-07 12:46:37.837 | create/reload failed on loop5p1
2019-11-07 12:46:37.838 | + ROOT_LOOPDEV=
2019-11-07 12:46:37.838 | ++ rm -r /tmp/tmp.JFLzt8mOgb
2019-11-07 12:46:38.101 | + /home/images/new-images/dib/diskimage-builder/diskimage_builder/lib/common-functions:run_d:1 : trap_cleanup
2019-11-07 12:46:38.103 | + /home/images/new-images/dib/diskimage-builder/diskimage_builder/lib/img-functions:trap_cleanup:36exitval=1

大神帮我看下是啥问题，可以吗

ARTS_003

"week 03"

[Algrothm] knight-dialer

problem

思路

我的解法

递归

存储

改为非递归，即动态规划的方式

solution

[Review]

[Tip] python type hint

what

why

how

CATALOG

FEATURED TAGS

FRIENDS

[Algrothm] knight-dialer

problem

思路

我的解法

递归

存储

改为非递归，即动态规划的方式

solution

[Review]

[Tip] python type hint

what

why

how

[Share] 美团技术leader：写给工程师的十条精进原则

CATALOG

FEATURED TAGS

FRIENDS