Clojurians Log v2

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

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

I added the failing AoC code to that ticket.

deque, p2 "Elapsed time: 2390.909256 msecs"

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

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

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

(still with homerolled circular doubly linked list)

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

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

guess not 😞

down to 500ms with ArrayDeque

A transient vector wouldn't do it? I might give it a try with transient vectors. I don't think it should be a lot slower then Java.

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

There is a way

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

Or maybe when there most close together?

heh, yeah

ok, that's fair

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

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

note I did say "easy"

😛

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

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

Yeah

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

I waited until the height was less than 30

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

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

As in you aren’t converging to letters?

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

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

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

😐

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

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

sorry, not sure

Oh dear, you drew each step in Quil? 😬

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

so a lot of steps get skipped

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

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

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

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.

My day 10: https://github.com/pesterhazy/advent2018/blob/master/src/advent/puzzle10.clj#L65

made an animation for day10. very unattractive. 😖

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

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

https://github.com/plexus/advent-of-code/blob/master/src/advent2018/day10.clj

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

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

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.

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

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

@plexus you had this logging thingy running right?

https://clojurians-log.clojureverse.org/adventofcode

Updates once a day I believe

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

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

My solution for Day 10 https://github.com/benfle/advent-of-code-2018/blob/master/day10.clj

Thanks. This looks quite amusing.

day 10 visualized w/Quil https://www.youtube.com/watch?v=4YtCXEalgTw

looks amazing

Thanks! I spent perhaps too long tinkering with it haha

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

@taylor 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 😄

Thanks, learning some stuff from your approach

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

and the code https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2018/10.clj

Day 10 https://github.com/mfikes/advent-of-code/blob/master/src/advent_2018/day_10.cljc

wow, thanks for your inspiring code!

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

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

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

Like a grid that said something

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

Yeah me too

How much time takes you part-1?

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

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

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

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

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)))

Ohh the problem was pmap, now takes 5s

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

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

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

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

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

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

also drop-while might return a bit earlier than filter

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

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)]]))

I second the original statement. Thanks for making me smile

bounds still scans points 6 times :opieop:

(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))

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

I meant:

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

but I doubt it affected performance, rather - readability

right

for the interested: https://www.twitch.tv/timpote

Haven't done day10 yet?

Anyways here is my Day10, thanks @mishafor the insights https://github.com/Average-user/adventofcode-clj-2018/blob/master/src/adventofcode_clj_2018/day10.clj

I haven’t 😕 starting to get tired… 😛

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.

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))

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."

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

@quoll Informed me this morning.

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

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

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

Part 1: 34.33306 msecs Part 2: 8.483958 msecs

even better

answer in thread? @quoll

ok you've got my curiosity

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

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

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

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.

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

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

I've been meaning to level up my math

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)

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

why 10 units?

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

I got a C in Algebra 30 years ago

I think it's still a magic number

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

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

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

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)

Then you skip several thousand iterations?

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

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

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.

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

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

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

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

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

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

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

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

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

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

fortunately they didn't throw that at us

true )

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

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

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

but my rendering is sideways :D

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

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

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

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

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

it makes me feel smart :female-student:🤪

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

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

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

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

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

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

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

this sounds familiar

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

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)

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

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

simulating it was going to take years

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

have you done year 2016?

looks like I only did the first few days

https://github.com/taylorwood/advent-of-code/blob/master/src/advent_of_code/2016/

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.

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

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

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.)

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

🙂