наверно будет быстрее

каждому состоянию соответствует число, каждому числу состояние. Один к одному

и на тему распространения волны - в моем случае проходит 57 итераций волны, на 30-40-х волнах каждая итерация это по 150-200 тысяч состояний

новых

а, ну да, вместо массива размером 2^30 можно взять например хэш, который будет расти по мере необходимости. Но на С это написать сложнее, чем маллоком выделить гиг 8)

У меня почему-то на третьей волне всё стопорится. Кончаются ходы. Не могу понять, почему.

хм. Вообще да, выделять по байту на каждое состояние это перебор, достаточно выделять по биту, но тогда надо как-то сохранять фронт

в 11-й?

в 11-й?

Да.

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

На нём и делаю.

Сделал.

Чувствую, что где-то какая-то мелкая ошибка в коде. Но не могу её найти.

показывай код, поищем 8)

гипотеза - ты не спускаешься вниз

В 11 задаче прикол такой: если делать все возможный состояния, то их для первой части 250000 с плюсом. Если сделать матрицу возможных переходов - то не хватит памяти (62 500 000 000), а если проверять их на лету тупо на каждой волне - то очень долго. Поэтому не надо делать все возможные состояния =) И на каждой волне надо тупо проверять все доступные ходы, тогда считается за приемлемое время.

Ну и состояния надо хранить в целых числах, по два бита на номер этажа, иначе списки/туплы/словари тоже очень добавляют времени.

мм. Не, у меня нет никакой матрицы переходов

* но и туплы с булами нормально заходят, на самом деле

просто я могу из одного любого состояния (то есть числа от 0 до 2^30) сгенерить все остальные состояния, в которые можно перейти.

и это я делаю в рантайме

Ну у меня пока что set это этаж, а tuple — весь завод. Но я пока что не в это упираюсь.

код покажи 8)

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

код покажи 8)

http://pastebin.com/QyAkX7WJ

Положительное число — генератор. Отрицательное — чип.

у тебя элементы сетов - списки

у тебя элементы сетов - списки

Где? Числа там.

принт печатает

set([])

вот такое вот

set([])

У меня такого нет.

$ python santa11.py (0, 7, (set([]), set([]), set([-2]), set([1, 2, -1]))) (1, 21, (set([]), set([-2]), set([]), set([1, 2, -1]))) (2, 43, (set([-2]), set([]), set([]), set([1, 2, -1]))) (3, 43, (set([-2]), set([]), set([]), set([1, 2, -1])))

просто запустил

на старте у тебя лифт на 3-м этаже, на финише - на нулевом

а, ты с конца ищешь

set([])

Походу, это обозначение пустого сета у тебя. Хотя у меня оно set(). Python 3

а, сейчас третьим попробую

угу

field не включает положение лифта

а, field это объект класса Facility

чот _str_ не работает

во

ты действительно не уезжаешь на лифте обратно

чот _str_ не работает

Я на него в дебаггере смотрю.

ты действительно не уезжаешь на лифте обратно

Там есть moves_map. Для не крайних этажей оно включает соседние этажи. По идее, уезжать должен. Сейчас ещё уточню.

да

вот короче чо

вот я распечатываю все мувы

и вот начало

-1: (set(), set(), set(), {1, 2, -1, -2}) [3] go down from 3 0 7 0: (set(), set(), set(), {1, 2, -1, -2}) [3],-1: (set(), set(), {1, 2}, {-2, -1}) [2],-1: (set(), set(), {1, -1}, {2, -2}) [2],-1: (set(), set(), {2, -2}, {1, -1}) [2],-1: (set(), set(), {-1, -2}, {1, 2}) [2],-1: (set(), set(), {-1}, {1, 2, -2}) [2],-1: (set(), set(), {-2}, {1, 2, -1}) [2] -1: (set(), set(), {1, 2}, {-2, -1}) [2] go up from 2 go down from 2 -1: (set(), set(), {1, -1}, {2, -2}) [2] go up from 2 go down from 2

то есть go down генерит новые мувы, а go up нет

то есть go down генерит новые мувы, а go up нет

Понял. Спасибо. Сейчас буду разбираться.

мхмм...

не, чот не то

стоп

все верно, он генерит мувы

но такие уже были

если мы от финиша будем придумывать новые мувы, то они конечно всегда будут повторяться - ты не учитываешь положение лифта

... ща

Already seen move -1: (set(), set(), {-1}, {1, 2, -2}) [3]

это на втором шаге и это ложь - такого мува раньше невозможно было увидеть

ага, вижу непонятную штуку

на втором шаге почему-то среди possible moves есть мувы с переездом на третий этаж

на втором шаге почему-то среди possible moves есть мувы с переездом на третий этаж

Да. Я потом ifом проверяю, чтобы раньше таких мувов не было.

И остальные добавляю.

да, теперь понял

ERROR: S client not available

это на втором шаге и это ложь - такого мува раньше невозможно было увидеть

Да не. Это же шаг из первой волны. И на второй волне он встречается среди возможных ходов. Потом отбрасывается.

вот ... по-моему это лишнее

в каждой волне должны быть только шаги этой волны

вон как я сегодняшнюю задачу делал

Я сегодняшнюю не читал.

вот ... по-моему это лишнее

Иначе бесконечный цикл.

Или я не уловил идею.

я чуть выше кидал ссылку на решение. opaths это список всех состояний предыдущей волны, paths - список состояний этой волны. Каждая итерация - opaths = paths; paths = []

ну .. в сегодняшней задаче повторения есть

Я, кажется, догадываюсь, где ошибка.

Я правильно понимаю следующее? В fields теоретически не должно быть одинаковых состояний элементов + лифта? Но может быть такое, что состояние элементов одинаковое, а лифт на другом этаже?

да

У меня вот эта проверка на существование этого состояния никак не проверяет лифт. Проверяет только элементы.

поэтому у меня 30 бит - 2 бита на лифт, 28 бит это 7*2*2

И, соотстветственно, отбрасывает потенциально хорошее состояние.

именно

я поэтому и не вижу варианта "отвез 1 штуку на 3-й этаж и вернулся на 4-й" в списке мувов

New possible move -1: (set(), set(), {-1}, {1, 2, -2}) [0] 3

это есть

но на следующей итерации этого мува нет

ну да, у тебя происходит сравнение объектов как сравнение туплов, то есть туплы и сеты

а лифт не является частью тупла

Сейчас на «пятый» этаж запихаю индекс лифта тогда.

вот, победа

не, метод _eq_ пропиши

А, точно.

def __eq__(self, other): return super(Facility, self).__eq__(other) \ and self.elevator_position == other.elevator_position

Запустил считать puzzle_input. Чувствую, что сейчас упрётся во что-нибудь.

Хотя не. Там же в пямять ничто не упирается. Только CPU

@aragaer ответ на первую часть где-то в районе 30-40 же?

Your puzzle answer was 33.

кстати у тебя оно делает лишние ходы похоже