This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2018-12-12
Channels
- # adventofcode (135)
- # announcements (1)
- # beginners (192)
- # boot (5)
- # calva (130)
- # cider (42)
- # cljdoc (4)
- # cljs-dev (6)
- # cljsrn (3)
- # clojure (222)
- # clojure-europe (2)
- # clojure-greece (5)
- # clojure-italy (24)
- # clojure-nl (23)
- # clojure-russia (1)
- # clojure-spec (6)
- # clojure-uk (67)
- # clojurescript (35)
- # cursive (39)
- # datomic (61)
- # emacs (17)
- # figwheel (3)
- # figwheel-main (2)
- # fulcro (12)
- # hyperfiddle (10)
- # juxt (3)
- # leiningen (10)
- # nrepl (35)
- # off-topic (34)
- # onyx (3)
- # pathom (6)
- # quil (5)
- # re-frame (29)
- # reitit (6)
- # ring (1)
- # ring-swagger (8)
- # shadow-cljs (37)
- # spacemacs (9)
- # sql (9)
- # tools-deps (24)
- # unrepl (1)
- # vim (1)
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)))
Rows nested in columns, basically.On mobile right now so apologies for any errors in that code.
so in both directions, you have to find when the pattern stops producing new plants or something?
last year there was a similar problem, where the solution was to find a cycle
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.
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)
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.
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
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
just spent half an hour debugging the program and then discovering i was running on sample input instead of my input 😢
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
Today was painful 🙂 https://github.com/benfle/advent-of-code-2018/blob/master/day12.clj
I used something like (map rules (partition 5 1 pots) )
to get new generations
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])))))
(map-indexed vector "....#...###...##")
No, I add some \. to the start and the end on each generation
I didn't post that, sorry
Yeah, not sure how to shrink
https://github.com/akovantsev/adventofcode/blob/master/src/adventofcode/2018/day12.clj#L19-L37
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
but all of this does not really matter If equilibrium is just few hundred iterations away
(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 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.
That's not unlikely, as specific automata can have such proven properties, I think.
Yepp, it’s useful to look at your data
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.
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
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.
@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.
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
Sure go ahead!
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 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?
mine definitely went negative for a few generations but after that went straight positive
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 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.
the lists are infinite, so no manual padding required.
(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.
this is why I used a map with indices as keys and did get
with default value of \.
for simplicity
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!
That's my rule working on random initial conditions
@drowsy https://www.dropbox.com/s/wx0j13fj2iks455/Screenshot%202018-12-12%2023.34.54.png?dl=0