commit 6157648abc2cd42b0ed9455fdb6ec059c725dc73
parent e164c733157b73f4b758ea93df56b11338c34333
Author: Louis Burda <quent.burda@gmail.com>
Date: Tue, 8 Dec 2020 19:30:03 +0100
added day 8, fixed deinit with aoc env and added check if command script exists
Diffstat:
8 files changed, 871 insertions(+), 5 deletions(-)
diff --git a/aoc b/aoc
@@ -1,7 +1,7 @@
#!/bin/bash
function rmprefix() {
- echo "${1:$(echo -n "$2" | wc -c)}"
+ echo "${1:${#2}}"
}
SCRIPTPATH="$( cd "$( dirname "${BASH_SOURCE[0]}" )" >/dev/null 2>&1 && pwd )"
@@ -34,6 +34,9 @@ if [[ "${BASH_SOURCE[0]}" != "$0" ]]; then
fi
else
[ $# -lt 1 ] && exit 0
-
- "$REPOROOT/scripts/$1" ${@:2}
+ if [ -e "$REPOROOT/scripts/$1" ]; then
+ "$REPOROOT/scripts/$1" ${@:2}
+ else
+ echo "No such script"
+ fi
fi
diff --git a/lib/console8.zig b/lib/console8.zig
@@ -0,0 +1,91 @@
+const std = @import("std");
+
+pub const OpError = error{ InstructionPointerOOB, InvalidFormat, InstructionUnknown };
+pub const OpFuncSig = fn (ctx: *Console, arg: i64) OpError!void;
+pub const Instruction = struct {
+ opcode: []const u8, opfunc: OpFuncSig, argval: i64
+};
+
+pub const Console = struct {
+ accumulator: i64 = 0,
+ instructptr: u64 = 0,
+
+ jumpAddr: i65 = 0,
+
+ code: []const u8,
+ instlist: [][]const u8,
+ allocator: *std.mem.Allocator,
+ const Self = @This();
+
+ pub fn init(code: []const u8, allocator: *std.mem.Allocator) !Self {
+ var instvec = std.ArrayList([]const u8).init(allocator);
+ errdefer instvec.deinit();
+
+ var instit = std.mem.tokenize(code, "\n");
+ while (instit.next()) |inst| {
+ try instvec.append(inst);
+ }
+ return Console{
+ .code = code,
+ .instlist = instvec.toOwnedSlice(),
+ .allocator = allocator,
+ };
+ }
+
+ pub fn deinit(self: *Self) void {
+ self.allocator.free(self.instlist);
+ }
+
+ pub fn reset(self: *Self) void {
+ self.accumulator = 0;
+ self.instructptr = 0;
+ }
+
+ const instructionMap = std.ComptimeStringMap(OpFuncSig, .{
+ .{ "jmp", jumpInstruction },
+ .{ "acc", accInstruction },
+ .{ "nop", nopInstruction },
+ });
+
+ pub fn jumpInstruction(self: *Self, arg: i64) OpError!void {
+ self.jumpAddr = @intCast(i65, self.instructptr) + @intCast(i65, arg);
+ if (self.jumpAddr < 0 or self.jumpAddr >= self.instlist.len)
+ return error.InstructionPointerOOB;
+ self.instructptr = @intCast(u64, self.jumpAddr);
+ }
+
+ pub fn accInstruction(self: *Self, arg: i64) OpError!void {
+ self.accumulator += arg;
+ self.instructptr += 1;
+ }
+
+ pub fn nopInstruction(self: *Self, arg: i64) OpError!void {
+ self.instructptr += 1;
+ }
+
+ pub fn parseNext(self: *Self) !?Instruction {
+ if (self.instructptr >= self.instlist.len)
+ return null;
+
+ const inststr = self.instlist[self.instructptr];
+ const sep = std.mem.indexOfScalar(u8, inststr, ' ');
+ if (sep == null) return OpError.InvalidFormat;
+
+ const opcode = inststr[0..sep.?];
+ if (instructionMap.get(opcode)) |opfunc| {
+ const arg = inststr[sep.? + 1 ..];
+ const val = std.fmt.parseInt(i64, arg, 10) catch |err| {
+ std.debug.print("Failed to parse arg value: {}\n", .{arg});
+ return OpError.InvalidFormat;
+ };
+ return Instruction{ .opcode = opcode, .opfunc = opfunc, .argval = val };
+ } else {
+ std.debug.print("Unknown instruction: {}\n", .{inststr});
+ return OpError.InstructionUnknown;
+ }
+ }
+
+ pub fn exec(self: *Self, inst: *Instruction) !void {
+ try inst.opfunc(self, inst.argval);
+ }
+};
diff --git a/scripts/build b/scripts/build
@@ -3,4 +3,7 @@
[ -z "$REPOROOT" ] && exit 1
[ ! -e "$REPOROOT/cache" ] && mkdir "$REPOROOT/cache"
-zig build-exe --cache-dir "$REPOROOT/cache" --pkg-begin "aoc" "$REPOROOT/lib/aoc.zig" --pkg-end main.zig
+zig build-exe --cache-dir "$REPOROOT/cache" \
+ --pkg-begin "console8" "$REPOROOT/lib/console8.zig" --pkg-end \
+ --pkg-begin "aoc" "$REPOROOT/lib/aoc.zig" --pkg-end \
+ main.zig
diff --git a/scripts/run b/scripts/run
@@ -1,5 +1,4 @@
#!/bin/bash
[ ! -e "main" ] && aoc build
-
$PWD/main $@
diff --git a/src/day8/input b/src/day8/input
@@ -0,0 +1,628 @@
+jmp +336
+jmp +593
+jmp +121
+acc -8
+nop +459
+jmp +451
+acc -6
+acc +23
+acc +23
+acc -2
+jmp +113
+acc -11
+acc +25
+jmp +529
+acc +0
+jmp +1
+jmp +313
+acc +30
+nop +235
+jmp +45
+nop +195
+acc -11
+jmp +491
+acc +6
+nop +425
+nop +68
+acc +9
+jmp -25
+jmp +507
+jmp +456
+acc -1
+acc +49
+acc +5
+jmp +31
+acc +30
+nop +513
+jmp +499
+nop +533
+acc +18
+acc +28
+acc -2
+jmp +170
+acc -5
+jmp +180
+nop +179
+acc +15
+acc +33
+nop +27
+jmp +424
+acc +30
+acc +33
+acc +50
+jmp +348
+jmp +435
+acc +21
+acc +14
+acc +13
+jmp +1
+jmp +98
+jmp +39
+acc +11
+acc +23
+acc +44
+jmp +494
+acc +17
+acc -4
+acc +24
+acc +5
+jmp +204
+nop +454
+acc +45
+acc -10
+acc -3
+jmp +78
+acc +47
+acc +49
+nop +99
+acc +29
+jmp -76
+acc -9
+acc +43
+jmp +279
+jmp +460
+jmp +246
+jmp -78
+acc -8
+acc -3
+jmp +415
+acc -3
+acc -12
+jmp +117
+acc +32
+jmp +206
+acc +6
+acc +19
+jmp +291
+acc +8
+jmp +175
+acc +2
+jmp -6
+acc +11
+acc +28
+acc -19
+acc +1
+jmp +194
+acc +29
+nop +387
+acc +21
+jmp +507
+jmp +304
+acc +22
+acc -14
+acc -6
+acc +45
+jmp +101
+acc +12
+jmp +91
+acc +47
+jmp +171
+acc -4
+acc +24
+acc +3
+jmp +29
+nop +311
+acc -12
+jmp +179
+jmp +1
+acc -3
+acc +6
+acc +22
+jmp +214
+nop -101
+jmp -118
+acc +23
+acc +15
+jmp -42
+acc +22
+nop +391
+jmp +27
+acc -9
+jmp +449
+jmp +453
+jmp +208
+jmp +480
+jmp +335
+acc +23
+jmp +1
+acc +3
+acc +45
+jmp -18
+jmp +335
+jmp +165
+acc +26
+acc +8
+acc -3
+jmp -57
+jmp -112
+acc +14
+acc +20
+acc +21
+acc +13
+jmp -20
+acc +35
+jmp -81
+jmp +406
+acc -16
+acc +30
+acc -18
+jmp +79
+jmp +103
+jmp -96
+acc +43
+acc +36
+acc +31
+jmp +423
+nop +13
+acc -11
+acc +46
+nop +208
+jmp +398
+acc +50
+jmp +326
+acc +31
+jmp +45
+acc +50
+acc +13
+acc +38
+jmp +60
+nop -37
+nop -79
+jmp +213
+acc -19
+acc -16
+jmp +30
+jmp +1
+acc +27
+acc -4
+acc +46
+jmp -81
+jmp +29
+nop +23
+nop +388
+acc +40
+acc +46
+jmp +19
+acc +17
+jmp +287
+jmp +265
+acc +17
+acc +49
+jmp +353
+acc -4
+acc +39
+jmp +397
+jmp +84
+jmp -156
+jmp -41
+acc +2
+acc +7
+acc +45
+acc +26
+jmp +376
+jmp +143
+jmp -195
+acc +1
+acc -16
+acc +47
+jmp -225
+acc -11
+acc -7
+nop -166
+jmp +297
+acc +12
+acc +14
+acc -17
+jmp +9
+acc +49
+acc -9
+nop -31
+acc +17
+jmp -130
+acc +3
+acc +41
+jmp +112
+acc -11
+jmp +21
+jmp +125
+acc +2
+acc +37
+jmp -165
+acc +9
+acc +21
+jmp -35
+nop +9
+nop +303
+acc -6
+acc +12
+jmp +177
+acc +36
+acc +15
+nop -207
+jmp +224
+jmp -106
+acc +18
+nop -166
+jmp +39
+jmp +175
+acc -11
+acc -13
+acc +23
+acc -6
+jmp -269
+acc +8
+nop +212
+jmp -123
+jmp +188
+acc +35
+acc +43
+acc +33
+jmp -91
+acc +39
+acc +8
+acc -1
+acc +15
+jmp +29
+acc +44
+nop +18
+jmp -250
+jmp +83
+acc +10
+acc +12
+acc +18
+jmp +1
+jmp +170
+acc +47
+acc -13
+acc +4
+jmp +32
+acc +0
+jmp +203
+acc -16
+acc +11
+acc +38
+jmp -103
+jmp +2
+jmp -69
+nop -292
+jmp -90
+nop -97
+acc +29
+nop +124
+acc -12
+jmp -238
+acc +4
+jmp +36
+jmp -108
+acc +14
+acc +21
+jmp +82
+acc -6
+acc +28
+jmp -133
+acc -4
+acc +28
+jmp +155
+nop +168
+acc -2
+nop +86
+jmp +287
+acc +15
+acc +46
+acc +40
+acc -16
+jmp -139
+acc +39
+jmp +36
+acc -16
+acc +25
+nop -215
+jmp +146
+nop -296
+acc -12
+acc +40
+jmp -299
+acc +48
+acc +37
+nop -205
+acc -17
+jmp +215
+jmp +254
+jmp +53
+acc +15
+acc +34
+acc +8
+jmp +216
+nop +5
+acc +23
+jmp -195
+acc +0
+jmp +69
+acc +6
+jmp +187
+acc +14
+acc -2
+jmp -51
+acc -12
+acc +43
+nop -51
+jmp -193
+acc -1
+jmp -234
+acc +20
+jmp +1
+acc +33
+acc +23
+jmp -131
+acc +38
+acc +2
+jmp +179
+jmp +1
+jmp +209
+nop -187
+acc +41
+acc +32
+acc +6
+jmp +209
+nop -230
+acc +37
+acc +47
+acc +32
+jmp +82
+acc +45
+acc +21
+jmp -108
+acc +13
+acc +39
+jmp +127
+jmp +1
+nop +196
+jmp -146
+acc +19
+jmp -125
+jmp -149
+acc +28
+acc -1
+acc +35
+acc +7
+jmp -262
+acc -16
+acc -3
+acc +48
+acc +13
+jmp +177
+jmp -91
+acc +26
+nop +78
+acc +15
+jmp +1
+jmp +197
+acc +12
+acc -14
+acc +9
+jmp -317
+acc +41
+acc +2
+acc -11
+acc +6
+jmp -284
+acc +28
+acc -16
+jmp -65
+acc +31
+nop -276
+jmp -205
+acc +6
+acc +33
+acc +7
+acc -2
+jmp -125
+acc +34
+jmp -193
+acc -12
+acc +39
+jmp +1
+jmp -208
+acc +3
+acc +0
+nop +9
+jmp -112
+jmp +1
+jmp -314
+acc +34
+acc +9
+acc +5
+acc +20
+jmp +139
+acc -8
+acc +11
+acc +18
+jmp +1
+jmp -66
+acc -14
+jmp -173
+acc -3
+acc +31
+acc +0
+jmp +117
+acc +47
+acc +24
+acc +9
+acc +43
+jmp -427
+acc -11
+nop -226
+jmp -444
+acc +43
+acc -6
+acc -3
+jmp -202
+acc +34
+jmp -337
+acc +36
+acc +8
+acc +9
+jmp -162
+jmp +118
+acc +18
+jmp -481
+nop -144
+nop -236
+jmp -290
+acc -14
+jmp -448
+acc +29
+acc -19
+acc +21
+acc -11
+jmp -78
+acc +1
+acc +30
+acc -2
+jmp +114
+jmp +11
+jmp -117
+jmp -322
+acc +23
+jmp -361
+jmp -337
+acc +40
+nop +85
+nop -206
+acc +12
+jmp -199
+acc +38
+acc +20
+acc +19
+acc +33
+jmp -61
+acc +30
+nop -234
+acc +6
+acc +24
+jmp -463
+acc -10
+jmp +79
+acc +43
+acc +45
+jmp -261
+acc -13
+acc +1
+nop -217
+nop -82
+jmp -153
+acc +39
+jmp -340
+acc +37
+acc +17
+jmp -182
+acc +26
+acc +1
+acc +23
+jmp +16
+acc +39
+acc +13
+jmp -40
+acc +37
+acc -7
+jmp -119
+acc +20
+acc +44
+acc +44
+acc +14
+jmp -464
+acc +6
+acc +14
+acc +7
+jmp +54
+acc +10
+jmp -538
+acc +13
+acc -1
+acc +22
+jmp -397
+acc +17
+acc -8
+acc -5
+jmp -230
+acc +38
+nop -218
+jmp -81
+acc -19
+nop -14
+acc +32
+jmp -311
+nop -32
+acc +18
+jmp -232
+acc +40
+nop -242
+acc -11
+acc +34
+jmp -528
+jmp -484
+jmp -155
+acc -2
+acc +50
+acc -11
+acc +50
+jmp -116
+nop -361
+acc +12
+jmp -293
+acc +39
+jmp +17
+jmp -37
+acc -14
+jmp -440
+jmp -226
+acc +16
+acc +25
+acc +50
+acc +49
+jmp -242
+acc +47
+acc -19
+nop -435
+acc +41
+jmp -523
+acc +6
+jmp -458
+acc +0
+acc +37
+jmp -528
+acc +27
+jmp -57
+acc +47
+acc -9
+acc +23
+jmp -205
+acc +40
+nop -207
+acc -6
+jmp -129
+jmp +1
+acc +24
+acc -14
+jmp +1
+jmp +1
diff --git a/src/day8/main.zig b/src/day8/main.zig
@@ -0,0 +1,60 @@
+const std = @import("std");
+const aoc = @import("aoc");
+const Console = @import("console8").Console;
+
+fn runTillRepeat(console: *Console, instlist: *std.ArrayList(u64), swapon: ?u64) !void {
+ while (try console.parseNext()) |*inst| {
+ // std.debug.print("{:<5}: {} {}\n", .{ console.instructptr, inst.opcode, inst.argval });
+ if (std.mem.indexOfScalar(u64, instlist.items, console.instructptr) != null) {
+ return;
+ }
+ if (swapon != null and swapon.? == console.instructptr) {
+ inst.opfunc = switch (inst.opfunc) {
+ Console.jumpInstruction => Console.nopInstruction,
+ Console.nopInstruction => Console.jumpInstruction,
+ else => unreachable,
+ };
+ }
+ try instlist.append(console.instructptr);
+ try console.exec(inst);
+ }
+}
+
+fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
+ var console = try Console.init(input, allocator);
+ defer console.deinit();
+
+ var instlist = std.ArrayList(u64).init(allocator);
+ defer instlist.deinit();
+
+ try runTillRepeat(&console, &instlist, null);
+ std.debug.print("{}\n", .{console.accumulator});
+}
+
+fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
+ var console = try Console.init(input, allocator);
+ defer console.deinit();
+
+ var instlist = std.ArrayList(u64).init(allocator);
+ defer instlist.deinit();
+
+ try runTillRepeat(&console, &instlist, null);
+
+ for (instlist.items) |inst| {
+ if (std.mem.eql(u8, "acc"[0..3], console.instlist[inst][0..3]))
+ continue;
+
+ var sim_seen = std.ArrayList(u64).init(allocator);
+ defer sim_seen.deinit();
+
+ console.reset();
+ //std.debug.print("Swapping instruction: {:<5}: {}\n", .{ inst, console.instlist[inst] });
+ runTillRepeat(&console, &sim_seen, inst) catch {};
+ if (console.jumpAddr == console.instlist.len or console.instructptr == console.instlist.len) {
+ std.debug.print("{}\n", .{console.accumulator});
+ break;
+ }
+ }
+}
+
+pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day8/part1 b/src/day8/part1
@@ -0,0 +1,49 @@
+--- Day 8: Handheld Halting ---
+
+Your flight to the major airline hub reaches cruising altitude without incident. While you consider
+checking the in-flight menu for one of those drinks that come with a little umbrella, you are
+interrupted by the kid sitting next to you.
+
+Their handheld game console won't turn on! They ask if you can take a look.
+
+You narrow the problem down to a strange [1m[37minfinite loop[0m in the boot code (your puzzle
+input) of the device. You should be able to fix it, but first you need to be able to run the code in
+isolation.
+
+The boot code is represented as a text file with one [1m[37minstruction[0m per line of text. Each
+instruction consists of an [1m[37moperation[0m (acc, jmp, or nop) and an [1m[37margument[0m (a
+signed number like +4 or -20).
+
+- acc increases or decreases a single global value called the [1m[37maccumulator[0m by the value
+given in the argument. For example, acc +7 would increase the accumulator by 7. The accumulator
+starts at 0. After an acc instruction, the instruction immediately below it is executed next. - jmp
+[1m[37mjumps[0m to a new instruction relative to itself. The next instruction to execute is found
+using the argument as an [1m[37moffset[0m from the jmp instruction; for example, jmp +2 would
+skip the next instruction, jmp +1 would continue to the instruction immediately below it, and jmp
+-20 would cause the instruction 20 lines above to be executed next. - nop stands for [1m[37mNo
+OPeration[0m - it does nothing. The instruction immediately below it is executed next.
+
+For example, consider the following program:
+
+nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6
+
+These instructions are visited in this order:
+
+nop +0 | 1 acc +1 | 2, 8(!) jmp +4 | 3 acc +3 | 6 jmp -3 | 7 acc -99 | acc +1 | 4 jmp -4 | 5 acc +6
+|
+
+First, the nop +0 does nothing. Then, the accumulator is increased from 0 to 1 (acc +1) and jmp +4
+sets the next instruction to the other acc +1 near the bottom. After it increases the accumulator
+from 1 to 2, jmp -4 executes, setting the next instruction to the only acc +3. It sets the
+accumulator to 5, and jmp -3 causes the program to continue back at the first acc +1.
+
+This is an [1m[37minfinite loop[0m: with this sequence of jumps, the program will run forever.
+The moment the program tries to run any instruction a second time, you know it will never terminate.
+
+Immediately [1m[37mbefore[0m the program would run an instruction a second time, the value in the
+accumulator is [1m[37m5[0m.
+
+Run your copy of the boot code. Immediately before any instruction is executed a second time,
+[1m[37mwhat value is in the accumulator?[0m
+
+
diff --git a/src/day8/part2 b/src/day8/part2
@@ -0,0 +1,33 @@
+--- Part Two ---
+
+After some careful analysis, you believe that [1m[37mexactly one instruction is corrupted[0m.
+
+Somewhere in the program, [1m[37meither[0m a jmp is supposed to be a nop, [1m[37mor[0m a nop
+is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)
+
+The program is supposed to terminate by [1m[37mattempting to execute an instruction immediately
+after the last instruction in the file[0m. By changing exactly one jmp or nop, you can repair the
+boot code and make it terminate correctly.
+
+For example, consider the same program from above:
+
+nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6
+
+If you change the first instruction from nop +0 to jmp +0, it would create a single-instruction
+infinite loop, never leaving that instruction. If you change almost any of the jmp instructions, the
+program will still eventually find another jmp instruction and loop forever.
+
+However, if you change the second-to-last instruction (from jmp -4 to nop -4), the program
+terminates! The instructions are visited in this order:
+
+nop +0 | 1 acc +1 | 2 jmp +4 | 3 acc +3 | jmp -3 | acc -99 | acc +1 | 4 [1m[37mnop[0m -4 | 5 acc
++6 | 6
+
+After the last instruction (acc +6), the program terminates by attempting to run the instruction
+below the last instruction in the file. With this change, after the program terminates, the
+accumulator contains the value [1m[37m8[0m (acc +1, acc +1, acc +6).
+
+Fix the program so that it terminates normally by changing exactly one jmp (to nop) or nop (to jmp).
+[1m[37mWhat is the value of the accumulator after the program terminates?[0m
+
+
