Введение

У сборщика налогов есть некоторые проблемы с управлением налогами его королевства: исторические записи сгорели в большом пожаре.

Он хочет выяснить, сколько возможного прошлого может быть с точки зрения того, откуда унаследованы текущие деньги. К счастью, его королевство очень просто.

Королевство может быть смоделировано двумерной логической матрицей, где lпредставляет кого-то, кто унаследовал деньги, и Oкого-то, кто не имеет. Например:

l O l l

O O O l

l O l O

O O O l

(Это всегда будет прямоугольник)

В следующем поколении королевство меньше (волки сильны!).

Следующее поколение будет выглядеть так, наложенное на предыдущее поколение ( xэто заполнитель для потомка в следующем поколении)

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

Потомок будет смотреть на предков, которые непосредственно вокруг них (Таким образом, в левом верхнем углу xбудет видеть { l, O, O, O}, называется Unaligned прямоугольной окрестности )

Если только один предок унаследовал деньги, потомок унаследует деньги от них. Если более чем один предок унаследовал деньги, они ссорятся, и потомок в конечном итоге не наследует деньги. Если никто не унаследовал деньги, потомок не унаследует никаких денег.

(Более одного потомка могут наследовать от одного предка)

Итак, следующее поколение будет выглядеть так:

​
 l l O

 l l O

 l l O
​

Вызов

вход

Текущее состояние генерации, как массив массивов любых двух различных значений, где все внутренние массивы имеют одинаковую длину.

Например, для приведенного выше примера это может быть:

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

Вывод

Целое число, представляющее количество уникальных предыдущих поколений, где следующее поколение является входным.

Можно предположить, что ответ всегда будет меньше 2 ^ 30 - 1. (или 1073741823).

Предыдущее поколение будет называться «прообразом», и эта задача будет заключаться в подсчете прообразов .

счет

Это быстрый код вызов, поэтому каждая заявка будет проверена на моем компьютере, и заявка, которая займет меньше всего времени, станет победителем.

Пример ввода и вывода

(Где 1потомок, который унаследовал деньги, и 0потомок, который не унаследовал деньги)

Входные данные:

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

Вывод:

4

Входные данные:

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

Вывод:

254

Входные данные:

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

Вывод:

11567

C ++ с использованием библиотеки BuDDy

Это казалось хорошим предлогом для игры с бинарными диаграммами решений . Королевство преобразуется в большую логическую формулу, в которой мы должны подсчитать количество способов, которыми оно может быть удовлетворено. Это может (иногда) быть сделано более эффективно, чем кажется.

Царство должно быть задано как программная константа в виде плоского массива и явно заданных измерений. (Хороший ввод оставлен в качестве упражнения для читателя :-)

Вот неловко простой код:

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

Чтобы скомпилировать с Debian 8 (Джесси), установите libbdd-devи сделайте g++ -std=c++11 -o hist hist.cpp -lbdd. (Оптимизация параметров практически не имеет значения, потому что настоящая работа выполняется в библиотеке.)

Большие примеры могут привести к сообщениям о сборке мусора. Их можно подавить, но я предпочитаю их видеть.

bdd_satcountвозвращает a double, но этого достаточно для ожидаемого диапазона результатов. Та же техника подсчета возможна с точными (большими) целыми числами.

Код оптимизирован для ROWS<COLS. Если у вас намного больше строк, чем столбцов, было бы неплохо перенести матрицу.

Python 2.7

Это просто наивная первая попытка. Это не особенно быстро, но это правильно.

Первое наблюдение заключается в том, что каждая ячейка зависит ровно от четырех ячеек предыдущего поколения. Мы можем представить эти четыре ячейки как 4-битное число (0-15). Согласно правилам, если ровно одна соседняя ячейка в предыдущем поколении есть 1, то данная ячейка в текущем поколении будет 1, иначе будет 0. Те соответствуют полномочиям двух, а именно [1, 2, 4, 8]. Когда четыре предка представлены в виде 4-битного числа, любое другое число приведет к появлению 0в текущем поколении. С помощью этой информации, увидев ячейку в текущем поколении, мы можем сузить возможности соседства в предыдущем поколении до одной из четырех или одной из двенадцати возможностей соответственно.

Я решил представить окрестности следующим образом:

32
10

где 0 - младший бит и т. д.

Второе наблюдение состоит в том, что для двух соседних ячеек в текущем поколении два соседства из предыдущего поколения перекрываются:

32  32
10  10

или:

32
10

32
10

В горизонтальном случае 2соседство слева пересекается с 3соседством справа, а также 0слева и 1справа. В вертикальном случае область 1сверху сверху перекрывается с областью 3снизу, а также 0сверху и 2снизу.

Это совпадение означает, что мы можем сузить возможности для еще не выбранных районов на основе того, что мы уже выбрали. Код работает слева направо, сверху вниз, в рекурсивном поиске возможных глубин вначале глубины. Следующая диаграмма показывает, какие предыдущие окрестности мы должны учитывать при рассмотрении возможных окрестностей текущей ячейки:

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]

Вот код:

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

Чтобы запустить это:

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)