From e8e55c5275af6bd801f9e18138ccbf8baed37380 Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Wed, 9 Dec 2020 13:35:32 +0100
Subject: [PATCH] Day 8

---
 advent_of_code_2020.jl | 106 +++++++
 data/day08.txt         | 675 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 781 insertions(+)
 create mode 100644 data/day08.txt

diff --git a/advent_of_code_2020.jl b/advent_of_code_2020.jl
index 0bc826d..1dd73e7 100644
--- a/advent_of_code_2020.jl
+++ b/advent_of_code_2020.jl
@@ -498,6 +498,104 @@ md"
 **Result for part 2**: $(nb_bags_contained(\"shiny gold\", input_day7))
 "
 
+# ╔═╡ c35b8110-3a0a-11eb-11e8-73b1b2080079
+md"## Day 8"
+
+# ╔═╡ 7c64c710-3a0c-11eb-17bb-1db527c932a3
+struct Instruction
+	operator :: Symbol
+	argument :: Int
+end
+
+# ╔═╡ c8548b80-3a0a-11eb-067d-9dc6716dc325
+function parse_day8(lines)
+	map(lines) do line
+		splitted = split(line, ' ')
+		Instruction(Symbol(splitted[1]), parse(Int, splitted[2]))
+	end
+end
+
+# ╔═╡ 9d1a8980-3a0d-11eb-380e-8fcaf30c849c
+function execute(instructions) :: Tuple{Bool, Int}
+	pos = 1
+	accumulator = 0
+	n = length(instructions)
+	visited_positions = falses(n)
+	
+	while pos ≤ n && !visited_positions[pos]
+		visited_positions[pos] = true
+		ins = instructions[pos]
+		if ins.operator == :acc
+			accumulator += ins.argument
+			pos += 1			
+		elseif ins.operator == :jmp
+			pos += ins.argument
+		else # :nop.
+			pos += 1
+		end
+	end
+	pos > n, accumulator
+end
+
+# ╔═╡ 0f1d5380-3a10-11eb-2a71-1f0fddf65b70
+function fix_to_not_loop(instructions)
+	copy = deepcopy(instructions) # To avoid modifying the input.
+		
+	function switch(pos)
+		if copy[pos].operator == :jmp
+			copy[pos] = Instruction(:nop, copy[pos].argument)
+			true
+		elseif copy[pos].operator == :nop
+			copy[pos] = Instruction(:jmp, copy[pos].argument)
+			true
+		else
+			false
+		end
+	end
+	
+	for i ∈ 1:length(copy)
+		if switch(i)
+			finished, accumulator = execute(copy)
+			if finished
+				return accumulator
+			end
+			switch(i)
+		end
+	end
+end
+
+# ╔═╡ d6afedee-3a0a-11eb-31d7-3f16633dbf5d
+let
+	input = "nop +0
+acc +1
+jmp +4
+acc +3
+jmp -3
+acc -99
+acc +1
+jmp -4
+acc +6"
+	code = parse_day8(split(input, '\n'))
+	test1_part1 = execute(code)	
+	test1_part2 = fix_to_not_loop(code)
+	
+	md"
+Test 1, part 1: $(test1_part1 == (false, 5))
+	
+Test 1, part 2: $(test1_part2 == 8)
+	"
+end
+
+# ╔═╡ aa322be0-3a0e-11eb-27ec-d13acf9084aa
+input_day8 = parse_day8(readlines("data/day08.txt"))	
+
+# ╔═╡ d867dd80-3a12-11eb-1ae7-3119a294b25a
+md"
+**Result for part 1**: $(execute(input_day8))
+
+**Result for part 2**: $(fix_to_not_loop(input_day8))
+"
+
 # ╔═╡ Cell order:
 # ╟─661be9a0-353b-11eb-3598-a5b5245368cb
 # ╟─f0dd4400-3313-11eb-3295-af913c2212fb
@@ -549,3 +647,11 @@ md"
 # ╟─30488570-388f-11eb-2ede-b10bdd1a06e8
 # ╟─20351e70-396e-11eb-25da-87d7ef27f902
 # ╟─e825e690-39f9-11eb-21bc-099cc7a9e389
+# ╟─c35b8110-3a0a-11eb-11e8-73b1b2080079
+# ╠═7c64c710-3a0c-11eb-17bb-1db527c932a3
+# ╠═c8548b80-3a0a-11eb-067d-9dc6716dc325
+# ╠═9d1a8980-3a0d-11eb-380e-8fcaf30c849c
+# ╠═0f1d5380-3a10-11eb-2a71-1f0fddf65b70
+# ╟─d6afedee-3a0a-11eb-31d7-3f16633dbf5d
+# ╟─aa322be0-3a0e-11eb-27ec-d13acf9084aa
+# ╟─d867dd80-3a12-11eb-1ae7-3119a294b25a
diff --git a/data/day08.txt b/data/day08.txt
new file mode 100644
index 0000000..296e397
--- /dev/null
+++ b/data/day08.txt
@@ -0,0 +1,675 @@
+acc -8
+jmp +5
+acc +0
+acc +44
+acc +42
+jmp +324
+acc -17
+jmp +1
+acc -17
+jmp +51
+acc -13
+acc +4
+jmp +1
+nop +608
+jmp +274
+acc -17
+jmp +169
+acc +28
+nop +508
+jmp +1
+jmp +570
+acc +22
+acc -14
+jmp +377
+acc -13
+acc +27
+jmp +474
+acc -5
+jmp +1
+acc +12
+jmp +37
+jmp +184
+acc +36
+acc +32
+acc -8
+jmp +465
+acc -13
+acc +18
+jmp +169
+acc +20
+acc +26
+acc +23
+jmp +333
+jmp +584
+acc +9
+acc +28
+acc +28
+nop +571
+jmp +143
+acc +39
+acc +39
+acc -16
+jmp +361
+acc +48
+acc +3
+acc +15
+nop +4
+jmp +504
+acc +6
+jmp +285
+acc +26
+acc +33
+jmp +1
+acc +36
+jmp +577
+acc +36
+jmp +6
+nop +498
+acc +42
+jmp +496
+acc +10
+jmp +74
+acc +17
+acc +16
+acc +30
+jmp +254
+acc -3
+acc +16
+acc -2
+nop +106
+jmp +541
+acc -15
+jmp +579
+jmp +165
+acc +22
+acc -6
+acc +29
+acc -19
+jmp +342
+acc -19
+jmp +340
+acc +13
+acc +25
+acc +29
+jmp +269
+acc -14
+acc +27
+acc +41
+acc +49
+jmp +181
+nop +350
+jmp +1
+nop +437
+acc +34
+jmp +494
+acc +19
+acc +2
+acc +44
+jmp +558
+acc +10
+jmp +44
+nop +4
+nop -80
+nop +540
+jmp +16
+acc +28
+jmp +14
+acc +13
+nop +399
+acc +29
+nop -60
+jmp -6
+acc +41
+acc +30
+jmp +232
+acc +28
+nop +495
+acc +15
+acc +48
+jmp +157
+nop +483
+jmp -59
+acc +5
+acc +30
+acc +30
+acc +2
+jmp +349
+acc +11
+acc +27
+acc +1
+jmp +367
+acc +8
+acc +45
+acc +11
+jmp +171
+jmp -113
+acc +48
+jmp -38
+acc +12
+jmp +145
+acc +8
+nop +29
+nop +319
+jmp +154
+nop +166
+jmp +395
+nop +15
+jmp +237
+acc +22
+acc +3
+acc +42
+acc +1
+jmp +288
+jmp -63
+nop +489
+acc +33
+jmp +247
+jmp +1
+acc -8
+acc +9
+jmp +413
+acc -17
+acc +3
+acc +3
+jmp +432
+nop -17
+acc +36
+nop +198
+acc +45
+jmp +109
+nop +242
+acc +40
+acc +11
+jmp +448
+jmp +437
+acc +3
+acc +49
+acc +27
+jmp +221
+nop +158
+jmp +143
+acc +50
+jmp -70
+acc +46
+acc +8
+acc +35
+acc -3
+jmp +104
+acc +11
+acc +0
+jmp +34
+nop +132
+jmp +425
+jmp +219
+acc -12
+acc +48
+jmp +21
+jmp +434
+acc +30
+acc +1
+acc +40
+jmp +435
+jmp +132
+acc +40
+jmp +236
+jmp +179
+jmp -149
+acc +25
+acc +40
+acc -9
+acc +49
+jmp +445
+nop +399
+acc -14
+nop +374
+acc +0
+jmp +152
+acc +39
+nop +322
+acc +49
+nop +117
+jmp -19
+acc +24
+jmp +385
+acc +17
+acc +39
+acc +44
+acc -8
+jmp -58
+acc -18
+nop -76
+jmp +66
+acc +14
+jmp +427
+acc +11
+acc +47
+acc +9
+jmp +1
+acc +42
+jmp -7
+acc -16
+acc -13
+jmp +409
+acc +1
+acc +35
+acc +34
+jmp +371
+acc +24
+acc +46
+acc -4
+jmp +367
+acc +19
+acc +27
+acc -8
+acc +41
+jmp -184
+nop -185
+acc +23
+acc -8
+acc +35
+jmp -9
+acc -7
+nop -101
+nop +121
+acc +37
+jmp -72
+acc +24
+jmp +1
+nop -124
+jmp +163
+acc +37
+acc -12
+jmp +331
+acc -12
+acc +1
+jmp +232
+jmp -233
+jmp -72
+acc +28
+jmp +169
+acc +43
+acc +18
+nop +108
+jmp -184
+acc -4
+acc -10
+nop +317
+acc +48
+jmp +173
+nop +45
+jmp -73
+acc +35
+jmp +198
+acc -15
+acc +46
+acc +31
+jmp +41
+nop +169
+jmp +1
+nop -92
+nop -271
+jmp -113
+jmp +1
+nop -42
+jmp +42
+nop -283
+acc +22
+nop +200
+jmp -17
+jmp +1
+acc +49
+nop +35
+nop -185
+jmp +298
+acc +1
+jmp +1
+nop +301
+acc +19
+jmp -34
+jmp +163
+jmp +1
+acc +49
+jmp -115
+jmp -62
+acc +8
+acc +5
+acc -6
+jmp -146
+acc -4
+nop -202
+acc +47
+jmp -114
+acc +8
+jmp +57
+acc +37
+jmp +61
+jmp +267
+acc +2
+acc +28
+nop -20
+jmp -186
+acc +24
+nop +269
+acc +48
+acc +45
+jmp -22
+acc +11
+acc +36
+jmp -267
+acc +7
+nop -45
+nop -231
+jmp +32
+nop +220
+acc +19
+jmp -250
+acc +33
+jmp -169
+acc +45
+acc -13
+acc +0
+acc +44
+jmp +6
+acc +42
+jmp +84
+acc +48
+jmp -332
+jmp +213
+acc -16
+acc +31
+acc +17
+acc +3
+jmp -75
+jmp +1
+acc +11
+acc +4
+jmp -271
+acc -12
+nop +97
+nop +11
+jmp -43
+acc +30
+jmp +1
+jmp +49
+jmp -379
+nop -51
+acc +0
+acc -8
+nop -191
+jmp -346
+jmp -255
+acc +2
+acc +21
+acc -16
+nop +217
+jmp -30
+acc +31
+jmp -270
+jmp -324
+jmp +130
+acc +49
+nop +179
+jmp -37
+acc +11
+acc +15
+acc +29
+acc +17
+jmp -237
+acc +47
+acc -13
+acc +6
+jmp +169
+nop +54
+acc -12
+jmp -233
+nop +33
+acc +17
+acc +14
+acc +21
+jmp -275
+acc -8
+acc +1
+nop +229
+jmp +1
+jmp +119
+jmp -193
+nop +217
+jmp +95
+acc -2
+acc +1
+acc +41
+jmp -332
+acc +44
+nop -343
+acc +23
+jmp -165
+acc +7
+acc -12
+nop -339
+jmp +9
+nop -390
+acc -17
+acc +43
+jmp -138
+nop -247
+acc +42
+acc +0
+jmp +170
+acc +48
+jmp -139
+acc +6
+acc +13
+acc +35
+jmp -85
+nop -117
+jmp -307
+acc +25
+acc -10
+acc -14
+acc +0
+jmp -355
+jmp +102
+acc -8
+acc +47
+acc +36
+jmp +42
+acc +33
+acc +17
+acc +46
+jmp -331
+jmp +1
+acc -11
+jmp +1
+acc +27
+jmp +147
+acc -14
+nop -28
+acc +32
+jmp -482
+acc +11
+nop -390
+jmp -485
+acc -12
+acc +37
+acc +33
+acc +28
+jmp -32
+acc +42
+acc -11
+jmp -460
+acc +36
+acc +6
+acc +39
+jmp +80
+nop +123
+acc -13
+jmp -97
+acc +25
+acc +46
+acc +13
+nop -450
+jmp +84
+acc +3
+nop -260
+jmp +1
+acc +22
+jmp -510
+acc -4
+acc +17
+acc -19
+jmp -420
+acc -14
+acc +26
+acc +29
+acc +17
+jmp -458
+acc -10
+acc +23
+nop -2
+jmp -196
+acc -5
+jmp -416
+acc +49
+jmp -165
+acc +4
+acc +7
+acc +20
+nop -217
+jmp +103
+jmp +5
+acc -1
+acc +2
+jmp +1
+jmp +84
+acc -14
+jmp -518
+jmp +1
+acc +30
+acc +21
+jmp -202
+nop -18
+jmp -344
+jmp -88
+nop -472
+acc -5
+acc +13
+jmp -295
+nop -315
+acc +41
+nop -317
+jmp -299
+nop +105
+jmp -86
+acc +7
+jmp -226
+nop -277
+acc +21
+acc +13
+acc +47
+jmp -283
+acc -11
+acc -1
+jmp -408
+acc +47
+nop -553
+acc +37
+acc -11
+jmp -468
+acc +43
+nop -299
+acc +40
+acc +2
+jmp -275
+acc +24
+acc -14
+acc +13
+acc +36
+jmp -249
+acc +35
+jmp -45
+acc +47
+acc +31
+acc -19
+jmp -151
+jmp -33
+acc +6
+jmp -160
+jmp -553
+acc +25
+jmp +1
+nop -267
+jmp -430
+acc +23
+nop +63
+acc +37
+jmp -434
+nop -579
+jmp +11
+acc +25
+acc -17
+acc +22
+acc +27
+jmp +15
+jmp -546
+acc -4
+acc +41
+acc +0
+jmp -261
+acc +20
+jmp -404
+jmp -408
+acc +26
+jmp -464
+acc +34
+nop -80
+acc -12
+jmp -43
+jmp -410
+acc -13
+acc -3
+jmp -310
+nop -433
+acc -7
+acc -11
+acc +9
+jmp -29
+nop -564
+acc -5
+acc -16
+acc +36
+jmp -587
+jmp -115
+acc +24
+acc +35
+nop -638
+jmp -573
+acc +31
+acc +14
+jmp -609
+acc +25
+acc -10
+acc +18
+jmp -308
+acc +25
+acc +33
+acc +21
+acc -12
+jmp -172
+nop -37
+acc +12
+jmp -316
+acc +41
+acc +14
+jmp -415
+acc +40
+jmp -112
+jmp -613
+acc +26
+nop -151
+jmp -471
+acc +50
+acc +16
+nop -119
+acc +46
+jmp +1
-- 
2.45.2