Clojurians Log v2

ah, optimizing assembler, never thought i'd be doing that 😄

Whew!

I'll be curious to hear how other people decided to approach part2

did you solve it?

yeah

ah, i'm feeling very stupid right about now

it's really hard to see what it's doing

i see the loops but i'm unsure how to go about removing them

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

heh, middle-out, accidental silicon valley reference

heh

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

yeah, trying to eliminate registers one by one

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 rewrote it in python and got the wrong answer 😄

i must have made a mistake along the way

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 🙂

i got it, i had an off-by-one twice 😄

off-by-two you could say

today was actually fun, although it included very little programming

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

yes

@mfikes i'm guessing everyones did

with different bounds

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

Ah, stupid jnz; I thought I was counting the number of primes, not of non-primes.

Come on, 1 minute limit 🙂

i did the same...

5 minutes now. D’oh!

and then i missed the fact that the outer range should be inclusive

I have a list of primes from my bounds, I hope I can rely on them 🙂

Hah, I had the inclusive list problem also; it’s 1001 numbers, not 1000.

Day 23: https://github.com/orestis/adventofcode/blob/master/clojure/aoc/src/aoc/2017_day23.clj

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 🙂

https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day23.clj

yeah program analysis for the holidays

its funny how the heavy the resistance to actually just analyzing the program is

I just wanted to find an obvious countdown, but nope

Day 23: https://github.com/mfikes/advent-of-code/blob/master/src/advent_2017/day_23.cljc

the sub -1 got me quite a few times

No spoilers here. I like @bhauman’s inline analysis. I ended up with this crap

@mfikes uploaded a file: https://clojurians.slack.com/files/U04VDQDDY/F8JACTG2D/pasted_image_at_2017_12_23_11_47_am.png

that looks fun too

I wanted to optimize it but. I had already spent too much time once I saw what it was doing

yeah, its tough with that instruction set

and you have to change all the jnz offsets, blah

and we have christmas stuff to do

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 know the one

But, f-it. Too much time spent on this one 🙂

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

in loose pseudo; tl;dr, best I can tell, count all non-primes between two numbers

I'm still missing something critical, though

D'oh. Off-by-one.

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

@mikelis.vindavs shared a file: https://clojurians.slack.com/files/U89SBUQ4T/F8JS4FW2W/img_8127.jpg

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 😕

@borkdude understand the alg and get the answer

@borkdude I ran the optimized assembly until it finished for the answer

ok, because I find it really difficult to get the algorithm right with only these instructions…

even if you optimize the code it will run really slowly

in sane computing time

@thegeez How long did yours run?

I optimized one instruction: once you find something to be true, jump ahead so the loops are short circuited

people have mentioned adding the mod instruction back

yeah that would help but still slow

yeah, you could

I replaced loops with clojure loops that were smarter, that finished in 2 seconds

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.

yup

the theme for the last couple assignments is, do the easy thing and make it ridiculous for part 2.

I guess so yeah

fwiw, my code: https://github.com/borkdude/aoc2017/blob/master/src/day23.clj