AdventOfCode 2020 #112
Replies: 12 comments 26 replies
-
|
В №16 наконец-то интересная задачка для парсинга - нужно правильно ограничить жадность, вот это вот |
Beta Was this translation helpful? Give feedback.
-
|
Мне показалось, что наоборот - скучный парсинг. Очередная комбинация |
Beta Was this translation helpful? Give feedback.
-
|
Я имел в виду парсинг с помощью парсер-комбинаторов. Поэтому написал про "жадность". |
Beta Was this translation helpful? Give feedback.
-
|
А я не придумал как парсер-комбинаторами разбить на части, поэтому использовал их только для отдельных строк. |
Beta Was this translation helpful? Give feedback.
-
|
@aragaer стоило добить. Я потому про интересность и написал - это отличное упражнение. Разделитель здесь - пустая строка. Нужно так описать "много того-то", чтобы пустая строка не матчилась. |
Beta Was this translation helpful? Give feedback.
-
|
Впрочем, переписал. Единственное место, где это понадобилось, это первый кусок. (rule <* char '\n') `manyTill` char '\n' |
Beta Was this translation helpful? Give feedback.
-
|
В 17 задаче хочется как-то обобщить две части. Я пока придумал только один способ - использую оба раза 4 измерения, но в первой части при поиске "потенциальных новых активируемых" для 4 размерности всегда беру значение 0. inactive3 :: Set Point -> Set Point
inactive3 r = fromList [Point x y z 0 | x <- f x, y <- f y, z <- f z]
where f g = [findMin (S.map g r) - 1..findMax (S.map g r) + 1]
inactive4 :: Set Point -> Set Point
inactive4 r = fromList [Point x y z w | x <- f x, y <- f y, z <- f z, w <- f w]
where f g = [findMin (S.map g r) - 1..findMax (S.map g r) + 1] |
Beta Was this translation helpful? Give feedback.
-
|
Я обобщил для произвольной размерности :) Аннотируешь тип и получаешь требуемую: solve :: Set (() :*: Int :*: Int) -> (Int, Int)
solve w =
( Set.size $ 6 `times` step @(() :*: Int :*: Int :*: Int) $ expand w -- 3D
, Set.size $ 6 `times` step @(() :*: Int :*: Int :*: Int :*: Int) $ expand w -- 4D
) |
Beta Was this translation helpful? Give feedback.
-
|
А вот сегодня парсер как раз поинтереснее будет=) |
Beta Was this translation helpful? Give feedback.
-
|
Чем это? Разбор арифметических выражений - рутина и скукота. |
Beta Was this translation helpful? Give feedback.
-
|
Ну да, в документации parsec практически готовый пример. |
Beta Was this translation helpful? Give feedback.
-
|
19 день через "функции" получился, а вот чтобы из набора правил сделать парсер - не очень. validate :: Ruleset -> [String] -> [String]
validate ruleset strings = filter (any (=="") . match ruleset (Sequence [0])) strings
match rset (Character c) "" = fail "no match"
match rset (Character c) (x:xs) | c == x = pure xs
| otherwise = fail "no match"
match rset (Sequence []) s = pure s
match rset (Sequence (r:rs)) s = do
r <- rset ! r
m <- match rset r s
match rset (Sequence rs) mapplyRuleset rs = parse (parserFromRule rs (Sequence [0]) >> eof) ""
parserFromRule rset (Character c) = char c >> pure ()
parserFromRule rset (Sequence s) = mapM_ (fromChoice . (rset !)) s
where fromChoice = choice . map (try . parserFromRule rset)Первый вариант работает корректно, а во втором как будто не хватает откатывания после жадного захвата. |
Beta Was this translation helpful? Give feedback.
-
|
У меня день 19 в целом получился, но пришлось ограничить перебор вариантов для циклов :( Даже после того, как сделал его нежадным, всё равно где-то зацикливается, а времени докапываться до сути нет... |
Beta Was this translation helpful? Give feedback.
-
|
Странно, ведь там все правила имеют ширину строго больше нуля. То есть каждое применение правила уменьшает длину оставшейся строки. |
Beta Was this translation helpful? Give feedback.
-
|
У меня архитектура немного не туда ушла — я просто перебирал варианты с
возрастающей длиной. А так, да, можно было отслеживать уменьшение инпута
…On Sat, Dec 19, 2020, 20:59 Ilya Konovalov ***@***.***> wrote:
Странно, ведь там все правила имеют ширину строго больше нуля. То есть
каждое применение правила уменьшает длину оставшейся строки.
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#112 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABD2E25WVJNZ7OQNH4GZ3SLSVTLXTANCNFSM4U5PQYXA>
.
|
Beta Was this translation helpful? Give feedback.
-
|
Чёт у меня ресурсов не хватает у ноута, чтобы day22 досчитать %) |
Beta Was this translation helpful? Give feedback.
-
|
Там же игра в пьяницу? Навскидку первая половина выглядит достаточно просто. |
Beta Was this translation helpful? Give feedback.
-
|
Потратил целый день, но все-таки переписал ее через State и тайпклассы. |
Beta Was this translation helpful? Give feedback.
-
|
Первая половина простая. Во второй мутная формулировка и дебаг с пристальным вглядыванием в пример. |
Beta Was this translation helpful? Give feedback.
-
|
По второй части day23 - тупо в лоб c iterate' долго получается. В прошлом году задачка на тасовку карт решалась через математику. Тут что-то похожее? |
Beta Was this translation helpful? Give feedback.
-
|
Я тоже попробовал в лоб, и да - долго :) |
Beta Was this translation helpful? Give feedback.
-
|
На Reddit пишут, что реализации на мутабельных linked lists отрабатывают за единицы секунд даже 10М шагов %) |
Beta Was this translation helpful? Give feedback.
-
|
Есть какая-нибудь готовая библиотека? Ну или краткое руководстов, как переписать с обычных списков на такие шустрые? |
Beta Was this translation helpful? Give feedback.
-
|
Я условие только читал, но выглядит всё именно так. |
Beta Was this translation helpful? Give feedback.
-
|
Обычные тоже шустрые, но не в таком сценарии использования. Двусвязные
мутабельные списки можно сделать на Foreign Pointers, наверное
…On Wed, Dec 23, 2020, 15:54 Ilya Konovalov ***@***.***> wrote:
Есть какая-нибудь готовая библиотека? Ну или краткое руководстов, как
переписать с обычных списков на такие шустрые?
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#112 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABD2E25H4Y6FFKQTCOBF733SWHK7HANCNFSM4U5PQYXA>
.
|
Beta Was this translation helpful? Give feedback.
-
|
Может есть готовая реализация? Гугл выдал мне какую-то статью по mergesort using mutable arrays, но там ссылка ведет на протухший hpaste. |
Beta Was this translation helpful? Give feedback.
-
|
Не нужен тут array, в том то и дело! Двусвязный список позволяет вырезать и
вставлять куски за константное время и реализовывать замкнутое кольцо,
которое можно прокручивать в обе стороны
…On Wed, Dec 23, 2020, 16:15 Ilya Konovalov ***@***.***> wrote:
Может есть готовая реализация? Гугл выдал мне какую-то статью по mergesort
using mutable arrays, но там ссылка ведет на протухший hpaste.
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#112 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABD2E23F6XEGQCCUB3ES6B3SWHNONANCNFSM4U5PQYXA>
.
|
Beta Was this translation helpful? Give feedback.
-
|
Ну там требуется поиск элемента по значению - это линейное время. Но ускорить разрезание и переклеивание очень хочется. Короче, если это надо писать самому, то я на такое не способен. Если есть готовая библиотека с такими структурами или хотя бы пример реализации, то было бы очень кстати. |
Beta Was this translation helpful? Give feedback.
-
|
Линейный поиск дешевле, чем односвязный список перекладывать из стопки в
стопку
…On Wed, Dec 23, 2020, 16:51 Ilya Konovalov ***@***.***> wrote:
Ну там требуется поиск элемента по значению - это линейное время. Но
ускорить разрезание и переклеивание очень хочется.
Короче, если это надо писать самому, то я на такое не способен. Если есть
готовая библиотека с такими структурами или хотя бы пример реализации, то
было бы очень кстати.
—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
<#112 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABD2E22F75A322W3V5P7PXDSWHRWTANCNFSM4U5PQYXA>
.
|
Beta Was this translation helpful? Give feedback.
-
|
Сделал совсем жесть - на базе Vector.Primitive.Mutable сделал эмуляцию связного списка (значение по индексу - номер следующей ячейки). 10 млн итераций за 0.9 секунды. |
Beta Was this translation helpful? Give feedback.
-
|
Итак, достаточно быстро и шустро можно все сделать, если действительно иметь закольцованный single-linked list. А чтобы его иметь достаточно иметь cons-пары. А дальше я вспомнил старый прием, который еще в бейсике использовался - вместо "указателей" используются индексы в некотором массиве. Таким образом нам нужны пары вида "ключ-индекс", а их уже легко сделать даже той же Data.Map. Это может быть будет работать не за секунду, но каждая итерация превращается в 5 чтений и 4 записи, каждое из которых делается за константу. |
Beta Was this translation helpful? Give feedback.
-
|
На мутабельном массиве связей и правда получается за единицы секунд! Но выглядит это с непривычки так, что Си кажется изящным ) |
Beta Was this translation helpful? Give feedback.
-
|
Я сделал на |
Beta Was this translation helpful? Give feedback.
-
|
Но у меня двусвязный список. М.б. можно будет и отбросить вторую связь, вроде я в одну сторону хожу всё время... |
Beta Was this translation helpful? Give feedback.
-
|
Чёт 24 и 25 сделаны "на отвяжись". В итоге у меня |
Beta Was this translation helpful? Give feedback.
-
Пробуем обсуждать AdventOfCode тут, чтобы не оффтопить в чатах.
Beta Was this translation helpful? Give feedback.
All reactions