Historyk podatków

9

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 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
Artyer
źródło
6
„LOOLLOOOOLLlololoLOLOLOOLOLOLOLL” to wszystko, co zobaczyłem, kiedy po raz pierwszy otworzyłem stronę.
Magic Octopus Urn

Odpowiedzi:

4

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.

Christian Sievers
źródło
2,39 sekundy. To połowa czasu, jaki miałem! Oznaczenie tego jako zaakceptowane.
Artyer
1
@Artyer: Czy chciałbyś opublikować swój najdłużej ukryty przypadek testowy? Jak również swoje rozwiązanie, jeśli chcesz.
Andrew Epstein,
@AndrewEpstein Niedawno miałem awarię dysku twardego i zgubiłem zarówno kod, jak i oryginalne przypadki testowe (były ich setki, a ich maksymalna szerokość to 300, chyba 10-wysoka). Przepraszam.
Artyer
3

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)
Andrew Epstein
źródło
1
Wykonanie ukrytych przypadków testowych zajmuje dużo czasu, więc nie oceniam tego zgłoszenia. Wypróbuj inny algorytm, ponieważ jest on zbyt skomplikowany czasowo ( O(<something>^n)tak myślę.)
Artyer