aboutsummaryrefslogtreecommitdiff
path: root/2022/07-no-space-left-on-device
diff options
context:
space:
mode:
authorJulien Dessaux2022-12-07 16:14:51 +0100
committerJulien Dessaux2022-12-07 16:14:51 +0100
commitb307eb91b0481d60cc1ab630f0b30d5b7138a3f2 (patch)
tree923a6f700bd5e4d3b1c1f18a2de46b02f07f5650 /2022/07-no-space-left-on-device
parent2022-07 in zig (diff)
downloadadvent-of-code-b307eb91b0481d60cc1ab630f0b30d5b7138a3f2.tar.gz
advent-of-code-b307eb91b0481d60cc1ab630f0b30d5b7138a3f2.tar.bz2
advent-of-code-b307eb91b0481d60cc1ab630f0b30d5b7138a3f2.zip
dychotomy was really unnecessary
Diffstat (limited to '')
-rw-r--r--2022/07-no-space-left-on-device/second.zig17
1 files changed, 6 insertions, 11 deletions
diff --git a/2022/07-no-space-left-on-device/second.zig b/2022/07-no-space-left-on-device/second.zig
index 537ef6e..49e53b0 100644
--- a/2022/07-no-space-left-on-device/second.zig
+++ b/2022/07-no-space-left-on-device/second.zig
@@ -51,17 +51,12 @@ fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 {
}
try sizes.append(stack.items[n]); // we do not forget the last one
n = 30000000 - (70000000 - tot); // the amount of space we need to free
- // let's run a dychotomy on the array
- std.sort.sort(u64, sizes.items, {}, std.sort.asc(u64));
- var a: usize = 0;
- var b = sizes.items.len - 1;
- while (b - a > 2) {
- const m = a + (b - a) / 2;
- if (sizes.items[m] < n) {
- a = m;
- } else {
- b = m;
+ // let's find the minimum that is the closest to that
+ tot = 70000000;
+ for (sizes.items) |v| {
+ if (v > n and v < tot) {
+ tot = v;
}
}
- return sizes.items[b];
+ return tot;
}