aboutsummaryrefslogtreecommitdiff
path: root/2021/18
diff options
context:
space:
mode:
authorJulien Dessaux2021-12-20 23:15:56 +0100
committerJulien Dessaux2021-12-20 23:16:51 +0100
commit11088124920c7bc8bd1c54c4265e9dcafb7a024b (patch)
treed9743eaf93ad6abd7ae46a8abda07e19a0527ad6 /2021/18
parentAdded solutions for 17th day: target practice (diff)
downloadadvent-of-code-11088124920c7bc8bd1c54c4265e9dcafb7a024b.tar.gz
advent-of-code-11088124920c7bc8bd1c54c4265e9dcafb7a024b.tar.bz2
advent-of-code-11088124920c7bc8bd1c54c4265e9dcafb7a024b.zip
Added solutions for 18th day: snailfish arithmetic
Diffstat (limited to '2021/18')
-rw-r--r--2021/18/example5
-rw-r--r--2021/18/example210
-rw-r--r--2021/18/example310
-rw-r--r--2021/18/first.go28
-rw-r--r--2021/18/go.mod3
-rw-r--r--2021/18/input100
-rw-r--r--2021/18/pairs/parser.go296
-rw-r--r--2021/18/second.go35
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)
+}