Clojurians Log v2

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

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

what would it colls be here?

(for [y ys]
  (for [x xs]
    (f x y)))

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

shit.. forgot this was going on hahaha

having fun everyone?

anyone have a strategy for part 2? 😄

crap, there are people who've done it already

there must be some super-efficient algorithm for this

ah, apparently the pattern stabilizes

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

heh

that

does it go on forever?

got me really good

yes

at least in theory

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

yep

not very well described problem

it could have been clearer

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

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

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

and

most people aren't simulating it

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

yeah

yeah, indeed

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

how did you do it?

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

Thanks for the tip, mattly ^^

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)

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

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.

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)

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

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

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

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

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.

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

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

https://git.sr.ht/~ihabunek/aoc2018/tree/master/clojure/src/aoc2018/day12.clj

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

.

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

@taylor same

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

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

(->> generations (drop 102) :kappa:

:man-shrugging:

REPL-driven development

https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/2018/day12.clj

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

it made detecting patterns very easy

just (map - next-gen current-gen)

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

what is that 😄

Today was painful 🙂 https://github.com/benfle/advent-of-code-2018/blob/master/day12.clj

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

ah, right

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

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

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

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

but what is pots?

sorted-map? sorted-set?

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

does this assume pots don't expand below 0?

either code is to dense or I am :kappa:

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

I didn't post that, sorry

and you dont clean up those paddings?

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

Yeah, not sure how to shrink

https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/2018/day12.clj#L19-L37

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

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

Mine is something like

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

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

makes sense

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

because https://clojurians.slack.com/archives/C0GLTDB2T/p1544626959449600

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

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

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

time*

Has someone prove that there always will be an equilibrium?

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

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

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

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.

Yepp, it’s useful to look at your data

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

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

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

@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

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

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

Seems to work now?

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

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

but once I have merged it to master, you will

so shall I?

Sure go ahead!

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

fixed

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

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

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

actually not too tricky:

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

just take a little of the other side

and add it to the front of this side.

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?

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

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.

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

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

the lists are infinite, so no manual padding required.

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!

https://www.wolframalpha.com/input/?i=rule+3111423880+r%3D2+random+ic

That's my rule working on random initial conditions

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

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.

https://www.wolframalpha.com/examples/science-and-technology/computational-sciences/cellular-automata/

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

@drowsy https://www.dropbox.com/s/wx0j13fj2iks455/Screenshot%202018-12-12%2023.34.54.png?dl=0

oh nice new table 🙂

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

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

https://github.com/borkdude/advent-of-cljc#scores