Fork me on GitHub
#adventofcode
<
2017-12-04
>
minikomi04:12:54

Hallo fellow adventers

minikomi05:12:07

well, day3 upped the ante a little i see

dpsutton06:12:24

yeah this is a tricky one

dpsutton06:12:35

my inputs agree with their outputs for the first 23 values but i'm not getting the right answer for part b

fellshard06:12:36

Misread the value they're looking for?

dpsutton07:12:50

turns out what i thought was a special case for one number was in fact general

dpsutton07:12:12

i was thinking in terms of rings of the spiral. so i ask which cells are adjacent in the inner ring and then which are adjacent in the same ring

fellshard07:12:12

I went for a generic 3x3 scan so I didn't have to worry about details of which cells would or wouldn't be filled

dpsutton07:12:29

yeah. i compute mine on the fly. and looking at the walk and create method, it looks better

dpsutton07:12:45

and the code i saw uses the coordinates to know when to turn,, etc. it looks nice

dpsutton07:12:58

i've never seen the with-tests macro either. that's pretty nice

dpsutton07:12:18

but i do like the way mine came together

dpsutton07:12:21

(defn cell-value [n]
  (if (= n 1)
    1
    (let [inner (inner-touching n)
          outer (outer-touching n)
          touching (distinct (concat inner outer))]
      ;; so a cell's value is the sum of the values it is touching,
      ;; either in its own ring or in the inner ring
      (apply + (map cell-value touching)))))

dpsutton07:12:57

but lots of edge cases in the outer touching functoin

dpsutton07:12:08

can you link me your day3.clj?

dpsutton07:12:26

and then wrap that in a memoize and map it over a range and drop while lest than what they are looking for

minikomi08:12:32

totally brute forced day3

minikomi08:12:43

https://github.com/minikomi/advent-of-code/blob/master/src/advent/2017/day3.clj#L9-L14 Once I blagged that out on the repl / with pen & paper, I got it.. but not a solution I'm happy with

val_waeselynck09:12:20

day 4: almost a no-brainer 🙂

borkdude09:12:30

@val_waeselynck Very nice solution

minikomi09:12:19

yeah, day4 was a piece of cake 😄

fellshard09:12:10

Yeh. Hurrah for quick set conversion

borkdude09:12:33

@fellshard Link to your solution?

fellshard09:12:16

I dumped the entire input in, heh. 😫

borkdude09:12:08

I had this too at first #(= (count %) (count (set %)) == (apply distinct? ...)

fellshard09:12:25

I haven't used distinct much, that's one to add to the toolkit!

borkdude09:12:30

Yeah, I’ve seen sort a couple of times now. I feel so dumb

fellshard09:12:14

First thing to think when looking for anagrams is a lex-sort : )

fellshard09:12:38

Not when making them, so much

borkdude09:12:16

Yeah, checking whether they exist vs. creating them

val_waeselynck10:12:59

I'd like to practice core.logic, anyone knows a problem from AoC 2016 or 2015 for which it's a nice fit?

borkdude10:12:58

@val_waeselynck hmm, I think this problem should be solvable with core.logic: https://blog.michielborkent.nl/blog/2017/10/10/parsing-a-circuit-with-clojure-spec/

val_waeselynck10:12:25

@borkdude yeah so mostly a graph computation. Clara-rules or plumatic/graph could be a nice fit for that too.

orestis11:12:54

The variability of answers for the “simple” puzzles is really an indicator of the language used, I’d think. I also used distinct and sort 🙂 https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day4.clj

minikomi11:12:32

ooh, thought of a better way to do day3-part1

erwin11:12:27

maybe use (into [] ,,,) with count instead of transduce with highlighted line?

borkdude11:12:32

yeah, or (count (sequence xform input))

borkdude11:12:07

so:

(count
   (sequence (map identity)
             [1 2 3]))
  ;; vs
  (transduce (map (constantly 1))
             +
             [1 2 3])

minikomi12:12:28

Another idea:

(def xf (comp (filter odd?) (map inc)))
(transduce xf #(inc %) 0 (range 5))

borkdude12:12:00

doesn’t compile

borkdude12:12:42

day 4: I first checked for palindromes, but then realized they were not anagrams and then refactored… and eventually ended up with an inefficient solution 😳

borkdude12:12:16

This one is nice. He just does it in the browser while having his input open: https://www.reddit.com/r/adventofcode/comments/7hf5xb/2017_day_4_solutions/dqqjrq2/

thegeez13:12:34

@borkdude for counts with transducers use net.cgrand.xforms/count to replace the (map (constantly 1))

borkdude13:12:49

@thegeez something like this?

(first (eduction x/count
              [1 2 3]))

borkdude13:12:03

(not yet familiar with this lib)

borkdude13:12:13

o no, this is better: (x/count (map identity) [1 2 3])

dpsutton14:12:07

@mfikes can you explain your invariant in your step function for day 3? In looking for the next location, you tag the locations as visited or not. And you find the first one unvisited after one that is visited in the list of potential squares left, down, right, up. Can you tell me why this works?

mfikes14:12:07

@dpsutton I unfortunately don’t have anything close to a proof of why that approach works. It intuitively matches what I would do if I were trying to “spiral counter-clockwise,” without knowing which “linear direction” I’m already moving: I would try to choose the “counter-clockwise-most” free location. Perhaps a proof by contradiction could be constructed where if you chose any other location, you wouldn’t trace a spiral, but I don’t know if that reasoning is too sketchy. In short, it is a physical intuition that matches the concept of keeping your left hand on the wall and just tracing your path.

dpsutton14:12:43

sounds good to me. that was very clever. I'm enjoying reading the code. People that are doing the spiral are having to enumerate how to make decisions. The one I've seen used the coordinates and the fact that it is a square to know when to turn. Yours didn't need this big decision tree and is quite clever

mfikes14:12:14

It would be very interesting to categorize the kinds of solution “trees” that people have. I imagine they involve recognizing and using perfect squares, keeping track of a current linear direction and knowing when to turn (by memory, or by counting, or by being at a place where x=y or x=-y), or left-hand on wall. Maybe those are the 3?

minikomi14:12:48

For me it was -- did we change layers? go :up (went over another odd square), is it a "corner"? turn left.. (worked out a formula on the repl to generate a set of corners for current layer) otherwise, continue on in the current direction

mfikes14:12:23

Yeah, I suspect a broad class of the solutions have a “state” in #{:up :left :down :right} that gets flipped at a corner, and then differences on how you detect a corner.

mfikes14:12:23

FWIW, I think my solution is wasteful of memory, but I got lucky that the problem fit in RAM. 🙂

dpsutton14:12:55

also your potential candidates function is written really well

dpsutton14:12:12

(defn adjacent-locations
  "Given a location, produces the eight adjacent locations."
  [[x y]]
  (map (fn [[dx dy]]
         [(+ x dx) (+ y dy)])
    [[-1  1] [ 0  1] [ 1  1]
     [-1  0]         [ 1  0]
     [-1 -1] [ 0 -1] [ 1 -1]]))

dpsutton14:12:36

ahh the formatting messed up but the grid layout and the hole for current location is super nice

mfikes14:12:56

That second category doesn’t require O(n^2) memory, I’d guess

borkdude14:12:07

@mfikes It felt a bit like cheating in the second part to keep a map around with all the previous “tiles” (as I called them), because that required more memory than needed maybe

dpsutton14:12:19

my solution feels wasteful in trying to determine which cells in the current ring and inner ring are necessary for computation

dpsutton14:12:35

and involved bringing edge cases rather than just a notion of "add 'em if you got 'em"

mfikes14:12:56

@dpsutton Yes, I like using a “graphical” code solution sometimes. Here is another, where you need to parse digits from a file containing their representations. I chose to solve it by putting their representations in the code and then constructing a reverse mapping from those representations to the digits.

(def rendered-digit-lines
  "A sequence of 3 lines representing all of the digits in order."
  [" _     _  _     _  _  _  _  _ "
   "| |  | _| _||_||_ |_   ||_||_|"
   "|_|  ||_  _|  | _||_|  ||_| _| "])

(defn- lines->digit-representations
  "Converts a sequence of 3 lines into a sequence of representations
  of the digits on those lines, where each digit representation is
  a sequence of character triplets."
  [lines]
  (apply map list (map #(partition 3 %) lines)))

(def digit-representation->digit
  "A map from digit representation to digit."
  (zipmap (lines->digit-representations rendered-digit-lines)
          (range 10)))
If you look at digit-representation->digit, you’ll see what I mean.

borkdude14:12:18

Ah, now I see it in your solution @mfikes, nicely done 🙂

mfikes14:12:41

With the “hole” in the matrix, I had to be careful not to let my editor reformat the code 🙂

dpsutton14:12:03

(def numerals-text (str " _     _  _     _  _  _  _  _ \n"
                        "| |  | _| _||_||_ |_   ||_||_|\n"
                        "|_|  ||_  _|  | _||_|  ||_| _|\n"))

(def numeral-streams (->> numerals-text
                          str/split-lines
                          (remove str/blank?)))

(defn chunk3
  "Partition a string into 3 character substrings"
  [s]
(map #(apply str %) (partition 3 s)))

minikomi14:12:55

I think the 2d syntax from racket takes that kind of thing to the extreme https://docs.racket-lang.org/2d/index.html

minikomi14:12:24

ascii art as syntax

borkdude14:12:03

spaces in between are not usually formatted right?

dpsutton14:12:16

i did the same thing

borkdude14:12:22

Is the digits example from last year?

mfikes14:12:25

Cursive will ignore the spaces and just mess it all up 🙂

dpsutton14:12:34

it's a kata about ocr

mfikes14:12:44

No the digits example is from a pre-screen interview I did

mfikes14:12:04

Damn. You are right! 🙂

dpsutton14:12:14

did you get the gig?

mfikes14:12:30

Yes, but I didn’t take it

mfikes14:12:27

Wow, the whole Kata looks the same. OK: User Story 1: I created a new project using lein new bank-ocr and this is the core file: https://gist.github.com/mfikes/f43d382057efa017ebfb User Story 2: I created a bank-ocr2, and took the contents of the previous story and simply added a account-number-value? method to compute the validity of a bank account: https://gist.github.com/mfikes/17ec1cfcdddfdba2b2f4 User Story 3: I created a bank-ocr3, took the stuff from User Story 2 and added a account-number-illegible? and revised the account number printing logic to print “?” characters and the additional “ILL” and “ERR” descriptors https://gist.github.com/mfikes/3c714859cb3da9384d52

dpsutton14:12:12

yup. was it a health care company you interviewed with?

mfikes14:12:19

No, it was Outpace

dpsutton14:12:33

ah. i had the same thing with healthfinch

mfikes14:12:31

FWIW, Outpace is/was awesome. The issue was mine: I backed out because I didn’t want to jump into full-time pairing without having done any, and not knowing what it was like to actually do it full time.

dpsutton15:12:21

healthfinch seemed cool as well. they did the full time pair thing as well. which i think i would like if i were working remotely for the comraderie

mfikes15:12:53

My Day 4 solutions are up. Wondering if anyone found anything simpler. I debated the aspect of counting the number of times a predicate matches a sequence, but in the end went with the obvious one. Perhaps there will be more interesting variation on how people detect valid passphrases. https://github.com/mfikes/advent-of-cljs/commit/4bff774da3e9760e10fbb6cb1e33d7614a185634

val_waeselynck19:12:47

@mfikes pretty much the same for me, with frequencies instead of sort

borkdude15:12:10

@mfikes I think that’s as simple/efficient as it gets. It would be even simpler if you would put the two parts in one namespace, because a lot of the logic is re-usable (matter of taste)

mfikes15:12:47

Yeah, that’s a recurring pattern with the part 1 / part 2 aspect.

borkdude15:12:29

Notice that this one is almost the same as part 1, except for this line: https://github.com/borkdude/aoc2017/blob/master/src/day4.clj#L58

mfikes15:12:34

I might take tha approach of putting common bits in a shared core ns.

mfikes15:12:03

Yes, for me the addition of sort was the difference.

mfikes15:12:30

I think that for this one, if you happen to remember that there is a core predicate that you can use, the problem is trivial. (Especially compared to Day 3.)

mfikes15:12:40

Ahh nice—tentamen’s use of frequencies instead of sort might be faster if the words are long. 🤔

borkdude15:12:42

@mfikes With my puzzle input it turned out to be the same (sloppy benchmark of course): https://github.com/borkdude/aoc2017/blob/master/src/day4.clj#L77

mfikes15:12:28

Yeah, if s contains the entire contents of /usr/share/dict/words, in self-hosted ClojureScript:

cljs.user=> (time (do (sort s) nil))
"Elapsed time: 4993.764097 msecs"
nil
cljs.user=> (time (do (frequencies s) nil))
"Elapsed time: 1341.280391 msecs"
nil

mfikes16:12:39

I wish there were a better way to know who, of the people listed at https://github.com/adventofcode-clojurians/adventofcode-clojurians have finished Day 4.

borkdude16:12:55

@mfikes The leaderboard!

borkdude16:12:52

I was looking at this yesterday. There’s an API that returns JSON. Maybe we could somehow hook it up to the README?

borkdude16:12:30

It would be a bonus puzzle 😉

mfikes16:12:04

What I really want to do: Survey each solution, trying to pick out novel aspects that never crossed my mind or made better use of core fns.

dpsutton16:12:03

^ yeah. be nice to see a curated list of different interesting aspects

borkdude16:12:06

That would be a manual effort I guess but worth doing!

mfikes16:12:49

What I’m interested in, from a learning perspective for example. If you are doing (= (count (distinct xs)) (count xs)), there is a core predicate that makes this trivial.

borkdude16:12:33

Yes, or (set xs) is what I was doing

mfikes16:12:54

In fact, this core predicate, is almost cheating—it nearly solves Day 4 with one fn.

borkdude16:12:22

Two things I learned today: distinct? and normalize data if you want to compare it on one property (without actually generating solutions which you don’t need).

mfikes16:12:18

By “normalize data,” are you thinking of the sort in day 4 part 2?

borkdude16:12:01

Yes, maybe projection is the better word: sort and frequencies are a projection of anagrams into a smaller search space

borkdude16:12:34

Maybe there are other projections possible

mfikes16:12:32

Yes, need to dig up one of my math books, the term they use for your “projection” is “hash”, when applied to the concept of defining a partition (induced by an equivalence relation)

dpsutton16:12:56

the math term i'd think applied would be an injection or an embedding. embed the underlying representation into its equivalence class

dpsutton16:12:08

A -> equivalence classes over A

borkdude16:12:24

> In mathematics, a projection is a mapping of a set (or other mathematical structure) into a subset (or sub-structure) https://en.wikipedia.org/wiki/Projection_(mathematics) > In mathematics, an injective function or injection or one-to-one function is a function that preserves distinctness https://en.wikipedia.org/wiki/Injective_function > In mathematics, an embedding (or imbedding[1]) is one instance of some mathematical structure contained within another instance https://en.wikipedia.org/wiki/Embedding It might be taste, but I find projection the most fitting, or hash if you’re programming 🙂

borkdude16:12:14

Embedding seems to be about groups, category theory etc.

dpsutton16:12:27

embedding is structural preserving. most examples are the copies of the naturals in the integers, integers in the rationals, rationals in the reals, etc

dpsutton16:12:43

so since this would throw away structure it's not the right usage

dpsutton16:12:54

(or add structure)

borkdude16:12:49

ah yes, it was nice when I got those classes about countability, etc. https://en.wikipedia.org/wiki/Countable_set

borkdude16:12:11

There seems to be no name for a function (which is a projection) that is nor injective, bijective and surjective

borkdude16:12:44

With the word projection I think of physics where you see the light being concentrated through a lense.

mfikes16:12:28

There are functions that tend to be named with the suffix -by, which take a function which essentially maps the values prior to doing whatever that function was going to do. Maybe there is a curiously recurring concept there.

borkdude17:12:10

we also use distinct-by in JVM clojure. It would be cool if there was also a distinct-by?, that would be effectively the solution for part 2 with sort or frequencies as a key

borkdude17:12:28

@mfikes Looking at that link, wondering what they use Levenshtein for

mfikes17:12:14

It is used to find compiler configuration keys that are slightly off

borkdude17:12:57

and then it gives a suggestion: “did you mean…” or does it blindly accept it

mfikes17:12:23

(This was an attempt to validate configuration, prior to Spec’s release.)

borkdude17:12:41

Levenshtein + spec could still be cool 🙂

borkdude17:12:55

as a layer on top maybe, or does the user now get a raw spec error message?

borkdude17:12:20

(haven’t messed around with cljs compiler config for a while, it’s been the same for a while)

chrisblom19:12:28

i like the advent of code repo, i've already picked some nice tricks

borkdude19:12:58

@chrisblom welcome to the repo, just merged your PR

borkdude19:12:14

@chrisblom I think we also met at EuroClojure 2016 if I’m not mistaking

chrisblom19:12:04

ah yes, we were on the same bus & had coffee

mfikes19:12:23

@borkdude The ClojureScript compiler doesn’t use Spec to validate compiler configuration. On the other hand, I believe Figwheel uses this lib https://github.com/bhauman/strictly-specking

val_waeselynck20:12:53

What are you guys using for parsing inputs? I find it rather tedious, I wish I could find some pattern-matching lib to speed up the process

val_waeselynck20:12:58

I realize parsing has not been much of a problem so far in AoC 2017, but as I'm working through some problems from last year I find them more and more demanding in this regard

chrisblom20:12:33

usually instaparse for complex things, otherwise clojure core & string function

borkdude20:12:42

usually just str/split etc, but at one point clojure.spec, although I first did it with regexes, which was good enough

nooga20:12:48

I’m solving in cljs, planck so .split. tbh I used it today for the first time

borkdude20:12:36

I didn’t solve all of last year’s problems. Can you give an example of more complex parsing problems there?

mfikes20:12:38

@ For problems involving parsing integers, frequently Clojure solutions involve clojure.core/read-string as opposed to Long/parseLong. FWIW, Planck now has planck.core/read-string in master. (For now, I’ve just been using js/parseInt.)

nooga20:12:49

oh, I just wrap numeric tables with [] in emacs and paste them into the repl

nooga20:12:05

too lazy to create files

mfikes20:12:59

Right 🙂 Previously I was even wrapping strings with '[] and just working on the resulting symbols

borkdude20:12:43

@mfikes That’s what I’ve also done. Wrap in [], then clojure.edn/read-string and process the rest using clojure.spec 🙂

mfikes20:12:29

Hey, since we are working in a language that is so data-centric, it doesn’t feel like cheating to paste the data into the source file.

borkdude20:12:24

Some people do this to avoid the IO monad 😉

val_waeselynck21:12:38

@borkdude @mfikes clever!

nooga21:12:27

I’d totally quote that

borkdude21:12:30

@val_waeselynck for that input i’d use the mentioned [] + read-string approach and then simply destructuring + case for processing

nooga20:12:19

todays puzzle is hilariously straightforward

mfikes20:12:26

It was distinctly easy 😜

nooga20:12:00

and applying map will sort the second part ;D

bhauman23:12:58

My solutions for day 3 and doy 4 are posted...

bhauman23:12:13

now to check everyone else's