ダブルテトロミノ
締め切りが 2017/02/17 10:00 AM なので，その 1 分後に投稿されるように予約
下図のように、黒いマスが 8つあります。
テトロミノ2つを使って黒いマスで示された図形を作るには、どんなテトロミノが必要なのか、全ての組み合わせを求めてください。
例えば上の例の場合、
LとO、LとS
という組み合わせが考えられます。
テトロミノは、下図の 5 種類があります：
裏返したり回転したりしてできるテトロミノは同じ名前です。
入力は
56 37 36 55 35 46 45 47
のような感じです。
空白区切りで黒いマスの位置が書かれています。
黒いマスの位置は、1文字目が x 座標、2文字目がy座標です。
出力は、
LO,LS
のような感じです。
ペアをコンマ区切りで並べてください。
ペア間もペア内も、アルファベット順に整列しておく必要があります。
下表の通りです。
誤 LS,LO
誤 OL,SL
正 LO,LS
入力の形が2つのテトロミノでは作れない場合は、
-
を出力してください。
【例】
入力 出力
56 37 36 55 35 46 45 47 LO,LS
70 07 44 34 98 11 00 32 -
63 60 67 65 64 62 61 66 II
【補足】
不正な入力に対処する必要はありません。
入力には、かならず8マス含まれています。重複はありません。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
テトロミノは回転・対称も考えて 19 通りあるので，それをデータ化する。
たとえば，図にある T テトロミノは，左にある黒を(0,0) として，残り 3 つの正方形は (-1,1), (0,1), (1,1) にあるなど。
19 通りのテトロミノを最初の盤面の黒の位置に順次置いていって，最初の同じ盤面になれば 2 つのテトロミノの種類を記憶する。
ブルートフォースでプログラムしたが，制限時間内に答えが出るので，チューンアップはしない。
f = function(s) {
a = cbind(
c(0,0,1,0,2,0,3,0), # I
c(0,0,0,1,0,2,0,3),
c(0,0,1,0,2,0,2,1), # L
c(0,0,0,1,0,2,-1,2),
c(0,0,0,1,1,1,2,1),
c(0,0,1,0,0,1,0,2),
c(0,0,0,1,-1,1,-2,1),
c(0,0,0,1,0,2,1,2),
c(0,0,1,0,2,0,0,1),
c(0,0,1,0,1,1,1,2),
c(0,0,1,0,0,1,1,1), # O
c(0,0,1,0,1,1,2,1), # S
c(0,0,0,1,-1,1,-1,2),
c(0,0,0,1,1,1,1,2),
c(0,0,1,0,0,1,-1,1),
c(0,0,-1,1,0,1,1,1), # T
c(0,0,0,1,0,2,1,1),
c(0,0,1,0,2,0,1,1),
c(0,0,0,1,0,2,-1,1)
)
dim(a) = c(2, 4, 19) # ピースを構成する正方形の4つの座標(x, y)が19種類
p = c("I", "I", rep("L", 8), "O", rep("S", 4), rep("T", 4)) # ピースの名前
xy = matrix(as.numeric(unlist(strsplit(gsub(" ", "", s), ""))) + 1, byrow = TRUE, ncol = 2) # 10行10列の行列における黒いマスの座標
b0 = matrix(0, 10, 10)
b = matrix(0, 10, 10)
b[xy] = 1 # マーク
kxy = (xy[, 2] - 1) * 10 + xy[, 1] # ここまでで盤面の設定（手本の盤面と呼ぶ）
ans = NULL
for (i in 1:19) { # 回転・反転を考慮した19種のテトロミノを順次試す
for (j in i:19) { # 回転・反転を考慮した19種のテトロミノを順次試す
for (k1 in 1:8) { # i番目のテトロミノを置くマスの位置 (xy[k1,1], xy[k1,2]) を順次試す
for (k2 in 1:8) { # j番目のテトロミノを置くマスの位置 (xy[k2,1], xy[k2,2]) を順次試す
b1 = b0 # 新しい（クリーンな）盤面
for (l in 1:4) { # テトロミノを構成する4つの正方形で盤面をマークする
sxi = xy[k1, 1] + a[1, l, i] # i番目のテトロミノが置かれる盤面の行
syi = xy[k1, 2] + a[2, l, i] # i番目のテトロミノが置かれる盤面の列
if ((sxi >= 1 && 10 >= sxi) && (syi >= 1 && 10 >= syi)) {
b1[sxi, syi] = 1 # はみ出さないのでマーク
}
sxj = xy[k2, 1] + a[1, l, j] # j番目のテトロミノが置かれる盤面の行
syj = xy[k2, 2] + a[2, l, j] # j番目のテトロミノが置かれる盤面の列
if ((sxj >= 1 && 10 >= sxj) && (syj >= 1 && 10 >= syj)) {
b1[sxj, syj] = 1 # はみ出さないのでマーク
}
}
if (all(b1 == b)) { # 手本の盤面と同じであれば結果を記録（2つのテトロミノは何だったか）
ans = rbind(ans, c(p[i], p[j]))
}
}
}
}
}
ans = unique(as.data.frame(ans)) # 同じ解を取り除く
if (nrow(ans) == 0) { # 解がないとき
cat("-")
} else { # 解があるとき
cat(paste(apply(ans, 1, paste, collapse = ""), collapse = ","))
}
cat("\n")
}
f("56 37 36 55 35 46 45 47") # LO,LS
f("70 07 44 34 98 11 00 32") # -
f("63 60 67 65 64 62 61 66") # II
f("65 46 45 66 54 44 64 56") # LL
f("34 46 36 47 33 44 35 45") # II,SS,TT
f("85 75 76 84 83 73 86 74") # II,LL,OO
f("67 76 77 78 68 69 58 57") # LT,ST
f("44 45 34 55 43 35 33 56") # LO,LS
f("55 46 66 45 44 57 54 56") # LT,OT
f("43 24 35 33 34 32 23 44") # SS,TT
f("20 10 12 21 03 22 13 11") # LL,OS
f("53 54 75 45 55 35 65 56") # -
f("88 89 86 87 78 68 99 79") # -
f("28 37 25 38 35 47 46 36") # SS
f("94 93 01 03 02 91 92 04") # II
