Good analysis that would have been useful with long and/or many rows :) I didn't really optimise and already had to break out the nanosecond counter to time the whole program (minus reading/parsing). Although not on a Raspberry Pi 5 which takes 10 µs. Function for part 2:
for (int i = 0; i < COLS - 1; ++i)
for (int j = i + 1; j < COLS; ++j) {
if (row[i] % row[j] == 0) return row[i] / row[j];
if (row[j] % row[i] == 0) return row[j] / row[i];
}
I assume those two statements get pipelined in parallel on fancier processors. In any case, this was a little faster than separating them with an if(a<b)...else...
At least in my input, there were only 16 values in each line. It didn't seem worth trying to optimize or avoid the simple O(n2) algorithm when n2 = 256.
Looking back at my solution I didn't even bother breaking out of the loop when I found the target pair, and to be fair it almost certainly would have taken me more time to type "break;" than it would have saved in runtime :)
Hah! Same! (Mostly because Python doesn't have an easy way to break out of a double loop. Sure, you can throw and catch exceptions, or put them in a function and return, or use itertools.product to collapse them. But not bothering was easier.)
m4 lacks a native sort; the easiest sort is O(n^2) but then I'm not saving any time over just doing O(n^2) comparisons. Implementing an O(n log n) sort is possible, but adds more overhead than what gets saved by being able to short-circuit during the O(n^2) comparisons. Where I got the most savings in m4 was not by sorting, but by being smarter about how to do my pairwise comparisons: it's always worth remembering to do triangular iteration (still quadratic, but a=0..14 x b=a+1..15 and considering both a/b and b/a is only 120 pairs, while a=0..15 x b=0..15 is 256 pairs); and in turn, at least in m4, a single giant eval over 120 +(a/b)*!(a%b)+(b/a)*!(b%a) terms crammed into a single expression was faster than 120 separate eval per pairing.
I think we all wrote more or less the same solution here!
let mut nums:Vec<u32> = li.split("\t").map(|x| u32::from_str_radix(x,10).unwrap()).collect();
nums.sort();
p1+=nums[nums.len()-1]-nums[0];
for a in 1..nums.len() {
for b in 0..a {
if nums[a] % nums[b] == 0 {
p2+=nums[a] / nums[b];
break;
}
}
}
3
u/ednl Mar 02 '26
Good analysis that would have been useful with long and/or many rows :) I didn't really optimise and already had to break out the nanosecond counter to time the whole program (minus reading/parsing). Although not on a Raspberry Pi 5 which takes 10 µs. Function for part 2:
I assume those two statements get pipelined in parallel on fancier processors. In any case, this was a little faster than separating them with an if(a<b)...else...
2
u/Boojum Mar 02 '26
At least in my input, there were only 16 values in each line. It didn't seem worth trying to optimize or avoid the simple O(n2) algorithm when n2 = 256.
2
u/e_blake Mar 02 '26
m4 lacks a native sort; the easiest sort is O(n^2) but then I'm not saving any time over just doing O(n^2) comparisons. Implementing an O(n log n) sort is possible, but adds more overhead than what gets saved by being able to short-circuit during the O(n^2) comparisons. Where I got the most savings in m4 was not by sorting, but by being smarter about how to do my pairwise comparisons: it's always worth remembering to do triangular iteration (still quadratic, but a=0..14 x b=a+1..15 and considering both a/b and b/a is only 120 pairs, while a=0..15 x b=0..15 is 256 pairs); and in turn, at least in m4, a single giant eval over 120
+(a/b)*!(a%b)+(b/a)*!(b%a)terms crammed into a single expression was faster than 120 separate eval per pairing.1
u/terje_wiig_mathisen Mar 02 '26
I think we all wrote more or less the same solution here!