Google Foobar Level 5- сотовые автоматы / динамическое программирование
В настоящее время я работаю над 5 уровнем foobar. Я получил следующую проблему
По результатам сканирования туманности вы обнаружили, что она очень плоская и распределена по разным участкам, поэтому вы можете смоделировать ее как двумерную сетку. Вы обнаружите, что текущее существование газа в ячейке сетки определяется именно его 4 соседними ячейками, а именно: (1) этой ячейкой, (2) ячейкой под ней, (3) ячейкой справа от нее, и (4) клетка внизу и справа от нее. Если в текущем состоянии ровно 1 из этих 4 ячеек в блоке 2х2 имеет газ, то в следующем состоянии он также будет иметь газ. В противном случае ячейка будет пустой в следующем состоянии.
Например, скажем, предыдущее состояние сетки (p) было:
.O..
..O.
...O
O...
Чтобы увидеть, как эта сетка изменится и станет текущей сеткой (c) в течение следующего временного шага, рассмотрим блоки 2x2 ячеек вокруг каждой ячейки. Из блока 2x2 из [p[0][0], p[0][1], p[1][0], p[1][1]], только p [0] [1] имеет газ в это, что означает, что этот блок 2x2 станет ячейкой c[0][0] с газом в следующем шаге по времени:
.O -> O
..
Аналогично, в следующем блоке 2x2 справа, состоящем из [p[0][1], p[0][2], p[1][1], p[1][2]], два из которых содержат ячейки имеют газ, поэтому в следующем состоянии сетки, c[0][1] НЕ будет иметь газ:
O. -> .
.O
Следуя этой схеме до ее завершения, из предыдущего состояния p текущее состояние сетки c будет:
O.O
.O.
O.O
Обратите внимание, что результирующий вывод будет иметь на 1 меньше строки и столбца, поскольку в нижней и правой ячейках нет ячейки ниже и справа от них соответственно.
Напишите функцию answer(g), где g - это массив массивов bools, в которых указано, есть ли газ в каждой ячейке (текущее сканирование туманности), и верните int с числом возможных предыдущих состояний, которые могли привести к тому, что сетка после 1 временного шага. Например, если бы функции было присвоено текущее состояние c, указанное выше, то было бы выведено, что возможными предыдущими состояниями были p (заданные выше), а также ее горизонтальное и вертикальное отражение, и было бы возвращено 4. Ширина сетки будет между От 3 до 50 включительно, а высота сетки будет от 3 до 9 включительно. Ответ всегда будет меньше одного миллиарда (10^9).
Test cases
==========
Inputs:
(boolean) g = [[true, false, true], [false, true, false], [true, false, true]]
Output:
(int) 4
Inputs:
(boolean) g = [[true, false, true, false, false, true, true, true], [true, false, true, false, false, false, true, false], [true, true, true, false, false, false, true, false], [true, false, true, false, false, false, true, false], [true, false, true, false, false, true, true, true]]
Output:
(int) 254
Inputs:
(boolean) g = [[true, true, false, true, false, true, false, true, true, false], [true, true, false, false, false, false, true, true, true, false], [true, true, false, false, false, false, false, false, false, true], [false, true, false, false, false, false, true, true, false, false]]
Output:
(int) 11567
Я вижу, что это проблема клеточных автоматов, но я никогда не изучал CA до глубины, поэтому я не знаю, существует ли уже алгоритм, который может найти прообраз CA по этому типу правила.
Вместо этого я решил сделать это простым способом построения решения столбец за столбцом. Любой столбец m x 1 будет иметь (m+1) x 2 прообраз по этому правилу. Чтобы найти (m + 1) x2 простых образов столбца, я запускаю DFS вдоль столбца сверху вниз. Затем я строю решения для всей сетки, объединяя отдельные решения для столбцов. Чтобы решения двух последовательных столбцов были включены в окончательное решение, второй столбец первого прообраза должен перекрываться с первым столбцом второго прообраза. Таким образом, все решения могут быть найдены путем подсчета всех возможных таких цепочек решений отдельных столбцов, идущих от первого столбца к последнему.
PREV_STATES2 = {0: ((0, 0),
(1, 1),
(0, 3),
(1, 2),
(1, 3),
(2, 1),
(3, 0),
(3, 1),
(2, 2),
(2, 3),
(3, 2),
(3, 3)),
1: ((2, 0),
(0, 2),
(1, 0),
(0, 1))}
def column_k(g, k, r=-1):
if r == -1:
return tuple([g[i][k] for i in range(len(g))])
return tuple([g[i][k] for i in range(r)])
def next_state(col):
result = []
for i in range(len(col) - 1):
result.append(int(sum(int(k) for k in col[i] + col[i + 1]) == 1))
return result
def check_overlap(int_pair_prev, int_pair_next):
check1 = int_pair_prev[0] % 2 == int(int_pair_next[0] > 1)
check2 = int_pair_prev[1] % 2 == int(int_pair_next[1] > 1)
return check1 and check2
def append_bits(partial_soln, nums_to_append):
result1 = (partial_soln[0] << 1) + (nums_to_append[0] % 2)
result2 = (partial_soln[1] << 1) + (nums_to_append[1] % 2)
return (result1, result2)
def past_states2(col):
col = [int(b) for b in col]
m = len(col)
first_past_states = PREV_STATES2[col[0]]
fringe = [(s, 0) for s in first_past_states]
solutions = set()
while len(fringe) != 0:
partial_solution = fringe.pop()
k = partial_solution[1]
if k == m - 1:
solutions |= {partial_solution[0]}
else:
bool = col[k + 1]
valid_past_states = (s for s in PREV_STATES2[bool] if check_overlap(partial_solution[0], s))
for valid_state in valid_past_states:
next_partial_solution = append_bits(partial_solution[0], valid_state)
fringe.append((next_partial_solution, k + 1))
return solutions
def answer(g):
num_paths_prev = {}
num_paths_curr = {}
col_cache = {}
for i in range(len(g[0])):
col = column_k(g, i)
if len(num_paths_prev) == 0:
for column_sol in past_states2(col):
if column_sol in num_paths_curr:
num_paths_curr[column_sol] += 1
else:
num_paths_curr[column_sol] = 1
else:
if col in col_cache:
current_predeccessors = col_cache[col]
else:
current_predeccessors = past_states2(col)
col_cache[col] = current_predeccessors
for column_sol in current_predeccessors:
for prev_solution in num_paths_prev:
if column_sol[0] == prev_solution[1]:
if column_sol in num_paths_curr:
num_paths_curr[column_sol] += num_paths_prev[prev_solution]
else:
num_paths_curr[column_sol] = num_paths_prev[prev_solution]
num_paths_prev = num_paths_curr
num_paths_curr = {}
return sum(num_paths_prev.values())
Я пытаюсь использовать подход DP для подсчета решений. Обходя столбцы конечной сетки слева направо, на каждой итерации я веду только список возможных прообразов столбца i и столбца i + 1 вместе со словарем, отображающим прообразы столбца i на количество найденных к настоящему времени путей. этот конец в этом прообразе. Я использую этот словарь, чтобы обновить счетчики для прообразов столбца i + 1 соответственно, пока не достигну последнего столбца. Кроме того, я храню столбцы не как массивы, а как целые числа (путем преобразования столбца 1 и 0 в двоичное число). Это просто для экономии места, а также потому, что сравнение целых чисел намного быстрее.
Тем не менее, похоже, что мое решение заключается в преодолении. Для тестового примера 2 у меня должно быть 254 решения, но мой алгоритм насчитывает 832. Я попытался отладить свою DFS вдоль столбцов, но, похоже, не возвращает дубликаты. Я думаю, что это может быть из-за моего подхода к подсчету решений в функции ответа (g). Тем не менее, я не уверен, где это может пойти не так концептуально. Мой вопрос, если мой подход к подсчету решений кажется правильным. Если это так, что может быть причиной перерасхода в этом случае? Также,
РЕДАКТИРОВАТЬ 2: Я нашел ошибку, из-за которой код возвращал неправильный ответ, включил некоторые оригинальные ответы Фам Трунга и реорганизовал мой подход, чтобы лучше использовать целочисленное представление столбцов. Теперь алгоритм работает для всех тестовых случаев, которые я пробовал. Теперь проблема в том, что он не соответствует требованию времени выполнения foobar. Я ищу, чтобы оптимизировать, или, возможно, изменить подходы в целом
Есть ли более эффективный способ решения этой проблемы, который может использовать теорию CA? Не ищу код, просто полезные указатели. Спасибо!
РЕДАКТИРОВАТЬ 1: я забыл добавить ограничения. Сетка имеет от 3 до 9 (включительно) строк и не более 50 столбцов.
1 ответ
Я думаю, что вы идете в правильном направлении, но, если честно, я не совсем понимаю ваш код, поэтому я поделюсь своим подходом здесь:
Итак, мы создадим возможную конфигурацию для каждого столбца (вы также можете сделать со строкой), а не ячейку за ячейкой, и сравним их с последним сгенерированным столбцом, мы можем проверить конфигурацию.
Предполагая, что у нас есть прямоугольник n x m, вот возможное решение:
int cal(int index, int lastCol, int n, int m, boolean[][]p){
if(index == m){
return 1;
}
if (this state is done before){
return dp[index][lastCol];
}
int result = 0;
#Generate all possible configurations for col index
for(int i = 0; i < (1<<n); i++){
if (check(i, lastCol, p)){
result += cal(index + 1, i, n, m, p);
}
}
return dp[index][lastCol] = result;
}
Итак, функция check будет повторять бросок каждого квадрата 2x2 и проверять, будет ли этот квадрат генерировать правильное следующее состояние в p
Временная сложность будет O(m*4^n).
Изменить: так как число строк мало, поэтому я изменил подход от строки к строке на столбец на столбец.
Подход "снизу вверх
int[][]dp;
for(int i = 0; i < (1<<n); i++){
dp[0][i] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 0; j < (1<<n); j++){
for(int k = 0; k < (1<<n); k++){
if(check(j,k,p)){
dp[i][k] += dp[i - 1][j];
}
}
}
}