introduction

Il y a un collecteur d'impôts qui a du mal à gérer les impôts de son royaume: les documents historiques ont brûlé dans un grand incendie.

Il veut savoir combien de passés possibles il pourrait y avoir en termes de provenance de l'argent actuel. Heureusement, son royaume est très simple.

Le royaume peut être modélisé par une matrice booléenne 2D, où lreprésente quelqu'un qui a hérité de l'argent et Oreprésente quelqu'un qui ne l'a pas. Par exemple:

l O l l

O O O l

l O l O

O O O l

(Ce sera toujours un rectangle)

Dans la génération suivante, le royaume est plus petit (les loups sont forts!).

La prochaine génération ressemblerait à ceci, superposée à la génération précédente ( xest un espace réservé pour un descendant de la génération suivante)

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

Descendante se penchera sur les ancêtres qui sont directement autour d' eux (donc en haut à gauche xverra { l, O, O, O}, appelé un quartier rectangulaire Unaligned )

Si un seul ancêtre a hérité de l'argent, le descendant en héritera. Si plus d'un ancêtre a hérité de l'argent, ils se disputeront et le descendant finira par ne pas hériter de l'argent. Si personne n'a hérité d'argent, le descendant n'héritera pas d'argent.

(Plus d'un descendant peut hériter d'un ancêtre)

Ainsi, la prochaine génération ressemblerait à:

​
 l l O

 l l O

 l l O
​

Défi

Contribution

L'état actuel de la génération, sous la forme d'un tableau de tableaux de deux valeurs distinctes, où les tableaux internes sont tous de la même longueur.

Par exemple, pour l'exemple ci-dessus, cela pourrait être:

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

Production

Un entier représentant le nombre de générations précédentes uniques où la génération suivante est l'entrée.

Vous pouvez supposer que la réponse sera toujours inférieure à 2 ^ 30 - 1. (ou 1073741823).

La génération précédente s'appellerait une "préimage" et ce défi serait de compter les préimages .

Notation

C'est un défi de code le plus rapide , donc chaque soumission sera testée sur mon ordinateur, et la soumission qui prend le moins de temps sera gagnante.

Exemple d'entrée et de sortie

(Où 1est un descendant qui a hérité de l'argent, et 0est un descendant qui n'a pas hérité de l'argent)

Contribution:

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

Production:

4

Contribution:

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

Production:

254

Contribution:

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

Production:

11567

C ++ à l'aide de la bibliothèque BuDDy

Cela semblait être une bonne excuse pour jouer avec des diagrammes de décision binaires . Le royaume est converti en une grande formule booléenne où il faut compter le nombre de façons dont il peut être satisfait. Cela peut (parfois) être fait plus efficacement qu'il n'y paraît.

Le royaume doit être donné comme une constante de programme comme un tableau plat et des dimensions explicitement données. (Une belle entrée est laissée en exécution pour le lecteur :-)

Voici le code d'une simplicité embarrassante:

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

Pour compiler avec Debian 8 (Jessie), installez libbdd-devet faites g++ -std=c++11 -o hist hist.cpp -lbdd. (Les options d'optimisation ne font pratiquement aucune différence car le vrai travail est effectué dans la bibliothèque.)

De grands exemples peuvent conduire à des messages sur la récupération de place. Ils pourraient être supprimés, mais je préfère les voir.

bdd_satcountrenvoie un double, mais cela suffit pour la plage de résultats attendue. La même technique de comptage est possible avec des (grands) entiers exacts.

Le code est optimisé pour ROWS<COLS. Si vous avez beaucoup plus de lignes que de colonnes, ce pourrait être une bonne idée de transposer la matrice.

Python 2.7

Ce n'est qu'une première tentative naïve. Ce n'est pas particulièrement rapide, mais c'est correct.

La première observation est que chaque cellule dépend exactement de quatre cellules de la génération précédente. Nous pouvons représenter ces quatre cellules sous la forme d'un nombre à 4 bits (0-15). Selon les règles, si exactement une cellule voisine de la génération précédente l'est 1, alors une cellule donnée de la génération actuelle le sera 1, sinon, elle le sera 0. Ceux-ci correspondent aux pouvoirs de deux, à savoir [1, 2, 4, 8]. Lorsque les quatre ancêtres sont représentés comme un nombre à 4 bits, tout autre nombre entraînera un 0dans la génération actuelle. Avec ces informations, en voyant une cellule de la génération actuelle, nous pouvons réduire les possibilités du voisinage de la génération précédente à l'une des quatre ou une des douze possibilités respectivement.

J'ai choisi de représenter le quartier comme suit:

32
10

où 0 est le bit le moins significatif, et ainsi de suite.

La deuxième observation est que pour deux cellules adjacentes de la génération actuelle, les deux quartiers de la génération précédente se chevauchent:

32  32
10  10

ou:

32
10

32
10

Dans le cas horizontal, le 2quartier de gauche chevauche le 3quartier de droite et de même avec le 0côté gauche et le 1côté droit. Dans le cas vertical, le 1voisinage supérieur chevauche le 3voisinage inférieur et, de la même manière 0, le sommet et 2le bas.

Ce chevauchement signifie que nous pouvons réduire les possibilités de quartiers encore non choisis en fonction de ce que nous avons déjà choisi. Le code fonctionne de gauche à droite, de haut en bas, dans une recherche récursive en profondeur pour les pré-images possibles. Le diagramme suivant indique les quartiers précédents que nous devons prendre en compte lorsque nous examinons les quartiers possibles d'une cellule actuelle:

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]

Voici le code:

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

Pour l'exécuter:

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)