Python引用计数

Python里object都会有一个属性:被引用次数,垃圾回收的时候会用到,最简单的情形是引用计数=0,直接回收掉即可。其他复杂些的情形,如循环引用,则需要通过标记-清除和分代回收机制来进行。
sys.getrefcount(obj)可以查看一个object被引用的次数。有趣的是它给出的结果总是比实际数目多1,原因是调用函数时也增加了一次引用。
其文档https://docs.python.org/3.7/library/sys.html#sys.getrefcount是如此描述的:

sys.getrefcount(object)
Return the reference count of the object. The count returned is generally one higher than you might expect, because it includes the (temporary) reference as an argument to getrefcount().

“generally one higher”,是说一般情况下会多一,但特殊情况不会多?否则直接减一然后返回实际值就行了?
值得研究一下。

二手HP LaserJet 1020 提示“前端盖打开或缺少硒鼓”的错误排查

首先这个报错的设定真是特别2,因为真正的原因甚至不止这两种,而把多个错误放到一条提示里,违反了基本的行事逻辑,平白增加了排错的难度,真是懒到家了,这样做可能可以少用几根信号线,我只能认为这是节省成本节约到姥姥家了。

搜索得知此报错的原因千奇百怪,但都和我的情况不符,我这边前端盖显然没有打开,前端盖的传感器连杆也好好的,硒鼓也是半新的,硒鼓的金属触点也是好的。

折腾了半天,把打印机拎起来晃也没用。继续搜索,在惠普官网终于找到了相关信息:未检测到硒鼓,提示有一个传感器未复位可能导致检测不到硒鼓。拆下硒鼓,找到机器里进纸口上方金属横杆边靠左侧的传感器,用手按压,发现传感器不能移动,用手反复按压,虽有严重阻滞,但传感器终于动了。按上硒鼓后,机器终于恢复。

不过此时打印的效果不佳,页面总有几道白线无墨,勉强打印了几页之后,机器又不动了。怒了拆下硒鼓摇晃,把机器也180°翻转过来。继续尝试,这时出纸口竟然有一片枯树叶和纸一起送出来,仔细看根本不是我这附近的树,只能说商家卖东西太不上心了,说发货前清理过,结果呢。

另外这个解决方案是放在“卡纸后无法继续打印”这个话题里,如果能加上如标题里的报错信息,就能让人直接检索到了。

跟医生看病一样,多个症状对应多个病因,只有对情况比较熟悉,才有可能找到真正原因。

UVa1600

1170: 暴躁机器人

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 7
[提交] [状态] [讨论版] [命题人:test]

题目描述

PIPI发明了一个暴躁机器人,机器人位于一个 n*m 的网格中, 网格中的一些格子是空地(数字0表示),另一些是障碍物(数字1表示),暴躁机器人从左上角(1,1)出发前往右下角(n,m), 机器人每一步可以往上下左右四个方向走一个,由于机器人很暴躁,所以它可以摧毁障碍物。但是它最多连续穿过k 个障碍物,求机器人从左上角到右下角的最短路长度。 保证起点和终点是空地。

输入

输入包含一个正整数T,代表测试用例个数。 
对于每组测试用例,第一行包含三个整数 n,m,k (1<=n,m<=20, 0<=k <=20)。 
接下来包含一个 n*m 的01矩阵,代表网格矩阵。 

输出

对于每组测试用例,输出机器人从左上角走到右下角的最少步数。若无法到达右下角,输出 -1 。

样例输入

1
3 6 1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0

样例输出

9

提示

测试用例的走法: (1,1) -> (2,1) -> (2,2) -> (2,3) ->(2,4) -> (1,4) -> (1,5) -> (1,6) -> (2,6) -> (3,6) . 路径长度为 9. 

来源/分类

中等搜索

今天被这道题拦住了。

原因倒是不难理解,如果像传统搜索题那样只用二维数组记录一个坐标是否已被访问,由于访问路径的先后顺序问题,可能错过最优解或者错判为无解。所以关键在于怎样容纳多次访问重复的坐标,而且还要做必要的剪枝。

因为初始不熟悉这类问题,看答案都看不明白,不懂为什么只要用三维数组控制障碍数,不需要管其他指标,而且最后结果不需要去比较所有层级的最小值。

等到最后想明白究竟搜索时在控制什么指标,其他人的答案也就看明白了。

其实有两个重要指标:机器人走到某个坐标时,1. 走的步数,2. 当前剩余的突破能力。每个坐标都维护这些阈值,如果机器人走过来,走的步数小于当前坐标记录的最小值,或者突破能力大(如果此处是障碍),都可以入队列继续搜索,否则就抛弃,因为之前已经有更优的解了。

要理解别人的答案,注意几个点。由于BFS的特性,可以保证第一次走到此坐标时一定是最短距离。三维数组的第三维就是在记录到此为止突破的障碍数,每一层只访问一次,不重复,但不同的层级可以多次访问同一坐标,层级之间并没有顺序关系。剩余的突破能力应该越大越好,不过这一点可以忽略不去控制,多几次入队没有本质影响。因为突破能力弱的要么到不了终点,要么是之前拆墙走了捷径所以最终到达终点时用的步数可能要少一些。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>

using namespace std;

const int MAX = 1 << 30;

struct point {
  int x;  // location
  int y;
  int able;  // ability left to go through obstacle
  int steps;
  point(int x=0, int y=0, int able=0, int steps=0): x(x), y(y), able(able), steps(steps) {}
};

bool valid(int x, int y, vector<vector<int>> &arr) {
  return x >= 0 && x < arr.size() && y >= 0 && y < arr[0].size();
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  #ifndef ONLINE_JUDGE
  freopen("3.in", "r", stdin);
  freopen("3.out", "w", stdout);
  #endif
  int T;
  int n, m, k;
  cin >> T;
  for (int cs=1; cs <= T; cs++) {
    cin >> n >> m >> k;
    vector<vector<int>> arr(n, vector<int>(m));
    vector<vector<point>> v(n, vector<point>(m, point(0, 0, 0, MAX)));
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
        cin >> arr[i][j];
      }
    }
    queue<point> q;
    point p = point(0, 0, k, 0);
    q.push(p);
    v[0][0].steps = 0;
    v[0][0].able = k;

    int able;
    vector<int> m1 = {1, -1, 0, 0};
    vector<int> m2 = {0, 0, 1, -1};
    int x, y;
    while(!q.empty()) {
      p = q.front();
      q.pop();
      x = p.x;
      y = p.y;
      
      if(x == n-1 && y == m-1) {
        break;
      }
      for(int i=0; i<4; i++) {
        int nx = m1[i] + x;
        int ny = m2[i] + y;
        if(valid(nx, ny, arr) ) {
          bool flag = false;
          if(arr[nx][ny] == 0) {
            if(v[nx][ny].steps > p.steps + 1) {
              v[nx][ny].steps = p.steps + 1;
              q.push(point(nx, ny, k, p.steps+1));
            }
          }
          else if (p.able > 0) {
            if(v[nx][ny].steps > p.steps + 1) {
              v[nx][ny].steps = p.steps + 1;
            }
            else if(p.able > v[nx][ny].able) {
              v[nx][ny].able = p.able;
            }
            else {
              continue;
            }
            q.push(point(nx, ny, p.able-1, p.steps+1));
          }
        }
      }
    }

    if(v[n-1][m-1].steps != MAX) {
      cout << v[n-1][m-1].steps << "\n";
    }
    else {
      cout << "-1\n";
    }
  }
  return 0;
}

软件源被墙的解决办法

一般下载会用到wget和curl,那么为它们设置代理即可。

编辑 ~/.wgetrc

内容为:

use_proxy=on
http_proxy=127.0.0.1:8123
https_proxy=127.0.0.1:8123

编辑 ~/.curlrc

内容为:

proxy = localhost:8123

我使用polipo将SS转换为http代理,所以代理服务器地址是本地。

个人觉得这样的方式比较好,不用重启,只修改当前用户。不需要的时候可以用#把代理配置注释掉,还是比较方便的。

manjaro与video-vesa

手欠安装了video-vesa驱动,然后manjaro就无法启动了(表面上)。

第一思路是用启动盘进入live系统,chroot进入原系统,卸载错误驱动。这样确实可以解决问题,但其实杀鸡用了牛刀。(BTW:live系统root默认密码是manjaro)

显卡驱动只是导致图形界面无法启动,命令行是可以正常使用的。所以更快的解决办法是:

  1. Ctr-Alt F2 and log in
  2. sudo mhwd -r pci video-vesa
  3. Restart, and that’s it.

via: https://forum.manjaro.org/t/my-video-vesa-nightmare-solved/31505

树:节点的深度与高度定义

(考虑深度时,把树看作液体,节点越往下越深;考虑高度时,把树当作建筑,从最深的子孙-地基数上来。节点和兄弟,深度一定相同,高度不一定相同。)

origin:https://stackoverflow.com/a/2603707/2098804

I learned that depth and height are properties of a node:

  • The depth of a node is the number of edges from the node to the tree’s root node.
    A root node will have a depth of 0.
  • The height of a node is the number of edges on the longest path from the node to a leaf.
    A leaf node will have a height of 0.

Properties of a tree:

  • The height of a tree would be the height of its root node,
    or equivalently, the depth of its deepest node.
  • The diameter (or width) of a tree is the number of nodes on the longest path between any two leaf nodes. The tree below has a diameter of 6 nodes.
A tree, with height and depth of each node

Why numbering should start at zero – E. W. Dijkstra

EWD831

Why numbering should start at zero

To denote the subsequence of natural numbers 2, 3, …, 12 without the pernicious three dots, four conventions are open to us

a)2 ≤ i < 13
b)1 < i ≤ 12
c)2 ≤ i ≤ 12
d)1 < i < 13

Are there reasons to prefer one convention to the other? Yes, there are. The observation that conventions a) and b) have the advantage that the difference between the bounds as mentioned equals the length of the subsequence is valid. So is the observation that, as a consequence, in either convention two subsequences are adjacent means that the upper bound of the one equals the lower bound of the other. Valid as these observations are, they don’t enable us to choose between a) and b); so let us start afresh.

There is a smallest natural number. Exclusion of the lower bound —as in b) and d)— forces for a subsequence starting at the smallest natural number the lower bound as mentioned into the realm of the unnatural numbers. That is ugly, so for the lower bound we prefer the ≤ as in a) and c). Consider now the subsequences starting at the smallest natural number: inclusion of the upper bound would then force the latter to be unnatural by the time the sequence has shrunk to the empty one. That is ugly, so for the upper bound we prefer < as in a) and d). We conclude that convention a) is to be preferred.

Remark  The programming language Mesa, developed at Xerox PARC, has special notations for intervals of integers in all four conventions. Extensive experience with Mesa has shown that the use of the other three conventions has been a constant source of clumsiness and mistakes, and on account of that experience Mesa programmers are now strongly advised not to use the latter three available features. I mention this experimental evidence —for what it is worth— because some people feel uncomfortable with conclusions that have not been confirmed in practice. (End of Remark.)

*                *
*

When dealing with a sequence of length N, the elements of which we wish to distinguish by subscript, the next vexing question is what subscript value to assign to its starting element. Adhering to convention a) yields, when starting with subscript 1, the subscript range 1 ≤ i < N+1; starting with 0, however, gives the nicer range 0 ≤  i < N. So let us let our ordinals start at zero: an element’s ordinal (subscript) equals the number of elements preceding it in the sequence. And the moral of the story is that we had better regard —after all those centuries!— zero as a most natural number.

Remark  Many programming languages have been designed without due attention to this detail. In FORTRAN subscripts always start at 1; in ALGOL 60 and in PASCAL, convention c) has been adopted; the more recent SASL has fallen back on the FORTRAN convention: a sequence in SASL is at the same time a function on the positive integers. Pity! (End of Remark.)

*                *
*

The above has been triggered by a recent incident, when, in an emotional outburst, one of my mathematical colleagues at the University —not a computing scientist— accused a number of younger computing scientists of “pedantry” because —as they do by habit— they started numbering at zero. He took consciously adopting the most sensible convention as a provocation. (Also the “End of …” convention is viewed of as provocative; but the convention is useful: I know of a student who almost failed at an examination by the tacit assumption that the questions ended at the bottom of the first page.) I think Antony Jay is right when he states: “In corporate religions as in others, the heretic must be cast out not because of the probability that he is wrong but because of the possibility that he is right.”

Plataanstraat 5
5671 AL NUENEN
The Netherlands
11 August 1982
prof.dr. Edsger W. Dijkstra
Burroughs Research Fellow

Transcriber: Kevin Hely.
Last revised on Fri, 2 May 2008.

origin: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html