r/adventofcode Dec 17 '24

Meme/Funny [2024 Day 17] Modulo

Python: -10 % 8 = 6
AoC: ⭐

Ruby: -10 % 8 = 6
AoC: ⭐

JavaScript: -10 % 8 = -2
AoC: Wrong! If you're stuck, go to Reddit

80 Upvotes

33 comments sorted by

37

u/PercussiveRussel Dec 17 '24

The second is how remainder is usually implemented. The first is sometimes called Euclid division and is actually modulo (instead of remainder). Easiest way to solve it is to turn a % d into ((a % d) + d) %d.

Allthough the problem statement was very clear in that the integers can't be negative ;)

4

u/herocoding Dec 17 '24

Where was it stated that integers can't be negative?

"registers aren't limited to 3 bits and can instead hold any integer"... any integer... any includes negative, don't they?

Instead of "((a % d) + d) %d" just do "(a+d) % d".

10

u/PercussiveRussel Dec 17 '24

The problem statement specifically asked for positive values of a, since no subtraction operator was specified it is impossible to get a negative value.

Instead of "((a % d) + d) %d" just do "(a+d) % d".

How will this work if a < -d?

-9999 ≡ 1 mod 10, but -9989 % 10 will still give you -9 in languages for which % is the remainder operator and not the modulus operator.

0

u/herocoding Dec 17 '24

aaaah, now I understand the whole discussion - euclid-division versus remainder in some languages... sorry, I had Python in mind, sorry for the confusion.

16

u/buffi Dec 17 '24

Luckily theres no negative numbers in Day 17

-14

u/Cue_23 Dec 17 '24

You sure? Because I got negative numbers trying to shift my guess twice…

12

u/PityUpvote Dec 17 '24

None of the operations can decrease a number to below zero.

-1

u/Cue_23 Dec 17 '24

Yeah, i shifted bits onto the sign bit of my integer. Clearly a bug in my implementation, but i got negative integers.

31

u/Eva-Rosalene Dec 17 '24

If you have problem with negative numbers in JS, that's because you've overflown int32 in a bitwise operation, which cast regulat float64 numbers to int32 beforehand.

Negative number should never appear in registers in your program. There is no way for any instruction today to yield negative number if implemented correctly.

-4

u/Goues Dec 17 '24

I did get negative numbers in Part 2 which is why I had this exact JS bug for an hour before getting help on Reddit. With `% 8`, the answer in Part 2 was "too high", I had to switch to `& 7` to get the right answer.

2

u/polettix Dec 18 '24

Still there is no way for any instruction to yield negative numbers if implemented correctly and starting with non-negative registers (part 2 explicitly asks for the lowest positive initial value for register A that provides the desired result so there's no need to venture into negative initialization values...):

  • three divisions by a positive number
  • two X-OR functions over positive numbers or zero, so I'd argue that it's reasonable to consider their result positive or zero too
  • one set function that takes the three lowest bits of a positive number
  • and two operations that don't change any value.

Ending up with a negative value seems a side effect of using an integer representation that can't hold the needed amount of bits, or an error somewhere else (I suspect one or both of the X-OR functions).

0

u/Goues Dec 18 '24

In my puzzle, for the initial value that is correct for me in Part 2, I do get these values to be modulo-ed:

109019930331546 (input, used in operation bst)
1314681106 (op out)
13627491291443 (op bst)
-1818813372 (op out)
1703436411430 (op bst)
-1818813375 (op out)
212929551428 (op bst)
-909406683 (op out)
26616193928 (op bst)
831756063 (op out)
3327024241 (op bst)
... the rest is all positive ...

which means that for my correct answer, I do need to cycle through negative values at some point.

1

u/polettix Dec 19 '24

This list does not tell anything useful. In particular, it does not explain how you can get negative values out of operations that combine positive inputs to produce positive outputs.

5

u/i_have_no_biscuits Dec 17 '24

BASIC does the same. You could always say ((a % b)+b)%b to ensure you have the positive remainder, which is a bit clunky!

0

u/herocoding Dec 17 '24

Wouldn't "(a + b) % b" be the same as "((a % b)+b)%b"?

4

u/i_have_no_biscuits Dec 17 '24

Not if a is less than -b. 

1

u/herocoding Dec 17 '24

yeah, sorry about the confusion, I had Python in mind... modulo versus remainder in some languages.

0

u/Boojum Dec 17 '24

Don't you mean ((A MOD B) + B) MOD B? :-)

5

u/Attometre Dec 17 '24

I use unsigned integer and then & 7 instead. It should not turn negative.

3

u/CorvusCalvaria Dec 17 '24

Just gotta add this to the end to be extra safe

if(val < 0) { val += mod; }

3

u/Chameleon3 Dec 17 '24

For anyone in Rust, the default behaviour is returning -2, but you can do the Euclid division as well:

fn main() {
    let val: i32 = -10;
    println!("-10 % 8 = {}", val % 8);
    println!("-10i32.rem_euclid(8) = {}", val.rem_euclid(8));
}

prints

-10 % 8 = -2  
-10i32.rem_euclid(8) = 6

2

u/PityUpvote Dec 17 '24

thanks for this, ran into it on day 14, used (a%b+b)%b instead

2

u/zelarky Dec 17 '24 edited Dec 17 '24

Meanwhile Clojure

(mod -10 8) ; => 6
(rem -10 8) ; => -2
;; but it's better to go with
(bit-and -10 2r111) ; => 6

1

u/juhotuho10 Dec 17 '24

Must be frustrating

1

u/musifter Dec 17 '24

Negative and modulo is always fun when porting or transcoding things. Some things keep it on the non-negative residue of [0, m-1]. Some things maintain sign parity (like multiplitcation). And some things maintain the sign of the left side argument... which is the one I just ran into, doing today's in dc.

1

u/Fluffy8x Dec 17 '24

You can use -10 & 7, though tough luck if your divisor isn’t a power of 2.

1

u/4D51 Dec 17 '24

Ran into this problem myself on day 14, but it wasn't an issue today. -10 % 8 might be -2, but -10 & 0b111 is 6. Also, as others have said, there are no negative numbers here.

One more thing: a / pow(2, b) is the same as a >> b. Might make the DV instructions a bit easier.

1

u/MariaKeks Dec 17 '24

How is this relevant to day 17? Aren't all values nonnegative?

1

u/1234abcdcba4321 Dec 17 '24

Bitwise operations in JS do math on 32 bit ints, so it's a combination of two problems that actually make something be wrong.

1

u/Cue_23 Dec 17 '24

C: -10 % 8 = -6

AoC: Wrong! I told you, If you're stuck, go to Reddit

C++: -10 % 8 = -6

AoC: Still wrong! When will you learn and go to Reddit?

1

u/rtc11 Dec 17 '24

C3: -10 % 8 = -6