10 を作る（その 2）

「10 を作る」の発展版 1158 で10 を 作れと... あんたは，ほんとに，「いい娘や」ねえ

とはいえ，汎用のプログラムを書く気にはならないので，少しだけ変更・追加

Expr = c("n1 %s (n2 %s (n3 %s n4))",
         "(n1 %s n2) %s (n3 %s n4)",
         "((n1 %s n2) %s n3) %s n4",
         "(n1 %s (n2 %s n3)) %s n4",
         "n1 %s ((n2 %s n3) %s n4)")
Op = c("+", "-", "*", "/")
Num = c(1, 1, 5, 8)
Eval = function(Expr) {
  for (i in Op) {
    for (j in Op) {
      for (k in Op) {
        s = sprintf(Expr, i, j, k)
        a = eval(parse(text=s))
        if (!is.na(a) && a == 10) {
          cat(s, "\n")
        }
      }
    }
  }
}
library(e1071)
n = permutations(4)
for (i in 1:24) {
  Expr2 = gsub("n1", Num[n[i, 1]], Expr)
  Expr2 = gsub("n2", Num[n[i, 2]], Expr2)
  Expr2 = gsub("n3", Num[n[i, 3]], Expr2)
  Expr2 = gsub("n4", Num[n[i, 4]], Expr2)
  for (expr in Expr2) {
    Eval(expr)
  }
}

ダブルで出てくるが，解答は

8 / (1 - (1 / 5))

乱数の実装を問題にする？

C# で 0 から 9 の数字が入っている配列をシャッフルするコードを書いてください。 配列のサイズは 10 で全て異なる数値です。0 から 9 が順番に入っている配列になります。 ただし、配列のシャッフルではそれぞれの数値が出力される確率に偏りがあってはいけません。
正しい実装では今回の場合、１万回～10万回ほど実行してもそれぞれの数値が0番目の位置に現れる確率はいずれも10%に近くなります。

然るべき乱数発生エンジンを使えば良いだけ。そのようなものが使えないシステムは使うべきではない。ちなみに，例題の結果として示されているのは，たまたまなので，けっこうばらつきのある結果も出るもんだよ。R だと，以下のようになるね。

> a = sample(0:9, 1e6, replace=TRUE)
> table(a)/1e6　* 100
a
       0       1       2       3       4       5       6       7       8       9
  9.9577 10.0018 10.0432 10.0209  9.9628 10.0059  9.9601 10.0122 10.0420  9.9934

モールス符号

小学校5，6年のとき，担任の先生にモールス信号の覚え方を教わった。「イ」は「伊藤」，「ロ」は「路上歩行」，「ハ」は「ハーモニカ」など。それ以外は数字とSOSは覚えている。

灯火信号と言えば，まずはモールス信号だろう。

モールス信号の「ツー」を 1，「トン」を 0 として，1 文字を 1 文字列で表す。
モールス信号をカタカナの文字列に変換する関数 mk と，その逆関数 km を作る（簡単なんだけどね）。

実用にするには，モールス信号を感知して 0/1 文字列に直して，mk 関数に放り込んだり，カタカナ文字列を入力して，灯火信号を発するようなシステムを繋げばよいのだが。

# モールス符号（カタカナ，数字）
m = c(
"01", "0101", "1000", "1010", "100", "0", "00100",
"0010", "110", "0000", "10110", "0111",
"101", "0100", "11", "10", "111", "1110",
"0110", "1101", "010", "000", "1",
"001", "01001", "0011", "01000", "0001", "011", "1001",
"1011", "1100", "1111", "10111", "01011",
"11011", "10101", "10100", "10011", "10001", "00101", "11010",
"01100", "11001", "10010", "01110", "11101","01010",
"00", "00110", "01101", "010101", "010100",
"01111", "00111", "00011", "00001", "00000",
"10000", "11000", "11100", "11110", "11111")
# カタカナ，数字
k = c(
"イ", "ロ", "ハ", "ニ", "ホ", "ヘ", "ト",
"チ", "リ", "ヌ", "ル", "ヲ",
"ワ", "カ", "ヨ", "タ", "レ", "ソ",
"ツ", "ネ", "ナ", "ラ", "ム",
"ウ", "ヰ", "ノ", "オ", "ク", "ヤ", "マ",
"ケ", "フ", "コ", "エ", "テ",
"ア", "サ", "キ", "ユ", "メ", "ミ", "シ",
"ヱ", "ヒ", "モ", "セ", "ス", "ン",
"゛", "゜", "ー", "、", "。",
"1", "2", "3", "4", "5", "6", "7", "8", "9", "0")
# カタカナ，数字　→　モールス符号
km = function(str) {
    m[sapply(unlist(strsplit(str, "")), grep, k)]
}
# モールス符号　→　カタカナ，数字
mk = function(str) {
    paste(k[sapply(str, function(s) grep(sprintf("^%s$", s), m))], collapse="")
}
# 実行例
reibun = c("1111", "01010", "011", "0100", "111", "01101", "000", "01",
"11101", "11101", "0001", "00", "0100", "10111", "111")
mk(reibun)
km(mk(reibun))

> mk(reibun)
[1] "コンヤカレーライススク゛カエレ"
> km(mk(reibun))
 [1] "1111"  "01010" "011"   "0100"  "111"   "01101" "000"   "01"    "11101"
     "11101" "0001"  "00"    "0100"  "10111" "111"  

圧力が不正を生む？

東大論文不正:３３本に不正 規範委が最終報告、教員ら１１人関与

群馬大の附属病院 来月にも立ち入り検査

衆院選で集計ミス隠蔽、仙台 ９７６票水増し処理

ＳＴＡＰ細胞なし確実 理研は幕引き図る

不正論文に関与、元特任講師の学位取り消し 徳島大

 

なんか，変な方向へ行ってるね（^_^）

クラウディアさんが鏡餅をご希望だぞ

勇者よ、きゃんちを仲間にするのじゃ！

池澤あやかとクリスマスコーディング！

林檎と城下の物語～１６進数編～

続！4ナンバー美女からの挑戦状

FizzBuzzっぽく愛の告白をして

天地創造 - 産めよ増えよ地に満ちよ

4ナンバーを愛す美女からの挑戦

そこまで行かなくても，単純な問題の記述をわざわざラノベ風にするとか

品がない

いかにも男性嗜好なようで，「女性は対象外」とでも言っているのだろうか

これとは別の問題だろうが，掲載から2，3日で，締め切りを待たずに削除された（IT との関連は薄そうな）問題もあったが

ちゃんとした IT 技術者を募集するなら，ちゃんとした様式・内容で募集する方がよいと思うけど...

簡単な数列の問題

1，1，2，3，5，?

? の所にくる数値は？

解答は，この記事のコメントを参照

でかい数の階乗の末尾の 0

1000000! の末尾に連続する 0 はいくつあるか

答え 249998

プログラム例は，この記事のコメントを参照

数独（ナンプレ）

R の数独ライブラリはすごい。

ブルートフォースで解くプログラムを書いてみたが，うまくいくときはまあまあだが，同じ問題でも，転置行列を入力すると数倍遅くなるなんてこともある。

solve = function(arg) {
  if (length(arg) == 1) arg = scan(arg, what = "")
  m = t(sapply(strsplit(arg, ""), function(s) as.integer(gsub("-", "0", unlist(s)))))
  m = array(c(m[1:3, 1:3], m[4:6, 1:3], m[7:9, 1:3],
              m[1:3, 4:6], m[4:6, 4:6], m[7:9, 4:6],
              m[1:3, 7:9], m[4:6, 7:9], m[7:9, 7:9]), dim = rep(3, 4))
  func = function(k, l) {
    a = which(m[, , k, l] != 0, arr.ind = TRUE)
    ok = colSums(t(pos[, (a[, 1] - 1) + (a[, 2] - 1) * 3 + 1, drop = FALSE]) == m[, , k, l][a]) == nrow(a)
    pos2 = pos[ok, ]
    for (j in (1:3)[-l]) {
      a = which(m[, , k, j] != 0, arr.ind = TRUE)
      num = m[, , k, j][a]
      for (i in 1:nrow(a)) {
        for (i2 in 0:2 * 3) {
          pos2 = pos2[pos2[, a[i, 1] + i2, drop = FALSE] != num[i], , drop = FALSE]
        }
      }
    }
    for (j in (1:3)[-k]) {
      a = which(m[, , j, l] != 0, arr.ind = TRUE)
      num = m[, , j, l][a]
      for (i in 1:nrow(a)) {
        for (i2 in 1:3) {
          pos2 = pos2[pos2[, (a[i, 2] - 1) * 3 + i2, drop = FALSE] != num[i], , drop = FALSE]
        }
      }
    }
    pos2
  }
  library(e1071)
  pos = permutations(9)
  pos11 = func(1, 1)
  pos12 = func(1, 2)
  pos13 = func(1, 3)
  pos21 = func(2, 1)
  pos22 = func(2, 2)
  pos23 = func(2, 3)
  pos31 = func(3, 1)
  pos32 = func(3, 2)
  pos33 = func(3, 3)
  a = matrix(0, 9, 9)
  dimnames(a) = list(letters[1:9], letters[1:9])
  notUnique = function(a, sw, n) any(apply(a, sw, function(x) length(unique(x)) != n))
  for (i11 in 1:nrow(pos11)) {
    a[1:3, 1:3] = pos11[i11, ]
    for (i12 in 1:nrow(pos12)) {
      a[1:3, 4:6] = pos12[i12, ]
      if (notUnique(a[1:3, 1:6], 1, 6)) next
      for (i13 in 1:nrow(pos13)) {
        a[1:3, 7:9] = pos13[i13, ]
        if (notUnique(a[1:3, ], 1, 9)) next
        for (i21 in 1:nrow(pos21)) {
          a[4:6, 1:3] = pos21[i21, ]
          if (notUnique(a[1:6, 1:3], 2, 6)) next
          for (i22 in 1:nrow(pos22)) {
            a[4:6, 4:6] = pos22[i22, ]
            if (notUnique(a[4:6, 1:6], 1, 6) || notUnique(a[1:6, 4:6], 2, 6)) next
            for (i23 in 1:nrow(pos23)) {
              a[4:6, 7:9] = pos23[i23, ]
              if (notUnique(a[4:6, ], 1, 9) || notUnique(a[1:6, 7:9], 2, 6)) next
              for (i31 in 1:nrow(pos31)) {
                a[7:9, 1:3] = pos31[i31, ]
                if (notUnique(a[, 1:3], 2, 9)) next
                for (i32 in 1:nrow(pos32)) {
                  a[7:9, 4:6] = pos32[i32, ]
                  if (notUnique(a[7:9, 1:6], 1, 6) || notUnique(a[, 4:6], 2, 9)) next
                  for (i33 in 1:nrow(pos33)) {
                    a[7:9, 7:9] = pos33[i33, ]
                    if (notUnique(a[7:9, ], 1, 9) || notUnique(a[, 7:9], 2, 9)) next
                    return(a)
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}
solve(system.file("puz1.txt",package="sudoku"))
solve(c("--9----6-",
        "1---3---7",
        "-6---93--",
        "--3----4-",
        "7---1---8",
        "-4----2--",
        "--74---1-",
        "2---8---5",
        "-8----9--"))

10 を作る

9 を 4 個使って，+, -, *, / の演算子を適当に使って，かっこも適当に使って演算結果を 10 にせよ。

全ての数を対象にしないので，以下のように適当にプログラムすればよい。
余計な括弧もあるけど，間違いじゃないし。
実行時間は 0.050 秒なので最適化する必要もない。

Expr = c("9%s(9%s(9%s9))",
         "(9%s9)%s(9%s9)",
         "((9%s9)%s9)%s9",
         "(9%s(9%s9))%s9",
         "9%s((9%s9)%s9)")
Op = c("+", "-", "*", "/")
Eval = function(Expr) {
  for (i in Op) {
    for (j in Op) {
      for (k in Op) {
        s = sprintf(Expr, i, j, k)
        a = eval(parse(text=s))
        if (!is.na(a) && a == 10) {
          cat(s, "\n")
        }
      }
    }
  }
}
for (expr in Expr) {
  Eval(expr)
}

((9*9)+9)/9
(9+(9*9))/9

ナンプレ

簡単なクイズを解けと。

・2x2 のマス（Box）が縦横ふたつずつ並んだ 4x4 のマスがある
・それぞれのマスには 1~4 の数字が入り、それらは行・列の 4 つのマスに同じ数字がくることはない（行・列の合計は 10 となる）
・2x2 のマス（Box）にも同じ数字がくることはなく、合計は 10 となる
・最初に 1~4 の数字がランダムにひとつずつ設定されている（同じ行・列・Boxに複数の数字が設定されることは無い）

初期状態は csv ファイルで与えられる

sample1.csv

1,0,0,0
0,0,3,0
0,0,0,4
0,2,0,0

sample2.csv

0,0,0,4
0,2,0,0
0,0,3,0
1,0,0,0

解

solve = function(file.name) {
  m = read.csv(file.name, header=FALSE)
  dimnames(m) = list(1:4, 1:4)
  cat("init\n")
  print(m)
  func = function(i, j) {
    a = which(m[i, j] != 0, arr.ind=TRUE)
    pos[pos[, (a[1]-1)+(a[2]-1)*2+1] == m[i,j][a],]
  }
  library(e1071)
  pos = permutations(4)
  pos1 = func(1:2, 1:2)
  pos2 = func(1:2, 3:4)
  pos3 = func(3:4, 1:2)
  pos4 = func(3:4, 3:4)
  for (i1 in 1:6) {
    a1 = matrix(pos1[i1,], 2)
    for (i2 in 1:6) {
      a2 = matrix(pos2[i2,], 2)
      for (i3 in 1:6) {
        a3 = matrix(pos3[i3,], 2)
        for (i4 in 1:6) {
          a4 = matrix(pos4[i4,], 2)
          a = rbind(cbind(a1, a2), cbind(a3, a4))
          if (all(c(apply(a, 1, function(x) length(table(x)) == 4),
                    apply(a, 2, function(x) length(table(x)) == 4)))) {
            dimnames(a) = list(1:4, 1:4)
            cat("ans\n")
            print(a)
          }
        }
      }
    }
  }
}
solve("sample1.csv")
solve("sample2.csv")

2 問についての所要時間は合計 3.245 秒。
まあまあか？

実行結果

init
  1 2 3 4
1 1 0 0 0
2 0 0 3 0
3 0 0 0 4
4 0 2 0 0

ans
  1 2 3 4
1 1 3 4 2
2 2 4 3 1
3 3 1 2 4
4 4 2 1 3

init
  1 2 3 4
1 0 0 0 4
2 0 2 0 0
3 0 0 3 0
4 1 0 0 0

ans
  1 2 3 4
1 3 1 2 4
2 4 2 1 3
3 2 4 3 1
4 1 3 4 2

約数の個数

指数表記を使わずに整数を素因数分解する。たとえば，72 = 2*2*2*3*3 のように表現する。このときに使う乗算記号 "*" の数は 4 つ。
4 桁の数の「各桁の和」が「素因数分解した "*" の数」と等しくなるものを列挙せよ。

基本的には，約数の個数を求めること（乗算記号の数は約数の数から 1 をひいたもの）。

以下のプログラムの実行時間は 0.542 秒

prime = c(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
               71,73,79,83,89,97)
func = function(n) {
  Sum = sum(as.integer(unlist(strsplit(as.character(n), ""))))
  Count = 0
  for (j in prime) { # 97 までの素数を調べれば十分
    repeat {
      if (n == 1 || n %% j) break
      Count = Count+1
      n = n %/% j
    }
  }
  if (n != 1) Count = Count+1
  return(Sum == Count-1)
}

for (i in 1000:9999) {
  if (func(i)) print(i)
}

gmp を使って無精をすれば以下のように簡単に書ける。この実行時間は 0.300 秒

library(gmp)
for (i in 1000:9999) {
  Count = length(as.character(factorize(i)))-1
  Sum = sum(as.integer(unlist(strsplit(as.character(i), ""))))
  if (Count == Sum) print(i)
}

答：以下の 13 個の整数

[1] 1001
[1] 1010
[1] 1040
[1] 1110
[1] 1300
[1] 1400
[1] 1600
[1] 2010
[1] 2304
[1] 3100
[1] 3120
[1] 4200
[1] 8000

階乗の約数の個数

2!，3!，4!，…，305! をそれぞれ素因数分解したときに，「2 が素因数として出てくる個数」と「2 ではない素数が素因数として出てくる個数の和」が一致するものがいくつあるか

たとえば，7! を考える場合，2, 3, 4, 5, 6, 7 それぞれの数について，2 とそれ以外の約数が何個ずつあるか数える。7! の約数はそれを全部合計すればよい。 8! の約数は，7! の約数に 8 の約数を加える。以下順に。

prime = c(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,
157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,
241,251,257,263,269,271,277,281,283,293)
twos = others = numeric(305)
for (i in 2:305) {
  n = i
  t = 0 # 約数 2 の個数
  repeat {
    if (n %% 2) break
    t = t+1
    n = n %/% 2
  }
  twos[i] = t
  for (j in prime) {
    if (n == 1) break
    o = 0 # 2 以外の約数の個数
    repeat {
      if (n %% j) break
      o = o+1
      n = n %/% j
      if (n == 1) break
    }
    others[i] = others[i]+o
  }
}
twos = cumsum(twos)[-1]
others = cumsum(others)[-1]
(2:305)[twos == others]

3!,  7!, 11!, 13!, 14!, 18!, 20! の 7 個（くそおもしろくもない。なんで 305 までにしたんだ？）

所要時間は 0.053 秒

gmp を使って手抜きをすれば，以下のように簡単に記述できる。所用時間も 0.259 秒となり，ほどほどだ。

library(gmp)
for (i in 2:305) {
  x = table(as.character(factorize(factorialZ(i))))
  if (sum(x)/2 == x["2"]) print(i)
}

左右対称な素数

1,000,000,000 より小さい最大の素数で，各桁の数が左右対称（10301 など）でなおかつ，その素数の各桁の数値の和（10301 なら 5)

も素数であるような，まさにその素数を求めよ。

回答は，この記事のコメントを参照。

偶数の和

偶数を，以下のようにならべてゆく
 
 1段目    0
 2段目    2    4
 3段目    6    8   10
 4段目   12   14   16   18
 ：

 1e100 段目に並ぶ数の総和はいくつになるか。

答は，この記事のコメントを参照。

パスカルの三角形の n 段目の数の二乗和

n 段目にある数の 2 乗和の桁数を求めよ。

sum(choose(n-1, 0:(n-1))^2) ≡ choose(2*(n-1), n-1)

よって，33 段目ならば，choose(2*(33-1), 33-1) = 1.832624e+18 であるが，「桁数を答えよ」ということなので，答は「19 桁」である。