This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2017-12-23
Channels
- # adventofcode (92)
- # beginners (12)
- # boot (3)
- # boot-dev (38)
- # cider (9)
- # clara (26)
- # cljs-dev (26)
- # cljsrn (3)
- # clojars (3)
- # clojure (48)
- # clojure-france (6)
- # clojure-greece (2)
- # clojure-spec (3)
- # clojurescript (7)
- # datomic (3)
- # fulcro (6)
- # hoplon (19)
- # jobs-discuss (1)
- # leiningen (4)
- # lumo (9)
- # off-topic (8)
- # onyx (43)
- # planck (10)
- # powderkeg (4)
- # precept (44)
- # re-frame (4)
- # shadow-cljs (4)
- # sql (13)
- # uncomplicate (1)
- # unrepl (3)
Whew!
I'll be curious to hear how other people decided to approach part2
it's really hard to see what it's doing
you might need to figure out what the loops are doing
or rather why they exist
so would a middle-out approach work here? start with the innermost loop and try to remove it
just make sure you get that weissman score way up
I think it's worth analyzing the loops from the middle out
I think it's also worth looking at how the registers are used and, most importantly, at what points their values no longer matter
i rewrote the assembly to C, figured out what it does and found the answer by hand
I’d be really curious to see others’ inputs, but at least in my case, no amount of compiler optimization would help because the algorithm itself is fundamentally flawed
I am just running the interpreter for some time now, but I don't think that is going to work 🤓
it makes 3 nested loops for my input, with 100k iterations each, so i don't think brute force is viable 🙂
For fun I compiled the C code and let it for half an hour but it didn’t finish. Replacing a small subroutine with one that has better algorithmic complexity let it finish instantly
Did your input program also do ... ? spoilers inside
Count the number of non-primes in a range?
By using a really bad prime checking function
it should be easy to fix the assembler code if you were allowed to use mod
like in day 18
here's my translation of asm to python:
h = 0
for b in range(106700, 123700 + 1, 17):
f = 1
for d in range(2, b):
for e in range(2, b):
if d * e == b:
f = 0
h += f
I wonder what’s the O complexity for this; we have O(N N/2 M), where N ~= 100k and M 1000/17?
I also had the off by one error initially when solving by hand :)
as they say, two most difficult problems in programming are naming things, cache invalidation and off-by-one errors 🙂
Day 23: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day23.clj
https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day23.clj
Day 23: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_23.cljc
I wanted to optimize it but. I had already spent too much time once I saw what it was doing
Yeah, with respect to the instruction set, I was thinking along the lines of re-adding an instruction that was in the day 18 computer
i had the same but digital 🙂 cleaned up version:
set b 106700 ; starting value for b
set c 123700 ; ending value for b
+----->set f 1 ; iterate b from 106700 to 123700, step 17
| set d 2
| +--->set e 2 ; iterate d from 2 to b - 1
| | +->set g d ; iterate e from 2 to b - 1
| | | mul g e
| | | sub g b
| | | jnz g 2 ---+
| | | set f 0 | ; set f = 0 if d * e == b
| | | sub e -1 <-+
| | | set g e
| | | sub g b
| | +--jnz g -8 ; jump unless e == b
| | sub d -1
| | set g d
| | sub g b
| +----jnz g -13 ; jump unless d == b
| jnz f 2 --+
| sub h -1 | ; increment h if f == 0
| set g b <-+
| sub g c
| jnz g 2 ---+
| jnz 1 3 | ; exit
| sub b -17 <-+
+------jnz 1 -23
total = 0
curr = 108100 to 125100 (exc.) by 17
flag = 1
d = 2 to curr (inc.)
e = 2 to curr (inc.)
flag = 0 if d*e = curr
total++ if flag = 0
@U1YPTG4UF i think everyone had the off-by-one problem in this one, i had two 😄
My solution for today went similarly Part 1: - https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day23.clj Part 2: - First on paper https://www.dropbox.com/s/rmb78q1dml3d1na/IMG_8127.JPG?dl=0 - Then turning jumps into loops https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day23-1.txt - Then into more readable pseudo-C https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day23-2.txt - Used that + wolfram alpha to get the answer - Actual C (with feasible runtime) for fun https://github.com/axelarge/advent-of-code/blob/master/src/advent_of_code/2017/day23.c
I was hoping that the task would be to programmatically optimize the algorithm
@mfikes looks like we even had the same inputs
Asking for a little help: is it the intention of the puzzle to optimize the assembly or just calculate the answer once you know what it’s doing?
today was good to get the average time per day spent on AoC to grow exponentially 😕
ok, because I find it really difficult to get the algorithm right with only these instructions…
I optimized one instruction: once you find something to be true, jump ahead so the loops are short circuited
Not sure if that counts as optimized assembly or a calculation of the answer, perhaps both
Earlier today I was thinking, maybe I could write it in C and let the C compiler optimize the assembly, but then I didn’t know yet what it was doing. Knowing this, it will probably surely not work.
When you understand the instructions enough to write the C code it is faster to just calculate the answer and be done with it
I know, but … fun … adding the mod instruction back like @bhauman could surely work, but I’m kind of done with it.
you could add mod and remove one loop and shortcut the algorithm, but than you could also just use isProbablePrime from BigInteger and run your algorithm a couple of rounds to find the values for b and c.