Part 2 took me forever bc I kept misinterpreting rules 8 and 11 and for the longest time I thought (ceiling (/ c 2)) was the same thing as (add1 (floor (/ c 2))) (spoilers: it is not) https://github.com/ionathanch/adventofcode-2020/blob/main/src/19.rkt It’s pretty specific to the input but to be fair, there were tons of hints in the text telling you to take the shortcuts

Sitting in bed this morning trying to decide whether or not parser combinators can have “parser” (or map from int to parser) as the result type. since they are strictly more powerful than regex, it’s not necessary, but it means that my input-parsing code will generate the parsers needed to run on the input :exploding_head: turtles all the way down

I’m still trying to figure out how to handle some cases for part 2…

@hazel youre farther than i am. I dont have any code or solutions yet. Just ideas. What’s the “monadic approach”?

basically parser combinators but by hand

bunch of mutually recursive validators that return either success "rest-to-parse" or failure "error"

here’s my code thus far: https://0x0.st/iC-L.rkt

what I’m confused about is where I commented “what do I do here?” — clearly failure isn’t the right approach as then it doesn’t function on the test input

also ignore [Vectorof Rule], I moved to a hash for Part 2 — those comments were only there to help me when I was having some issues with monadic composition, I guess?

So it looks like your problem case is both sides of \| match, but neither is empty—example: “abc” and I have a rule matching "a" \| "ab"? Idk, you could take the longest match, or the first (i.e. leftmost)? I did spot “Fortunately, there are no loops in the rules, so the list of possible matches will be finite.”

did I get that right? Sometimes working through a concrete example helps me—maybe I missed something. do you have a better example?

And it would seem difficult to have to implement backtracking this way :thinking_face:

spoiler: part 2 has loops

ahhhh. duh

they also implemented it in the worst way possible, hence the hash-set*: they don’t give you a new input, they expect you to change some rules in your input

which is… mega weird.

I see it now in 8 (rule 8 (or-obj (list 42) (list 42 8)))—this looks like 8: 42 \| 42 8, is that right? could you collapse that to a kleene star (42 42* ) and add a new validator? or probably I would go with longest-match. similar idea for 11: 42 31 \| 42 11 31 is like 11: 42 (42 31)* 31 I think?

I didn’t think of the Kleene star, that’s clever

but longest match probably works

FAs are one of my favorite parts of ways to compute things :slightly_smiling_face: so much is “just” a state-machine

I tried the longest match method and that didn’t work, so I modified it to make a Kleene star — but that doesn’t work either

https://0x0.st/iCoo.rkt has a function validate-star that should iterate until the given list for the star stops matching

this passes part 1 fine

gonna try something… kinda dumb

megaparsack abuse time

Rule 8 is 42*, but rule 11 isn’t 42 (42 31)* 31, since that expands to 42 42 31 42 31 … 42 31 31, but what you need is 42 42 42 … 31 31 31

Which isn’t regular, but you could just handle that case specially and use whatever you had for part1 on the 42 parts and the 31 parts

Ah, yes, good point on 11. Why is 8 only 42*? You have to get at least one 42, hence 42 42*?

Oh that’s right Alternatively, 42+

Agreed

I dont think my parsers generating parsers approach will work out, because eventually they needed a function from integers to parsers, but there was some circularity in the type-system / self-referential problem in defining the function. I’ve currently switched to building a bare-bones ast and then collapsing that to a parser when needed, hoping that will work. Otherwise I’ll have to go Hazel’s route of manually implementing the parsing alg for the ast.

I got very close to generating parsers using megaparsack @ben.knoble

…but close is not a solution, is it?

True. I have code that type-checks and runs, but produces the wrong answer, and now I’m not sure why. erg.

Hm. I haven’t proved this yet, but I suspect it’s because the parser-combinators lib I’m using has committed choice, not backtracking. I wonder if I can implement that part myself, or if it’s even needed for part1?

You don’t need backtracking for part 1

Lol so something else is the problem. Yay.

What library are you using?

It’s SML, not racket, but https://www.smlnj.org/doc/smlnj-lib/Util/str-ParserComb.html

My biggest issue rn is debugging is hard: it will take a while to find by hand a “counter-example” where my code is wrong.

my issue with part 2 right now is that my rule 8 overlaps with rule 11

because rule 8 is 42 42* and rule 11 is 42 31 | 42 11 31, so I need to somehow remove the last 42 match from rule-8/p

or just find the combination that matches

you basically need back-tracking for that, don’t you? Or non-determinism, or some way of producing parse-forests (and if any tree is valid, consider it valid), etc. I think these things are all equivalent.

yes I need backtracking but I don’t know how to do it w/ megaparsack

yah me neither

I’m aware how to backtrack in an or/p but not in a do

I have a set of functions that generates an arbitrary parser for a given rule, the issue is sequencing them

; shoot first ask questions later is a good comment to see

(disclaimer: no)

Hmm… I’m missing something for part 2. My rules 8 & 11 are: 8: 42 11: 42 31 I was supposed to effectively change them to: 8: 42 \| 42 8 11: 42 31 \| 42 11 31 So, I did a brute force solution that iterated on changing those rules successively i.e. 8: 42 \| 42 42 \| 42 42 42 \| ... 11: 42 31 \| 42 42 31 31 \| 42 42 42 31 31 31 \| ... I just wanted to get something working before thinking of better solutions, but this doesn’t work, so I must’ve misinterpreted the effect of the rule change.

Oh, I’m converting this to a regex.

I’m about to collapse to a regex for part1 just to debug… but that won’t work for part2 :)

I guess another way to ask this question is whether just making rules 8 & 11 sufficiently long manually would work, since that’s basically what my program is doing in an automated way.

Ah, manually updating does work for the sample, where my code does not, so I must have a bug…

I do feel a bit dirty for <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2020/day19.rkt|using regexes to solve Day 19> , but for this particular puzzle, I think it’s a reasonable solution.

Yeah, mapping to a regex for debugging found 49 examples where the re accepts the string but the generated parser does not. Odd…

I’ll probably create a proper parser version tomorrow for comparison.

I’m just not sure what my parser bug is :disappointed:

I might have found it; I think it has to do with my ast and some possibly empty alternations that should not be considered

yep, sigh

day 20 is literally the worst code i have every written for any challenge this year, and also by far the longest (167 sloc, 2.5x longer than my day 11)

also the only solution so far that is really heavily dependent on certain properties of the input, but i don’t really want to genericize my code because i literally never want to look at it again u___u

spoilers in thread

so being a massive noob for part 1 i did a lazy solution of haha just make a graph so i literally go through each pair of tiles and each pair of edges on those tiles and if they match or reverse-match i make an edge, and i identified the corners by the 4 vertices in the resulting graph with only 2 neighbors. this was sufficient for part 1 but for part 2 i realized i had basically done none of the actual work that would normally have gone into part 1 so it was a huge challenge

so this is already dependent on the property that in the entire input every tile edge matches exactly 0 or 1 other tile edges, which turned out to be true luckily for part 2 i took an arbitrary corner, changed the input parsing so it would magically end up in the correct orientation and then oriented the rest of the top row (chose arbitrary other corner with a 12-node path to the first corner) relative to that one, left to right then for the next row, i take the neighbors of the leftmost and rightmost nodes of the previous row that aren’t already visited, and do fewest-vertices-path between those to get the next row of the grid, which i also orient relative to the row above it then i construct the full picture from the now oriented grid, and then just brute force every coordinate to see if there’s a monster in any of its 8 possible orientations