@sputnic
Android Developer

Задача про стену и кирпичи. Как решить?

Добрый день!
Задали на юниорском собеседовании такую задачу, на которой я застрял.
Вот задача, подскажите куда копать? Все решение которые мне в голову приходят требуют огромного количества памяти и жутко неоптимальны:(
Сама задача:
Есть два вида кирпичей: длиной 3 и 4. Из этих кирпичей нужно построить стену длиной 25 и высотой 10 рядов. Дополнительное условие - в двух последовательных рядах щели между кирпичами не должны создавать вертикальные линии. То есть, к примеру стену длиной 8 и высотой в два ряда не построить(1 ряд (4,4), 2 ряд (4,4) - щель по середине).
Требуется посчитать, сколько всего возможных комбинаций кирпичей при постройке стены такого размера.
Заранее спасибо за помощь
  • Вопрос задан
  • 2872 просмотра
Решения вопроса 3
@Andy_U
Ну, я бы начал с решения уравнения в целых положительных числах 3*x+4*y=25. Решений две штуки: (x=3, y=4) и (x=7, y=1). Т.е. у нас 2 класса рядов. Вариантов расположения кирпичей в первом классе 7!/(3!*4!)=35, во втором классе 8!/(7!*1!)=8. Итого 35+8=43 вариантов ряда. Генерируем их. Теперь заполняем матрицу размером 43*43, ставя единички там, где ряды кирпичей (один в столбце, второй в колонке) совместимы с условием отсутствия общей вертикальной щели (для каждого варианта ряда строим множество {L[1], L[1]+L[2], ... L1+...L[N-1]}, потом очевидно, что ряды "совместимы", если пересечение множеств пустое). Это все быстро и памяти немного надо. На питоне - 30 строк. Кстати, в построенной матрице нулей сильно больше, чем единиц. несколько рядов просто ни с одним другим не совместимы. А потом, увы, перебор, если я правильно понял условие задачи. Типа как в классической задаче "поставить 8 ферзей на шахматную доску, чтобы они не били друг друга".

Update:

Код на питоне 3.4.3, решающий задачу перебором (кроме получения "классов" рядов), приведен ниже:

import itertools


def build_tail(height, row):
    if height == 9:
        return neighbours_number[row]
    else:
        return sum(build_tail(height+1, i) for i in acceptable_neighbours[row])


rows = {i for i in itertools.permutations([3, 3, 3, 4, 4, 4, 4], 7)} | \
       {i for i in itertools.permutations([3, 3, 3, 3, 3, 3, 3, 4], 8)}

acc_rows = [set(itertools.accumulate(row[: -1])) for row in rows]
acceptable_neighbours = [[i for i, b in enumerate(acc_rows) if not (a & b)] for a in acc_rows] # copied from @bobrovskyserg
neighbours_number = [len(i) for i in acceptable_neighbours]

print(sum(build_tail(1, i) for i in range(0, len(acc_rows))))


Время решения ~40 секунд, ответ bobrovskyserg подтверждаю. Пошел разбираться с его алгоритмом...
Ответ написан
bobrovskyserg
@bobrovskyserg
Копай в динамическое программирование.
UPDATE
> А потом, увы, перебор, если я правильно понял условие задачи
хе-хе, не хочет копать Andy_U
# строим всевозможные комбинации кирпичей длинной 25
nxt, rows = [(3,), (4,)], []
while nxt:
    cur, nxt = nxt, []
    for row in cur:
        for brick in 3, 4:
            le = row[-1] + brick
            if le < 23:
                nxt.append(row + (le,))
            elif le == 25:
                rows.append(frozenset(row))

# все комбинации длинны 25 лежат в листе rows, т.е. занумерованы
# строим лист, где по номеру каждой комбинации
# лежит список номеров неконфликтующих комбинаций
friendly_row = [[i for i, b in enumerate(rows) if not (a & b)] for a in rows]

nxt = [1] * len(rows)  # в первом слое может лежать любая комбинация
for _ in range(10 - 1):  # есть же один слой
    cur, nxt = nxt, [0] * len(rows)
    for i, n in enumerate(cur):
        for j in friendly_row[i]:
            nxt[j] += n
print(sum(nxt))


UPUPDATE: разгоним рекурсивное решение
cache = {}

def build_tail(height, row):
    if height == 9:
        return neighbours_number[row]
    if (height, row) in cache:
        return cache[height, row]
    cache[height, row] = res = sum(build_tail(height + 1, i) for i in acceptable_neighbours[row])
    return res

rows = {i for i in itertools.permutations([3, 3, 3, 4, 4, 4, 4], 7)} | \
       {i for i in itertools.permutations([3, 3, 3, 3, 3, 3, 3, 4], 8)}

acc_rows = [set(itertools.accumulate(row[: -1])) for row in rows]
acceptable_neighbours = [[i for i, b in enumerate(acc_rows) if not (a & b)] for a in acc_rows]
neighbours_number = [len(i) for i in acceptable_neighbours]

print(sum(build_tail(1, i) for i in range(0, len(acc_rows))))
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Строите матрицу перехода между рядами (43х43, как описано в ответе Andy_U ), потом возводите её в 9-ю степень (поскольку у нас 9 переходов) и считаете сумму всех элементов (поскольку первый и последний ряд могут быть любыми). Всё.
Работает для любого числа рядов, хоть для триллиона :) Только потребуется быстрое возведение в степень.
Но это будет число способов построить стену. Если имелось в виду число наборов кирпичей (сколько может быть кирпичей 3x1 и сколько 4x1), то надо подумать, как сделать проще всего.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Adamos
@Adamos
Обычная комбинаторика
1. Определяем все различные комбинации кирпичей, укладывающиеся ровно в 25 м - их, кстати, не так уж много, ибо 25 = 3х3 + 4х4 = 7х3 + 1х4, и только
2. Определяем, какие из них не могут лежать рядом из-за просветов
3. Перебор рекурсией получившихся вариантов для первого, для него - второго и т.д. рядов

Ничего особенно неоптимального по памяти не должно получаться

P.S. Ах да, нужно же только подсчитать количество. Тогда задачу проще начать решать на бумажке в клеточку - глядишь, программировать вовсе не понадобится
Ответ написан
prototype_denis
@prototype_denis
Symfony
Стена должна быть ровной. Верно?

Строим дерево.
(слева +3, справа +4)
Идем только до 21, 22 и 25
3 
|\
6  7
|\ |\
9 10 11
|\ |\ |\
12 13 14 15
15 16 17 18 19
18 19    21 22 
21 22       25
   25


С 4 проще. там всего 2 значения. Остальные ветки уже были в тройке.

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

0
3  4 
6  7  8
9 10 11
12 13 
15 16 
18 19
21 22
   25


То есть, 4 + 4 + 4|3 Суммы совпадут, если начинать с 3.
3 + 4 + 4 = 4 + 4 + 3
3 + 3 + 3 + 3 = 4 + 4 + 4

Но 8 ты не соберешь.
3 + 3|4 != 4 + 4

Считаем ветки. 11 штук.
Но нас не интересует пересечение первого и последнего. 11 - 1.

Что в итоге? У нас бесшовная стена, точнее её ряды (10 рядов).
10! = 3628800;

ЗЫ.
Да простят меня математики.

UPD: Исправил ветки.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы