Julia によるプログラムを追加 2021/09/25
パズルゲーム「2048」の組み合わせは何通り？
締め切りが 2017/09/26 10:00 AM なので，その 1 分後に投稿されるように予約
設問
2048というパズルゲームがあります。(Wikipedia)
iPhoneやAndroidなどのアプリだけでなく、Web上で楽しむこともできます。
実際の動かし方は試してみるとよくわかるのですが、ここでは動かし方は問いませんので、以下の遊び方は理解しなくても問題ありません。
以下、Wikipediaによる「遊び方」からの抜粋です。
4×4のマスに数字が書かれたタイルがあり、スライドさせるとそれらはマスの端まで移動し、同時に新たなタイルが出現する。
同じ数字のタイルがぶつかると2+2=4、4+4=8というように数字が足し合わされていく。
最終的に2048のタイルができればゲームクリアだが、それ以後も続けることはできる。
また、完全にタイルが動かせない状態になるとゲームオーバーとなる。
ここでは、ゲームオーバーとなった状態、つまり隣同士（各マスの上下左右）に同じ数字が並んでおらず、すべてのマスが埋まった状態だけを考えます。
このときのスコアは、それぞれのマスを作るときに足し合わされた数の和です。
例えば、「4」のマスは「2」と「2」のマスが足しあわされたもの、「8」のマスは「4」と「4」のマスが足しあわされたものですので、「4」のマスを作ると2+2=4点、「8」のマスを作るときは「4」のマスを作り、さらに足し合わせた(2+2)+(2+2)+4+4=16点、「n」のマスを作ると n×(log2n - 1)点です。この点数をすべてのマスについて足し合わせてスコアを求めます。
※iPhoneアプリなどでは最初から「4」のマスが登場する場合があるため、冒頭のスクリーンショットでは合計が一致しませんが、今回は最初にすべて「2」のマスで始まるため、「2」のマスのみ点数に加算されないものとします。（※上記の図の場合、今回の計算方法でのスコアは52536点になります。）
標準入力からスコアが与えられたとき、ゲームオーバーとなった状態が何通りあるかを求め、標準出力に出力してください。
なお、入力されるスコアは500以下の正の整数とします。
例えば、スコアが32のとき、以下の2パターンがありますので、以下のような入出力になります。
【入出力サンプル】
標準入力
32
標準出力
2
=====
n = 400 の場合，R だと 29.445 秒，Java だと 0.814 秒，C ならば 0.878 秒ということであるが，投稿先の処理系では Java は 1 秒以上で，C だと 0.4 秒で制限時間内となった。
難易度は最上位の「★ 4 つ」になっている，プログラム的にはどうということもなく，実行速度の速い言語（処理系）に依存するという結果になった。
● R
f = function(n) {
count = 0
x = c(0, 4, 16, 48, 128, 320)
for (i1 in x) {
if (i1 > n) break
for (i2 in x) {
i1.2 = i1 + i2
if (i1.2 > n) break else if (i1 == i2) next
for (i3 in x) {
i1.3 = i1.2 + i3
if (i1.3 > n) break else if (i2 == i3) next
for (i4 in x) {
i1.4 = i1.3 + i4
if (i1.4 > n) break else if (i3 == i4) next
for (i5 in x) {
i1.5 = i1.4 + i5
if (i1.5 > n) break else if (i1 == i5) next
for (i6 in x) {
i1.6 = i1.5 + i6
if (i1.6 > n) break else if (i5 == i6 || i2 == i6) next
for (i7 in x) {
i1.7 = i1.6 + i7
if (i1.7 > n) break else if (i3 == i7 || i6 == i7) next
for (i8 in x) {
i1.8 = i1.7 + i8
if (i1.8 > n) break else if (i4 == i8 || i7 == i8) next
for (i9 in x) {
i1.9 = i1.8 + i9
if (i1.9 > n) break else if (i5 == i9) next
for (i10 in x) {
i1.10 = i1.9 + i10
if (i1.10 > n) break else if (i6 == i10 || i9 == i10) next
for (i11 in x) {
i1.11 = i1.10 + i11
if (i1.11 > n) break else if (i7 == i11 || i10 == i11) next
for (i12 in x) {
i1.12 = i1.11 + i12
if (i1.12 > n) break else if (i8 == i12 || i11 == i12) next
for (i13 in x) {
i1.13 = i1.12 + i13
if (i1.13 > n) break else if (i9 == i13) next
for (i14 in x) {
i1.14 = i1.13 + i14
if (i1.14 > n) break else if (i10 == i14 || i13 == i14) next
for (i15 in x) {
i1.15 = i1.14 + i15
if (i1.15 > n) break else if (i11 == i15 || i14 == i15) next
for (i16 in x) {
i1.16 = i1.15 + i16
if (i1.16 > n) break else if (i12 == i16 || i15 == i16) next
if (i1.16 == n) count = count + 1
}}}}}}}}}}}}}}}}
cat(count)
}
system.time(f(32)) # 2
system.time(f(48)) # 16
system.time(f(56)) # 56
system.time(f(256)) # 311088, 2.318sec.
system.time(f(400)) # 3430350, 28.740sec.
========================================================================================================================
● Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n;
if (false) {
Scanner cin = new Scanner(System.in);
String line;
line = cin.nextLine();
n = Integer.parseInt(line);
} else {
n = 400;
}
long start = System.currentTimeMillis();
f(n);
long end = System.currentTimeMillis();
System.out.println((end - start) + "ms");
}
static void f(int n) {
int count = 0;
int i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i13, i14, i15, i16;
int i1to2, i1to3, i1to4, i1to5, i1to6, i1to7, i1to8, i1to9, i1to10, i1to11, i1to12, i1to13, i1to14, i1to15;
int[] x = { 0, 4, 16, 48, 128, 320 };
for (i1 = 0; i1 < 6; i1++) {
if (x[i1] > n) break;
for (i2 = 0; i2 < 6; i2++) {
i1to2 = x[i1] + x[i2];
if (i1to2 > n) break; else if (i1 == i2) continue;
for (i3 = 0; i3 < 6; i3++) {
i1to3 = i1to2 + x[i3];
if (i1to3 > n) break; else if (i2 == i3) continue;
for (i4 = 0; i4 < 6; i4++) {
i1to4 = i1to3 + x[i4];
if (i1to4 > n) break; else if (i3 == i4) continue;
for (i5 = 0; i5 < 6; i5++) {
i1to5 = i1to4 + x[i5];
if (i1to5 > n) break; else if (i1 == i5) continue;
for (i6 = 0; i6 < 6; i6++) {
i1to6 = i1to5 + x[i6];
if (i1to6 > n) break; else if (i5 == i6 || i2 == i6) continue;
for (i7 = 0; i7 < 6; i7++) {
i1to7 = i1to6 + x[i7];
if (i1to7 > n) break; else if (i3 == i7 || i6 == i7) continue;
for (i8 = 0; i8 < 6; i8++) {
i1to8 = i1to7 + x[i8];
if (i1to8 > n) break; else if (i4 == i8 || i7 == i8) continue;
for (i9 = 0; i9 < 6; i9++) {
i1to9 = i1to8 + x[i9];
if (i1to9 > n) break; else if (i5 == i9) continue;
for (i10 = 0; i10 < 6; i10++) {
i1to10 = i1to9 + x[i10];
if (i1to10 > n) break; else if (i6 == i10 || i9 == i10) continue;
for (i11 = 0; i11 < 6; i11++) {
i1to11 = i1to10 + x[i11];
if (i1to11 > n) break; else if (i7 == i11 || i10 == i11) continue;
for (i12 = 0; i12 < 6; i12++) {
i1to12 = i1to11 + x[i12];
if (i1to12 > n) break; else if (i8 == i12 || i11 == i12) continue;
for (i13 = 0; i13 < 6; i13++) {
i1to13 = i1to12 + x[i13];
if (i1to13 > n) break; else if (i9 == i13) continue;
for (i14 = 0; i14 < 6; i14++) {
i1to14 = i1to13 + x[i14];
if (i1to14 > n) break; else if (i10 == i14 || i13 == i14) continue;
for (i15 = 0; i15 < 6; i15++) {
i1to15 = i1to14 + x[i15];
if (i1to15 > n) break; else if (i11 == i15 || i14 == i15) continue;
for (i16 = 0; i16 < 6; i16++) {
if (i1to15 + x[i16] > n) break; else if (i12 == i16 || i15 == i16) continue;
if (i1to15 + x[i16] == n) count++;
}}}}}}}}}}}}}}}}
System.out.println(count);
}
}
##############
Julia では，R に比べて 40 倍ほど速い
function f(n)
count = 0
x = [0, 4, 16, 48, 128, 320]
for i1 in x
i1 > n && break
for i2 in x
i1_2 = i1 + i2
i1_2 > n && break
i1 == i2 && continue
for i3 in x
i1_3 = i1_2 + i3
i1_3 > n && break
i2 == i3 && continue
for i4 in x
i1_4 = i1_3 + i4
i1_4 > n && break
i3 == i4 && continue
for i5 in x
i1_5 = i1_4 + i5
i1_5 > n && break
i1 == i5 && continue
for i6 in x
i1_6 = i1_5 + i6
i1_6 > n && break
(i5 == i6 || i2 == i6) && continue
for i7 in x
i1_7 = i1_6 + i7
i1_7 > n && break
(i3 == i7 || i6 == i7) && continue
for i8 in x
i1_8 = i1_7 + i8
i1_8 > n && break
(i4 == i8 || i7 == i8) && continue
for i9 in x
i1_9 = i1_8 + i9
i1_9 > n && break
i5 == i9 && continue
for i10 in x
i1_10 = i1_9 + i10
i1_10 > n && break
(i6 == i10 || i9 == i10) && continue
for i11 in x
i1_11 = i1_10 + i11
i1_11 > n && break
(i7 == i11 || i10 == i11) && continue
for i12 in x
i1_12 = i1_11 + i12
i1_12 > n && break
(i8 == i12 || i11 == i12) && continue
for i13 in x
i1_13 = i1_12 + i13
i1_13 > n && break
i9 == i13 && continue
for i14 in x
i1_14 = i1_13 + i14
i1_14 > n && break
(i10 == i14 || i13 == i14) && continue
for i15 in x
i1_15 = i1_14 + i15
i1_15 > n && break
(i11 == i15 || i14 == i15) && continue
for i16 in x
i1_16 = i1_15 + i16
i1_16 > n && break
(i12 == i16 || i15 == i16) && continue
i1_16 == n && (count += 1)
end
end
end
end
end
end
end
end
end
end
end
end
end
end
end
end
println(count)
end
