badkins
2020-12-14 16:01:09

Ended up with the following after the all important “Chinese remainder theorem” hint :) #lang racket (require math/number-theory) (require threading) (define pairs (filter car (for/list ([ i (in-naturals) ] [ id (in-list (~> (second (file->lines "day13.txt")) (string-split _ ",") (map string->number _))) ]) (cons id (and id (- id i)))))) (solve-chinese (map cdr pairs) (map car pairs)) I’m curious about approaches that didn’t make use of the Chinese remainder theorem. My brute force approach of iterating by adding the largest bus id wasn’t quite fast enough to get the job done.


soegaard2
2020-12-14 22:01:29

@soegaard2 has joined the channel


jaz
2020-12-15 01:30:44

@jaz has joined the channel


hazel
2020-12-15 01:38:02

aoc2020/day14 on  canon [⇡$!] λ racket day14.test.rkt 165 aoc2020/day14 on  canon [⇡$!] λ racket day14.test2.rkt 208 aoc2020/day14 on  canon [⇡$!] λ racket day14.input.rkt 2900994392308


hazel
2020-12-15 01:38:05

why do I do the things that I do


hazel
2020-12-15 01:42:57

my goal with AoC is to write Racket more like Racket and less like Scheme and I’ve manifested this by writing #langs for Day 8 and 14


hazel
2020-12-15 01:42:59

great.


badkins
2020-12-15 02:13:08

link?



hazel
2020-12-15 02:16:49

also this code is not that great tbh aside from the parser


hazel
2020-12-15 02:18:05

I could have done a clever fold like I did for Day 8 but I didn’t


badkins
2020-12-15 02:19:51

@mbutterick it’s not intuitively obvious why you’d add that particular value. Also, the two values you check for in parts 1 & 2 are different than the solutions. What are they?


badkins
2020-12-15 02:39:36

Using the product of bus ids makes more sense to me if we were looking for a time when they all departed, but the offsets were what threw me off.


hazel
2020-12-15 05:28:55

difficulty curve this year is all over the place


hazel
2020-12-15 05:39:00

day 15 spoilers in thread, questions about racket also in thread


me1890
2020-12-15 05:39:27

Did you think today was hard or easy?


hazel
2020-12-15 05:39:38

very easy


me1890
2020-12-15 05:39:38

I’ve seen this type of problem before, so i’m not to judge


me1890
2020-12-15 05:40:12

Did you recognize the math concept?


hazel
2020-12-15 05:40:36

anyway, so here’s a naive solution: (define (solution numbers stop) (define seen (make-hasheq)) (define prev (for/last ([num (in-list numbers)] [turn (in-naturals)]) (hash-set! seen num turn) num)) (hash-remove! seen prev) (for/fold ([prev prev]) ([turn (in-range (length numbers) stop)]) (begin0 (match (hash-ref seen prev #f) [#f 0] [idx (- turn 1 idx)]) (hash-set! seen prev (sub1 turn))))) here’s the thing. when I change the begin0 block to: (define new-val (match (hash-ref seen-numbers prev #f) [#f 0] [idx (- i 1 idx)])) ;; _now_ we've "seen" it, but it happened on the last turn (hash-set! seen-numbers prev (sub1 i)) new-val) the runtime increases drastically. why?


hazel
2020-12-15 05:40:48

nah I pretty much bruteforced it lol


me1890
2020-12-15 05:42:14

I used a very similar solution, but the math it’s using is a generalization of something called Van Eck’s sequence. https://oeis.org/A181391


hazel
2020-12-15 05:44:04

I’m more confused about why begin0 makes this code drastically faster


me1890
2020-12-15 05:44:10

I have no idea about the racket question though, i’m pretty much a beginner


me1890
2020-12-15 05:45:25

I made an stream struct for the sequences that was identical to my rust implementation of the problem, unfortunately, my solution is very slow