pengantar

Ada seorang pemungut pajak yang mengalami kesulitan mengelola pajak kerajaannya: catatan sejarah telah terbakar dalam api besar.

Dia ingin mencari tahu berapa banyak masa lalu yang mungkin ada dalam hal di mana uang saat ini diwarisi dari. Untungnya, kerajaannya sangat sederhana.

Kerajaan dapat dimodelkan dengan matriks boolean 2D, di mana lmewakili seseorang yang telah mewarisi uang, dan Omewakili seseorang yang belum. Sebagai contoh:

l O l l

O O O l

l O l O

O O O l

(Ini akan selalu menjadi persegi panjang)

Pada generasi berikutnya, kerajaan lebih kecil (Serigala kuat!).

Generasi berikutnya akan terlihat seperti ini, ditumpangkan pada generasi sebelumnya ( xadalah pengganti bagi keturunan di generasi berikutnya)

l O l l
 x x x
O O O l
 x x x
l O l O
 x x x
O O O l

Sebuah keturunan akan melihat nenek moyang yang secara langsung di sekitar mereka (Jadi atas meninggalkan xakan melihat { l, O, O, O}, disebut lingkungan persegi panjang unaligned )

Jika hanya satu leluhur yang mewarisi uang, keturunan akan mewarisi uang dari mereka. Jika lebih dari satu leluhur memiliki uang warisan, mereka akan bertengkar dan keturunannya tidak akan mewarisi uang. Jika tidak ada yang mewarisi uang, keturunannya tidak akan mewarisi uang.

(Lebih dari satu keturunan dapat mewarisi dari satu leluhur)

Jadi, generasi berikutnya akan terlihat seperti:

​
 l l O

 l l O

 l l O
​

Tantangan

Memasukkan

Keadaan saat ini dari generasi, sebagai array array dari dua nilai berbeda, di mana array dalam semua memiliki panjang yang sama.

Misalnya, untuk contoh di atas, bisa jadi:

[
  [True, True, False],
  [True, True, False],
  [True, True, False]
]

Keluaran

Integer mewakili jumlah generasi unik sebelumnya di mana generasi berikutnya adalah input.

Anda dapat mengasumsikan bahwa jawabannya akan selalu kurang dari 2 ^ 30 - 1. (atau 1073741823).

Generasi sebelumnya akan disebut "preimage" dan tantangan ini adalah menghitung preimage .

Mencetak gol

Ini adalah tantangan kode tercepat , sehingga setiap pengiriman akan diuji di komputer saya, dan pengiriman yang membutuhkan waktu paling sedikit akan menjadi pemenang.

Contoh Input dan Output

(Di mana 1keturunan yang mewarisi uang, dan 0merupakan keturunan yang tidak mewarisi uang)

Memasukkan:

[[1, 0, 1],
 [0, 1, 0],
 [1, 0, 1]]

Keluaran:

4

Memasukkan:

[[1, 0, 1, 0, 0, 1, 1, 1],
 [1, 0, 1, 0, 0, 0, 1, 0],
 [1, 1, 1, 0, 0, 0, 1, 0],
 [1, 0, 1, 0, 0, 0, 1, 0],
 [1, 0, 1, 0, 0, 1, 1, 1]]

Keluaran:

254

Memasukkan:

[[1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
 [1, 1, 0, 0, 0, 0, 1, 1, 1, 0],
 [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
 [0, 1, 0, 0, 0, 0, 1, 1, 0, 0]]

Keluaran:

11567

C ++ menggunakan perpustakaan BuDDy

Ini sepertinya alasan yang bagus untuk bermain dengan diagram keputusan biner . Kerajaan diubah menjadi formula boolean besar di mana kita harus menghitung jumlah cara yang bisa dipenuhi. Itu bisa (kadang-kadang) dilakukan lebih efisien daripada yang terdengar.

Kerajaan harus diberikan sebagai program konstan sebagai array datar dan dimensi yang diberikan secara eksplisit. (Masukan bagus dibiarkan sebagai eksekusi untuk pembaca :-)

Berikut adalah kode sederhana yang memalukan:

#include <iostream>
#include <bdd.h>

// describe the kingdom here:

constexpr int ROWS = 4;
constexpr int COLS = 10;

constexpr int a[] = {
   1, 1, 0, 1, 0, 1, 0, 1, 1, 0,
   1, 1, 0, 0, 0, 0, 1, 1, 1, 0,
   1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
   0, 1, 0, 0, 0, 0, 1, 1, 0, 0,
};

// end of description

// check dimensions
static_assert(ROWS*COLS*sizeof(int)==sizeof(a),
          "ROWS*COLS must be the number of entries of a");

// dimensions of previous generation
constexpr int R1 = ROWS+1;
constexpr int C1 = COLS+1;

// condition that exactly one is true
bdd one(bdd a, bdd b, bdd c, bdd d){
  bdd q = a & !b & !c & !d;
  q |= !a & b & !c & !d;
  q |= !a & !b & c & !d;
  q |= !a & !b & !c & d;
  return q;
}

int main()
{
  bdd_init(1000000, 10000); // tuneable, but not too important
  bdd_setvarnum(R1*C1);
  bdd q { bddtrue };
  for(int j=COLS-1; j>=0; j--) // handle high vars first
    for (int i=ROWS-1; i>=0; i--){
      int x=i+R1*j;
      bdd p=one(bdd_ithvar(x), bdd_ithvar(x+1),
                bdd_ithvar(x+R1), bdd_ithvar(x+R1+1));
      if (!a[COLS*i+j])
        p = !p;
      q &= p;
    }
  std::cout << "There are " << bdd_satcount(q) << " preimages\n";
  bdd_done();
}

Untuk mengkompilasi dengan debian 8 (jessie), instal libbdd-devdan lakukan g++ -std=c++11 -o hist hist.cpp -lbdd. (Opsi pengoptimalan hampir tidak membuat perbedaan karena pekerjaan nyata dilakukan di perpustakaan.)

Contoh besar dapat menyebabkan pesan tentang pengumpulan sampah. Mereka bisa ditekan, tetapi saya lebih suka melihat mereka.

bdd_satcountmengembalikan a double, tapi itu cukup baik untuk rentang hasil yang diharapkan. Teknik penghitungan yang sama dimungkinkan dengan bilangan bulat (besar) yang tepat.

Kode dioptimalkan untuk ROWS<COLS. Jika Anda memiliki lebih banyak baris daripada kolom, mungkin ide yang baik untuk memindahkan matriks.

Python 2.7

Ini hanya upaya pertama yang naif. Ini tidak terlalu cepat, tetapi itu benar.

Pengamatan pertama adalah bahwa setiap sel bergantung pada empat sel pada generasi sebelumnya. Kita dapat mewakili keempat sel itu sebagai angka 4-bit (0-15). Menurut aturan, jika persis satu sel tetangga pada generasi sebelumnya 1, maka sel yang diberikan pada generasi saat ini adalah 1, jika tidak, itu akan menjadi 0. Itu sesuai dengan kekuatan dua, yaitu [1, 2, 4, 8],. Ketika keempat leluhur diwakili sebagai angka 4-bit, angka lainnya akan menghasilkan dalam 0generasi saat ini. Dengan informasi ini, setelah melihat sel dalam generasi saat ini, kita dapat mempersempit kemungkinan lingkungan pada generasi sebelumnya menjadi satu dari empat atau satu dari dua belas kemungkinan masing-masing.

Saya memilih untuk mewakili lingkungan sebagai berikut:

32
10

di mana 0 adalah bit paling tidak signifikan, dan seterusnya.

Pengamatan kedua adalah bahwa untuk dua sel yang berdekatan pada generasi saat ini, dua lingkungan dari generasi sebelumnya tumpang tindih:

32  32
10  10

atau:

32
10

32
10

Dalam kasus horizontal, dari 2dari lingkungan kiri tumpang tindih dengan dari 3dari lingkungan kanan, dan juga dengan 0di kiri dan 1di kanan. Dalam kasus vertikal, 1dari lingkungan atas tumpang tindih dengan 3dari lingkungan bawah, dan juga dengan 0di atas dan 2di bawah.

Tumpang tindih ini berarti bahwa kita dapat mempersempit kemungkinan untuk lingkungan yang belum dipilih berdasarkan apa yang telah kita pilih. Kode berfungsi dengan cara dari kiri ke kanan, atas ke bawah, dalam pencarian mendalam-pertama secara rekursif untuk kemungkinan preimage. Diagram berikut menunjukkan lingkungan mana yang sebelumnya harus kita pertimbangkan ketika melihat lingkungan yang mungkin dari sel saat ini:

f = free choice
h = only have to look at the neighborhood to the left
v = only have to look at the neighborhood to the top
b = have to look at both left and top neighborhoods

[f, h, h, h, h],
[v, b, b, b, b],
[v, b, b, b, b],
[v, b, b, b, b]

Berikut kodenya:

def good_horizontal(left, right):
    if (left & 4) >> 2 != (right & 8) >> 3:
        return False
    if left & 1 != (right & 2) >> 1:
        return False
    return True


def good_vertical(bottom, top):
    if (bottom & 8) >> 3 != (top & 2) >> 1:
        return False
    if (bottom & 4) >> 2 != (top & 1):
        return False
    return True


ones = [1, 2, 4, 8]
zeros = [0, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]
h = {}
v = {}

for i in range(16):
    h[i] = [j for j in range(16) if good_horizontal(i, j)]
    v[i] = [j for j in range(16) if good_vertical(i, j)]


def solve(arr):
    height = len(arr)
    width = len(arr[0])

    if height == 1 and width == 1:
        if arr[0][0] == 1:
            return 4
        else:
            return 12
    return solve_helper(arr)


def solve_helper(arr, i=0, j=0, partial=None):
    height = len(arr)
    width = len(arr[0])

    if arr[i][j] == 1:
        poss = ones
    else:
        poss = zeros

    if i == height - 1 and j == width - 1:  # We made it to the end of this chain
        if height == 1:
            return sum([1 for p in poss if p in h[partial[-1][-1]]])
        else:
            return sum([1 for p in poss if partial[-2][-1] in v[p] and p in h[partial[-1][-1]]])

    if j == width - 1:
        new_i, new_j = i + 1, 0
    else:
        new_i, new_j = i, j + 1

    if i == 0:
        if j == 0:
            # first call
            return sum([solve_helper(arr, new_i, new_j, [[p]]) for p in poss])
        # still in the first row
        return sum([solve_helper(arr, new_i, new_j, [partial[0] + [p]]) for p in poss if p in h[partial[0][-1]]])
    if j == 0:  # starting a new row
        return sum([solve_helper(arr, new_i, new_j, [r for r in partial + [[p]]]) for p in poss if partial[i - 1][0] in v[p]])
    return sum([solve_helper(arr, new_i, new_j, [r for r in partial[:-1] + ([partial[-1] + [p]])]) for p in poss if p in h[partial[i][-1]] and partial[i - 1][j] in v[p]])

Untuk menjalankannya:

test3 = [
    [1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 1, 1, 0, 0]
]

expected3 = 11567

assert(solve(test3) == expected3)