Fork me on GitHub
#adventofcode
<
2018-12-12
>
ben.grabow00:12:01

There's some really beautiful symmetry in creating the summed area table:

(defn summed-area-table [colls]
  (->> colls
       (map #(reductions + %))
       (reductions #(map + %1 %2))))

lucaspolymeris02:12:50

what would it colls be here?

ben.grabow02:12:58

(for [y ys]
  (for [x xs]
    (f x y)))
Rows nested in columns, basically.

ben.grabow02:12:48

On mobile right now so apologies for any errors in that code.

minikomi05:12:58

shit.. forgot this was going on hahaha

minikomi05:12:08

having fun everyone?

mattly05:12:22

anyone have a strategy for part 2? 😄

mattly05:12:43

crap, there are people who've done it already

mattly05:12:54

there must be some super-efficient algorithm for this

mattly05:12:58

ah, apparently the pattern stabilizes

taylor06:12:17

just started on this one and I don’t understand how to handle the negative range?

taylor06:12:28

does it go on forever?

mattly06:12:32

got me really good

mattly06:12:51

at least in theory

taylor06:12:47

so in both directions, you have to find when the pattern stops producing new plants or something?

taylor06:12:14

not very well described problem

mattly06:12:35

it could have been clearer

fellshard06:12:03

It's weirder than 'stops producing new plants...' at least with my input

mattly06:12:54

so, part 2 asks you to solve for 50 billion iterations

mattly06:12:17

i'm "cheating" for the first time and checking reddit

mattly06:12:25

most people aren't simulating it

lucaspolymeris06:12:06

last year there was a similar problem, where the solution was to find a cycle

mattly06:12:52

yeah, indeed

norman06:12:44

ugghh.. done.. I disliked this problem a lott

lucaspolymeris06:12:20

how did you do it?

norman06:12:23

.. in a very non-robust manner. At first I storing the prior states looking for a repeat. No exact state repeated, but it when I normalized (removed the leading/trailing dots) it repeated with a cycle length of one.

fellshard06:12:45

Thanks for the tip, mattly ^^

norman06:12:47

So, then under the assumption that I had this end condition, once I duplicated the state, I was able to advance immediately to the final 50b state (just shifting the pattern out)

fellshard06:12:23

This one pretty much depends on reaching a fixed point, yeah. The offset changes, but the pattern fixes.

fellshard06:12:02

That's often the case when they throw giant numbers at you; usually that's a hint you're missing an optimization in how you approach the problem.

norman06:12:46

I don’t consider this an optimization. It feels more like side-stepping the problem to efficiently solve only the given input. Is there a guarantee we’ll always hit a cycle? Maybe - I dunno. Will it always manifest like this? I suppose with some deep thought I could answer that? In the end, I don’t feel like I wrote useful code - I just used some code to help me solve a single instance of a puzzle. That’s not very satisfying to me. (but I realize that’s how most of the top leaderboard operates overall)

fellshard07:12:01

Pretty sure you'd be waiting a loooong time running each generation by hand. It's expected the inputs are designed to reach some fixed point like this, just because any that diverge would be infeasible to solve for a challenge like this.

norman06:12:39

Oh, and just for amusement, before I searched for a pattern repeat, I searched for a score (sum of plant positions) repeat. I got several nonsensical repeats, and it took me a few minute to realize that there were many un-related patterns that could produce the same score. So then moved on to tracking the patterns

mattly07:12:25

I ended up looking for a repeat of the difference in sums

taylor07:12:37

this is what I’m currently trying but I must be missing something b/c I don’t see a repeat

taylor07:12:42

hmm yeah just solved part 2 by finding the repeated pattern (started @ ~100 generations for me) and extrapolating the repetitive score difference to 50B

ihabunek13:12:12

just spent half an hour debugging the program and then discovering i was running on sample input instead of my input 😢

ihabunek13:12:33

today was familiar to anyone who played last year, pattern searching

ihabunek13:12:56

Part 1 "Elapsed time: 20.185556 msecs"
Part 2 "Elapsed time: 102.438381 msecs"

misha14:12:41

.

p1 "Elapsed time: 5.678204 msecs"
p2 "Elapsed time: 43.402724 msecs"

misha14:12:34

@taylor same

taylor14:12:25

curious to see what data structures people used to represent the pots. I used a map where the keys where the pot numbers and it made the logic pretty easy

misha14:12:25

(->> generations (drop 102) kappa

taylor14:12:45

:man-shrugging:

taylor14:12:56

REPL-driven development

ihabunek14:12:05

@taylor I used a sorted set containing indexes of full pots

ihabunek14:12:30

it made detecting patterns very easy

ihabunek14:12:49

just (map - next-gen current-gen)

misha14:12:53

transient {pot-idx <"#"|".">} e.g. {-1 "." 0 "#" ...}

ihabunek15:12:03

what is that 😄

misha15:12:39

transient map + sort keys turned out to be faster than sorted-map

lucaspolymeris15:12:31

I used something like (map rules (partition 5 1 pots) ) to get new generations

misha15:12:02

I started with it, but after 1st wrong answer, I realized I need to track pot indexes kappa

misha15:12:18

also, if you don't shrink, and equilibrium is few 100k iterations away - you are in trouble

lucaspolymeris15:12:05

I do track them:

(defn next-generation [pots rules]
  (->> pots
       (partition 5 1)
       (map #(let [r (rules (map second %))
                   i (first (nth % 2))]
               (if (nil? r) [i \.] [i r])))))

misha15:12:28

but what is pots?

misha15:12:47

sorted-map? sorted-set?

lucaspolymeris15:12:03

(map-indexed vector "....#...###...##")

misha15:12:14

does this assume pots don't expand below 0?

misha15:12:28

either code is to dense or I am kappa

lucaspolymeris15:12:30

No, I add some \. to the start and the end on each generation

lucaspolymeris15:12:41

I didn't post that, sorry

misha15:12:59

and you dont clean up those paddings?

misha15:12:45

first, I added pads w/o shrinking, and boiled my CPU opieop

lucaspolymeris15:12:11

Yeah, not sure how to shrink

lucaspolymeris15:12:46

Mine is something like

(defn shrink [pots]
  (if (= '(\. \. \.) (map second (take 3 pots)))
    (recur (rest pots))
    pots))

misha15:12:19

I used indexes because I already had them in client fn, and did not want to pay reverse for shrink-right

misha15:12:01

and I had them because I did not want to pay sort for map before each iteration

misha15:12:34

m! is {-1 "." 0 "#" ...}

misha15:12:23

I am sure it has some off-by-1 error in there, but meh ¯\(ツ)

misha15:12:02

but all of this does not really matter If equilibrium is just few hundred iterations away opieop

lucaspolymeris15:12:32

(time (vector (part-1) (part-2)))
"Elapsed time: 161.300258 msecs"
[3890 4800000001087]

lucaspolymeris15:12:47

Ended up with that, fair timo to be using just lists

lucaspolymeris15:12:32

Has someone prove that there always will be an equilibrium?

ben.grabow21:12:00

I tried 10,000 trials of a random initial state of 100 pots through my rule set and got a converging answer each time. So it seems the convergence is not dependent on the input pattern. It may indeed be possible to prove convergence based on only the rule set.

fellshard21:12:05

That's not unlikely, as specific automata can have such proven properties, I think.

misha15:12:23

I printed like 1000 of steps, it never changes, just drifts to the right (for me)

meikemertsch17:12:40

Yepp, it’s useful to look at your data

misha15:12:34

I thought it would fluctuate, like gliders in game of life

misha15:12:23

and started with a loop to track anything seen to detect loops, but then printed it, and saw there is just a shift, no loops

namenu16:12:10

https://github.com/namenu/advent-of-code-2018/blob/master/src/year2018/day12.clj I've encoded rules into binary digits (e.g. .#.#. -> 10), and looped through pots with five bits window.

borkdude21:12:01

Advent of CLJC will now store times from comitted days and print an overview of times of solutions for committed days: E.g: https://circleci.com/gh/borkdude/advent-of-cljc/375

==== Scores:
  year | day | time | username | environment |  test  
------+-----+------+----------+-------------+--------
 2018 |   1 |    0 | borkdude | jvm         | part-1
 2018 |   1 |   31 | borkdude | node        | part-1
 2018 |   1 |  156 | borkdude | jvm         | part-2
 2018 |   1 |  329 | borkdude | node        | part-2

borkdude21:12:06

@ben.grabow I see there is an issue with my ssh command when building a PR. I’ll fix that now and let you know

ben.grabow21:12:26

No worries. Tell me if you need me to do anything on my end.

borkdude21:12:49

Fixed. Can you rebase or merge with master and then update the PR?

borkdude22:12:38

Seems to work now?

ben.grabow22:12:15

Yeah, looks great. I don't see a table summarizing the times though. Should I?

borkdude22:12:49

No, not in PRs, since the private key of my server is needed for that and PRs can’t access that

borkdude22:12:57

but once I have merged it to master, you will

borkdude22:12:01

so shall I?

ben.grabow22:12:07

Sure go ahead!

borkdude22:12:10

crap, there’s still an error, I will fix

magic_bloat22:12:05

the pots were two infinite lazy lists for me - one representing postive numbered pots, one representing negative numbered pots. The negative pots were in "reverse" order, -1, -2, -3, -4, -5

magic_bloat22:12:49

however negative points weren't really needed, my pattern moved rightwards, apart from a few exceptions at the start.

fellshard22:12:32

I think they were mostly needed to ensure pot 0 had known empty pots to its left at the beginning. You say it did dip below 0 briefly?

taylor22:12:03

mine definitely went negative for a few generations but after that went straight positive

ben.grabow22:12:57

I considered doing something like that but shuddered at the thought of coding the step function near the origin. How did you handle it?

magic_bloat22:12:06

actually not too tricky:

magic_bloat22:12:11

(defn evolve-lhs [[lhs rhs]] (map (comp rule reverse) (partition 5 1 (cons (second rhs) (cons (first rhs) lhs))))) (defn evolve-rhs [[lhs rhs]] (map rule (partition 5 1 (cons (second lhs) (cons (first lhs) rhs)))))

magic_bloat22:12:25

just take a little of the other side

magic_bloat22:12:32

and add it to the front of this side.

ben.grabow22:12:46

I guess you keep a little padding at the ends of each list so the partition 5 picks up the entire range?

fellshard22:12:49

I pad the ends at the beginning and trim the ends at the end, keeping track of the new initial index. It seems to have worked reasonably well, though may be overkill; it really is just there to make the partition work.

magic_bloat22:12:33

the lists are infinite, so no manual padding required.

magic_bloat22:12:19

(def start-row [(repeat \.) (lazy-cat (seq input) (repeat \.))])

magic_bloat22:12:47

The first item in the vector is the left hand side, all dots, the second is the right hand side, i.e. my input followed by dots.

magic_bloat22:12:00

This scheme ran out of stack space before I got to 500 iterations though 🙂

taylor22:12:01

this is why I used a map with indices as keys and did get with default value of \. for simplicity

magic_bloat22:12:23

If this has piqued anyones interest then Wolfram Alpha can show you your pot plants graphically, and millions of other pot plant reproduction schemes also!

magic_bloat22:12:35

That's my rule working on random initial conditions

drowsy22:12:58

oh nice new table 🙂

borkdude22:12:08

yeah, it’s instead of running all solutions now, which seemed not feasible anymore given the accumulation of state in namespaces

drowsy22:12:02

yeah, I saw this when looking at the ci job 🙂. Pretty cool!