Day 10: Syntax Scoring

s=0
for l in open(0):
 k=[]
 for c in l[:-1]:
  if 5922%(ord(c)+1):k+=[c]
  elif abs(ord(c)-ord(k.pop()))>2:s+={1:3,3:57,0:1197,2:25137}[ord(c)%5]
print(s)

S=[]
for l in open(0):
 k=[]
 for c in l[:-1]:
  if 5922%(ord(c)+1):k=[c]+k
  elif abs(ord(c)-ord(k.pop(0)))>2:k=[];break
 if k:
  e=''.join(chr(ord(c)+(1 if c=='('else 2))for c in k);s=0
  for c in e:s*=5;s+={1:1,3:2,0:3,2:4}[ord(c)%5]
  S.append(s)
print(sorted(S)[len(S)//2])

defmodule AdventOfCode.Solution.Year2021.Day10 do
  def part1(input) do
    input
    |> parse_input()
    |> Enum.map(&corrupted_char/1)
    |> Enum.reject(&is_nil/1)
    |> Enum.map(&corrupted_score/1)
    |> Enum.sum()
  end

  def part2(input) do
    input
    |> parse_input()
    |> Enum.map(&incomplete_stack/1)
    |> Enum.reject(&match?('', &1))
    |> Enum.map(&autocomplete_score/1)
    |> Enum.sort()
    |> then(fn scores -> Enum.at(scores, div(length(scores), 2)) end)
  end

  defp corrupted_char(line, bracket_stack \\ '')

  defp corrupted_char('', _), do: nil

  for {open, close} <- [{?(, ?)}, {?[, ?]}, {?{, ?}}, {?<, ?>}] do
    defp corrupted_char([unquote(open) | rest_line], stack) do
      corrupted_char(rest_line, [unquote(close) | stack])
    end

    defp corrupted_char([unquote(close) | rest_line], [unquote(close) | rest_stack]) do
      corrupted_char(rest_line, rest_stack)
    end
  end

  defp corrupted_char([char | _], _), do: char

  defp incomplete_stack(line, bracket_stack \\ '')

  defp incomplete_stack('', stack), do: stack

  for {open, close} <- [{?(, ?)}, {?[, ?]}, {?{, ?}}, {?<, ?>}] do
    defp incomplete_stack([unquote(open) | rest_line], stack) do
      incomplete_stack(rest_line, [unquote(close) | stack])
    end

    defp incomplete_stack([unquote(close) | rest_line], [unquote(close) | rest_stack]) do
      incomplete_stack(rest_line, rest_stack)
    end
  end

  defp incomplete_stack([_ | _], _), do: ''

  defp corrupted_score(?)), do: 3
  defp corrupted_score(?]), do: 57
  defp corrupted_score(?}), do: 1197
  defp corrupted_score(?>), do: 25137

  defp autocomplete_score(stack) do
    Enum.reduce(stack, 0, fn char, acc -> acc * 5 + autocomplete_point_value(char) end)
  end

  defp autocomplete_point_value(?)), do: 1
  defp autocomplete_point_value(?]), do: 2
  defp autocomplete_point_value(?}), do: 3
  defp autocomplete_point_value(?>), do: 4

  defp parse_input(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&String.to_charlist/1)
  end
end

Use a stack!

Pattern matching is a core concept in Elixir, and allows for pretty concise and expressive code. It's sort of like JavaScript's destructuring on steroids—you can bind nested values in a data structure to variables while also asserting the shape of the structure. Pattern matching is most often done with the case expression, but it's also possible to use directly in function heads and in many other parts of the language.

At its core, pattern matching lets you write assertive code based on how the data looks, which can be more expressive than in other languages where the main tool at your disposal is if + an expression that evaluates to a boolean.

data = %{a: %{b: [1, 2, 3]}, c: "foobar"}

case data do
  %{a: %{b: [_ | _], other_key: _}, c: a_string} -> "Won't match because nested map doesn't have :other_key key"
  %{a: [_ | _], c: "foobar"} -> "Won't match because :a key doesn't have a list value"
  %{c: "foo" <> rest_of_string} -> "Matches. rest_of_string is #{rest_of_string} == bar"
end

Pattern matching
Case expression

In Elixir, much more logic can live in the function head than in a lot of other languages—you can pattern match on the arguments there rather than inside the function body. This allows you to split out different branches of logic of a function into completely separate clauses, changing the mental model of function definitions to be closer to simple mapping operations. "Function f, applied to a value that looks like X, produces X'. Function f, applied to a value that looks like Y, produces Y'. ..."

Pattern matching is also generally a constant-time operation due to restrictions on the assertions you can make, and when it's done in the function head it gets optimized even more during compilation. This means you can gain a pretty significant performance boost by moving a lot of logic into the function head.

defmodule MyList do
  def length([]), do: 0
  def length([_element | rest]), do: 1 + length(rest)
end

Multiple function clauses

The final piece of the puzzle here is Elixir's metaprogramming facilities. I've only dipped my toes in macros since they come with a lot of caveats, but one relatively safe use is generating a lot of similar function clauses from a list of "seed" values at compile time. This essentially boils down to programmatically generating the patterns instead of writing them all out manually. It also often comes with a big performance boost since the work is done at compile time. You can see an extreme example of this in Elixir's Unicode tokenizer—at compile time, it parses all of the codepoints from a text file and creates a huge number of function clauses.

defmodule Greeter do
  # Not the best real-world example, but hopefully it gets the point across
  for spanish_name <- ["María", "Juan", "Sofía", "Carlos"] do
    def greet(unquote(spanish_name)), do: "Hola, #{unquote(spanish_name)}"
  end

  for english_name <- ["Mary", "John", "Sophia", "Carl"] do
    def greet(unquote(english_name)), do: "Hello, #{unquote(english_name)}"
  end
end

iex> Greeter.greet("Carlos")
"Hola, Carlos"

iex> Greeter.greet("Mary")
"Hello, Mary"

Macros

|>: pipe operator. div(abs(n), 2) == n |> abs() |> div(2)

&: function capture operator. Captures a named function to be bound to a variable or otherwise passed around. Syntax is &function_name/arity; alternatively it can be used for quickly creating anonymous functions or partial application/closures by using &1, &2 etc as positional arguments: increment = &Kernel.+(&1, 1)

?: codepoint operator. Gets the unicode codepoint of a single character. ?a == 97, ?0 == 48

'': charlist. As opposed to a string "foo", a charlist 'foo' is literally a list of codepoints. 'foo' == [?f, ?o, ?o] == [102, 111, 111]. Great for when you need to work through a string one character at a time.

_: "any" pattern match. Lets you assert the structure of a piece of data without caring about its value. {:ok, _} = {:ok, 5}

| (in a list): head/tail separator. Elixir lists are singly-linked lists and the syntax for getting the head and the tail is [head | tail]. [1, 2, 3] == [1 | [2 | [3 | []]]]

This was pretty straightforward, especially since in one of the classes I teach, I use a very similar example to have students practice with using a stack :).

const OPENING_BRACKETS = {
    '(': ')',
    '[': ']',
    '{': '}',
    '<': '>',
};

const CLOSING_BRACKETS = {
    ')': 3,
    ']': 57,
    '}': 1197,
    '>': 25137,
};

function parse_line(line) {
    let stack = [];

    for (let bracket of line) {
        if (bracket in OPENING_BRACKETS) {
            stack.push(bracket);
        } else {
            if (!stack.length) {
                return [0, stack];
            }

            let previous = stack.pop();
            if (bracket != OPENING_BRACKETS[previous]) {
                return [CLOSING_BRACKETS[bracket], null];
            }
        }
    }

    return [0, stack];
}

let lines  = IO.readlines(line => line.split(''));
let part_a = lines.reduce((s, l) => s + parse_line(l)[0], 0);
IO.print(`Part A: ${part_a}`);

For this part, I had a lot of fun using JavaScripts functional programming capabilities.

const COMPLETE_POINTS = {
    '(': 1,
    '[': 2,
    '{': 3,
    '<': 4,
};

function complete_line(line) {
    return line.reverse().reduce((s, b) => 5*s + COMPLETE_POINTS[b], 0);
}

let scores = lines.map(parse_line)
		  .filter(p => !p[0])
		  .map(p => complete_line(p[1]))
		  .sort((a, b) => (a - b));
let part_b = scores[Math.floor(scores.length / 2)];
IO.print(`Part B: ${part_b}`);

=ARRAYFORMULA(
  IF(C3=FALSE,,
   SUM(
    IFERROR(
     VLOOKUP(
      IFERROR(
       VLOOKUP(
        SEQUENCE(COUNTA(A2:A)),
        QUERY(
         IFERROR(
          SPLIT(
           FLATTEN(
            ROW(A2:A)&"|"&
             IFERROR(
              FIND(
               {")",">","]","}"},
               IF(
                REGEXMATCH(
                 REGEXREPLACE(
                  REGEXREPLACE(
                   REGEXREPLACE(
                    REGEXREPLACE(
                     REGEXREPLACE(
                      REGEXREPLACE(
                       REGEXREPLACE(
                        A2:A,
                        "\(\)|\[\]|\{\}|<>",""),
                       "\(\)|\[\]|\{\}|<>",""),
                      "\(\)|\[\]|\{\}|<>",""),
                     "\(\)|\[\]|\{\}|<>",""),
                    "\(\)|\[\]|\{\}|<>",""),
                   "\(\)|\[\]|\{\}|<>",""),
                  "\(\)|\[\]|\{\}|<>",""),
                 "\)|\}|\]|>"),
               REGEXREPLACE(
                REGEXREPLACE(
                 REGEXREPLACE(
                  REGEXREPLACE(
                   REGEXREPLACE(
                    REGEXREPLACE(
                     REGEXREPLACE(
                      REGEXREPLACE(
                       REGEXREPLACE(
                        REGEXREPLACE(
                         REGEXREPLACE(
                          A2:A,
                          "\(\)|\{\}|\[\]|<>",""),
                         "\(\)|\{\}|\[\]|<>",""),
                        "\(\)|\{\}|\[\]|<>",""),
                       "\(\)|\{\}|\[\]|<>",""),
                      "\(\)|\{\}|\[\]|<>",""),
                     "\(\)|\{\}|\[\]|<>",""),
                    "\(\)|\{\}|\[\]|<>",""),
                   "\(\)|\{\}|\[\]|<>",""),
                  "\(\)|\{\}|\[\]|<>",""),
                 "\(\)|\{\}|\[\]|<>",""),
                "\(\)|\{\}|\[\]|<>",""),)))&"|"&
            {")",">","]","}"}),
           "|",TRUE,FALSE)),
         "where Col2 is not null
          order by Col1, Col2"),
        3,FALSE)),
      {")",3;
       "]",57;
       "}",1197;
       ">",25137},
      2,FALSE)))))

lets flip it and reverrrrrse it.

=ARRAYFORMULA(
  IF(C3=FALSE,,
   QUERY(
    SPLIT(
     TRANSPOSE(
      QUERY(
       TRANSPOSE(
        IFERROR(
         TRANSPOSE(
          SORT(
           TRANSPOSE(
            QUERY(
             {SEQUENCE(1,MAX(LEN(G2:G)));
              IF(ISBLANK(G2:G),,
               IFERROR(
                VLOOKUP(
                 SPLIT(
                  REGEXREPLACE(G2:G,"(.)","$1|"),
                  "|"),
                 {"(",1;
                  "[",2;
                  "{",3;
                  "<",4},
                 2,FALSE)))},
             "where Col1 is not null")),
           1,FALSE)))),
       "",9^9 )),
     " ",TRUE,TRUE),
    "where Col1 is not null
     offset 1")))

This is basically creating a QUERY with the MAX(LEN sequence across the top. It transposes it, sorts it in reverse, transposes again, offsets by one... then goes into this weird concat system.

With that out of the way I've got a phat table that is a breeze to work with.

First column

=ARRAYFORMULA(
  IF(ISBLANK(I2:I),,
   I2:I*IF(ISBLANK(J2:J),,5)))

Next column, dragged across for the fourteen remaining columns,

=ARRAYFORMULA(
  IF(ISBLANK($I2:$I),,
   (Y2:Y+J2:J)*IF(ISBLANK(K2:K),1,5)))

Take the MEDIAN and we're good as gold.

#!/usr/bin/awk -f
BEGIN { FS = "" }

{
	split("", chunk)

	for (i = 1; i <= NF; ++i) {
		c = $i

		if (c ~ /[\(\[\{\<]/)
			stack[++ptr] = c

		val = 0

		if (c == ")")
			val = (stack[ptr--] == "(") ? 0 : 3
		else if (c == "]")
			val = (stack[ptr--] == "[") ? 0 : 57
		else if (c == "}")
			val = (stack[ptr--] == "{") ? 0 : 1197
		else if (c == ">")
			val = (stack[ptr--] == "<") ? 0 : 25137

		if (val) {
			total += val
			next
		}
	}
}

END { print total }

#!/usr/bin/awk -f
function qsort(arr, left, right,	i, j, tmp, pivot) {
	if (left >= 0 && right >= 0 && left < right) {
		pivot = arr[int((left + right) / 2)]

		i = left - 1
		j = right + 1

		while (1) {
			do {
				i = i + 1
			} while (arr[i] < pivot)

			do {
				j = j - 1
			} while (arr[j] > pivot)

			if (i >= j)
				break

			tmp = arr[i]
			arr[i] = arr[j]
			arr[j] = tmp
		}

		qsort(arr, left, j)
		qsort(arr, j + 1, right)
	}
}

BEGIN { FS = "" }

{
	split("", chunk)

	ptr = 0

	for (i = 1; i <= NF; ++i) {
		c = $i

		if (c ~ /[\(\[\{\<]/)
			stack[++ptr] = c

		flag = 1

		if (c == ")")
			flag = (stack[ptr--] == "(")
		else if (c == "]")
			flag = (stack[ptr--] == "[")
		else if (c == "}")
			flag = (stack[ptr--] == "{")
		else if (c == ">")
			flag = (stack[ptr--] == "<")

		if (! flag)
			next
	}

	val = 0

	while (ptr) {
		c = stack[ptr--]
		val *= 5
		
		if (c == "(")
			val += 1
		else if (c == "[")
			val += 2
		else if (c == "{")
			val += 3
		else if (c == "<")
			val += 4
	}

	score[++pt] = val
}

END {
	qsort(score, 1, pt)
	print score[pt/2+.5]
}

Edit::
Sometimes the excitement in the arena gets to you.
After spending time away, having some dinner and relaxing a bit, I realised I'm dumb. Part 1 parse already collects the opened items yet I use it to filter out corrupt lines in Part 2 and then iterate again re-collecting them ... like a doofus. Now I return both the collected openers and the corruption character together; part 1 only uses the corruption, part 2 skips any corruptions and calculates the score of the opened items left on the stack.
I'll leave my idiocy on display here for posterity - you can see the improved version in the repo..

This is ugly code, but it's deliberate to get the runtime down as much as I could. Any tips to make it faster are very welcome. In Lisp a stack is just a list so parse maintains a stack of opening chars and the offending character that causes corruption.

(define (part-01 input)
  (for*/fold ([s 0])
             ([l input])
    (match (parse l)
      [#\) (+ s 3)]
      [#\] (+ s 57)]
      [#\} (+ s 1197)]
      [#\> (+ s 25137)]
      [_ s])))

(define (parse l)
  (for/fold ([remaining null]
             [corrupt #f]
             #:result corrupt)
            ([c (in-string l)] #:break corrupt)
    (case c
      [(#\( #\[ #\{ #\<) (values (cons c remaining) corrupt)]
      [else (mismatch remaining c corrupt)])))

(define (mismatch remaining c closing)
  (cond [(null? remaining) (values remaining c)]
        [(eq? c #\))
         (values (rest remaining) (if (eq? (first remaining) #\() closing c))]
        [(eq? c #\])
         (values (rest remaining) (if (eq? (first remaining) #\[) closing c))]
        [(eq? c #\})
         (values (rest remaining) (if (eq? (first remaining) #\{) closing c))]
        [(eq? c #\>)
         (values (rest remaining) (if (eq? (first remaining) #\<) closing c))]))

I did toy with the idea of using Racket's own parser (read) loose on the problem but it's not really the right tool for the job and involves catching exceptions rather than failing gracefully.

I used parse from Part 1 to filter out the corrupt lines. 'completion' pushes and pops the opening characters on the stack (list !) - safe in the knowledge it isn't corrupt. Whatever is left over on the stack at the end is those openers that need completing.

(define (part-02 input)
  (for*/fold ([scores null]
              #:result (median scores))
             ([l input] #:unless (parse l))
    (cons (completion-score (completion l)) scores)))

(define (median xs)
  (first (drop (sort xs <)
               (/ (sub1 (length xs)) 2))))

(define (completion l)
  (for/fold ([opens null]
             #:result (list->string (map closing-pair opens)))
            ([c l])
    (cond [(eq? c #\() (cons c opens)]
          [(eq? c #\[) (cons c opens)]
          [(eq? c #\{) (cons c opens)]
          [(eq? c #\<) (cons c opens)]
          [else (rest opens)])))

(define (completion-score s)
  (for/fold ([score 0])
            ([c s])
    (+ (* score 5)
       (cond [(eq? c #\)) 1]
             [(eq? c #\]) 2]
             [(eq? c #\}) 3]
             [(eq? c #\>) 4]))))

(define (closing-pair c)
  (match c
    [#\( #\)]
    [#\[ #\]]
    [#\{ #\}]
    [#\< #\>]))

Did this feel especially difficult, because I feel Eric provided a pretty impressive test-suite in this question - above and beyond what's normally given. For posterity here's my test-suite taken directly from the question

(module+ test
  (require rackunit)

  (check-not-false (parse "(]"))
  (check-not-false (parse "{()()()>"))
  (check-not-false (parse "(((()))}"))

  (check-eq? (parse "{([(<{}[<>[]}>{[]{[(<()>") #\})
  (check-eq? (parse "[[<[([]))<([[{}[[()]]]") #\))
  (check-eq? (parse "[{[{({}]{}}([{[{{{}}([]") #\])
  (check-eq? (parse "[<(<(<(<{}))><([]([]()") #\))
  (check-eq? (parse "<{([([[(<>()){}]>(<<{{") #\>)

  (check-= (part-01 test-input) 26397 0)

  (check-equal? (completion "[({(<(())[]>[[{[]{<()<>>") "}}]])})]")
  (check-equal? (completion "[(()[<>])]({[<{<<[]>>(") ")}>]})")
  (check-equal? (completion "(((({<>}<{<{<>}{[]{[]{}") "}}>}>))))")
  (check-equal? (completion "{<[[]]>}<{[{[{[]{()[[[]") "]]}}]}]}>")
  (check-equal? (completion "<{([{{}}[<[[[<>{}]]]>[]]") "])}>")

  (check-= (completion-score "}}]])})]") 288957 0)
  (check-= (completion-score ")}>]})") 5566 0)
  (check-= (completion-score "}}>}>))))") 1480781 0)
  (check-= (completion-score "]]}}]}]}>") 995444 0)
  (check-= (completion-score "])}>") 294 0)

  (check-= (part-02 test-input) 288957 0)

  ;; regression tests specific for my input only
  ;; (check-= (part-01 input) 168417 0)
  ;; (check-= (part-02 input) 2802519786 0)

  )

const fs = require('fs');
const readline = require('readline');

let inputArr = [];

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		try {
			inputArr.push(line);
		} catch(e) {
			console.error(e);
		}
	}
}

function analyzeLine(line) {
	console.log("DEBUG: analyzing line " + line);
	let stack = [];
	for (const char of line) {
		let compare = undefined;
		switch (char) {
			case '(': stack.push(char); break;
			case '[': stack.push(char); break;
			case '{': stack.push(char); break;
			case '<': stack.push(char); break;
			case ')': compare = stack.pop();
				if (compare != '(') {
					return { corrupted: true, violationCharacter: char };
				}
				break;
			case ']': compare = stack.pop();
				if (compare != '[') {
					return { corrupted: true, violationCharacter: char };
				}
				break;
			case '}': compare = stack.pop();
				if (compare != '{') {
					return { corrupted: true, violationCharacter: char };
				}
				break;
			case '>': compare = stack.pop();
				if (compare != '<') {
					return { corrupted: true, violationCharacter: char };
				}
				break;
		}
	}
	return { corrupted: false, violationCharacter: undefined };
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let totalSum = 0;
	for (const line of inputArr) {
		let lineResult = analyzeLine(line);
		console.log(lineResult);
		if (lineResult.corrupted === true) {
			let lineScore = 0;
			console.log(lineResult.violationCharacter);
			switch (lineResult.violationCharacter) {
				case ')': lineScore = 3;
					console.log("DEBUG: ) detected");
					break;
				case ']': lineScore = 57;
					console.log("DEBUG: ] detected");
					break;
				case '}': lineScore = 1197;
					console.log("DEBUG: } detected");
					break;
				case '>': lineScore = 25137;
					console.log("DEBUG: > detected");
					break;
			}
			console.log("DEBUG: Adding " + lineScore + " to " + totalSum);
			totalSum += lineScore;
		}
	}
	console.log("Answer found! " + totalSum);
})();

const fs = require('fs');
const readline = require('readline');

let inputArr = [];

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		try {
			inputArr.push(line);
		} catch(e) {
			console.error(e);
		}
	}
}

function analyzeLine(line) {
	console.log("DEBUG: analyzing line " + line);
	let stack = [];
	let completionSequence = [];
	for (const char of line) {
		let compare = undefined;
		switch (char) {
			case '(': stack.push(char); break;
			case '[': stack.push(char); break;
			case '{': stack.push(char); break;
			case '<': stack.push(char); break;
			case ')': compare = stack.pop();
				if (compare != '(') {
					return { corrupted: true, violationCharacter: char, completionSequence: undefined };
				}
				break;
			case ']': compare = stack.pop();
				if (compare != '[') {
					return { corrupted: true, violationCharacter: char, completionSequence: undefined };
				}
				break;
			case '}': compare = stack.pop();
				if (compare != '{') {
					return { corrupted: true, violationCharacter: char, completionSequence: undefined };
				}
				break;
			case '>': compare = stack.pop();
				if (compare != '<') {
					return { corrupted: true, violationCharacter: char, completionSequence: undefined };
				}
				break;
		}
	}
	if (stack.length > 0) {
		while (stack.length > 0) {
			let currentOpening = stack.pop();
			switch (currentOpening) {
				case '(': completionSequence.push(')'); break;
				case '[': completionSequence.push(']'); break;
				case '{': completionSequence.push('}'); break;
				case '<': completionSequence.push('>'); break;
			}
		}
		return { corrupted: false, violationCharacter: undefined, completionSequence: completionSequence };
	} else {
			return { corrupted: false, violationCharacter: undefined, completionSequence: undefined };
	}
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let lineScores = [];
	for (const line of inputArr) {
		let lineResult = analyzeLine(line);
		console.log(lineResult);
		if (lineResult.corrupted === false) {
			let lineScore = 0;
			for (const char of lineResult.completionSequence) {
				lineScore *= 5;
				let charValue = 0;
				switch (char) {
					case ')': charValue = 1; break;
					case ']': charValue = 2; break;
					case '}': charValue = 3; break;
					case '>': charValue = 4; break;
				}
				lineScore += charValue;
			}
			console.log("DEBUG: Line complete! lineScore = " + lineScore);
			lineScores.push(lineScore);
		}
	}
	console.log(lineScores);
	console.log("Answer found! " + lineScores.sort((a,b) => { return a - b })[Math.floor((lineScores.length - 1) / 2)]);
})();

total = 0
complete = []
for line in input:
    close = ""
    for brace in line:
        if brace == "(": close += ")"
        elif brace == "[": close += "]"
        elif brace == "{": close += "}"
        elif brace == "<": close += ">"
        elif brace == close[-1]: close = close[0:-1]
        else:
            if brace == ")": total += 3
            elif brace == "]": total += 57
            elif brace == "}": total += 1197
            elif brace == ">": total += 25137
            else: complete.append(close[::-1])
            break
print(total)

totals = []
for seq in complete:
    total = 0
    for brace in seq:
        total *= 5
        if brace == ")": total += 1
        elif brace == "]": total += 2
        elif brace == "}": total += 3
        elif brace == ">": total += 4
    totals.append(total)
print(sorted(totals)[len(totals) // 2])

pairs = {"(": ")", "[": "]", "{": "}", "<": ">"}
illegal = int()
incomplete = list()

for chunks in [line for line in open("input.txt").read().split()]:
    history = list()
    for chunk in chunks:
        if chunk not in pairs.keys():
            if chunk == pairs[history[-1]]:
                history.pop(-1)
            else:
                illegal += {")": 3, "]": 57, "}": 1197, ">": 25137}[chunk]
                history.clear()
                break
        else:
            history.append(chunk)
    if history:
        points = int()
        for h in history[::-1]:
            points = points * 5 + {")": 1, "]": 2, "}": 3, ">": 4}[pairs[h]]
        incomplete.append(points)

print("Part One:", illegal)
print("Part Two:", sorted(incomplete)[len(incomplete) // 2])

This is a pretty classic parsing situation, we just need to use a stack to keep track of how many layers of brackets deep we are, and what kind of closing bracket we expect to see next. Each time we find a new opening bracket we add the appropriate closing bracket to our stack, and each time we find a closing bracket we just remove the top item from our stack and check to see if it's the same.

def compute_p1(input)
  parens = {
    '(' => ')',
    '[' => ']',
    '{' => '}',
    '<' => '>'
  }

  points = {
    ')' => 3,
    ']' => 57,
    '}' => 1197,
    '>' => 25137
  }

  input.lines.map(&:chomp).reduce(0) do |sum, line|
    expect_stack = []
    line.chars.each do |char|
      if parens.keys.include?(char)
        expect_stack.push(parens[char])
      elsif parens.values.include?(char) && expect_stack.pop != char
        sum += points[char]
      end
    end
    sum
  end
end

Somewhat surprisingly, not really any harder than part 1. We do pretty much the exact same thing here, except that we know all the lines are "well formed" and don't have any incorrect closing brackets anywhere (since we just wrote a function we can use to filter them out).

We just run the exact same logic to build up a stack of expected closing brackets, popping them back off as we find them in the line, and whatever is left over in our stack of expected values is what we use to score the line.

def compute_p2(input)
  parens = {
    '(' => ')',
    '[' => ']',
    '{' => '}',
    '<' => '>'
  }

  points = {
    ')' => 1,
    ']' => 2,
    '}' => 3,
    '>' => 4
  }

  scores = input
             .lines
             .map(&:chomp)
             .filter { compute_p1(_1) == 0 }
             .map do |line|
    expect_stack = []
    line.chars.each do |char|
      if parens.keys.include?(char)
        expect_stack.push(parens[char])
      elsif parens.values.include?(char) && expect_stack.pop != char
        # binding.pry
      end
    end
    expect_stack.reverse.reduce(0) { |sum,char| (sum * 5) + points[char] }
  end

  scores.sort[scores.size/2]
end

Regex putting in work once again. I iterated through the strings replacing completed sets of brackets until I couldn't anymore, either because I ran out of characters or the string stayed the same size after trying all possible combinations.

Once the string was reduced, whipped up some regex of possible invalid combinations and looked for those. Though having looked through more of the data, I'm pretty sure I could have just looked for the first remaining closing bracket. From there it was was trivial to sum up the score

I don't know if I got lucky or it was by design, but none of my strings seemed to have multiple copies of invalid characters. That could have thrown a wrench into my plans.

import re

#data = test_data
data = real_data
data = data.split('\n')

close_brackets_1 = re.compile(r'\(\)')
close_brackets_2 = re.compile(r'\[\]')
close_brackets_3 = re.compile(r'\{\}')
close_brackets_4 = re.compile(r'\<\>')


find_error_1 = re.compile(r'[\[\{\<]\)')
find_error_2 = re.compile(r'[\(\{\<]\]')
find_error_3 = re.compile(r'[\(\[\<]\}')
find_error_4 = re.compile(r'[\(\[\{]\>')


score = 0
for row in data:
    reducing = True
    while reducing:
        row_size = len(row)
        row = re.sub(close_brackets_1, '' , str(row))
        row = re.sub(close_brackets_2, '' , str(row))
        row = re.sub(close_brackets_3, '' , str(row))
        row = re.sub(close_brackets_4, '' , str(row))
        if len(row) == row_size or len(row) == 0:
            reducing = False
    error_1 = find_error_1.search(row)
    error_2 = find_error_2.search(row)
    error_3 = find_error_3.search(row)
    error_4 = find_error_4.search(row)
    #print(row)
    if error_1:
        score = score + 3
        #print("found error 1")
    if error_2: 
        score = score + 57
        #print("found error 2")
    if error_3: 
        score = score + 1197
        #print("found error 3")
    if error_4: 
        score = score + 25137
        #print("found error 4")
print(score)

My method for Part A put me in a good position for Part B, since it left me with the remainder, which was the mirror of what I wanted. Just flip the string and do some replacement to swap the characters with their closing counterparts.

from collections import defaultdict
import re

#data = test_data
data = real_data
data = data.split('\n')

close_brackets_1 = re.compile(r'\(\)')
close_brackets_2 = re.compile(r'\[\]')
close_brackets_3 = re.compile(r'\{\}')
close_brackets_4 = re.compile(r'\<\>')


find_error_1 = re.compile(r'[\[\{\<]\)')
find_error_2 = re.compile(r'[\(\{\<]\]')
find_error_3 = re.compile(r'[\(\[\<]\}')
find_error_4 = re.compile(r'[\(\[\{]\>')

char_swap_1 = re.compile(r'\(')
char_swap_2 = re.compile(r'\[')
char_swap_3 = re.compile(r'\{')
char_swap_4 = re.compile(r'\<')

scores = []
for row in data:
    reducing = True
    while reducing:
        row_size = len(row)
        row = re.sub(close_brackets_1, '' , str(row))
        row = re.sub(close_brackets_2, '' , str(row))
        row = re.sub(close_brackets_3, '' , str(row))
        row = re.sub(close_brackets_4, '' , str(row))
        if len(row) == row_size or len(row) == 0:
            reducing = False
    error_1 = find_error_1.search(row)
    error_2 = find_error_2.search(row)
    error_3 = find_error_3.search(row)
    error_4 = find_error_4.search(row)
    if error_1 or error_2 or error_3 or error_4:
        continue #reject the line
    reduced_row = row
    flipped_row = row[::-1]
    flipped_row = re.sub(char_swap_1, ')', flipped_row)
    flipped_row = re.sub(char_swap_2, ']', flipped_row)
    flipped_row = re.sub(char_swap_3, '}', flipped_row)
    flipped_row = re.sub(char_swap_4, '>', flipped_row)
    
    #print(reduced_row, "  ++++  ", flipped_row )  
    score = 0
    for char in list(flipped_row):
        score = score * 5
        if char == ')': score = score + 1
        elif char == ']': score = score + 2
        elif char == '}': score = score + 3
        elif char == '>': score = score + 4
    #print(score)
    scores.append(score)
scores.sort()
length = len(scores)
mid = length//2
print(scores[mid])

• If you haven't already, I HIGHLY recommend looking into learning Regular Expressions. https://regexone.com/ was where I learned how to use them, it's really helpful. And https://regexr.com/ is a great sandbox for testing your patterns and debugging them

• In part A I found it much easier to remove matches one at a time, rather than trying to process them in place

• Depending on how you approach Part A, Part B might just require flipping some strings around

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::VecDeque;
fn corresponding(delim: char) -> char {
    match delim {
        '(' => ')',
        '[' => ']',
        '{' => '}',
        '<' => '>',
        other => panic!("Syntax error: unexpected character: {}",other),
    }
}
fn delim_score_p1(delim: char) -> usize {
    match delim {
        ')' => 3,
        ']' => 57,
        '}' => 1197,
        '>' => 25137,
        other => panic!("Syntax error: unexpected character: {}",other),
    }
}
fn delim_score_p2(delim: char) -> usize {
    match delim {
        ')' => 1,
        ']' => 2,
        '}' => 3,
        '>' => 4,
        other => panic!("Syntax error: unexpected character: {}",other),
    }
}
fn score_line_p1(line: &str) -> usize {
    let mut stack: VecDeque<char> = VecDeque::new();
    for ch in line.chars() {
        match ch {
            '(' | '[' | '{' | '<' => stack.push_front(ch),
            ')' | ']' | '}' | '>' => {
                let next = stack.pop_front().unwrap();
                if ch != corresponding(next) {
                    return delim_score_p1(ch); // corrupted line
                }
            },
            other => panic!("Syntax error: unexpected character: {}",other),
        }
    }
    0 // incomplete line
}
fn complete_line(line: &str) -> String {
    let mut completion = String::new();
    let mut stack: VecDeque<char> = VecDeque::new();
    // Parse existing string
    for ch in line.chars() {
        match ch {
            '(' | '[' | '{' | '<' => { stack.push_front(ch) },
            ')' | ']' | '}' | '>' => { stack.pop_front(); },
            other => panic!("Syntax error: unexpected character: {}",other),
        }
    }
    // Complete string
    while stack.len() > 0 {
        let next = stack.pop_front().unwrap();
        let corresponding = corresponding(next);
        completion.push_str(&corresponding.to_string());
    }
    completion
}
fn score_line_p2(completion: String) -> usize {
    completion.chars().fold(0, |score, ch| score * 5 +  delim_score_p2(ch))
}
fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);
    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };
    // Part 1
    let part1: usize = input.clone().iter().map(|x| score_line_p1(x)).sum();
    println!("Part 1: {}", part1); // 392043
    // Part 2
    let incomplete_lines: Vec<_> = input
        .iter()
        .filter(|x| score_line_p1(x) == 0)
        .collect();
    let mut part2_scores = incomplete_lines
        .iter()
        .map(|x| complete_line(x))
        .map(|x| score_line_p2(x))
        .collect::<Vec<_>>();
    part2_scores.sort();
    let middle_index = part2_scores.len()/2;
    let part2 = part2_scores.iter().nth(middle_index).unwrap();
    println!("Part 2: {}", part2); // 1605968119
    Ok(())
}
fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

If the line is corrupt, LineState will contain the offending char. If the line is incomplete, it contains the characters for completing the line in reverse order (i.e. as a stack).

type Line = Vec<char>;

enum LineState {
    Incomplete(Vec<char>),
    Corrupt(char),
}

fn parse_navigation(input: &str) -> Vec<Line> {
    input.lines().map(|l| l.trim().chars().collect()).collect()
}

This uses a stack to keep track of which closing character is next.

fn line_state_of(line: &Line) -> LineState {
    let mut stack = Vec::new();

    for &c in line.iter() {
        match c {
            '(' => stack.push(')'),
            '[' => stack.push(']'),
            '{' => stack.push('}'),
            '<' => stack.push('>'),
            _ => {
                if stack.len() == 0 || stack[stack.len() - 1] != c {
                    return LineState::Corrupt(c);
                } else {
                    stack.pop();
                }
            }
        }
    }

    LineState::Incomplete(stack)
}

fn part1(lines: &Vec<Line>) -> usize {
    lines.iter().fold(0, |acc, l| match line_state_of(&l) {
        LineState::Incomplete(_) => acc,
        LineState::Corrupt(')') => acc + 3,
        LineState::Corrupt(']') => acc + 57,
        LineState::Corrupt('}') => acc + 1197,
        LineState::Corrupt('>') => acc + 25137,
        _ => unreachable!(),
    })
}

fn part2(lines: &Vec<Line>) -> usize {
    let stacks = lines.iter().filter_map(|l| match line_state_of(&l) {
        LineState::Incomplete(stack) => Some(stack),
        _ => None,
    });

    let mut scores: Vec<usize> = stacks
        .map(|mut s| {
            let mut score = 0;
            while let Some(c) = s.pop() {
                score *= 5;
                match c {
                    ')' => score += 1,
                    ']' => score += 2,
                    '}' => score += 3,
                    '>' => score += 4,
                    _ => unreachable!(),
                }
            }

            score
        })
        .collect();

    let num_scores = scores.len();

    assert!(num_scores % 2 == 1);

    *scores.select_nth_unstable(num_scores / 2).1
}

fn main() {
    let input = include_str!("../../input-10.txt");
    let nav = parse_navigation(input);

    println!("Part I:  {}", part1(&nav));
    println!("Part II: {}", part2(&nav));
}

use crate::lib::aoc;

pub fn run() {
    let lines = aoc::get_lines("./inputs/day10.in");

    let mut error_score = 0;
    let mut completion_scores: Vec<u64> = Vec::new();
    for line in lines {
        let mut stack: Vec<char> = Vec::new();
        let mut is_valid = true;
        // Check if the line is valid
        for c in line.chars() {
            match c {
                '(' | '[' | '{' | '<' => stack.push(c),
                ')' => match stack.pop() {
                    Some('(') => { /* This is what we want but there's nothingto do */ }
                    _ => {
                        error_score += 3;
                        is_valid = false
                    }
                },
                ']' => match stack.pop() {
                    Some('[') => { /* This is what we want but there's nothingto do */ }
                    _ => {
                        error_score += 57;
                        is_valid = false
                    }
                },
                '}' => match stack.pop() {
                    Some('{') => { /* This is what we want but there's nothingto do */ }
                    _ => {
                        error_score += 1197;
                        is_valid = false
                    }
                },
                '>' => match stack.pop() {
                    Some('<') => { /* This is what we want but there's nothingto do */ }
                    _ => {
                        error_score += 25137;
                        is_valid = false
                    }
                },
                _ => eprintln!("Non-bracket character ({}) found! Ignoring...", c),
            }
        }
        // If it is valid, get the line's completion score
        if is_valid {
            let mut completion_score = 0;
            for c in stack.iter().rev() {
                completion_score *= 5;
                match c {
                    '(' => completion_score += 1,
                    '[' => completion_score += 2,
                    '{' => completion_score += 3,
                    '<' => completion_score += 4,
                    _ => {
                        eprintln!("Non-opening-bracket character ({}) found! Ignoring...", c);
                        // Unmultiply the score
                        completion_score /= 5;
                    }
                }
            }
            completion_scores.push(completion_score);
        }
    }
    completion_scores.sort_unstable();

    aoc::big_output(
        10,
        "score",
        error_score,
        completion_scores[completion_scores.len() / 2],
    );
}

This one was not too bad! It looks like a lot of people used regex for this, but since it was so simple and I used a sequence as a stack it made part 2 not too difficult. I just had to modify my output and filter it to get the right information to the right places, and then remember to reverse the stack. I do wish Nim had a more graceful way to iterate backwards, given how nice a lot of the other syntax is.

import std/[strformat, sequtils, strutils, sugar, tables, algorithm]

proc parseFile(inputFile: string): seq[string] = 
  return collect(newSeq):
    for line in inputFile.lines: line

func findIllegalCharacter(line: string): char = 
  var stack: seq[char]

  var opens = @['[', '{', '(', '<']
  var closes = @[']', '}', ')', '>']
  var openToClose = {'[' : ']',
                       '{' : '}',
                       '(' : ')',
                       '<' : '>'}.toTable()

  for character in line:
    if character in opens:
      stack.add(open_to_close[character])
    if character in closes:
      if character != stack[^1]:
        return character
      else:
        stack = stack[0 .. ^2]

  return ' '

func scoreErrors(errors: seq[char]): int = 
  var errorToValue = {')' : 3,
                      ']' : 57,
                      '}' : 1197,
                      '>' : 25137}.toTable()

  var score: int
  for error in errors:
    score = score + errorToValue[error]

  return score

proc main(inputFile: string) =
  var lines = parseFile(inputFile)

  var illegalCharacters = mapIt(lines, findIllegalCharacter(it))
  keepItIf(illegalCharacters, it != ' ')
  
  echo &"The total syntax error score is {scoreErrors(illegalCharacters)}"

when is_main_module:
  # main("test.txt")
  main("input.txt")

@@ -4,7 +4,7 @@ proc parseFile(inputFile: string): seq[string] =
   return collect(newSeq):
     for line in inputFile.lines: line
 
-func findIllegalCharacter(line: string): char = 
+func findIllegalCharacter(line: string): seq[char] = 
   var stack: seq[char]
 
   var opens = @['[', '{', '(', '<']
@@ -19,11 +19,11 @@ func findIllegalCharacter(line: string): char =
       stack.add(open_to_close[character])
     if character in closes:
       if character != stack[^1]:
-        return character
+        return @[character]
       else:
         stack = stack[0 .. ^2]
 
-  return ' '
+  return stack & @[' ']
 
 func scoreErrors(errors: seq[char]): int = 
   var errorToValue = {')' : 3,
@@ -37,14 +37,38 @@ func scoreErrors(errors: seq[char]): int =
 
   return score
 
+func scoreCompletions(completion: seq[char]): int =
+  var completionToValue = {')' : 1,
+                           ']' : 2,
+                           '}' : 3,
+                           '>' : 4}.toTable()
+
+  var score: int
+  for idx in countdown(completion.len - 1, 0, 1):
+    score = score * 5 + completionToValue[completion[idx]]
+
+  return score
+
 proc main(inputFile: string) =
   var lines = parseFile(inputFile)
 
-  var illegalCharacters = mapIt(lines, findIllegalCharacter(it))
-  keepItIf(illegalCharacters, it != ' ')
+  var syntaxChecking = mapIt(lines, findIllegalCharacter(it))
+  var illegalCharactersSeq = filterIt(syntaxChecking, it[^1] != ' ')
+
+  # There must be a better way to do this but oh well
+  var illegalCharacters: seq[char]
+  for list in illegalCharactersSeq:
+    illegalCharacters.add(list[0])
   
   echo &"The total syntax error score is {scoreErrors(illegalCharacters)}"
 
+  var lineCompletions = filterIt(syntaxChecking, it[^1] == ' ')
+  applyIt(lineCompletions, it[0 .. ^2])
+  var completionScores = mapIt(lineCompletions, scoreCompletions(it))
+  sort(completionScores)
+
+  echo &"The middle line completion scroe is {completionScores[completionScores.len div 2]}"
+
 when is_main_module:
   # main("test.txt")
   main("input.txt")