覆面算

READ + WRITE + TALK = SKILL　を満たす解が何通りあるか。

以下のプログラムは，2 番目のものより 10 倍ほど「遅い」。

library(e1071)
d = permutations(10)-1
w = c(1000, 100, 10, 1)
w2 = c(w*10, 1)
ans = apply(d, 1, function(x) all(x[c(1,5,7,10)] != 0) && sum(x[1:4]*w)+sum(x[c(5,1,6,7,2)]*w2)+sum(x[c(7,3,8,9)]*w) == sum(x[c(10,9,6,8,8)]*w2))
sum(ans)
d = d[ans,]
apply(d, 1, function(x) cat(sprintf("%i + %i + %i = %i\n", sum(x[1:4]*w), sum(x[c(5,1,6,7,2)]*w2), sum(x[c(7,3,8,9)]*w), sum(x[c(10,9,6,8,8)]*w2))))

なるべくベクトル演算を使うと速くなる。

library(e1071)
d = t(permutations(10)-1)
w = c(1000, 100, 10, 1)
w2 = c(w*10, 1)
read  = colSums(d[1:4,]*w)
write = colSums(d[c(5,1,6,7,2),]*w2)
talk  = colSums(d[c(7,3,8,9),]*w)
skill = colSums(d[c(10,9,6,8,8),]*w2)
ans = d[1,]*d[5,]*d[7,]*d[10,] != 0 & read+write+talk == skill
sum(ans)
data.frame(read=read[ans], write=write[ans], talk=talk[ans], skill=skill[ans])

   read write talk skill
1  5270 85132 3764 94166
2  2543 72065 6491 81099
3  5180 65921 2843 73944
4  1632 41976 7380 50988
5  5094 75310 1962 82366
6  5096 35710 1982 42788
7  7092 37510 1986 46588
8  7092 47310 1986 56388
9  4905 24689 8017 37611
10 9728 19467 6205 35400

 

添え字の検索

プログラムの冒頭に示すような，1 文字を要素とする 20×20 の行列がある。

"STAY HUNGRY, STAY FOOLISH" の各文字が，行列のどこにあるか，添え字を求めよ。

ただし，一度検索された要素（添え字）は二度目以降は検索対象にならない。

box <- matrix(c(
"Z","T","A","V","O","J","Z","G","W","L","M","A","W","B","Y","I","M","D","K","Y",
"P","G","P","N","C","Q","E","R","I","Q","I","T","O","K","H","F","T","O","Z","Z",
"D","T","S","E","L","F","N","O","L","H","Z","K","L","N","F","D","J","C","G","A",
"A","E","U","J","U","I","N","Z","D","T","D","U","W","J","O","N","C","S","L","H",
"Z","W","E","F","G","Z","B","R","I","O","T","U","N","B","O","G","N","U","Z","Y",
"U","Y","C","O","C","P","Z","G","W","C","O","D","J","X","J","L","F","V","J","H",
"D","B","K","Q","I","J","M","Q","X","P","U","P","Z","G","C","G","S","M","I","P",
"F","E","N","Q","R","Z","T","B","U","J","T","M","E","B","U","T","N","F","E","Y",
"R","E"," ","Y","D","G","B","A","C","F","B"," ","A","B","W","X","U","J","A","Z",
"M","D","O","W","W","X","S","C","O","E","J","W","N","L","U","F","E","X","H","X",
"E","F","O","F","W","P","V","R","U","I","G","R","E","Z","W","O","U","G"," ","E",
"W","I","M","V","D","Q","V","S","I","Y","Y","B","R","Z","O","Y","S","U","W","Y",
"D",",","A","G","U","F","L","Z","L","N","X","O","E","Q","J","X","E","G","H","E",
"O","N","E","M","V","J","Z","N","C","Q","P","Z","K","W","F","M","V","K","Y","M",
"M","B"," ","H","R","M","L","S","T","I","A","O","O","O","O",",","E","H","M","E",
"I","U","O","Q","B","J","Z","N","Q","N","Q","H","U","D","Y","J","A","B","I","P",
"X","K","K","I","S","H","Z","H","D","L","Z","O","J","N","P","C","W","O","O","R",
"L","Y","Y","M"," ","B","N","T","K","X","C"," ","S","B","K","H","R","W","M","D",
"V","N","U","L","L","Z","M","I","O","G","S","M","P","U","E","P","E","O","A","C",
"R","E","T","L","F","S","D","T","Q"," ","U","P","Y","K","A","F","P","G","W","O"),
ncol=20, byrow=TRUE)
types = unlist(strsplit("STAY HUNGRY, STAY FOOLISH", ""))
for (i in seq_along(types)) {
  ans = which(types[i] == box, arr.ind=TRUE)[1, , drop=FALSE]
  box[ans] = ""
  print(c(ans))
}

最適な組合せ

16 種類のオーダーと，それにかかる日数と売上代金の表がある。同じオーダーを 2 つ以上使うことはできない。同時に 2 つ以上のオーダーは処理できない。代金が最大になるような複数のオーダーの組合せを求めよ。ただし，所要日数の合計は 100 日以内でなければならない。

            所用日数  売上代金
オーダー 1         9      130
オーダー 2        12      150
オーダー 3        20      190
オーダー 4        23      190
オーダー 5        27      230
オーダー 6        33      290
オーダー 7        31      330
オーダー 8         9       70
オーダー 9        30      330
オーダー 10        9      110
オーダー 11        6       90
オーダー 12       34      310
オーダー 13       34      330
オーダー 14       22      190
オーダー 15       25      230
オーダー 16       13      170

fee = rev(c(130, 150, 190, 190, 230, 290, 330, 70, 330, 110, 90, 310, 330, 190, 230, 170))
day = rev(c(9, 12, 20, 23, 27, 33, 31, 9, 30, 9, 6, 34, 34, 22, 25, 13))
library(e1071)
bc = bincombinations(length(fee))
ans = apply(bc, 1, function(x) { x = as.logical(x); ifelse(sum(day[x]) <= 100, sum(fee[x]), 0) })
( max.fee = max(ans) )
apply(bc[ans == max.fee, ], 1, function(x) paste(paste("Order", which(rev(x) == 1)), collapse=", "))

最短距離のルート選択

「最もエネルギー効率のよいルート選択」と同じであるが，こちらは，合計距離が最短になるルート選択。エネルギー行列と違って，距離行列は対称行列である。

ノードが少なければ，しらみつぶし探索でも問題ないが，ノードが多くなったら，別の解法を採らないとね...

dist = matrix(c(0,1,3,4,5, 1,0,2,3,4, 3,2,0,1,2, 4,3,1,0,1, 5,4,2,1,0), 5)
library(e1071)
route = permutations(5)
d = apply(route, 1, function(r) sum(dist[cbind(r, c(r[-1], r[1]))]))
( min.dist = min(d) ) # 最短距離
route[d == min.dist,] # 径路（逆順も含む）