Fork me on GitHub
#adventofcode
<
2018-12-10
>
nam.hyunwoo00:12:09

@mfikes At least you found a bug in core implementation. 😃 (BTW, I wish rrb-tree were under data.rrb-vector)

mfikes00:12:14

Ahh it is a known issue. https://dev.clojure.org/jira/browse/CRRBV-20 But now I can perhaps file an easier repro.

mfikes00:12:57

I added the failing AoC code to that ticket.

misha00:12:02

deque, p2 "Elapsed time: 2390.909256 msecs"

misha00:12:56

beware of calling (->> q (iterate f) (take x)) on mutable things kappa

misha01:12:36

@mfikes TIL rrb-vector. efficient concatenation that could have kept my room temperature lower

potetm03:12:29

K, loop/recur instead of reduce gets me down to 1.2s (from 2.6s)

potetm03:12:04

(still with homerolled circular doubly linked list)

theeternalpulse03:12:36

I'm in the penalty box for day 3 hoping it's not telling me I'm wrong just because of one character lol

theeternalpulse03:12:04

I can't think of why my algo doesn't work but I think it's the format of the id, we'll see in 4 minutes

potetm04:12:19

down to 500ms with ArrayDeque

mattly05:12:38

day 10 is kinda fun, there's not really an easy way to determine the correct answer programatically, you have to start printing output at some point

norman05:12:12

There is a way

gklijs05:12:37

I was wondering, you could probably have some 'statistic' like n alligned stars

gklijs05:12:56

Or maybe when there most close together?

mattly05:12:44

ok, that's fair

mattly05:12:32

I brute-forced it and simply printed anything with a certain compactness

norman05:12:24

I mean technically, I suppose it you could make an input where the right answer was one or two off from that, so there’s no guarantee, but it’ll certainly get you in the ballpark. And, in may case it was exactly right

mattly05:12:32

note I did say "easy"

mattly06:12:58

Oh I suppose you could just stop when it starts growing again

roman01la11:12:18

that worked from the first try for me, stopped once the width started growing 👌

norman06:12:26

What would be really fun, for another day, would be to write something that would find the local minimum more efficiently than stepping by 1

norman06:12:43

I wrote mine to take a range of steps and than checked each 1000 or so until I got in the area

mattly06:12:01

I waited until the height was less than 30

helios08:12:31

Yeah that was the easiest direction. I had it run for 100k iteration and saw what was the minimum distance, and I tried to print that. Luckily it worked at the first go, but otherwise I would have only printed the (hopefully not many) iterations in which the distance was less than a threshold.

helios08:12:11

The interesting bit is that this approach is far from being guaranteed to produce a good result. I wonder how you could "see" letters in the text 😄

norman06:12:54

seems reasonable. I used total area. I guess when you have to read a display out many, any heuristic that gets you there is valid

taylor06:12:41

I’m having trouble making any sense out of mine…

norman06:12:02

As in you aren’t converging to letters?

taylor06:12:43

yeah I went straight to a visualization approach w/Quil and I’m finding it hard to pick out the exact frame as things converge

fellshard06:12:13

I had an issue where all letters but the last were capital

fellshard06:12:20

... and the last letter was a lower-case 'L'

fellshard07:12:04

Also, is there a 'safe' way to use Quil from CIDER? I ended up hopping over and drawing everything to a PPM instead

taylor07:12:39

sorry, not sure

Average-user07:12:48

I've used quil with cider without problems. What do you think is unsafe?

fellshard08:12:32

Not so much unsafe as acting strangely. When I'd close the opened sketch frame, it would cause the repl to freeze up to the point I had to kill it, because emacs would stutter consistently while editing.

fellshard08:12:45

There was an error message in the minibuffer, I'll see if I can replicate it later.

taylor07:12:25

whew… in hindsight I should’ve used an algorithmic approach, wasted a lot of time tinkering with Quil to get scale/speed rate to be able to see the letters

fellshard07:12:42

Oh dear, you drew each step in Quil? 😬

taylor07:12:10

yeah but I put in a bunch of logic to control the speed and scale to make it easier to spot the message

taylor07:12:21

so a lot of steps get skipped

fellshard07:12:03

It would be neat to see the zooming happen, at least, hopefully we get to see the results 😄

taylor07:12:28

yeah, gonna polish it up and put it on YouTube and will post it here. Gotta go to bed soon though 💤

gklijs07:12:03

Quil seems cool to use for the problems, do you use it only for clj, or also cljs. For next year I might want to give that I try, used quil before for both java and javascript.

taylor14:12:22

I’ve only been running these on the JVM, but I’m not using any JVM-specific functionality so I think they should all be easily portable to CLJS

nam.hyunwoo10:12:21

made an animation for day10. very unattractive. 😖

taylor14:12:51

Very cool! Let me know if you post the code so I can compare approaches

nam.hyunwoo15:12:36

@U3DAE8HMG https://github.com/namenu/advent-of-code-2018/blob/master/src/year2018/day10.clj I've slightly changed easing fn in repo, still the algorithm is same 😄

taylor15:12:36

Thanks, learning some stuff from your approach

taylor15:12:52

I took a totally different approach to easing (knowing next to nothing about animation) https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/10.clj

nam.hyunwoo16:12:20

wow, thanks for your inspiring code!

nam.hyunwoo16:12:10

omg moving things were stars not elves 😱 (not reading a description is a bad habit)

helios10:12:16

why unattractive? i actually think it's pretty cool 😄

plexus11:12:50

Today was a great excuse to use a library I've been working on for building console UIs 🙂

plexus11:12:08

still a bit rough around the edges but you can already do fun things with it: https://github.com/lambdaisland/trikl/

norman14:12:04

Thanks. This looks quite amusing.

borkdude11:12:00

day 10 seems like fun. I’ll save it for later, short on time right now and my priority with AOC lies with keeping advent-of-cljc running

borkdude11:12:59

there was a memory issue because of the memoized state and delays that were built up in all the testing namespaces. now only new or changed solutions are tested on CI.

borkdude11:12:37

if anyone knows a neat trick to destroy namespaces after tests are finished to free up memory, I’m all ears

borkdude11:12:01

is this channel logged somewhere? I’d like to read the discussions after AOC is finished for the ones I didn’t get to yet

borkdude11:12:13

@plexus you had this logging thingy running right?

plexus11:12:51

Updates once a day I believe

borkdude11:12:15

@plexus I love terminal UIs. I got reagent working with react-blessed once: https://twitter.com/borkdude/status/1002623954320871426

plexus12:12:30

Very nice! I ended up writing Trikl after I got dissatisfied with Lanterna and wanted some in native clojure

pesterhazy14:12:33

looks amazing

taylor14:12:09

Thanks! I spent perhaps too long tinkering with it haha

meikemertsch17:12:40

I second the original statement. Thanks for making me smile

misha16:12:38

> (or (> width 80) (> height 10)))) kappa @mfikes

Average-user16:12:04

Don't remember if it was in 2016 or 2015, but there also was like this one

Average-user16:12:10

Like a grid that said something

taylor17:12:31

it reminded me of one from last year where you had to determine when some points w/velocities were going to stop converging or something, very similar input and algorithm but didn't involve finding a message from the points

Average-user17:12:16

How much time takes you part-1?

Average-user17:12:05

And also, has someone been able to transform the grid to a string with the word?

Ben Grabow19:12:26

Yep, there are two main steps to transforming to a string: 1. Group the stars by character 2. Convert each group into a character Stars that all belong to the same character will have contiguous x-values. (They will also have contiguous y-values, but characters are taller than they are wide, so it's cheaper to group by x. Once the stars are grouped, I made a simple stars -> character hashmap, and reverse-engineered what the stars pattern should be for each character. I only had 7 unique characters in my data set, so I only have 7 of 26 characters in my hashmap. Once I get borkdude's data I'll need to reverse engineer again and add some entries to my hashmap for my solution to work automatically with his input.

Ben Grabow19:12:44

Here's my method for grouping by x-position:

(defn left-most-x-neighbor [all-points point]
  (let [x-vals (into #{} (map first all-points))]
    (loop [x (first point)]
      (if (x-vals (dec x))
        (recur (dec x))
        x))))

(defn group-stars [stars] 
  (group-by 
    (partial left-most-x-neighbor stars)
    stars))

Ben Grabow19:12:09

This group-by pattern is something I've encountered a couple times now. "Start a group by unconditionally taking the first item in a seq. Continue adding to the group as long as (pred group new-item) is truthy. When it is falsy, start a new group with new-item instead."

taylor17:12:01

to write the code, or run the visualization? Took me a couple hours to get the answer b/c I immediately went for visualization approach w/Quil instead of finding a heuristic for convergence, and I had a lot to learn about dealing with visualizing big spaces w/Quil and controlling animation speed such that I could read the message which is only legible for a handful of frames. Part 2 was easy b/c I just added a hack atom to track passage of time in my draw function

misha17:12:02

. "Elapsed time: 3387.126557 msecs" part1 "Elapsed time: 3091.846753 msecs" part2 (same, but no drawing)

Average-user17:12:25

don't know what I'm doing wrong, but it takes me 13000 msecs

Average-user17:12:20

I think this would be all you need to know about my code:

Clojure
(defn step [points]
  (pmap (fn [[[x y] [vx vy]]] [[(+ x vx) (+ y vy)] [vx vy]])
        points))

(defn boundaries [points]
  (let [xs (map ffirst points)
        ys (map (comp second first) points)
        [maxx minx] [(reduce max xs) (reduce min xs)]
        [maxy miny] [(reduce max ys) (reduce min ys)]]
    [[minx miny] [maxx maxy]]))

(defn area [points]
  (let [[[x1 y1] [x2 y2]] (boundaries points)]
    (* (- x2 x1) (- y2 y1))))

(defn final-grid []
  (->> (parse-input)
       (iterate step)
       (map vector (range))
       (partition 2 1)
       (filter (fn [[[s p] [_ p']]] (> (area p') (area p))))
       (ffirst)))

Average-user17:12:19

Ohh the problem was pmap, now takes 5s

misha17:12:01

you pack/unpack a lot: (let [[[x1 y1] [x2 y2]] [[minx miny] [maxx maxy]] ;; (boundaries points)]

misha17:12:10

offtopic: (map vector (range)) can be just (map-indexed vector)

misha17:12:01

move velocities out as soon as you parse input. those do not change, and you pay all this packing/destructuring as a result

misha17:12:00

then you might want to (map area) before partition. now you calculate it twice for each frame

misha17:12:22

calculating maxx/maxy in one iteration will not hurt, now you scan all the points 6 times instead of once

misha17:12:36

map, map, reduce, reduce, reduce, reduce, instead of 1 tiny-bit-uglier reduce

misha17:12:19

also drop-while might return a bit earlier than filter

Average-user17:12:06

Thanks, calculating areas before partition makes a lot of sense, should have thought of that (hehe). drop-while instead of filter probably wont change much but I'll try it out anyway

Average-user17:12:30

Also, changed step and area to

(defn step [{:keys [points velocities] :as data}]
  (update data :points #(map (partial mapv +) % velocities)))

(defn bounds [{:keys [points]}]
  (let [xs (map first points)
        ys (map second points)]
    [[(reduce min xs) (reduce min ys)]
     [(reduce max xs) (reduce max ys)]]))
And makes the program slower

misha17:12:51

bounds still scans points 6 times opieop

misha17:12:41

(defn frame [[[x y] & points]]
  (reduce
    (fn [[x1 x2 y1 y2] [px py]]
      [(min x1 px) (max x2 px)
       (min y1 py) (max y2 py)])
    [x x y y]
    points))

Average-user17:12:47

Yeah ,I said that regarding your advice to separate points from velocities

misha17:12:45

I meant:

(defn tick [velocities points]
  (map (partial mapv +) points velocities))
...
(->> points
  (iterate (partial tick velocities))
...

misha17:12:11

but I doubt it affected performance, rather - readability

Average-user17:12:26

Haven't done day10 yet?

potetm19:12:32

I haven’t 😕 starting to get tired… 😛

potetm19:12:08

Have someone already talked about the trick to pre-calculate the time the letters show up?

potetm19:12:38

@quoll Informed me this morning.

taylor19:12:20

I think one heuristic is finding the point when the set of points' X/Y coords shrinks then starts growing again

potetm19:12:51

there’s a way to know almost for sure (no heuristic)

taylor20:12:15

i.e. when the coords are most aligned with each other

quoll20:12:19

Part 1: 34.33306 msecs Part 2: 8.483958 msecs

potetm20:12:23

even better

potetm20:12:36

answer in thread? @quoll

mattly20:12:41

ok you've got my curiosity

quoll20:12:51

my part 2 re-calculates everything, but I figure it’s warmed up

quoll20:12:01

After parsing the file into a seq of lists 4 numbers wide, I start with this:

quoll20:12:10

(let [[[_ y1 _ y1v] [_ y2 _ y2v]] data
        estimated-t (Math/abs (long (/ (- (Math/abs (- y1 y2)) 10) (- y1v y2v))))

Ben Grabow20:12:17

You can take two points with different velocities and do a closed form arithmetic calculation to find the time at which they pass each other in the x- or y-dimension. That will get you close within a few iterations.

Ben Grabow20:12:48

The larger the velocity difference, the closer you'll get to the actual time.

quoll20:12:17

you know that the final answer has every y-coordinate within 10 units of each other

mattly20:12:25

I've been meaning to level up my math

quoll20:12:58

it’s literally year 9 algebra (I know, because my son is in year 9, and I’ve been helping him with inequalities in recent weeks)

mattly20:12:00

they actually didn't specify the height, only implied it from the example

taylor20:12:04

why 10 units?

quoll20:12:53

that is true. In fact, the example was 8 high. I started by using an inequality of 8. It still gave a very good estimate

mattly20:12:02

I got a C in Algebra 30 years ago

misha20:12:18

I think it's still a magic number

quoll20:12:22

but then I saw that the result was 10 high, so I updated my code to have 10 instead of 8 😄

misha20:12:56

by all means, use it to get yourself higher on a scoreboard, tho. but as soon as we are taking time to optimize for speed, – it's a magic number

potetm20:12:02

Every example I’ve seen was 10. But, yeah, it’s an assumption.

taylor20:12:06

I think that works perfectly fine for this problem but it's not a general solution (which doesn't matter for AoC but y'know)

mfikes20:12:13

Then you skip several thousand iterations?

quoll20:12:02

when the number was 8, my estimate was 10519. When the height is set to 10, the estimate came in at 10510. The final answer for my data was 10511

misha20:12:35

you can try to optimize against (+ guess-algo-time wrong-answer-timeout) opieop

Ben Grabow20:12:07

If you want a solution without a magic number, find the time at which two points pass each other in y, then iterate both backwards and forwards in time until you find the minimum y-height. The algorithm will be entirely based on the input data, no magic numbers.

quoll20:12:19

if I presumed that the height was 1, then the estimate was 10508. So my presumed height really didn’t matter

quoll20:12:55

Letters cannot be smaller than 1, so that’s reasonable, and does not include a magic number

misha20:12:39

I think there might be some inputs which would not work, like if text is sideways (since it was probably for human eyes anyways)

Ben Grabow20:12:10

@quoll Is there a way you check that the convergence hasn't already passed?

quoll20:12:17

no, but it would make the estimate come in further away from the final result

misha20:12:37

but yes, min area, or height, etc - is a very good approach, I think

quoll20:12:33

I increment the time, and compare the area of the points. If it’s larger, then I start going back in time. If it’s smaller, then I go forward in time. I keep iterating while the area gets smaller. As soon as it starts to get larger again, I’ve found my minimum area

misha20:12:52

I imagined an input which 1st crosses over itself, and then aligns. that would throw off min-area heuristic a bit

quoll20:12:10

I tested by pushing my “estimate” smaller and larger, and it moves in the correct direction each time

misha20:12:37

I mean 5 4 3 2 1 2 3 result instead of 5 4 3 2 1 result

mattly20:12:54

fortunately they didn't throw that at us

quoll20:12:05

@misha I did consider that it’s possible for it to have a minimum area that wasn’t the solution.

quoll20:12:28

But I cheated, and ran through the renderings by hand before I automated it 😜

misha20:12:35

I did (consider) too, but when I saw an accepted answer I just chilled kappa

misha20:12:08

but my rendering is sideways :D

quoll20:12:11

It’s also possible (though unlikely with integer velocities) to have every point occupy a single point at some time

misha20:12:20

I put points count asserts in each frame, but did not commit it into git eventually

quoll20:12:07

To be honest…. I got my initial estimate by hand

quoll20:12:05

when I went to bed last night, the puzzle had been published, so I looked it up, then put my phone down and tried to sleep. But then I started thinking about how the final rendering must have all the y-coordinates within a small range (was it just one line? Multiple lines?). Anyway, it was too much for me, and pulled my phone back out, grabbed a couple of numbers from my input, and did the algebra. That gave me the number 10519. That’s the number I started with this morning. And my answer was at 10511

quoll20:12:31

I do like it when you can shortcut a whole lot of the work with a little bit of math

quoll20:12:14

it makes me feel smart :female-student::zany_face:

mattly20:12:30

that's one of the fun things about these puzzles, is how flexible you can be at arriving at the solution

mattly20:12:00

and it's fun watching the different approaches people take to get there

Average-user20:12:13

I did https://adventofcode.com/2017/day/7 (part1) with the searching feature (ctrl+f) of chrome in a couple of seconds. Sadly I was doing it the day after so I didn't get in the leaderboard

genmeblog20:12:31

My estimate is like that (long (* 0.99 (/ extent vextent)))

genmeblog20:12:53

where extent is maximum absolute coordinate value and vextent same for speed

quoll20:12:46

oh, someone just reminded me of another approach that I considered, but am glad I didn’t spend time on… The roman alphabet has lots of vertical lines (my solution has 16 vertical lines of length 3 or greater. 4x length 3, 1x length 4, 1x length 5, 1x length 8, 9x length 10). My other way of looking was to look for vertical lines in the rendered field. However, unlike the “minimum area” approach, it wouldn’t tell me if I was going in the right direction when I went forward to backward in time. (Not a huge deal, given the accuracy of estimating the time). Luckily, while looking at the various renderings, I saw the area converging to the minimum, so I didn’t waste time on that

taylor21:12:29

am I remembering correctly last year there was a problem that was possible to solve by equation, but the most obvious solution was simulation

quoll21:12:14

this sounds familiar

quoll21:12:08

day 22 was a simulation of a processor with a small instruction set, which was solved by simulation

quoll21:12:37

day 23 used the same instruction set, but multiplied 2 large numbers with the multiplication algorithm of:

a*b => if b = 1: a
       else: a + a*(b-1)
and
a+b => if b = 0: a
       else: (a+1) + (b-1)

quoll21:12:21

I think that was it. Anyway, it just needed you to multiply the numbers. But you had to decode what it was doing before you knew that was what you were attempting

quoll21:12:01

simulating it was going to take years

taylor21:12:13

yeah I'm looking at my solution for that and remembering having to essentially turn the assembler instructions into C-style code so I could write equivalent Clojure before refactoring it https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2017/23.clj

Average-user21:12:17

have you done year 2016?

taylor21:12:25

looks like I only did the first few days

magic_bloat21:12:02

I looked at my input numbers, and noticed that all the ones around with coords at 50000 had velocities at -5, and so on for 40000, -4 and 30000, -3 etc.

magic_bloat21:12:23

So I fast forwarded to 10000 seconds and ran the visualization from there.

mfikes21:12:21

Yeah, it also appears that all of our answers are 10,000 + n where n is in the range of a few hundred

mfikes23:12:10

If you are solving these problems in ClojureScript (and in particularly via Advent of CLJC), there are a couple of new utilities, nth’ and count’ that you might find useful for lack of locals clearing. This makes a difference of 200 MB vs 3 GB for today’s solution (at least in the way I did it.)

Ben Grabow23:12:31

Someone is compiling layout of known characters for d10. Useful if you want to do programmatic identification of your message. https://www.reddit.com/r/adventofcode/comments/a4tbfl/trying_to_collect_all_used_letters_for_character/ https://gist.github.com/usbpc/5fa0be48ad7b4b0594b3b8b029bc47b4