Collatz問題 #16

値9232のノードがどの開始ノードからの経路上にあるのかを見る。

collatz10.g

BEGIN {
  if (ARGC != 1) {
    print("usage: gvpr -f collatz10.g -a <node_name>");
    exit(1);
  }
}

N [name == ARGV[0]] {
  graph_t g = graph("", "D"), h = graph("", "N");
  aset(clone(g, $), "peripheries", "2");
  node(h, $.name);
  node_t n;
  edge_t e;
  while (1) {
    n = fstnode(h);
    if (n == NULL) break;
    e = fstin(node($G, n.name));
    delete(h, n);
    if (e == NULL) continue;
    if (e.tail.name != 1) node(h, e.tail.name);
    clone(g, e);
    e = nxtin(e);
    if (e != NULL) {
      if (e.tail.name != 1) node(h, e.tail.name);
      clone(g, e);
    }
  }
  write(g);
  exit(0);
}

END {
  printf(2, "node <%s> is not found\n", ARGV[0]);
}

collatz10.gは引数で与えられたノードより上流のグラフを抜き出すgvprプログラムである。

$ ./collatz9 | tred 2> /dev/null | gvpr -fcollatz10.g -a9232 | gvpr 'N[indegree==0]{print(fstout($));}'
126->63
164->82
108->54
194->97

したがって、9232のノードは194->97から始まる最長経路上にあることが分かる。

tred 2> /dev/null

ではtredで出る警告を捨てるために標準エラーをナルデバイスに捨てている。
Windowsであればnulに捨てればいい。