経過時間の筆算

2 つの時刻の間の時間数の筆算で，0 ～ 9 の全てが現れる計算は何通りあるか

例

  16時27分
 - 5時38分
==========   
  10時49分

0x 時とか 0y 分のような zero fill の 0 は除く
また，0 時 zz 分も除く

プログラム1
以下の AWK(GAWK) プログラムが 4 秒ほどで，一番速かった。

#!/usr/local/bin/gawk -f

BEGIN {
  for (h1 = 1; h1 < 24; h1++) {
    for (m1 = 0; m1 < 60; m1++) {
      t1 = h1*60+m1
      for (h2 = 1; h2 <= h1; h2++) {
        for (m2 = 0; m2 < 60; m2++) {
          t2 = h2*60+m2
          if (t2 > t1) break
          diff = t1-t2
          m3 = diff%60
          h3 = int(diff/60)
          tbl(h1)
          tbl(h2)
          if (h3 > 0) tbl(h3)
          tbl(m1)
          tbl(m2)
          tbl(m3)
          if (length(digits) == 10) {
#           print h1, m1, h2, m2, h3, m3
            count++
          }
          delete digits
        }
      }
    }
  }
  print "ans =", count
}

function tbl(d,     d1) {
  d1 = int(d/10)
  if (d1 > 0) digits[d1]
  digits[d%10]
}

文字列を使って以下のようにしたものは 7 秒強かかる。

#!/usr/local/bin/gawk -f

BEGIN {
  for (h1 = 1; h1 < 24; h1++) {
    for (m1 = 0; m1 < 60; m1++) {
      t1 = h1*60+m1
      for (h2 = 1; h2 <= h1; h2++) {
        for (m2 = 0; m2 < 60; m2++) {
          t2 = h2*60+m2
          if (t2 > t1) break
          diff = t1-t2
          m3 = diff%60
          h3 = int(diff/60)
          hm = m1 m2 m3 h1 h2
          if (h3 > 0) hm = hm h3
          split(hm, a, "")
          for (i in a) digits[a[i]]
          if (length(digits) == 10) {
#           print h1, m1, h2, m2, h3, m3
            count++
          }
          delete digits
        }
      }
    }
  }
  print "ans =", count
}

最初のプログラムを R で描き直すと，25 秒もかかる。ほぼ 6 倍ということだ。

tbl = function(d, digits) {
  d1 = d %/% 10
  if (d1 > 0) digits[d1+1] = TRUE
  digits[d %% 10+1] = TRUE
  return(digits)
}
count = 0
for (h1 in 1:23) {
  for (m1 in 0:59) {
    t1 = h1*60+m1
    for (h2 in 1:h1) {
      for (m2 in 0:59) {
        t2 = h2*60+m2
        if (t1 < t2) break
        diff = t1-t2
        m3 = diff %% 60
        h3 = diff %/% 60
        digits = logical(10)
        digits = tbl(h1, digits)
        digits = tbl(h2, digits)
        if (h3 > 0) digits = tbl(h3, digits)
        digits = tbl(m1, digits)
        digits = tbl(m2, digits)
        digits = tbl(m3, digits)
        if (sum(digits) == 10) {
#         cat(h1, m1, h2, m2, h3, m3, "\n")
          count = count+1
        }
      }
    }
  }
}
cat("ans =", count, "\n")

R で定石のベクトル演算を使って書いてみたら，260 秒もかかるとんでもないプログラムになった。最短 AWK プログラムのほぼ 65 倍ということだ。

a = expand.grid(1:23, 0:59, 1:23, 0:59)
t1 = a[,1]*60+a[,2]
t2 = a[,3]*60+a[,4]
diff = t1 - t2
flag = diff > 0
a$diff1 = diff %/% 60
a$diff2 = diff %% 60
a = a[flag,]
func = function(d) {
  d2 = d%%10
  d1 = d%/%10
  d1[d1 == 0] = NA
  return(length(table(c(d1, d2))))
}
count = 0
apply(a, 1, function(x) {
  if (x[5] == 0) x = x[-5]
  if (func(x) == 10) {
#   cat(h1, m1, h2, m2, h3, m3, "\n")
    count+1 ->> count
  }
})
cat("ans =", count, "\n")

解答は，以下の 48 通りということである。

16時27分 -  5時38分 = 10時49分
16時27分 -  5時39分 = 10時48分
16時27分 -  5時48分 = 10時39分
16時27分 -  5時49分 = 10時38分
16時27分 - 10時38分 =  5時49分
16時27分 - 10時39分 =  5時48分
16時27分 - 10時48分 =  5時39分
16時27分 - 10時49分 =  5時38分
18時25分 -  7時36分 = 10時49分
18時25分 -  7時39分 = 10時46分
18時25分 -  7時46分 = 10時39分
18時25分 -  7時49分 = 10時36分
18時25分 - 10時36分 =  7時49分
18時25分 - 10時39分 =  7時46分
18時25分 - 10時46分 =  7時39分
18時25分 - 10時49分 =  7時36分
20時47分 -  3時48分 = 16時59分
20時47分 -  3時49分 = 16時58分
20時47分 -  3時58分 = 16時49分
20時47分 -  3時59分 = 16時48分
20時47分 -  6時48分 = 13時59分
20時47分 -  6時49分 = 13時58分
20時47分 -  6時58分 = 13時49分
20時47分 -  6時59分 = 13時48分
20時47分 - 13時48分 =  6時59分
20時47分 - 13時49分 =  6時58分
20時47分 - 13時58分 =  6時49分
20時47分 - 13時59分 =  6時48分
20時47分 - 16時48分 =  3時59分
20時47分 - 16時49分 =  3時58分
20時47分 - 16時58分 =  3時49分
20時47分 - 16時59分 =  3時48分
20時57分 -  4時18分 = 16時39分
20時57分 -  4時19分 = 16時38分
20時57分 -  4時38分 = 16時19分
20時57分 -  4時39分 = 16時18分
20時57分 -  6時18分 = 14時39分
20時57分 -  6時19分 = 14時38分
20時57分 -  6時38分 = 14時19分
20時57分 -  6時39分 = 14時18分
20時57分 - 14時18分 =  6時39分
20時57分 - 14時19分 =  6時38分
20時57分 - 14時38分 =  6時19分
20時57分 - 14時39分 =  6時18分
20時57分 - 16時18分 =  4時39分
20時57分 - 16時19分 =  4時38分
20時57分 - 16時38分 =  4時19分
20時57分 - 16時39分 =  4時18分