combinations x | x < 1     = 0
               | x == 1    = 1
               | otherwise = combinations (x-1) + combinations (x-2) + combinations (x-3)

Древовидная рекурсия там, где можно было обойтись без неё? Ну-ну

с мемоизацией нормально

но наверняка можно переписать по аналогии с фибоначчи

combinations x | x < 1     = 0
               | x == 1    = 1
               | otherwise = combinations (x-1) + combinations (x-2) + combinations (x-3)

Где тут мемоизация?

По-вашему, Хаскель всё подряд мемоизирует магически?

наверно, надо читать "если с мемоизацией, то нормально"

Если с "если", то нормально :)

уверен что можно за О(1) сделать, в худшем случае за логарифм

да, предполагалось с если

Какая хорошая сегодня задачка на AoC

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

На бумаге почеркал, да. Потому что не у компа был, а хотелось развлечься :)

не знаю про две минуты, я полчаса тупил 8)

Я просто сгенерил все замены вида
[1, 1, 1, 1, 1]
[1,    2,    2]
[   2, 1, 1, 1]
[   2,       3]
...
(такие разницы получаются, если выкинуть один или два элемента с вкладом +1)

Количества вариантов мемоизировал, а дальше

product . map ((variants !!) . length) . filter ((== 1) . head) . group

(только менее partial :))

Похвастаюсь:
$ stack exec -- advent --day 10 +RTS -s
<print answers>
        953,472 bytes allocated in the heap
             48 bytes copied during GC
         56,008 bytes maximum residency (1 sample(s))
        116,024 bytes maximum slop
<skip>
 INIT    time    0.000s  (  0.001s elapsed)
 MUT     time    0.000s  (  0.011s elapsed)
 GC      time    0.000s  (  0.000s elapsed)
 EXIT    time    0.000s  (  0.000s elapsed)
 Total   time    0.000s  (  0.012s elapsed)

мемоизации нет

Да оно и без мемоизации быстро работает, на самом деле. Главное — не делать перебор всего набора данных :)