diff options
Diffstat (limited to '')
| -rw-r--r-- | 2021/18/example | 5 | ||||
| -rw-r--r-- | 2021/18/example2 | 10 | ||||
| -rw-r--r-- | 2021/18/example3 | 10 | ||||
| -rw-r--r-- | 2021/18/first.go | 28 | ||||
| -rw-r--r-- | 2021/18/go.mod | 3 | ||||
| -rw-r--r-- | 2021/18/input | 100 | ||||
| -rw-r--r-- | 2021/18/pairs/parser.go | 296 | ||||
| -rw-r--r-- | 2021/18/second.go | 35 |
8 files changed, 487 insertions, 0 deletions
diff --git a/2021/18/example b/2021/18/example new file mode 100644 index 0000000..13fdd19 --- /dev/null +++ b/2021/18/example @@ -0,0 +1,5 @@ +[1,1] +[2,2] +[3,3] +[4,4] +[5,5] diff --git a/2021/18/example2 b/2021/18/example2 new file mode 100644 index 0000000..70e9071 --- /dev/null +++ b/2021/18/example2 @@ -0,0 +1,10 @@ +[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]] +[7,[[[3,7],[4,3]],[[6,3],[8,8]]]] +[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]] +[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]] +[7,[5,[[3,8],[1,4]]]] +[[2,[2,2]],[8,[8,1]]] +[2,9] +[1,[[[9,3],9],[[9,0],[0,7]]]] +[[[5,[7,4]],7],1] +[[[[4,2],2],6],[8,7]] diff --git a/2021/18/example3 b/2021/18/example3 new file mode 100644 index 0000000..1368dc4 --- /dev/null +++ b/2021/18/example3 @@ -0,0 +1,10 @@ +[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]] +[[[5,[2,8]],4],[5,[[9,9],0]]] +[6,[[[6,2],[5,6]],[[7,6],[4,7]]]] +[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]] +[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]] +[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]] +[[[[5,4],[7,7]],8],[[8,3],8]] +[[9,3],[[9,9],[6,[4,9]]]] +[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]] +[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]] diff --git a/2021/18/first.go b/2021/18/first.go new file mode 100644 index 0000000..ffe7050 --- /dev/null +++ b/2021/18/first.go @@ -0,0 +1,28 @@ +package main + +import ( + "fmt" + "log" + "os" + + "git.adyxax.org/aoc/2021/18/pairs" +) + +func main() { + parser := pairs.NewParser(os.Stdin) + pair, err := parser.Parse() + if err != nil { + log.Fatalf("%w", err) + } + for { + pair2, err := parser.Parse() + if err != nil { + break + } + pair = pair.Add(pair2) + } + fmt.Println(pair) + pair.Reduce() + fmt.Println(pair) + fmt.Println(pair.Magnitude()) +} diff --git a/2021/18/go.mod b/2021/18/go.mod new file mode 100644 index 0000000..6f1a126 --- /dev/null +++ b/2021/18/go.mod @@ -0,0 +1,3 @@ +module git.adyxax.org/aoc/2021/18 + +go 1.17 diff --git a/2021/18/input b/2021/18/input new file mode 100644 index 0000000..0e53f1b --- /dev/null +++ b/2021/18/input @@ -0,0 +1,100 @@ +[[[[8,1],8],[[8,1],0]],[[8,[2,4]],[0,8]]] +[[[[2,2],[7,4]],[[9,1],6]],8] +[[[3,6],[[8,7],[2,9]]],[8,[[2,3],9]]] +[[[[4,5],[1,4]],1],[[0,8],[2,[6,8]]]] +[[7,[[4,6],[0,0]]],[[4,3],5]] +[[[[8,4],4],[[4,4],[1,0]]],[[5,[5,5]],[[5,2],1]]] +[[[0,[5,8]],[1,7]],[[[5,0],[1,3]],7]] +[4,[[[6,2],[7,8]],[0,[4,4]]]] +[[[3,[5,3]],8],[[[6,8],4],[8,9]]] +[[[6,0],[9,[8,1]]],[[[9,7],3],0]] +[[9,[[9,3],[0,8]]],[[[5,3],0],[[5,6],2]]] +[[3,[[7,7],3]],[[7,[5,2]],[[6,9],0]]] +[1,[4,[3,8]]] +[[[[0,2],9],[[0,7],8]],[[5,4],[2,8]]] +[[[[1,8],9],[1,7]],[[4,[8,5]],[[6,3],[1,0]]]] +[[9,[[4,3],[3,3]]],[[[4,9],[0,9]],6]] +[7,[[8,0],[5,6]]] +[[[[3,2],1],[[4,9],6]],[[9,[1,1]],[[8,7],1]]] +[[[[5,1],[3,3]],0],[1,[[3,2],2]]] +[[7,9],[[9,9],[5,[9,5]]]] +[[[[4,3],[1,7]],[4,[9,2]]],[[6,[1,7]],[[8,0],3]]] +[[[5,[2,8]],[[1,2],7]],[[3,[0,5]],[[3,5],8]]] +[[[[2,2],6],[[2,1],7]],[[[4,6],8],7]] +[[2,[[3,0],[0,5]]],[[[3,4],[0,1]],0]] +[[[[9,9],5],[[9,9],6]],[[[4,1],2],0]] +[4,[[2,9],[6,2]]] +[[[8,6],6],7] +[[7,[8,2]],[[[5,5],6],[9,0]]] +[5,[[2,5],[[4,9],[8,6]]]] +[[4,[7,[9,6]]],7] +[[[9,[3,3]],[[3,1],[8,7]]],[[6,[3,5]],[4,1]]] +[[8,6],[8,[[0,2],[8,1]]]] +[6,[8,[[7,7],0]]] +[3,4] +[[9,[8,0]],[[[7,8],3],1]] +[5,[[3,[8,7]],[[5,0],[9,7]]]] +[[[[4,2],9],[6,[0,2]]],6] +[[4,[3,[4,9]]],[[4,[1,6]],1]] +[[[6,3],[8,8]],[5,[[9,3],[6,3]]]] +[[[9,9],[[7,1],6]],[[[1,0],[7,4]],[3,[2,0]]]] +[[[[2,5],9],[3,[6,2]]],[4,7]] +[[1,[7,8]],[[[0,1],8],[[1,1],9]]] +[[[9,[6,4]],[[9,8],[0,2]]],[[[8,9],[2,3]],[3,[8,0]]]] +[[[[6,8],2],3],[[2,2],5]] +[[[4,[8,5]],[[4,3],1]],[[[2,4],[4,4]],[[4,1],[1,7]]]] +[[[[2,6],6],[[9,2],4]],[[[9,9],[9,5]],5]] +[[[[7,5],[4,9]],4],[[[0,7],[3,6]],[[6,5],[3,0]]]] +[[[4,4],[[5,7],[8,5]]],[0,8]] +[[3,[[1,3],[7,5]]],[6,[[8,1],0]]] +[[[9,9],[5,[9,6]]],[[[4,0],[5,4]],6]] +[0,[[[9,2],4],3]] +[[[1,[8,5]],[0,[6,0]]],[[[6,5],[3,1]],[[6,2],[1,5]]]] +[[[4,0],[4,7]],6] +[1,[[[5,2],9],[[3,9],4]]] +[[[[9,6],[4,1]],4],[2,[[0,2],6]]] +[9,[[[1,5],[3,1]],1]] +[5,0] +[9,[[[7,5],[2,1]],[[2,3],[5,3]]]] +[[5,[[0,5],[9,5]]],[[[2,7],3],[[2,9],[3,5]]]] +[[[1,9],2],[[7,[1,7]],[8,[9,8]]]] +[[8,9],[[5,[9,0]],[[6,8],[5,2]]]] +[6,[[[1,3],[0,8]],4]] +[[[[9,8],[0,9]],[[8,4],[3,5]]],[[[5,0],8],[[6,8],1]]] +[[6,[[1,4],[7,0]]],[[3,4],[[2,1],[2,7]]]] +[[[5,0],[3,[4,7]]],[[9,3],[[9,4],[9,6]]]] +[[[[8,3],[8,0]],5],[[[5,5],[0,2]],[[0,1],9]]] +[[[[6,4],[1,8]],[3,[0,2]]],[8,[[8,8],5]]] +[2,[[2,1],[1,4]]] +[8,[0,[3,5]]] +[[[[0,2],3],[[4,9],[1,2]]],[[8,2],[6,[7,1]]]] +[[[0,0],9],1] +[8,[[4,1],[[1,3],9]]] +[[[8,[5,9]],9],[[[5,7],[9,0]],3]] +[[5,[2,9]],7] +[5,6] +[[[[7,5],[8,3]],[[4,3],8]],[[2,2],[[7,2],[4,2]]]] +[[[9,5],[3,[1,5]]],6] +[[[[7,4],[7,9]],[[3,1],[3,1]]],[[[6,4],[0,1]],1]] +[[3,[[7,4],9]],[[[5,8],[2,7]],[[0,4],[3,6]]]] +[[[3,[2,3]],[[6,0],[7,7]]],1] +[[2,[[8,8],[2,3]]],[5,2]] +[[[0,[5,5]],[8,1]],5] +[[3,9],[6,[[0,5],[1,7]]]] +[[[[3,0],9],[8,2]],[[[2,2],8],0]] +[[[9,6],[[5,1],[4,9]]],[[[1,1],[0,3]],[[4,9],[7,5]]]] +[[[2,[6,1]],[[5,7],[9,2]]],[[[4,2],8],9]] +[[9,[7,1]],[[4,5],[9,1]]] +[[9,[5,0]],[[1,7],[[9,6],[4,5]]]] +[[[[1,1],[8,7]],4],[[0,4],[[1,7],[3,5]]]] +[[5,[1,[8,4]]],[[[9,4],0],[1,[5,5]]]] +[[[5,[1,6]],[6,0]],[[0,[9,7]],1]] +[2,[9,[[0,3],[2,3]]]] +[3,[4,[[0,9],8]]] +[[5,6],[[[9,9],[4,0]],[7,[2,0]]]] +[[[[5,1],6],[[1,0],[7,1]]],[[6,[1,0]],[[4,2],[0,0]]]] +[[[4,[0,2]],6],[[[4,3],[8,0]],[[9,6],[1,5]]]] +[[[[5,3],[2,2]],[8,[8,3]]],[[9,1],2]] +[[3,4],[[[4,7],[2,3]],[9,[9,0]]]] +[[[5,[6,2]],[[1,5],[9,2]]],[[[7,9],3],[[6,7],[6,2]]]] +[[[5,3],9],[[2,[4,3]],[[5,3],1]]] diff --git a/2021/18/pairs/parser.go b/2021/18/pairs/parser.go new file mode 100644 index 0000000..08183e4 --- /dev/null +++ b/2021/18/pairs/parser.go @@ -0,0 +1,296 @@ +package pairs + +import ( + "bufio" + "bytes" + "fmt" + "io" + "strconv" +) + +// Token represents a lexical token. +type Token int + +const ( + // Special tokens + ILLEGAL Token = iota + EOF + WHITESPACE + + // Literals + INT // integers + + // Misc characters + COMMA // , + OPEN_BRACKET + CLOSE_BRACKET +) + +type Pair struct { + HasSubPairs bool + Value int + Left, Right *Pair +} + +func (p Pair) String() string { + if p.HasSubPairs { + return fmt.Sprintf("[%s, %s]", p.Left.String(), p.Right.String()) + } + return fmt.Sprintf("%d", p.Value) +} + +func (p Pair) Magnitude() int { + if p.HasSubPairs { + return 3*p.Left.Magnitude() + 2*p.Right.Magnitude() + } + return p.Value +} + +func (p1 *Pair) Add(p2 *Pair) *Pair { + p := &Pair{ + HasSubPairs: true, + Left: p1, + Right: p2, + } + p.Reduce() + return p +} + +func (p Pair) DeepCopy() *Pair { + if p.HasSubPairs { + return &Pair{ + HasSubPairs: true, + Left: p.Left.DeepCopy(), + Right: p.Right.DeepCopy(), + } + } + return &Pair{Value: p.Value} +} + +func (p *Pair) Reduce() { + for { + if exploded, _, _ := p.TryExplode(0); exploded { + continue + } + if p.TrySplit() { + continue + } + break + } +} + +func (p *Pair) TrySplit() bool { + if p.HasSubPairs { + if p.Left.TrySplit() { + return true + } + return p.Right.TrySplit() + } + if p.Value >= 10 { + p.HasSubPairs = true + p.Left = &Pair{Value: p.Value / 2} + p.Right = &Pair{Value: p.Value/2 + p.Value%2} + p.Value = 0 + return true + } + return false +} + +func (p *Pair) TryExplode(depth int) (bool, *int, *int) { + if !p.HasSubPairs { + return false, nil, nil + } + if depth >= 4 { + p.HasSubPairs = false + p.Value = 0 + l := p.Left.Value + r := p.Right.Value + p.Left = nil + p.Right = nil + return true, &l, &r + } + depth++ + if exploded, l, r := p.Left.TryExplode(depth); exploded { + if r != nil { + r = p.Right.TryAddToLeftMostNumber(r) + } + return exploded, l, r + } + if exploded, l, r := p.Right.TryExplode(depth); exploded { + if l != nil { + l = p.Left.TryAddToRightMostNumber(l) + } + return exploded, l, r + } + return false, nil, nil +} + +func (p *Pair) TryAddToLeftMostNumber(n *int) *int { + if p.HasSubPairs { + return p.Left.TryAddToLeftMostNumber(n) + } + p.Value += *n + return nil +} + +func (p *Pair) TryAddToRightMostNumber(n *int) *int { + if p.HasSubPairs { + return p.Right.TryAddToRightMostNumber(n) + } + p.Value += *n + return nil +} + +func isWhitespace(ch rune) bool { + return ch == ' ' || ch == '\t' || ch == '\n' +} + +func isDigit(ch rune) bool { + return (ch >= '0' && ch <= '9') +} + +var eof = rune(0) + +// Scanner represents a lexical scanner. +type Scanner struct { + r *bufio.Reader +} + +// NewScanner returns a new instance of Scanner. +func NewScanner(r io.Reader) *Scanner { + return &Scanner{r: bufio.NewReader(r)} +} + +// read reads the next rune from the bufferred reader. +// Returns the rune(0) if an error occurs (or io.EOF is returned). +func (s *Scanner) read() rune { + ch, _, err := s.r.ReadRune() + if err != nil { + return eof + } + return ch +} + +// unread places the previously read rune back on the reader. +func (s *Scanner) unread() { _ = s.r.UnreadRune() } + +// Scan returns the next token and literal value. +func (s *Scanner) Scan() (tok Token, lit string) { + // Read the next rune. + ch := s.read() + + // If we see whitespace then consume all contiguous whitespace. + for isWhitespace(ch) { + ch = s.read() + } + + // If we see a digit then consume as an int. + if isDigit(ch) { + return s.scanInt(ch) + } + + // Otherwise read the individual character. + switch ch { + case eof: + return EOF, "" + case ',': + return COMMA, string(ch) + case '[': + return OPEN_BRACKET, string(ch) + case ']': + return CLOSE_BRACKET, string(ch) + } + + return ILLEGAL, string(ch) +} + +// scanInt consumes the current rune and all contiguous digit runes. +func (s *Scanner) scanInt(read rune) (tok Token, lit string) { + // Create a buffer and read the current character into it. + var buf bytes.Buffer + buf.WriteRune(read) + + // Read every subsequent ident character into the buffer. + // Non-ident characters and EOF will cause the loop to exit. + for { + if ch := s.read(); ch == eof { + break + } else if !isDigit(ch) { + s.unread() + break + } else { + _, _ = buf.WriteRune(ch) + } + } + + // Otherwise return as a regular identifier. + return INT, buf.String() +} + +// Parser represents a parser. +type Parser struct { + s *Scanner + buf struct { + tok Token // last read token + lit string // last read literal + n int // buffer size (max=1) + } +} + +// NewParser returns a new instance of Parser. +func NewParser(r io.Reader) *Parser { + return &Parser{s: NewScanner(r)} +} + +// scan returns the next token from the underlying scanner. +// If a token has been unscanned then read that instead. +func (p *Parser) scan() (tok Token, lit string) { + // If we have a token on the buffer, then return it. + if p.buf.n != 0 { + p.buf.n = 0 + return p.buf.tok, p.buf.lit + } + + // Otherwise read the next token from the scanner. + tok, lit = p.s.Scan() + + // Save it to the buffer in case we unscan later. + p.buf.tok, p.buf.lit = tok, lit + + return +} + +// unscan pushes the previously read token back onto the buffer. +func (p *Parser) unscan() { p.buf.n = 1 } + +func (p *Parser) Parse() (pair *Pair, err error) { + pair = &Pair{} + tok, lit := p.scan() + switch tok { + case OPEN_BRACKET: + pair.HasSubPairs = true + pair.Left, err = p.Parse() + if err != nil { + return nil, err + } + if tok, lit := p.scan(); tok != COMMA { + return nil, fmt.Errorf("found %q, expected COMMA", lit) + } + pair.Right, err = p.Parse() + if err != nil { + return nil, err + } + if tok, lit := p.scan(); tok != CLOSE_BRACKET { + return nil, fmt.Errorf("found %q, expected CLOSE_BRACKET", lit) + } + case INT: + if v, err := strconv.Atoi(lit); err != nil { + return nil, fmt.Errorf("failed to atoi an INT %s : %w", lit, err) + } else { + pair.Value = v + } + default: + return nil, fmt.Errorf("unexpected %q, expected OPEN_BRACKER or INT", lit) + } + return pair, nil +} diff --git a/2021/18/second.go b/2021/18/second.go new file mode 100644 index 0000000..6070d74 --- /dev/null +++ b/2021/18/second.go @@ -0,0 +1,35 @@ +package main + +import ( + "fmt" + "os" + + "git.adyxax.org/aoc/2021/18/pairs" +) + +func main() { + max := 0 + parser := pairs.NewParser(os.Stdin) + pairs := make([]*pairs.Pair, 0) + for { + pair, err := parser.Parse() + if err != nil { + break + } + pairs = append(pairs, pair) + } + l := len(pairs) + for i := 0; i < l; i++ { + for j := 0; j < l; j++ { + if i == j { + continue + } + p1 := pairs[i].DeepCopy() + p2 := pairs[j].DeepCopy() + if m := p1.Add(p2).Magnitude(); max < m { + max = m + } + } + } + fmt.Println(max) +} |