Fork me on GitHub
#adventofcode
<
2017-12-23
>
ihabunek06:12:54

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

dyankowsky07:12:04

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

ihabunek07:12:45

did you solve it?

ihabunek07:12:59

ah, i'm feeling very stupid right about now

dyankowsky07:12:15

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

ihabunek07:12:31

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

dyankowsky07:12:03

you might need to figure out what the loops are doing

dyankowsky07:12:09

or rather why they exist

ihabunek07:12:10

so would a middle-out approach work here? start with the innermost loop and try to remove it

ihabunek07:12:44

heh, middle-out, accidental silicon valley reference

dyankowsky07:12:07

just make sure you get that weissman score way up

dyankowsky07:12:27

I think it's worth analyzing the loops from the middle out

dyankowsky07:12:11

I think it's also worth looking at how the registers are used and, most importantly, at what points their values no longer matter

ihabunek07:12:02

yeah, trying to eliminate registers one by one

mikelis08:12:24

i rewrote the assembly to C, figured out what it does and found the answer by hand

mikelis08:12:25

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

ihabunek09:12:18

i rewrote it in python and got the wrong answer 😄

ihabunek09:12:25

i must have made a mistake along the way

erwin09:12:21

I am just running the interpreter for some time now, but I don't think that is going to work 🤓

ihabunek09:12:41

it makes 3 nested loops for my input, with 100k iterations each, so i don't think brute force is viable 🙂

ihabunek10:12:06

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

ihabunek10:12:15

off-by-two you could say

ihabunek10:12:48

today was actually fun, although it included very little programming

mikelis13:12:20

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

mikelis13:12:14

Did your input program also do ... ? spoilers inside

mikelis13:12:14

Did your input program also do ... ? spoilers inside

mikelis13:12:31

Count the number of non-primes in a range?

mikelis13:12:52

By using a really bad prime checking function

ihabunek13:12:55

@mfikes i'm guessing everyones did

ihabunek13:12:59

with different bounds

ihabunek13:12:41

it should be easy to fix the assembler code if you were allowed to use mod like in day 18

ihabunek13:12: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

orestis13:12:25

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

ihabunek13:12:39

i did the same...

ihabunek13:12:08

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

orestis13:12:10

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

orestis13:12:19

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

orestis14:12:19

I wonder what’s the O complexity for this; we have O(N N/2 M), where N ~= 100k and M 1000/17?

mikelis14:12:04

I also had the off by one error initially when solving by hand :)

ihabunek15:12:53

as they say, two most difficult problems in programming are naming things, cache invalidation and off-by-one errors 🙂

bhauman16:12:15

the sub -1 got me quite a few times

orestis13:12:35

Come on, 1 minute limit 🙂

orestis13:12:03

5 minutes now. D’oh!

bhauman16:12:07

yeah program analysis for the holidays

bhauman16:12:36

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

bhauman16:12:25

I just wanted to find an obvious countdown, but nope

mfikes16:12:25

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

bhauman16:12:40

that looks fun too

mfikes16:12:07

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

bhauman16:12:26

yeah, its tough with that instruction set

bhauman16:12:54

and you have to change all the jnz offsets, blah

bhauman16:12:27

and we have christmas stuff to do

mfikes16:12:04

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

bhauman16:12:23

I know the one

mfikes16:12:35

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

ihabunek17:12:42

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

fellshard18:12:29

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

fellshard18:12:43

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

fellshard18:12:42

I'm still missing something critical, though

fellshard18:12:09

D'oh. Off-by-one.

ihabunek11:12:37

@U1YPTG4UF i think everyone had the off-by-one problem in this one, i had two 😄

mikelis18:12:00

I was hoping that the task would be to programmatically optimize the algorithm

mikelis18:12:20

@mfikes looks like we even had the same inputs

borkdude19:12:12

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?

thegeez19:12:51

today was good to get the average time per day spent on AoC to grow exponentially 😕

bhauman19:12:43

@borkdude understand the alg and get the answer

thegeez19:12:08

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

borkdude19:12:09

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

bhauman19:12:20

even if you optimize the code it will run really slowly

borkdude19:12:24

in sane computing time

borkdude19:12:32

@thegeez How long did yours run?

bhauman19:12:12

people have mentioned adding the mod instruction back

borkdude19:12:34

yeah, you could

borkdude19:12:08

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

bhauman19:12:33

yeah that would help but still slow

thegeez19:12:47

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

thegeez19:12:07

Not sure if that counts as optimized assembly or a calculation of the answer, perhaps both

borkdude19:12:05

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.

erwin19:12:57

When you understand the instructions enough to write the C code it is faster to just calculate the answer and be done with it

borkdude19:12:58

I know, but … fun … adding the mod instruction back like @bhauman could surely work, but I’m kind of done with it.

erwin19:12:53

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.

erwin19:12:04

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

borkdude19:12:13

I guess so yeah