Fork me on GitHub
#adventofcode
<
2019-12-21
>
fellshard01:12:59

I'd like to think my parsing for it ended up fairly clean. The different arities of map are major helps in this.

fellshard05:12:56

My second program ended up being absurdly easy - I went with a very dumb initial heuristic thinking it would show me the next failed test, but nope, that was it

misha09:12:15

low level mutability eew

πŸ‘Œ 1
misha12:12:01

trying to write fn to translate sexpressions line (and a (not b)) into AND A J... and those 2 mutable registers are a world of pain

misha12:12:34

either api forces you to frame sexp from particular point of view, or infinite pain

Ben Grabow16:12:17

You can translate boolean expressions...

Ben Grabow16:12:50

using de morgan's laws to change (and (not x) (not y)) to (not (or x y)) to save register space

Ben Grabow16:12:01

Any expression that has more than one non-trivial operand is going to take up both of your registers

Ben Grabow16:12:01

So simplify the operands of any binary op until at least one of them is a trivial register. Unary ops can be computed with a single mutable register.

misha17:12:27

all of this is true. I wanted user not to worry about shape of the tree. But reshaping a tree with a bunch of substitution rules is not an easy task as well. but yeah, can be done for sure.

Alper Cugun20:12:02

I read half the book and threw this together: https://github.com/alper/aoc2019/blob/master/3.clj It’s a bit slow so suggestions of how to speed it up are very much welcome.

Alper Cugun22:12:13

It turns out that all time is spent in generate_points_from_steps.If anybody has a solution for this I can take a look at that would also be appreciated.

misha07:12:57

(defn generate-points-from-steps
  "For a vector of steps of the form [\"R\" 10] etc.,
   generates a vector of points starting from origin."
  [steps]
  (reduce
    (fn [path step] 
      (into []
        (concat path (loc-from-loc (last path) step))))
    [origin]
    steps))
can be just
(reduce
  (fn [path step]
    (into path
      (loc-from-loc (peek path) step)))
  [origin]
  steps)
with 2 key improvements: 1)`peek` is constant time lookup of last element in vector (`last` is linear time) 2) into directly into path vector bypasses concat and scans only new lock-from-loc segment. Where concat does not scan for concatting, but then scans entire seq: both old path and new lock-from-lock to put them into empty [] .

misha07:12:04

so in your code - each next iteration you scan old path segment twice: for last and after concat, instead of nonce

πŸ‘ 1
misha07:12:42

I think this:

(first (sort
         (fn [p1 p2] (< (dist-to-origin p1) (dist-to-origin p2))
           points)))
can be this:
(->> points
  (sort-by dist-to-origin <)
  (first))

misha07:12:25

(defn loc-from-loc
  "Loc is a hash with :x and :y, step is a vector with a direction string and an integer. Returns a list of locations that have been stepped over."
  [loc step]
  (case (first step)
    "R" (map (fn [step] (update loc :x + step)) (range 1 (+ (second step) 1)))
    "L" (map (fn [step] (update loc :x - step)) (range 1 (+ (second step) 1)))
    "U" (map (fn [step] (update loc :y + step)) (range 1 (+ (second step) 1)))
    "D" (map (fn [step] (update loc :y - step)) (range 1 (+ (second step) 1)))))
can be shorter with destructuring:
(defn loc-from-loc
  "Loc is a hash with :x and :y, step is a vector with a direction string and an integer.
   Returns a list of locations that have been stepped over."
  [loc [dir len]]
  (let [offsets (range 1 (+ 1 len))]
    (case dir
      "R" (map (fn [step] (update loc :x + step)) offsets)
      "L" (map (fn [step] (update loc :x - step)) offsets)
      "U" (map (fn [step] (update loc :y + step)) offsets)
      "D" (map (fn [step] (update loc :y - step)) offsets))))

Alper Cugun20:12:57

Just removing last and concat resulted in a 20x speed gain:

Alper Cugun20:12:05

Elapsed time: 7390.580613 msecs Elapsed time: 372.936439 msecs

Alper Cugun20:12:12

Thanks for that and the other hints.

πŸ‘ 1