Fork me on GitHub
#adventofcode
<
2017-12-09
>
grzm00:12:00

a little more than 4 hours…

borkdude08:12:52

My day 9 is up. Fairly straightforward.

fellshard08:12:05

I do love my iterate, but now that you say something reduce is probably more appropriate.

fellshard08:12:36

Eh, never mind. Might have worked if I'd kept the stream separate from the accumulated state, but part of the problem is that one of the 'instructions' modifies the stream itself, which makes function outputs weirder.

fellshard08:12:40

Hmm. Not sure if you're just lucky or not, but ! only ignores the next character while inside a garbage block, according to the problem statement

jmb08:12:27

Day 9 solved! yeeeeeeeee

borkdude08:12:53

@fellshard I read the problem statement as the futile ! were only inserted inside garbage, so I could just strip it away, as I don’t expect ! outside < >

fellshard08:12:44

I'm seeing them outside in my input, at least

fellshard08:12:29

Searching for >! will show cases where the ! must be outside garbage, in fact

borkdude08:12:29

@fellshard ok, if you have a link to your input + your expected answers I can give it a ty

borkdude08:12:26

Same answer for score, different for garbage. Guess I got lucky by input.

borkdude08:12:45

Maybe I’ll fix later today. Thanks.

fellshard08:12:24

Lucky! But hey, turned out nice and tidy. 🙂

borkdude13:12:18

Hey, are you sure your garbage output is 7825? just asking

borkdude13:12:25

@fellshard my program works for my input + the examples

borkdude13:12:31

but I get a different number

borkdude16:12:15

Turned out my first solution was correct after all. I just copied the quoted input to a file, which yielded a different answer. DOH.

fellshard18:12:45

Ick. My bad. I should really get a repl on my personal machine so I can use resource files instead, like you do. Easier to wrangle and share.

borkdude08:12:21

>! doesn’t necessarily mean you’re outside garbage

fellshard08:12:16

Wait, yes it does. > will exit a garbage block if you're in one, or have no effect if you're not.

bhauman11:12:22

take out the trash

borkdude13:12:32

@bhauman @fellshard pointed out my program was incorrect for his input. I tried yours and get same numbers as you now (not pushed yet). Could you try his input? I get a different number for the garbage. https://github.com/armstnp/advent-of-code-2017/blob/master/day-9.clj Score: 17390 Garbage: 7825

borkdude13:12:09

I wonder if anyone used InstaParse for this one

borkdude14:12:43

I’m going to try spec

nooga14:12:14

I went with straightforward automaton to count and filter garbage “in parallel”

bhauman14:12:34

@borkdude I tried his input and got the correct results

bhauman14:12:33

@nooga mine is similar but I reduced the states of the automaton by handling the score separately

bhauman14:12:06

and looking at yours I'm wondering why i didn't just use a vector for state

nooga14:12:08

@bhauman nice, reading it right now

nooga14:12:42

@bhauman no reason, I just typed this in one go 😄

nooga14:12:17

I could use a vector and change loop to reduce or something

nooga14:12:38

oh, sorry, misread that

bhauman14:12:46

no worries, easy to do

bhauman14:12:21

@borkdude string/replace takes a function arg that should do it

bhauman14:12:01

coming up with a much shorter solution now

bhauman14:12:52

so I'm thinking I can clean the garbage up with string/replace now that I know it takes a fn arg

bhauman14:12:21

including counting it I'm pretty sure

mfikes14:12:15

@grzm I think you can convert (condp = c \a (foo) \b (bar) :else (baz)) to (case c \a (foo) \b (bar) (baz)) and in addition to the simplification, you get a perf improvement with constant-time dispatch.

nooga14:12:57

nice @mfikes

nooga14:12:17

I did basically the same but in even more condensed form

mfikes14:12:46

@borkdude Hah, your solution is practically isomorphic to mine. 🙂

mfikes14:12:30

Nice @nooga. I tried yours on my input, and as you'd expect your version runs more quickly (it shaves off 25–50% or so)

nooga15:12:34

so not only is it short, it’s also fast ;d

bhauman15:12:02

OK much more concise and simple

borkdude15:12:32

Why is this so sloooooow?

(s/def ::garbage (s/cat :lab #{lab}
                        :content (s/* char?)
                        :rab #{rab}))

(s/def ::group (s/cat :lcb #{lcb}
                      :children
                      (s/* (s/cat :child (s/alt :group ::group
                                                :garbage ::garbage)
                                  :comma (s/? #{\,})))
                      :rcb #{rcb}))

(s/conform ::group (seq "{{},{<x>}}"))

(defn parse-string [s]
  (s/conform ::group (seq s)))

(comment 
         (def p (parse-string (data))))
Heap space exception

bhauman15:12:13

are you generating test input?

borkdude15:12:18

nope, just conforming

grzm15:12:39

@mfikes nice. I'll give that a shot. It's working at sub 10ms already.

bhauman15:12:40

it can't find a match so its continuing to search?

mfikes15:12:25

@grzm Yeah, for this problem, case is only better than condp = for readability IMHO

borkdude15:12:58

I noticed case doesn’t work when you’re aliasing stuff…

borkdude15:12:33

@mfikes Oh cool (isomorphic), but mine is incorrect for one out of three inputs I tried

grzm15:12:10

I was also thinking of rewriting it to dispatch on both args to move all dispatch logic into the multimethod.

borkdude15:12:42

@mfikes I noticed yours failed too for @fellshard’s input (returns 8373 for garbage count instead of 7825)

mfikes15:12:37

So, some part of the problem definition seemed underspecified to me, and I ended up assuming.

bhauman15:12:28

@borkdude mine now uses regexes like yours did and it works for @fellshard's input

borkdude15:12:31

@bhauman wow, I didn’t know str/replace took a function!

bhauman15:12:49

I sent you a message above stating just that!! 🙂

borkdude15:12:57

@bhauman > string/replace takes a function arg that should do it it being?

borkdude15:12:43

I meant: what do you mean with "it"?

borkdude15:12:10

I get it now, but I didn’t understand that message in the context of the thread 🙂

bhauman15:12:28

yeah not clear at all

borkdude15:12:24

@bhauman you’re replacing the exclamation marks regardless of whether they occur out or inside the question marks… but it seems they don’t ever occur outside

borkdude15:12:04

so I guess that’s fine

bhauman15:12:44

yes we have to assume there isn't stray chars

borkdude15:12:18

if I had a better up front understanding of the structure, e.g. {aaaxx!xxx{<x>}} doesn’t occur, I would have written a better solution… but to eager too find the answer 🙂

bhauman15:12:46

thats the cool thing about str/replace taking a function, is you can call str/replace again inside that fn

mfikes15:12:03

Wait, that's exactly the part that I thought was underspecified in the problem definition @borkdude

borkdude15:12:22

@bhauman that’s so good to know — thanks!

nooga15:12:42

> In a futile attempt to clean up the garbage, some program has canceled some of the characters within it using !: inside garbage, any character that comes after ! should be ignored, including <, >, and even another !.

bhauman15:12:44

so one way of reading that, is that ! only occurs inside garbage

borkdude15:12:18

yeah you could also deduce it from the examples

grzm15:12:56

Using case dropped part 1 from sub 10ms to sub 7ms

bhauman15:12:11

it seems like a fair assumption

mfikes15:12:14

Yes, my reading is that ! only has meaning inside garbage.

borkdude15:12:28

that’s what our solutions are doing too I believe mfikes

borkdude15:12:59

there has to be some edge case only occurring in fellshard’s input

mfikes15:12:10

@borkdude Is the problem that {aaa{foo}xxx} can occur?

borkdude15:12:30

@mfikes my code should interpret that too

mfikes15:12:43

My code would interpret that as a single group.

mfikes15:12:58

Or at least I didn't code for that case.

borkdude15:12:35

I get a score of 3 for that one

borkdude15:12:54

but it’s not likely that our code should handle it

mfikes15:12:01

Yeah, my code does that as well, but I would claim my code is undefined for that kind of input.

grzm15:12:06

That's invalid, per the spec

borkdude15:12:25

I shouldn’t affect the outcome though

grzm15:12:01

Depends on your stance on Postel's law 🙂

mfikes15:12:23

Accept bad input? Accept bad AoC problem definitions?

grzm15:12:39

Be liberal in what you accept, conservative in what you emit.

borkdude15:12:48

I subscribe to that law

grzm15:12:49

For me, it depends on whether or not I've had breakfast.

borkdude15:12:13

For nutrition, I subscribe to the reverse

borkdude15:12:32

@mfikes What should the garbage count for this one be?

(solve “{{<!!!>}}“)

mfikes15:12:42

I'm leading towards {aaa{foo}xxx} being a single group, because "things" are separated by commas

borkdude15:12:08

@mfikes I ignored commas too, I treat all things like whitespace if it’s not a group / garbage separator

mfikes15:12:08

There is no closing of the garbage in your example @borkdude

borkdude15:12:49

yes, of course..

bhauman15:12:46

the presense of non garbage garbage, doesn't affect the final score or the garbage count

borkdude15:12:07

I wonder what’s up with the garbage count in our code mfikes…. — yes, you’re right bhauman, I think we’re doing that

bhauman15:12:54

@borkdude i'd suspect its an odd even escape code thing

bhauman15:12:26

as thats the only thing that can mess up the count

mfikes15:12:02

@borkdude My code and fellshard's code produce the same 8373 for garbage cound

mfikes15:12:23

Yeah, perhaps there is no bug

bhauman15:12:25

@mfikes on fellshards input?

borkdude15:12:59

but he told me he got 7825 and bhauman + Vik got that too: https://twitter.com/pg_xocolatl/status/939517141606457344

bhauman15:12:29

both yours and his would probably be the same for your input

mfikes15:12:35

For fellshards input my code produces 17390 and 8373 and fellshard's produces {:score 17390, :garbage-count 8373}

bhauman15:12:51

that doesn't sound right

borkdude16:12:04

@mfikes Is your REPL state fresh?

borkdude16:12:30

Just checking 😄

mfikes16:12:45

I resarted it. Still getting {:score 17390, :garbage-count 8373}

bhauman16:12:11

well i get 7825

borkdude16:12:14

with /his/ code?

bhauman16:12:19

on fellshards input

borkdude16:12:51

@mfikes Did you also upgrade to clojure 1.9.0? maybe it’s a bug 😄

mfikes16:12:09

@borkdude I think the problem is this: In fellshard's code his input is defined in the code. I copied your input file in your repo, but the file is a direct copy, and the file has the quotes escaped in it

mfikes16:12:56

So, I'm getting the incorrect answer for the file, but the correct one from the literal code

mfikes16:12:45

In other words, the problem is here https://github.com/borkdude/aoc2017/blob/master/resources/day9-fellshard.txt at the first escaped quote

bhauman16:12:57

makes sense

borkdude16:12:18

aaaaaaaaaargh

borkdude16:12:51

so maybe my solution was correct to being with… let’s test

borkdude16:12:12

ok, so my first solution this morning was correct…

bhauman16:12:03

@borkdude @mfikes I mentioned this yesterday but have either of you tried TIS-100?

mfikes16:12:17

No. That looks interesting!

bhauman16:12:41

its way more fun than I expected

borkdude16:12:07

Sorry, not enough time for that right now 🙂

nooga16:12:08

I tried TIS-100

nooga16:12:16

it’s harder than it looks

nooga16:12:38

never finished it, requires lots of free time

bhauman16:12:52

@nooga yeah its not easy but I hurt my back the other day so i'm kinda stuck on the couch

bhauman16:12:41

and I was watching "Halt and Catch Fire" so I was a bit nostalgia driven

grzm16:12:48

They're all pretty close, though. Within 2 ms.

borkdude16:12:18

Maybe I should try instaparse

grzm16:12:29

It's pretty impressive how flexible spec is.

grzm16:12:23

What kind of speeds are you seeing with your spec solution?

borkdude16:12:24

yeah, but I think the data it’s generating for this thing becomes too big maybe?

borkdude16:12:45

@grzm Nothing yet. I can’t parse the whole input

borkdude16:12:51

Halting problem

grzm16:12:00

That makes sense. It's building up some sort of structure to be able to explain failures.

borkdude16:12:52

I love how you can just eval your boot file and it will pick up on new deps

thegeez17:12:17

@borkdude I think your specs are slow because the :content and :rab branches are not mutually exclusive because char? will also match rab. So it "blabla>yadayadayada" will parse as the whole string into :content first and then will need to backtrack

borkdude17:12:50

hmm yeah, how to improve that

thegeez17:12:20

replace char? with a more specific predicate, same for :children and :comma

orestis17:12:38

Hi all! I had to solve this in a real hurry today, here is my solution: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day9.clj

orestis17:12:17

Seems like similar to @nooga but with two functions for each state.

grzm17:12:48

@borkdude I've been eyeing your resource-reducible. I've been focusing on using more tranducers. Is that something you worked out yourself?

borkdude17:12:09

The link to the full blog post is at the bottom

grzm17:12:35

Ah! That post came up in my search for IReduceInit.

grzm17:12:02

One more piece to have in my back pocket. AoC, or rather, this community in AoC, has been really helpful for me. Thanks, all of you!

grzm17:12:06

And it's only Day 9 🙂

borkdude17:12:27

To be honest I didn’t really need it, line-seq or slurp is sufficient

grzm17:12:34

That may very well be the case, but if you didn't have it there, I wouldn't have been exposed to it. So regardless of whether you needed it, it served a purpose.

orestis18:12:08

Ah, I should have used letfn for my mutually recursive functions instead of pre-declaring them.

fellshard18:12:41

D'oh. Yeah, I should've considered the escaped quotes in my input 😞

fellshard18:12:52

I was wondering if someone would make a grammar for this, it's perfectly suited 😄

fellshard18:12:33

Instaparse looks really neat, should pick that up for one of these.

nooga19:12:02

funny, I’m writing a ghetto parser combinator lib atm

borkdude19:12:58

Inlined the grammar now, so you see the entire solution one file. See above link. Really happy with it 🙂

borkdude19:12:51

I think you could do the same with spec in hindsight as @thegeez said, more restricted rules/predicates. The nice thing with Instaparse is that you can hide tags and output. Not sure if that’s possible with spec. That would be nice in fact.

borkdude21:12:39

yes, I think it’s more or less the same thing (unless I’m missing something)

gnejs21:12:00

Howdy all 🙂. So.. day 9. I ended up with a couple of weirds constructs for dropping cancelled chars (and to drop garbage): https://github.com/metamorph/advent-of-code-2017/blob/master/adv2017/src/adv2017/day9.clj#L1 (`make-drop-!-xf`) where I use an atom to keep state in a filter. I'm thinking that there must be a better way of doing that (and still being "lazy"). Any suggestions?

borkdude21:12:53

@gnejs There is a possible solution with a single pass using a couple of values in a state with reduce

borkdude21:12:24

@mfikes also has one

gnejs21:12:51

@borkdude that's cool. 🙂 I was trying to split apart the concerns of "cancelling" and "dropping garbage" into separate transducers to avoid one big reducing function with all aspects mixed.

gnejs21:12:59

So my question is really - how do you implement a stateful filter (transducer-like) without resorting to using mutable state as I did?

mfikes21:12:17

@gnejs I think it is normal to keep state (usually using volatiles instead of atoms). See (source distinct)

gnejs21:12:55

@mfikes ah, cool. So it's not really an anti-pattern then 👍

mfikes21:12:30

I honestly don't know too much about it other than "stateful transducers have mutable state in them using volatiles"

gnejs21:12:41

Didn't know about volatile! before. Thanks for the pointer 👍 This seems to be pretty exhaustive explanation: https://stackoverflow.com/questions/31288608/what-is-clojure-volatile/31319731#31319731

mfikes21:12:26

Perhaps the reason is that there is no good way to thread a non-mutable state through. Like the step function inside the non-transducer version of distinct can do.)

grzm21:12:50

@thegeez yeah, it looks like there's a lot of goodness in xforms