Wprowadzenie

Jest poborca ​​podatkowy, który ma pewne problemy z zarządzaniem podatkami swojego królestwa: zapisy historyczne spłonęły w wielkim pożarze.

Chce dowiedzieć się, ile może istnieć przeszłości, jeśli chodzi o to, skąd odziedziczyły obecne pieniądze. Na szczęście jego królestwo jest bardzo proste.

Królestwo można modelować za pomocą macierzy boolowskiej 2D, w której lreprezentuje ktoś, kto odziedziczył pieniądze, i Oreprezentuje kogoś, kto tego nie zrobił. Na przykład:

l O l l

O O O l

l O l O

O O O l

(Zawsze będzie to prostokąt)

W następnym pokoleniu królestwo jest mniejsze (wilki są silne!).

Następna generacja wyglądałaby tak, nałożona na poprzednią generację ( xjest symbolem zastępczym dla potomka w następnej generacji)

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

Potomek będzie patrzeć na przodków, które są bezpośrednio wokół nich (So lewym górnym rogu xbędzie zobaczyć { l, O, O, O}, zwany aligné prostokątne sąsiedztwo )

Jeśli tylko jeden przodek odziedziczył pieniądze, potomek odziedziczy je od nich. Jeśli więcej niż jeden przodek odziedziczy pieniądze, będą się kłócić, a potomek nie odziedziczy pieniędzy. Jeśli nikt nie odziedziczył pieniędzy, potomek nie odziedziczy żadnych pieniędzy.

(Więcej niż jeden potomek może odziedziczyć po jednym przodku)

Tak więc następna generacja wyglądałaby następująco:

​
 l l O

 l l O

 l l O
​

Wyzwanie

Wejście

Obecny stan generacji, jako tablica tablic o dowolnych dwóch odrębnych wartościach, przy czym tablice wewnętrzne mają tę samą długość.

Na przykład w powyższym przykładzie może to być:

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

Wynik

Liczba całkowita reprezentująca liczbę unikalnych poprzednich generacji, przy czym wejście nowej generacji jest wejściem.

Możesz założyć, że odpowiedź będzie zawsze mniejsza niż 2 ^ 30 - 1. (lub 1073741823).

Poprzednia generacja nazywa się „preimage”, a tym wyzwaniem byłoby policzyć preimage .

Punktacja

To jest najszybszy kod wyzwanie, więc każde zgłoszenie zostanie przetestowane na moim komputerze, a zgłoszenie, które zajmie najmniej czasu, będzie zwycięzcą.

Przykład wejścia i wyjścia

(Gdzie 1jest potomek, który odziedziczył pieniądze i 0jest potomkiem, który nie odziedziczył pieniędzy)

Wejście:

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

Wynik:

4

Wejście:

[[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]]

Wynik:

254

Wejście:

[[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]]

Wynik:

11567

C ++ przy użyciu biblioteki BuDDy

Wydawało się, że to dobra wymówka do gry z binarnymi diagramami decyzyjnymi . Królestwo przekształca się w wielką formułę logiczną, w której musimy policzyć liczbę sposobów, w jakie można go spełnić. Można to (czasem) zrobić bardziej efektywnie, niż się wydaje.

Królestwo należy podać jako stałą programu jako płaską tablicę i wyraźnie podane wymiary. (Ładne wejście pozostało jako wykonanie dla czytelnika :-)

Oto zawstydzająco prosty kod:

#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();
}

Aby skompilować z debianem 8 (jessie), zainstaluj libbdd-devi wykonaj g++ -std=c++11 -o hist hist.cpp -lbdd. (Optymalizacja opcji nie robi prawie żadnej różnicy, ponieważ prawdziwa praca jest wykonywana w bibliotece).

Wielkie przykłady mogą prowadzić do komunikatów na temat wyrzucania elementów bezużytecznych. Można je stłumić, ale wolę je widzieć.

bdd_satcountzwraca a double, ale jest to wystarczająco dobre dla oczekiwanego zakresu wyników. Ta sama technika liczenia jest możliwa przy dokładnych (dużych) liczbach całkowitych.

Kod jest zoptymalizowany dla ROWS<COLS. Jeśli masz dużo więcej wierszy niż kolumn, dobrym pomysłem może być transpozycja macierzy.

Python 2.7

To tylko naiwna pierwsza próba. Nie jest to szczególnie szybkie, ale jest poprawne.

Pierwszą obserwacją jest to, że każda komórka jest zależna od dokładnie czterech komórek w poprzedniej generacji. Możemy przedstawić te cztery komórki jako liczbę 4-bitową (0–15). Zgodnie z regułami, jeśli dokładnie jedna sąsiednia komórka w poprzedniej generacji jest 1, to dana komórka w bieżącej generacji będzie 1, w przeciwnym razie będzie 0. Ci odpowiadają potęgi dwójki, a mianowicie [1, 2, 4, 8]. Gdy czterech przodków jest reprezentowanych jako liczba 4-bitowa, każda inna liczba spowoduje 0w bieżącej generacji. Dzięki tym informacjom, po zobaczeniu komórki w bieżącym pokoleniu, możemy zawęzić możliwości sąsiedztwa w poprzednim pokoleniu odpowiednio do jednej z czterech lub jednej z dwunastu możliwości.

Wybrałem reprezentowanie okolicy w następujący sposób:

32
10

gdzie 0 jest najmniej znaczącym bitem i tak dalej.

Drugą obserwacją jest to, że w przypadku dwóch sąsiednich komórek w bieżącym pokoleniu dwie dzielnice poprzedniej generacji pokrywają się:

32  32
10  10

lub:

32
10

32
10

W przypadku poziomym 2lewe sąsiedztwo zachodzi 3na prawe sąsiedztwo i podobnie z 0lewym i 1prawym. W przypadku pionowym 1górne sąsiedztwo pokrywa się 3z dolnym sąsiedztwem i podobnie z 0górnym i 2dolnym.

To nakładanie się oznacza, że ​​możemy zawęzić możliwości dla jeszcze nie wybranych dzielnic w oparciu o to, co już wybraliśmy. Kod działa w sposób od lewej do prawej, od góry do dołu, w rekurencyjnym poszukiwaniu głębokości w poszukiwaniu możliwych obrazów. Poniższy diagram wskazuje, które poprzednie sąsiedztwa musimy wziąć pod uwagę, patrząc na możliwe sąsiedztwa bieżącej komórki:

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]

Oto kod:

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]])

Aby uruchomić:

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)