-
Notifications
You must be signed in to change notification settings - Fork 0
/
AoC2020d7.java
67 lines (54 loc) · 2.17 KB
/
AoC2020d7.java
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
/***************************************
* Chris Carmine
* https://adventofcode.com/2020/day/7
***************************************/
import java.util.ArrayList;
import java.util.Stack;
public class AoC2020d7 {
public static void main(String args[]){
final int[][] rules = fileParse.ruleGen(args[0]);
boolean targetFound = false;
int numShinyGold = 0;
int row = 0;
int bag = 0;
int col = 0;
ArrayList<Integer> shinyGolds = new ArrayList<Integer>();
ArrayList<Integer> tree = new ArrayList<Integer>();
Stack<Integer> branch = new Stack<Integer>();
int shinyGoldIndex = 479;
for (bag = 0; bag < rules.length; bag++){
tree.clear();
branch.clear();
branch.push(-1); //dummy entry to enter the loop
row = bag;
tree.add(bag); //add yourself to the search tree
//build the tree
while(!branch.isEmpty()){
branch.pop(); //pop off inital dummy value and prior branch value
for (col = 0; col < rules[row].length;col++){
if (rules[row][col] != 0){
tree.add(col);
branch.push(col); //branches I am not sure get added to search tree, they may be empty
}
}
if (!branch.isEmpty()){
row = branch.peek();
}
}
//search the tree
targetFound = false;
for (Integer i : tree){
//System.out.printf("Branch %d, Searching bag %d%n",bag,i);
if (rules[i][shinyGoldIndex]!=0 && !targetFound){ // target is 4 in the smoke test, 479 in real puzzle
targetFound = true;
shinyGolds.add(bag);
numShinyGold++;
}
}
} // main for
System.out.printf("Number of shiny gold bags: %d%n",numShinyGold);
for (Integer s : shinyGolds){
System.out.printf("Bag %d%n",s);
}
} //main
} //class