ぐるぐるスクエア

ぐるぐるスクエア

締め切りが 2017/02/17 10:00 AM なので，その 1 分後に投稿されるように予約

【概要】

下図のように四角形のマスに数が入っています。



マスは無限に広がっており、全てのマスに数が入っています。
数を指定するので、その数が書かれているマスに隣接する（つまり、辺を共有する）4つのマスに書かれている数を、小さい順に出力してください。
※法則は図から読み取ってください

【入出力】
入力は
12
のように、普通に 10進数で来ます。

出力は、
3,11,13,29
のような感じです。

4つの数をコンマ区切りで昇順に並べてください。

【例】
入力     出力
12     3,11,13,29
34     15,33,35,61
77     46,76,78,116

【補足】

    不正な入力に対処する必要はありません。
    入力は、1以上、1000以下です。

================================================

規則性を利用してプログラム

「入力は、1以上、1000以下」の意味は何なのだろうか？上限は幾つだろうと計算時間はほとんど瞬殺。

ru = function(n) 4 * n^2 +  4 * n + 1 # 右上 1,9,25,49,81,... の数列　n=0,1,2,3,4,...
lu = function(n) 4 * n^2 +  6 * n + 3 # 左上 1,3,13,31,57,... の数列
ld = function(n) 4 * n^2 +  8 * n + 5 # 左下 1,5,17,37,65,... の数列
rd = function(n) 4 * n^2 + 10 * n + 7 # 右下 1,7,21,43,73,... の数列
up    = function(n) 8 * n + 9  # 上のサイクルへの差分 例えば 2（サイクル0） から 11（サイクル1） への差分
left  = function(n) 8 * n + 11 # 左のサイクルへの差分 例えば 3（サイクル0） から 14（サイクル1） への差分
down  = function(n) 8 * n + 13 # 下のサイクルへの差分 例えば 6（サイクル0） から 19（サイクル1） への差分
right = function(n) 8 * n + 15 # 右のサイクルへの差分 例えば 8（サイクル0） から 23（サイクル1） への差分

f = function(N) {
    n = 0 # どのサイクルにあるか検出s
    repeat { # サイクルは (1-8), (9-24), (25-48), ... をサイクル 0, 1, 2, ... とする
        if (N >= ru(n) && ru(n + 1) > N) {
            break
        }
        n = n + 1
    }
    RU = ru(n) # サイクルの開始点
    LU = lu(n) # サイクルの左折点（左向きから下向きへ）
    LD = ld(n) # サイクルの左折点（下向きから右向きへ）
    RD = rd(n) # サイクルの左折点（右向きから上向きへ）
    a = if (N == 1) {                                    # N = 1 は特別
        N + c(up(-1), left(-1), down(-1), right(-1))     # (2, 4, 6, 8)
    } else if (N == RU) {                                # N = RU = 49
        c(ru(n - 1) + 1, N - 1, N + 1, ru(n + 1) - 1)    # (26, 48, 50, 80)
    } else if (N == RU + 1) {                            # N = RU+1 = 50
        c(N - 1, N + 1, ru(n + 1), ru(n + 1) + 2)        # (49, 51, 81, 83)
    } else if (N > RU + 1 && LU - 1 > N) {               # N = 51 thru 55
        c(N - up(n - 1), N - 1, N + 1, N + up(n))        # N = 51; (26, 50, 52, 84)
    } else if (N == LU - 1) {                            # N = 56
        c(lu(n - 1), N - 1, N + 1, lu(n + 1) - 2)        # (31, 55, 57, 89)
    } else if (N == LU) {                                # N = LU = 57
        c(N - 1, N + 1, lu(n + 1) - 1, lu(n + 1) + 1)    # (56, 58, 90, 92)
    } else if (N > LU && LD > N) {                       # N = 58 thru 64
        c(N - left(n - 1), N - 1, N + 1, N + left(n))    # N = 58; (31, 57, 59, 93)
    } else if (N == LD) {                                # N = 65
        c(N - 1, N + 1, ld(n + 1) - 1, ld(n + 1) + 1)    # (64, 66, 100, 102)
    } else if (N > LD && RD > N) {                       # N = 66 thru 72
        c(N - down(n - 1), N - 1, N + 1, N + down(n))    # N = 66; (37, 65, 67, 103)
    } else if (N == RD) {                                # N = 73
        c(N - 1, N + 1, rd(n + 1) - 1, rd(n + 1) + 1)    # (72, 74, 110, 112)
    } else if (N > RD && ru(n + 1) > N) {                # N = 74 thru 81
        c(N - right(n - 1), N - 1, N + 1, N + right(n))  # n = 74; (43,73,75,113)
    }
    cat(a, sep = ",")
}

> f(1)
2,4,6,8
> f(2)
1,3,9,11
> f(3)
2,4,12,14
> f(4)
1,3,5,15
> f(5)
4,6,16,18
> f(6)
1,5,7,19
> f(7)
6,8,20,22
> f(8)
1,7,9,23
> f(9)
2,8,10,24
> f(10)
9,11,25,27
> f(100000)
98739,99999,100001,101269

ダブルテトロミノ

ダブルテトロミノ

締め切りが 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