Day 3: Mull It Over
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Sorry for the delay posting this one, Ategon seemed to have it covered, so I forgot :D I will do better.
Haskell
module Main where import Control.Arrow hiding ((+++)) import Data.Char import Data.Functor import Data.Maybe import Text.ParserCombinators.ReadP hiding (get) import Text.ParserCombinators.ReadP qualified as P data Op = Mul Int Int | Do | Dont deriving (Show) parser1 :: ReadP [(Int, Int)] parser1 = catMaybes <$> many ((Just <$> mul) <++ (P.get $> Nothing)) parser2 :: ReadP [Op] parser2 = catMaybes <$> many ((Just <$> operation) <++ (P.get $> Nothing)) mul :: ReadP (Int, Int) mul = (,) <$> (string "mul(" *> (read <$> munch1 isDigit <* char ',')) <*> (read <$> munch1 isDigit <* char ')') operation :: ReadP Op operation = (string "do()" $> Do) +++ (string "don't()" $> Dont) +++ (uncurry Mul <$> mul) foldOp :: (Bool, Int) -> Op -> (Bool, Int) foldOp (_, n) Do = (True, n) foldOp (_, n) Dont = (False, n) foldOp (True, n) (Mul a b) = (True, n + a * b) foldOp (False, n) _ = (False, n) part1 = sum . fmap (uncurry (*)) . fst . last . readP_to_S parser1 part2 = snd . foldl foldOp (True, 0) . fst . last . readP_to_S parser2 main = getContents >>= print . (part1 &&& part2)
Of course it’s point-free
C
Yay parsers! I’ve gotten quite comfortable writing these with C. Using out pointers arguments for the cursor that are only updated if the match is successful makes for easy bookkeeping.
Code
#include "common.h" static int parse_exact(const char **stringp, const char *expect) { const char *s = *stringp; int i; for (i=0; s[i] && expect[i] && s[i] == expect[i]; i++) ; if (expect[i]) return 0; *stringp = &s[i]; return 1; } static int parse_int(const char **stringp, int *outp) { char *end; int val; val = (int)strtol(*stringp, &end, 10); if (end == *stringp) return 0; *stringp = end; if (outp) *outp = val; return 1; } static int parse_mul(const char **stringp, int *ap, int *bp) { const char *cur = *stringp; int a,b; if (!parse_exact(&cur, "mul(") || !parse_int(&cur, &a) || !parse_exact(&cur, ",") || !parse_int(&cur, &b) || !parse_exact(&cur, ")")) return 0; *stringp = cur; if (ap) *ap = a; if (bp) *bp = b; return 1; } int main(int argc, char **argv) { static char buf[32*1024]; const char *cur; size_t nr; int p1=0,p2=0, a,b, dont=0; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); nr = fread(buf, 1, sizeof(buf), stdin); assert(!ferror(stdin)); assert(nr != sizeof(buf)); buf[nr] = '\0'; for (cur = buf; *cur; ) if (parse_exact(&cur, "do()")) dont = 0; else if (parse_exact(&cur, "don't()")) dont = 1; else if (parse_mul(&cur, &a, &b)) { p1 += a * b; if (!dont) p2 += a * b; } else cur++; printf("03: %d %d\n", p1, p2); }
Got the code a little shorter:
Code
#include "common.h" static int parse_mul(const char **stringp, int *ap, int *bp) { const char *cur = *stringp, *end; if (strncmp(cur, "mul(", 4)) { return 0; } cur += 4; *ap = (int)strtol(cur, (char **)&end, 10); if (end == cur) { return 0; } cur = end; if (*cur != ',') { return 0; } cur += 1; *bp = (int)strtol(cur, (char **)&end, 10); if (end == cur) { return 0; } cur = end; if (*cur != ')') { return 0; } cur += 1; *stringp = cur; return 1; } int main(int argc, char **argv) { static char buf[32*1024]; const char *p; size_t nr; int p1=0,p2=0, a,b, dont=0; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); nr = fread(buf, 1, sizeof(buf), stdin); assert(!ferror(stdin)); assert(nr != sizeof(buf)); buf[nr] = '\0'; for (p = buf; *p; ) if (parse_mul(&p, &a, &b)) { p1 += a*b; p2 += a*b*!dont; } else if (!strncmp(p, "do()", 4)) { dont = 0; p += 4; } else if (!strncmp(p, "don't()", 7)) { dont = 1; p += 7; } else p++; printf("03: %d %d\n", p1, p2); }
Nim
From a first glance it was obviously a regex problem.
I’m using tinyre here instead of stdlibre
library just because I’m more familiar with it.import pkg/tinyre proc solve(input: string): AOCSolution[int, int] = var allow = true for match in input.match(reG"mul\(\d+,\d+\)|do\(\)|don't\(\)"): if match == "do()": allow = true elif match == "don't()": allow = false else: let pair = match[4..^2].split(',') let mult = pair[0].parseInt * pair[1].parseInt result.part1 += mult if allow: result.part2 += mult
I shy away from regexes for these parsing problems because part 2 likes to mess those up but here it worked beautifully. Nice and compact solution!
I couldn’t figure it out in haskell, so I went with bash for the first part
Shell
cat example | grep -Eo "mul\([[:digit:]]{1,3},[[:digit:]]{1,3}\)" | cut -d "(" -f 2 | tr -d ")" | tr "," "*" | paste -sd+ | bc
but this wouldn’t rock anymore in the second part, so I had to resort to python for it
Python
import sys f = "\n".join(sys.stdin.readlines()) f = f.replace("don't()", "\ndon't()\n") f = f.replace("do()", "\ndo()\n") import re enabled = True muls = [] for line in f.split("\n"): if line == "don't()": enabled = False if line == "do()": enabled = True if enabled: for match in re.finditer(r"mul\((\d{1,3}),(\d{1,3})\)", line): muls.append(int(match.group(1)) * int(match.group(2))) pass pass print(sum(muls))
Really cool trick. I did a bunch of regex matching that I’m sure I won’t remember how it works few weeks from now, this is so much readable
Nice, sometimes a few extra linebreaks can do the trick…
My first insinct was similar, add line breaks to the do and dont modifiers. But I got toa caught up thinking id have to keep track of the added characters, I wound up just abusing split()-
Uiua
Uses experimental feature of
fold
to track the running state of do/don’t.[edit] Slightly re-written to make it less painful :-) Try it online!
# Experimental! DataP₁ ← $ xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5)) DataP₂ ← $ xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5)) GetMul ← $ mul\((\d{1,3}),(\d{1,3})\) GetMulDoDont ← $ mul\(\d{1,3},\d{1,3}\)|do\(\)|don\'t\(\) &p/+≡(/×≡⋕↘1)regexGetMul DataP₁ # Part 1 # Build an accumulator to track running state of do/don't Filter ← ↘1⊂:∧(⍣(0 °"don"|1 °"do("|.◌)) :1≡(↙3°□) ≡⊢ regex GetMulDoDont DataP₂ ▽⊸≡◇(≍"mul"↙3)▽⊸Filter # Apply Filter, remove the spare 'do's &p/+≡◇(/×≡◇⋕↘1⊢regexGetMul) # Get the digits and multiply, sum.
Factor
: get-input ( -- corrupted-input ) "vocab:aoc-2024/03/input.txt" utf8 file-contents ; : get-muls ( corrupted-input -- instructions ) R/ mul\(\d+,\d+\)/ all-matching-subseqs ; : process-mul ( instruction -- n ) R/ \d+/ all-matching-subseqs [ string>number ] map-product ; : solve ( corrupted-input -- n ) get-muls [ process-mul ] map-sum ; : part1 ( -- n ) get-input solve ; : part2 ( -- n ) get-input R/ don't\(\)(.|\n)*?do\(\)/ split concat R/ don't\(\)(.|\n)*/ "" re-replace solve ;
Haskell
Oof, a parsing problem :/ This is some nasty-ass code.
step
is almost the State monad written out explicitly.Solution
import Control.Monad import Data.Either import Data.List import Text.Parsec data Ins = Mul !Int !Int | Do | Dont readInput :: String -> [Ins] readInput = fromRight undefined . parse input "" where input = many ins <* many anyChar ins = choice . map try $ [ Mul <$> (string "mul(" *> arg) <*> (char ',' *> arg) <* char ')', Do <$ string "do()", Dont <$ string "don't()", anyChar *> ins ] arg = do s <- many1 digit guard $ length s <= 3 return $ read s run f = snd . foldl' step (True, 0) where step (e, a) i = case i of Mul x y -> (e, if f e then a + x * y else a) Do -> (True, a) Dont -> (False, a) main = do input <- readInput <$> readFile "input03" print $ run (const True) input print $ run id input
Love to see you chewing through this parsing problem in Haskell, I didn’t dare use Parsec because I wasn’t confident enough.
Why did you decide to have a strict definition ofMul !Int !Int
?My guess is because a linter and/or HLS was suggesting it. I know HLS used to suggest making your fields strict in almost all cases. In this case I have a hunch that it slightly cuts down on memory usage because we use almost all
Mul
s either way. So it does not need to keep the string it is parsed from in memory as part of the thunk.But it probably makes a small/negligible difference here.
Yep, HLS suggested it, and I figured since I’m definitely going to be using all of the values (in part one, at least), why not?
Normally I ignore that kind of nitpicky suggestion though.
Python
Part1:
matches = re.findall(r"(mul\((\d+),(\d+)\))", input) muls = [int(m[1]) * int(m[2]) for m in matches] print(sum(muls))
Part2:
instructions = list(re.findall(r"(do\(\)|don't\(\)|(mul\((\d+),(\d+)\)))", input) mul_enabled = True muls = 0 for inst in instructions: if inst[0] == "don't()": mul_enabled = False elif inst[0] == "do()": mul_enabled = True elif mul_enabled: muls += int(inst[2]) * int(inst[3]) print(muls)
I started poking at doing a proper lexer/parser, but then I thought about how early in AoC it is and how low the chance is that the second part will require proper parsing.
So therefore; hello regex my old friend, I’ve come to talk with you again.
C#
List<string> instructions = new List<string>(); public void Input(IEnumerable<string> lines) { foreach (var line in lines) instructions.AddRange(Regex.Matches(line, @"mul\(\d+,\d+\)|do\(\)|don't\(\)").Select(m => m.Value)); } public void Part1() { var sum = instructions.Select(mul => Regex.Match(mul, @"(\d+),(\d+)").Groups.Values.Skip(1).Select(g => int.Parse(g.Value))).Select(cc => cc.Aggregate(1, (acc, val) => acc * val)).Sum(); Console.WriteLine($"Sum: {sum}"); } public void Part2() { bool enabled = true; long sum = 0; foreach(var inst in instructions) { if (inst.StartsWith("don't")) enabled = false; else if (inst.StartsWith("do")) enabled = true; else if (enabled) sum += Regex.Match(inst, @"(\d+),(\d+)").Groups.Values.Skip(1).Select(g => int.Parse(g.Value)).Aggregate(1, (acc, val) => acc * val); } Console.WriteLine($"Sum: {sum}"); }
Rust
Didn’t do anything crazy here – ended up using regex like a bunch of other folks.
solution
use regex::Regex; use crate::shared::util::read_lines; fn parse_mul(input: &[String]) -> (u32, u32) { // Lazy, but rejoin after having removed `\n`ewlines. let joined = input.concat(); let re = Regex::new(r"mul\((\d+,\d+)\)|(do\(\))|(don't\(\))").expect("invalid regex"); // part1 let mut total1 = 0u32; // part2 -- adds `do()`s and `don't()`s let mut total2 = 0u32; let mut enabled = 1u32; re.captures_iter(&joined).for_each(|c| { let (_, [m]) = c.extract(); match m { "do()" => enabled = 1, "don't()" => enabled = 0, _ => { let product: u32 = m.split(",").map(|s| s.parse::<u32>().unwrap()).product(); total1 += product; total2 += product * enabled; } } }); (total1, total2) } pub fn solve() { let input = read_lines("inputs/day03.txt"); let (part1_res, part2_res) = parse_mul(&input); println!("Part 1: {}", part1_res); println!("Part 2: {}", part2_res); } #[cfg(test)] mod test { use super::*; #[test] fn test_solution() { let test_input = vec![ "xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))".to_string(), ]; let (p1, p2) = parse_mul(&test_input); eprintln!("P1: {p1}, P2: {p2}"); assert_eq!(161, p1); assert_eq!(48, p2); } }
Solution on my github (Made it public now)
Go
Part 1, just find the regex groups, parse to int, and done.
Part 1
func part1() { file, _ := os.Open("input.txt") defer file.Close() scanner := bufio.NewScanner(file) re := regexp.MustCompile(`mul\(([0-9]{1,3}),([0-9]{1,3})\)`) product := 0 for scanner.Scan() { line := scanner.Text() submatches := re.FindAllStringSubmatch(line, -1) for _, s := range submatches { a, _ := strconv.Atoi(s[1]) b, _ := strconv.Atoi(s[2]) product += (a * b) } } fmt.Println(product) }
Part 2, not so simple. Ended up doing some weird hack with a map to check if the multiplication was enabled or not. Also instead of finding regex groups I had to find the indices, and then interpret what those mean… Not very readable code I’m afraid
Part2
func part2() { file, _ := os.Open("input.txt") defer file.Close() scanner := bufio.NewScanner(file) mulRE := regexp.MustCompile(`mul\(([0-9]{1,3}),([0-9]{1,3})\)`) doRE := regexp.MustCompile(`do\(\)`) dontRE := regexp.MustCompile(`don't\(\)`) product := 0 enabled := true for scanner.Scan() { line := scanner.Text() doIndices := doRE.FindAllStringIndex(line, -1) dontIndices := dontRE.FindAllStringIndex(line, -1) mulSubIndices := mulRE.FindAllStringSubmatchIndex(line, -1) mapIndices := make(map[int]string) for _, do := range doIndices { mapIndices[do[0]] = "do" } for _, dont := range dontIndices { mapIndices[dont[0]] = "dont" } for _, mul := range mulSubIndices { mapIndices[mul[0]] = "mul" } nextMatch := 0 for i := 0; i < len(line); i++ { val, ok := mapIndices[i] if ok && val == "do" { enabled = true } else if ok && val == "dont" { enabled = false } else if ok && val == "mul" { if enabled { match := mulSubIndices[nextMatch] a, _ := strconv.Atoi(string(line[match[2]:match[3]])) b, _ := strconv.Atoi(string(line[match[4]:match[5]])) product += (a * b) } nextMatch++ } } } fmt.Println(product) }
I also used Go - my solution for part 1 was essentially identical to yours. I went a different route for part 2 that I think ended up being simpler though.
I just prepended
do()
anddon't()
to the original regex with a|
, that way it captured all 3 in order and I just looped through all the matches once and toggled theisEnabled
flag accordingly.Always interesting to see how other people tackle the same problem!
Part 2 Code
func part2() { filePath := "input.txt" file, _ := os.Open(filePath) defer file.Close() pattern := regexp.MustCompile(`do\(\)|don't\(\)|mul\((\d{1,3}),(\d{1,3})\)`) productSum := 0 isEnabled := true scanner := bufio.NewScanner(file) for scanner.Scan() { line := scanner.Text() matches := pattern.FindAllStringSubmatch(line, -1) for _, match := range matches { if match[0] == "do()" { isEnabled = true } else if match[0] == "don't()" { isEnabled = false } else if isEnabled && len(match) == 3 { n, _ := strconv.Atoi(match[1]) m, _ := strconv.Atoi(match[2]) productSum += n * m } } } fmt.Println("Total: ", productSum) }
Honestly this is soo much better, I’m not proud of my code at all haha. Thanks for sharing, definitely adding that | to my bag of tricks
Uiua
Part 1:
&fras "day3/input.txt" /+≡/×≡⋕≡↘1regex "mul\\((\\d+),(\\d+)\\)"
Part 2:
Filter ← ⍜⊜∘≡⋅""⊸⦷°□ .&fras "day3/input.txt" ∧Filter♭regex"don't\\(\\)?(.*?)(?:do\\(\\)|$)" /+≡/×≡⋕≡↘1regex "mul\\((\\d+),(\\d+)\\)"
Kotlin
fun part1(input: String): Int { val pattern = "mul\\((\\d{1,3}),(\\d{1,3})\\)".toRegex() var sum = 0 pattern.findAll(input).forEach { match -> val first = match.groups[1]?.value?.toInt()!! val second = match.groups[2]?.value?.toInt()!! sum += first * second } return sum } fun part2(input: String): Int { val pattern = "mul\\((\\d{1,3}),(\\d{1,3})\\)|don't\\(\\)|do\\(\\)".toRegex() var sum = 0 var enabled = true pattern.findAll(input).forEach { match -> if (match.value == "do()") enabled = true else if (match.value == "don't()") enabled = false else if (enabled) { val first = match.groups[1]?.value?.toInt()!! val second = match.groups[2]?.value?.toInt()!! sum += first * second } } return sum }
You can avoid having to escape the backslashes in regexps by using multiline strings:
val pattern = """mul\((\d{1,3}),(\d{1,3})\)""".toRegex()
deleted by creator