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.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Пробуем обсуждать AdventOfCode тут, чтобы не оффтопить в чатах.
Beta Was this translation helpful? Give feedback.
All reactions