題目：Advent of Code 2019 Day 7
使用語言：C#
Day 7 的題目真的是大魔王，又用到了前幾個題目寫的IntCode Program，將IntCode Program當成Amplifier使用。
這題光Part 1讓輸入經過五個Amplifier就讓我卡了好久，還有五個數字的排列組合作為設定，這裡是有點作弊去Google研究了遞迴的寫法，然後Amplifier的邏輯也研究很久……
我還記得Part 1一開始寫出答案的程式並不是下面範例的模樣，一開始想說先有就好就有點懶得整理架構，結果Part 2馬上被打臉，只好乖乖整理物件和架構，然後不小心沒有保留到原本的版本。
Part 2則是多了循環機制，也是研究結束條件研究了很久，我想我最大的問題應該是英文理解能力吧……最後還是靠Reddit上的討論才看懂。
Part 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186using System;
using System.Collections.Generic;
public class Program
{
public static List<int> opCodeList = new List<int>() {1,2,3,4,5,6,7,8};
public static bool isHalt = false;
private static List<int[]> PhaseList = new List<int[]>();
private static int Phase = -1;
private static int[] Permutation = new int[5] {0,0,0,0,0};
public static void Main()
{
// P1
var inputArray = new int[] {3,8,1001,8,10,8,105,1,0,0,21,42,51,76,101,118,199,280,361,442,99999,3,9,101,5,9,9,102,2,9,9,1001,9,4,9,102,2,9,9,4,9,99,3,9,1002,9,3,9,4,9,99,3,9,1002,9,4,9,1001,9,3,9,1002,9,5,9,101,3,9,9,1002,9,2,9,4,9,99,3,9,101,4,9,9,1002,9,2,9,1001,9,3,9,1002,9,3,9,101,4,9,9,4,9,99,3,9,101,3,9,9,1002,9,3,9,101,2,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,99,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,101,1,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,99};
//TEST
//var inputArray = new int[] {3,15,3,16,1002,16,10,16,1,16,15,15,4,15,99,0,0};
// 計算所有Phase Setting
CalculatePermutation(0);
int signal = 0;
int finalSignal = 0;
int[] finalPermutation = new int[5] {0,0,0,0,0};
// 取得每一台增幅器的Phase Setting
for(int phaseCount = 0;phaseCount<PhaseList.Count;phaseCount++)
{
// 建立五台增幅器
var ampA = new Amplifier(inputArray);
var ampB = new Amplifier(inputArray);
var ampC = new Amplifier(inputArray);
var ampD = new Amplifier(inputArray);
var ampE = new Amplifier(inputArray);
isHalt = false;
signal = 0;
var phaseSetting = PhaseList[phaseCount];
// 執行五台增幅器
signal = ampA.Amplify(signal, phaseSetting[0]);
signal = ampB.Amplify(signal, phaseSetting[1]);
signal = ampC.Amplify(signal, phaseSetting[2]);
signal = ampD.Amplify(signal, phaseSetting[3]);
signal = ampE.Amplify(signal, phaseSetting[4]);
if(finalSignal.Equals(0) || signal > finalSignal)
{
finalPermutation = phaseSetting;
finalSignal = signal;
}
}
Console.WriteLine("Result = " + finalSignal);
Console.WriteLine("finalPermutation = " + finalPermutation[0] + finalPermutation[1] + finalPermutation[2] + finalPermutation[3] + finalPermutation[4]);
}
public static void CalculatePermutation(int PermutationCount)
{
Phase++;
Permutation.SetValue(Phase, PermutationCount);
if(Phase.Equals(4))
{
PhaseList.Add(new int[] {Permutation[0], Permutation[1], Permutation[2], Permutation[3], Permutation[4]});
}
else
{
for(int i = 0;i < 5;i++)
if(Permutation[i].Equals(0)) CalculatePermutation(i);
}
Phase--;
Permutation.SetValue(0, PermutationCount);
}
public static int IntcodeProgram(ref int[] inputArray, int input, int phase)
{
int i = 0;
int outputValue = 0;
bool usePhase = false;
while(i < inputArray.Length)
{
var opCodeDigit = inputArray[i];
var opCode = opCodeDigit % 100;
var firstValueParameterMode = opCodeDigit / 100 % 10;
var secondValueParameterMode = opCodeDigit / 1000 % 10;
var ouputValueParameterMode = opCodeDigit / 10000 % 10;
if(opCode.Equals(99) || (!opCodeList.Contains(opCode))) break;
int outputPosition = 0;
int firstValue = 0;
int secondValue = 0;
firstValue = GetValue(firstValueParameterMode, inputArray[i+1], inputArray);
if(!opCode.Equals(3) && !opCode.Equals(4))
secondValue = GetValue(secondValueParameterMode, inputArray[i+2], inputArray);
switch(opCode)
{
case 1:
outputPosition = inputArray[i+3];
inputArray[outputPosition] = firstValue + secondValue;
i+=4;
break;
case 2:
outputPosition = inputArray[i+3];
inputArray[outputPosition] = firstValue * secondValue;
i+=4;
break;
case 3:
firstValue = inputArray[i+1];
// 第一次執行時使用Phase
inputArray[firstValue] = usePhase ? input : phase;
usePhase = true;
i+=2;
break;
case 4:
outputValue = firstValue;
i+=2;
break;
case 5:
if(!firstValue.Equals(0)) i = secondValue;
else i+=3;
break;
case 6:
if(firstValue.Equals(0)) i = secondValue;
else i+=3;
break;
case 7:
outputPosition = inputArray[i+3];
if(firstValue < secondValue) inputArray[outputPosition] = 1;
else inputArray[outputPosition] = 0;
i+=4;
break;
case 8:
outputPosition = inputArray[i+3];
if(firstValue.Equals(secondValue)) inputArray[outputPosition] = 1;
else inputArray[outputPosition] = 0;
i+=4;
break;
}
}
return outputValue;
}
public static int GetValue(int mode, int value, int[] dataSource)
{
if(mode.Equals(0))
return dataSource[value];
return value;
}
public class Amplifier
{
private int[] _intCodeArray = null;
public bool _usePhase = false;
public int[] intCodeArray
{
get { return _intCodeArray; }
}
public Amplifier(int[] inputArray)
{
_intCodeArray = inputArray;
}
public int Amplify(int input, int phase)
{
if(_usePhase)
{
phase = input;
_usePhase = true;
}
return IntcodeProgram(ref _intCodeArray, input, phase);
}
}
}
Part 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
using System;
using System.Collections.Generic;
public class Program
{
public static List<int> opCodeList = new List<int>() {1,2,3,4,5,6,7,8};
public static bool isHalt = false;
private static List<int[]> PhaseList = new List<int[]>();
private static int Phase = -1;
private static int[] Permutation = new int[5] {0,0,0,0,0};
private static int[] PhaseInput = new int[5] {5,6,7,8,9};
public static void Main()
{
// Input
var inputArray = new int[] {3,8,1001,8,10,8,105,1,0,0,21,42,51,76,101,118,199,280,361,442,99999,3,9,101,5,9,9,102,2,9,9,1001,9,4,9,102,2,9,9,4,9,99,3,9,1002,9,3,9,4,9,99,3,9,1002,9,4,9,1001,9,3,9,1002,9,5,9,101,3,9,9,1002,9,2,9,4,9,99,3,9,101,4,9,9,1002,9,2,9,1001,9,3,9,1002,9,3,9,101,4,9,9,4,9,99,3,9,101,3,9,9,1002,9,3,9,101,2,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,99,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,101,1,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,99};
// Test 1
//var inputArray = new int[] {3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5};
// Test 2
//var inputArray = new int[] {3,52,1001,52,-5,52,3,53,1,52,56,54,1007,54,5,55,1005,55,26,1001,54,-5,54,1105,1,12,1,53,54,53,1008,54,0,55,1001,55,1,55,2,53,55,53,4,53,1001,56,-1,56,1005,56,6,99,0,0,0,0,10};
// 計算所有Phase Setting
CalculatePermutation(0);
int signal = 0;
int finalSignal = 0;
int[] finalPermutation = new int[5] {0,0,0,0,0};
Console.WriteLine("PhaseList = " + PhaseList.Count);
// 取得每一台增幅器的Phase Setting
for(int phaseCount = 0;phaseCount<PhaseList.Count;phaseCount++)
{
// 建立五台增幅器
var ampA = new Amplifier(inputArray);
var ampB = new Amplifier(inputArray);
var ampC = new Amplifier(inputArray);
var ampD = new Amplifier(inputArray);
var ampE = new Amplifier(inputArray);
isHalt = false;
signal = 0;
var phaseSetting = PhaseList[phaseCount];
while(!isHalt)
{
// 執行五台增幅器
signal = ampA.Amplify(signal, phaseSetting[0]);
signal = ampB.Amplify(signal, phaseSetting[1]);
signal = ampC.Amplify(signal, phaseSetting[2]);
signal = ampD.Amplify(signal, phaseSetting[3]);
signal = ampE.Amplify(signal, phaseSetting[4]);
}
if(finalSignal.Equals(0) || signal > finalSignal)
{
finalPermutation = phaseSetting;
finalSignal = signal;
}
}
Console.WriteLine("Result = " + finalSignal);
Console.WriteLine("finalPermutation = " + finalPermutation[0] + finalPermutation[1] + finalPermutation[2] + finalPermutation[3] + finalPermutation[4]);
}
public static void CalculatePermutation(int PermutationCount)
{
Phase++;
Permutation.SetValue(Phase, PermutationCount);
if(Phase.Equals(4))
{
PhaseList.Add(new int[] {PhaseInput[Permutation[0]], PhaseInput[Permutation[1]], PhaseInput[Permutation[2]], PhaseInput[Permutation[3]], PhaseInput[Permutation[4]]});
}
else
{
for(int i = 0;i < 5;i++)
if(Permutation[i].Equals(0)) CalculatePermutation(i);
}
Phase--;
Permutation.SetValue(0, PermutationCount);
}
public static void PrintArray(int[] intArray)
{
var output = string.Empty;
for(int i = 0; i < intArray.Length;i++)
{
output += intArray[i] + ", ";
}
Console.WriteLine(output);
}
public static (int output, int pointer) IntcodeProgram(ref int[] inputArray, int input, int phase, int pointer)
{
int i = pointer;
int outputValue = 0;
bool usePhase = false;
while(i < inputArray.Length)
{
var opCodeDigit = inputArray[i];
var opCode = opCodeDigit % 100;
var firstValueParameterMode = opCodeDigit / 100 % 10;
var secondValueParameterMode = opCodeDigit / 1000 % 10;
var ouputValueParameterMode = opCodeDigit / 10000 % 10;
if(opCode.Equals(99) || (!opCodeList.Contains(opCode)))
{
isHalt = true;
return (input, 0);
}
int outputPosition = 0;
int firstValue = 0;
int secondValue = 0;
firstValue = GetValue(firstValueParameterMode, inputArray[i+1], inputArray);
if(!opCode.Equals(3) && !opCode.Equals(4))
secondValue = GetValue(secondValueParameterMode, inputArray[i+2], inputArray);
switch(opCode)
{
case 1:
outputPosition = inputArray[i+3];
inputArray[outputPosition] = firstValue + secondValue;
i+=4;
break;
case 2:
outputPosition = inputArray[i+3];
inputArray[outputPosition] = firstValue * secondValue;
i+=4;
break;
case 3:
firstValue = inputArray[i+1];
// 第一次執行時使用Phase
inputArray[firstValue] = usePhase ? input : phase;
usePhase = true;
i+=2;
break;
case 4:
outputValue = firstValue;
i+=2;
return (outputValue, i);
case 5:
if(!firstValue.Equals(0)) i = secondValue;
else i+=3;
break;
case 6:
if(firstValue.Equals(0)) i = secondValue;
else i+=3;
break;
case 7:
outputPosition = inputArray[i+3];
if(firstValue < secondValue) inputArray[outputPosition] = 1;
else inputArray[outputPosition] = 0;
i+=4;
break;
case 8:
outputPosition = inputArray[i+3];
if(firstValue.Equals(secondValue)) inputArray[outputPosition] = 1;
else inputArray[outputPosition] = 0;
i+=4;
break;
}
}
return (outputValue, i);
}
public static int GetValue(int mode, int value, int[] dataSource)
{
if(mode.Equals(0))
return dataSource[value];
return value;
}
public class Amplifier
{
private int[] _intCodeArray = null;
// 記錄Amplifier執行到IntCodeArray的哪個位置
private int arrayPointer = 0;
public bool _usePhase = false;
public int[] intCodeArray
{
get { return _intCodeArray; }
}
public Amplifier(int[] inputArray)
{
_intCodeArray = (int[])inputArray.Clone();
inputArray.CopyTo(_intCodeArray, 0);
}
public int Amplify(int input, int phase)
{
if(_usePhase)
{
phase = input;
}
_usePhase = true;
var result = IntcodeProgram(ref _intCodeArray, input, phase, arrayPointer);
// 保留Amplifier的執行位置
arrayPointer = result.pointer;
return result.output;
}
}
}
Comments