Fork me on GitHub
#adventofcode
<
2016-12-09
>
bhauman02:12:21

one thing I'm doing is really looking at medley https://github.com/weavejester/medley/blob/master/src/medley/core.cljc sure to come in handy

samueldev02:12:39

I’m scratching my head as to why many of these aren’t in clojure.core

bhauman02:12:31

assoc-some is a really good one

bhauman02:12:11

hows the weather up there?

samueldev02:12:46

for real, assoc-some, deref-swap!, dissoc-in

samueldev02:12:16

weather up here: cold. -10C (14F). fireplace is on and working on some cljs so can’t complain 🙂

bhauman02:12:03

its cold here today as well 0C

bhauman02:12:28

you live in Fredericton?

bhauman02:12:42

I'm looking on the map

samueldev02:12:59

I do! about 10 minutes outside of town

bhauman02:12:37

and its anglophone mostly?

samueldev02:12:54

it’s an anglophone bastion in an otherwise bilingual-or-french-focused province, yep

bhauman02:12:18

It's actually a pretty good looking town

bhauman02:12:49

I grew up in new england

bhauman02:12:58

Connecticut coast line

samueldev02:12:17

it ain’t half bad 🙂 a little on the conservative side for my liking....

samueldev02:12:25

otherwise great

samueldev02:12:32

and new england is great

samueldev02:12:23

unrelated: my colleague Angus Fletcher is doing AoC as well - https://github.com/angusiguess/advent-of-code2016 - he says you and he met in an elevator one time, not sure where haha

bhauman02:12:30

@fellshard ^ pin away!

fellshard02:12:30

You, too, have the power to pin in the palm of your hand :)

bhauman02:12:51

really! I had no idea!

samueldev02:12:00

private leaderboards are perhaps the best addition to AoC this year

samueldev02:12:36

compete with your friends rather than.... fail to get in the top 100 every day 😛

bhauman02:12:54

thats sweet!!

bhauman02:12:33

so when you say its a bit conservative ...

bhauman02:12:54

you mean social interactions? politically?

bhauman02:12:07

or in that rural provincial way?

samueldev02:12:08

politically, in that rural provincial way. anecdote: there was a small chance that a strip club was going to open up. in order to thwart such an endeavor, the city swooped in and paid the lease on the empty building in question to eliminate the option. they are still paying that lease on that empty building to this day.

fellshard02:12:15

Isn't that what zoning laws are usually for? Hah. That's a painful way to solve a problem.

samueldev02:12:27

^ yeah the taxpayers agree. lol.

samueldev02:12:46

:shrug_emoji:

bhauman02:12:04

well they could at least be paying the strippers with that money...

bhauman02:12:34

it was a joke that I'm sure has been made many times up there

samueldev02:12:58

it wasn’t a small sum of money either; something like $500,000 for 5 or 10 years of empty building or something

bhauman02:12:08

holy crap!

bhauman02:12:31

so all you have to do if your building isn't rented ...

samueldev02:12:53

bahahaha I hadn’t considered that path

samueldev02:12:05

not a bad idea

samueldev02:12:52

(this particular building is right in the heart of downtown, so I suspect that’s why they are willing to go the distance to prevent it from happening)

bhauman02:12:26

yeah but geez the could have started a tech incubator, 3d printing shop, or something

bhauman02:12:46

office space for start ups

samueldev02:12:57

yeah im puzzled as to why it’s not… something… yet

samueldev02:12:07

one could argue a strip club as a form of tech incubation

bhauman02:12:39

oh really ... the town is THAT backward

bhauman02:12:36

It really is a nice looking town

samueldev02:12:06

though I’ll admit that my particular employer has done nothing but irritate me for lack of willingness to adopt cljs (even though our entire backend is clojure)

samueldev02:12:17

so maybe not the best employer for, you know, the author of figwheel

fellshard02:12:55

Employers are prickly things

fellshard02:12:10

There's always the 'introduction by insubordination' tactic

fellshard02:12:24

"Well, too bad, because XYZ is already using it >:)"

samueldev02:12:40

Haha I’ve seriously considered that approach

fellshard02:12:50

(I have yet to pull this off, because consulting is very, very difficult to pull that off with)

fellshard02:12:06

Structured consulting firm, not freelance

samueldev02:12:54

all of the above said WRT conservativeness @bhauman : it’s also a university town where the students make up something like 25% of our population during the school year, so there’s no small amount of more modern mindsets around

samueldev02:12:59

i tend to surround myself with those groups 🙂

bhauman02:12:15

the rotate-vec method is still bothering me

bhauman02:12:34

(defn rotate-left [v i]
  (let [c (count v)]
    (vec (take c (drop (mod i c) (cycle v))))))

fellshard02:12:56

What's bugging you about it?

fellshard02:12:27

I noticed one of the pinned ones was pretty compact, it just concated take and drop.

samueldev02:12:44

^ big fan of that

fellshard02:12:57

(defn shift
  [l n]
  (let [n (- (count l) n)
        [first-part second-part] (split-at n l]]
    (vec (concat second-part first-part))))

fellshard02:12:19

I have a big soft spot for destructuring. This is what happens when you learn ML... >_>

fellshard02:12:58

But probably not worth it at that point, just yak shaving

bhauman03:12:04

what about transients?

fellshard03:12:54

I've not used them yet. How would you apply them here?

fellshard03:12:43

Ahh, think I see. You'd perform mutations on the screen using transients, since the intermediates don't need to be used elsewhere.

bhauman04:12:04

(defn rotate-left [v x]
  (let [v (vec v) c (count v) offset (mod x c)]
    (loop [i 0 accum (transient [])]
      (if (= i c)
        (persistent! accum)
        (recur (inc i) (assoc! accum i (get v (mod (+ offset i) c))))))))

bhauman04:12:29

so here is a more traditional imperative rotate

bhauman04:12:46

and ... simple benchmarking shows little difference

fellshard04:12:03

With a structure this size, yeah. Would probably make some difference with more operations / a bigger 'screen'.

bhauman04:12:11

oh shoot, transducers rock it though

bhauman04:12:33

(defn rotate-left2 [v i]
  (let [c (count v)]
    (sequence (comp (drop (mod i c)) (take c)) (cycle v))))

bhauman04:12:59

4 times as fast

samueldev05:12:12

todays problem doesn’t seem overly hard

samueldev05:12:22

but as I haven’t done yesterdays, ill have to do both later

fellshard06:12:44

I'm at a total loss today, I get completely different results when I paste today's string in raw than when I suck it in through a file. (the latter totally not being recognized by regexes even though it works fine when tested by hand)

fellshard06:12:54

And the former not giving a correct answer.

samueldev06:12:56

oh snap. you mean day 9?

samueldev06:12:13

if you’re having a hard time, then I feel as though I may have drastically underestimated the problem :^

fellshard06:12:49

It's not that hard, no

fellshard06:12:57

Finally got it, but was being stymied by technical issues

fellshard06:12:08

Will have to dig into it later 😐

fellshard06:12:42

Holy moly, parinfer deals strangely with parentheses in any position

fellshard06:12:57

Can't tell if it's parinfer or proto repl actually

fellshard07:12:18

.... /sigh. Okay, lesson learned. Good ol' re-matches was stymied by the newline at the end of the input.

abarylko07:12:51

Same thing 😊

fellshard07:12:35

Time to start using re-find instead...

fellshard07:12:03

Given how often this seems to happen in these coding challenges, maybe I should come up with a quick set of parsing methods for easy utility...

abarylko07:12:25

it's hard to say... but maybe worth it

abarylko07:12:34

like parse numbers with separator

abarylko07:12:00

though sometimes it depends how you use it...

fellshard07:12:03

More like 'lop off this pattern from the beginning, hand me the matched groups and the remainder of the string'

fellshard07:12:12

Very dumb greedy parser

abarylko07:12:22

yes, one the regex libraries in haskell has exactly that

mnespor14:12:58

Don't do what I did. Mine takes more than three hours to run 😕

bhauman16:12:27

well all the test cases pass, and everything seems correct, but says I have the wrong answer

bhauman16:12:46

oooops found a bug

bhauman16:12:05

by the way I used trampoline for easy recursive parsing

fellshard16:12:07

mnespor, for the last one, do you build out a string still or do you just consume the string and find the length?

fellshard16:12:35

The recursion depth doesn't require trampoline, though I did end up using mutual recursion...

mnespor16:12:56

I just consume the string and find the length. Tail call optimization turned the recursion into a loop for me

fellshard16:12:16

You only have to go as deep as any grouping of repeater tags ends up nesting.

mnespor16:12:33

I consume characters until the first marker, drop the marker, and push its expansion back into the input

bhauman16:12:01

(def data (string/trim (slurp (io/resource "day9.txt"))))

(defn parse-dir [d]
  (let [[_ directive & args] (re-matches #"(\((\d+)x(\d+)\)).*" (apply str d))]
    (cons (u/to-ints args) (list (drop (count directive) d)))))

(defn parse-directive [d]
  (let [[[cnt rpt] xs]  (parse-dir d)
        part            (take cnt xs)]
    [(apply concat (repeat rpt part))
     (drop cnt xs)]))

(defn parse* [accum d]
  (cond
    (empty? d) accum
    (= (first d) \() (let [[res rst] (parse-directive d)]
                       #(parse* (vec (concat accum res)) rst)) 
    :else #(parse* (conj (vec accum) (first d)) (rest d))))

(defn parse [d]
  (trampoline parse* [] d))

bhauman16:12:20

that's what I have so far haven't looked at the second part yet

fellshard16:12:22

In the end you're building a string that's hundreds of thousands, if not millions of characters long

fellshard16:12:54

I'm guessing you're shuffling your heap quite a bit trying to allocate new strings

fellshard16:12:16

Consider this: inside of a repetition tag and the region it affects, do any of the tags have any influence on characters outside of that region?

fellshard16:12:33

(Hmm, there's actually nothing in the specification that guarantees that...)

mnespor16:12:13

I think so?

fellshard16:12:19

I'm pretty sure they only generate input that satisfies the above. It could be I got a lucky input, but that seems like a constraint they intended to add, given the 'not enough memory to decompress' comment.

mnespor16:12:21

In this case, the first (9x2) ends at E, but the nested (9x2) covers up to I:

(9x2)(9x2)ABCDEFGHIJ
(9x2)ABCDE(9x2)ABCDEFGHIJ
ABCDE(9x2ABCDE(9x2)ABCDEFGHIJ
ABCDE(9x2ABCDEABCDEFGHIABCDEFGHIJ

mnespor16:12:56

I don't think any of the real inputs split a marker like that, however

mnespor16:12:23

(wasn't there a puzzle last year that asked you to tailor your solution to your input instead of solving the general case?)

fellshard16:12:01

I don't recall, but that implicit constraint is almost necessary to make the problem work as desired here.

mnespor16:12:14

There's almost certainly a constraint that forbids inputs like (5x3)(5x3)A

bhauman16:12:06

yeah that would be insane

fellshard16:12:24

I mean you could still have an algorithm that does that, and just assumes you'll return to the original string to consume when you run out of characters in the current region... but at that point you're in this really weird state, where the order of evaluation doesn't actually make sense....

bhauman16:12:00

hmmm wait a minute it looks like processing it backwards may be equivalent for problem 2

fellshard16:12:51

Actually yeah, order of execution is more important

fellshard16:12:26

Consider (9x2)(5x2)abcde

fellshard16:12:07

Do you get (5x2)abcd(5x2)abcde, or (9x2)abcdeabcde?

fellshard16:12:27

(well, ignoring the parenthesis overlap, but you get the idea of how this could play out)

mnespor16:12:06

What might that look like? It's probably not enough to seek backward to the first marker:

(5x3)(5x3)AAAB
(5x3)AAAAAAAAAAAAAAAB
AAAAAAAAAAAAAAAAAAAAAAAAAB

fellshard16:12:09

I think they tailored the input such that you don't have to worry about boundary crossing like that, too much ambiguity involved

bhauman16:12:46

I think backward may be equivalent in this case

bhauman16:12:09

(=   (parse   (concat  "(10x2)"  (parse "(5x2)abcde")))
       (parse2 "(10x2)(5x2)abcde"))

fellshard16:12:23

It won't be. (5x3)(5x3)AAAAB would expand to (5x3)(5x3)(5x3)AAAAB if evaluated from the left, and that clearly blows up

fellshard16:12:27

So they can't hand you input like that

fellshard16:12:49

Expanding from the right leaves you with AAAAA...AAB

mnespor16:12:50

oh, so the real inputs could be equivalent backward

bhauman16:12:42

if there isn't boundary crossing

bhauman16:12:13

but that is a long shot

mnespor16:12:08

Is this boundary crossing? (6x3)(1x3)A

fellshard17:12:02

It's boundary crossing if the inner input consumes characters beyond the outer input

fellshard17:12:50

(1x6)(2x2)ABCD

mnespor17:12:50

Oh, I get it

fellshard17:12:16

(1x6) only extends through A, (2x2) extends beyond A necessarily

mnespor17:12:33

That makes working backward complicated. (6x3)(1x3)A is valid forward, but not backward

fellshard17:12:43

A. I don't think they gave inputs like that

fellshard17:12:58

B. The examples they give work left to right, outer to inner, and I think that's an intentional cue

mnespor17:12:03

interesting

fellshard17:12:20

So it should be equivalent to the 'expand single tag and prepend the result' method

fellshard17:12:38

But you can chop out a bunch of work assuming that the boundary is never crossed, since that leads to absurd ambiguities in the spec

fellshard17:12:01

From the spec for part 1: > To decompress this marker, take the subsequent 10 characters and repeat them 2 times. Then, continue reading the file after the repeated data.

bhauman17:12:49

backwards doesn't work 😞

bhauman17:12:25

now I don't why I thought it did

bhauman17:12:39

its obvious why

bhauman17:12:37

now I'm obsessed with getting it to run fast...

fellshard17:12:32

My next move would be to quit bouncing between seqs and strings and using regexes, and just manually chew through the character stream instead

fellshard17:12:56

But even as I have it now, string conversions and all, the calculation time is very short

fellshard17:12:18

So that's more a memory usage optimization than anything

andrew.sinclair19:12:42

Hey I was a bit late to start todays... I'm on part 2 and I'm wondering if we are agreeing or not whether the boundaries can overlap?

andrew.sinclair20:12:38

It seems you could just parse it recursively if you don't allow overlap. That would be nice...

fellshard20:12:33

Based on a sample set of one - my own - I don't believe they intended for boundaries to overlap, no.

andrew.sinclair20:12:01

I see, thank you.

andrew.sinclair22:12:48

The part I don't understand is, "The puzzle is about trying to get the user to do some kind of recursive expansion". But can you assume recursive expansion will work? I thought, "You can't"

bhauman23:12:47

so for me memoization was the key trimming all that computation, I had a crazy input

bhauman23:12:30

my expansion was 10gigs: 10,931,789,799

bhauman23:12:46

and I had to count and not accumulate

bhauman23:12:51

the result

samueldev23:12:33

10 GIGS? holy cow

bhauman23:12:59

I think I have that right my answer was 10,931,789,799 characters

bhauman23:12:13

yep thats 10 Gigs

bhauman23:12:49

this would have been better as a bash script

bhauman23:12:18

my solution runs in 4 seconds

fellshard23:12:33

Yeah, exactly

fellshard23:12:37

Don't expand - just tally

fellshard23:12:36

Since no boundaries are crossed, you can safely say 'recursively count the decompression of this tag's region. Now multiply by this tag's number of repetitions.'

fellshard23:12:06

The recursion level is pretty flat for most inputs I'm guessing, so very little stack problems and you can deal with finite chunks of the input at a time.

bhauman23:12:41

well that was a bastard, I remember this pain from from last year now...