main.go (2553B)
1 package main
2
3 import (
4 "bufio"
5 "fmt"
6 "os"
7 "regexp"
8 "sort"
9 "strings"
10 )
11
12 func readInput(filename string) (igdList, algList [][]string) {
13 file, _ := os.Open(filename)
14 defer file.Close()
15
16 matcher := regexp.MustCompile(`[a-z]+`)
17 scanner := bufio.NewScanner(file)
18 for scanner.Scan() {
19 food := strings.Split(scanner.Text(), " (contains ")
20 igd, alg := []string{}, []string{}
21 for _, v := range matcher.FindAllStringSubmatch(food[0], -1) {
22 igd = append(igd, v[0])
23 }
24 for _, v := range matcher.FindAllStringSubmatch(food[1], -1) {
25 alg = append(alg, v[0])
26 }
27 igdList = append(igdList, igd)
28 algList = append(algList, alg)
29 }
30 return
31 }
32
33 func main() {
34 igdList, algList := readInput("./input.txt")
35 // 1945
36 fmt.Println(part1(igdList, algList))
37 // pgnpx,srmsh,ksdgk,dskjpq,nvbrx,khqsk,zbkbgp,xzb
38 fmt.Println(part2(igdList, algList))
39 }
40
41 func decodeAllergen(igdList, algList [][]string) (algMap map[string]string) {
42 algCandidate := map[string]map[string]bool{}
43 for i := 0; i < len(igdList); i++ {
44 for _, alg := range algList[i] {
45 if _, ok := algCandidate[alg]; !ok {
46 algCandidate[alg] = map[string]bool{}
47 for _, igd := range igdList[i] {
48 algCandidate[alg][igd] = true
49 }
50 } else {
51 newCandidate := map[string]bool{}
52 for _, igd := range igdList[i] {
53 newCandidate[igd] = algCandidate[alg][igd]
54 }
55 algCandidate[alg] = newCandidate
56 }
57 }
58 }
59 // Find mapping by ellimination.
60 algMap = map[string]string{}
61 for len(algCandidate) > 0 {
62 for alg, candidates := range algCandidate {
63 var dangerCount int
64 var igdLast string
65 for igd, danger := range candidates {
66 if danger {
67 dangerCount += 1
68 igdLast = igd
69 }
70 }
71 if dangerCount == 1 {
72 algMap[alg] = igdLast
73 delete(algCandidate, alg)
74 for alg, _ := range algCandidate {
75 algCandidate[alg][igdLast] = false
76 }
77 }
78 }
79 }
80 return
81 }
82
83 func part1(igdList, algList [][]string) (res int) {
84 algMap := decodeAllergen(igdList, algList)
85 hasAlg := map[string]bool{}
86 for _, igd := range algMap {
87 hasAlg[igd] = true
88 }
89 for i := 0; i < len(igdList); i++ {
90 for _, igd := range igdList[i] {
91 if !hasAlg[igd] {
92 res += 1
93 }
94 }
95 }
96 return
97 }
98
99 func part2(igdList, algList [][]string) (res string) {
100 algMap := decodeAllergen(igdList, algList)
101 algNames := []string{}
102 for alg, _ := range algMap {
103 algNames = append(algNames, alg)
104 }
105 sort.Strings(algNames)
106 dangerList := []string{}
107 for _, alg := range algNames {
108 dangerList = append(dangerList, algMap[alg])
109 }
110 return strings.Join(dangerList, ",")
111 }