Day 4: Scratchcards
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)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ or pastebin (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
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
🔒This post will be unlocked when there is a decent amount of submissions on the leaderboard to avoid cheating for top spots
🔓 Unlocked after 8 mins
I had to give Uiua another go today. (run it here)
{"Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53" "Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19" "Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1" "Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83" "Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36" "Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11"} LtoDec ← ∧(+ ×10:) :0 StoDec ← LtoDec▽≥0. ▽≤9. -@0 # Split on spaces, drop dross, parse ints ≡(⊜□≠0.⊐∵(StoDec)↘ 2⊜(□)≠@\s.⊔) # Find matches ≡(/+/+⊠(⌕)⊃(⊔⊢↙ 1)(⊔⊢↙¯1)) # part 1 /+ⁿ:2-1 ▽±.. # part 2 - start with matches and initial counts =..: # len times: get 1st of each, rotate both, add new counts ⍥(⬚0+↯: ⊙⊙∩(↻1) ⊙:∩(⊢.))⧻. /+⊙;
what if code obfuscation was built into the language?
WTF
I’m fascinated and horrified
Rust
This one wasn’t too bad. The example for part 2 even tells you how to process everything by visiting each card once in order. Another option could be to recursively look at all won copies, but that’s probably much less efficient.
LANGUAGE: Nim
Welcome to the advent of parsing!
Took me a lot more time than it should (Please, don’t check prior commits 😅).Please, don’t check prior commits
This should be the motto of AoC
Nim
This one was pretty simple, just parse the numbers into sets and check the size of the intersection. Part 2 just made the scoring mechanism a little more complicated.
Hi there! Looks like you linked to a Lemmy community using a URL instead of its name, which doesn’t work well for people on different instances. Try fixing it like this: !nim@programming.dev
That’s some elegant code! Then again, I suppose that’s the beauty of nim.
I’m rather spoiled by python, so I feel like it could be more elegant. xD
But yeah, I do like how this one turned out, and nim runs a whole lot faster than python does. I really like nim’s “method call syntax”. Instead of having methods associated with an individual type, you can just call any procedure as
x.f(remaining_args)
to callf
withx
as its first argument. Makes it easy to chain procedures. Since nim is strongly typed, it’ll know which procedure you mean to use by the signature.Aside from the general conciseness, the “universal function call syntax” is my favorite aspect of nim.
If you want to take chaining procedures to the next level, try a concatenative language like Factor (I have a day 4 solution in this thread – with no assignment to variables).
I also suggest having a look at Roc if you want a functional programming adventure, which offers great chaining syntax, a very friendly community, and is in an exciting development phase.
Thank you, I’ll keep those in mind. Functional programming seems interesting to me, but I don’t have any practical experience with it. At some point I want to learn one of the languages that are dedicated to it. Nim does have some features for enabling a functional style, but the overall flexibility of the language probably makes it harder to learn said style.
Haskell
11:39 – I spent most of the time reading the scoring rules and (as usual) writing a parser…
import Control.Monad import Data.Bifunctor import Data.List readCard :: String -> ([Int], [Int]) readCard = join bimap (map read) . second tail . break (== "|") . words . tail . dropWhile (/= ':') countShared = length . uncurry intersect part1 = sum . map ((\n -> if n > 0 then 2 ^ (n - 1) else 0) . countShared) part2 = sum . foldr ((\n a -> 1 + sum (take n a) : a) . countShared) [] main = do input <- map readCard . lines <$> readFile "input04" print $ part1 input print $ part2 input
Still trying to make sense of it but that part two fold is just jummy!
I’m really impressed by your part 2. And I thought my solution was short…
Not familiar with Lean4 but it looks like the same approach. High five!
Factor on github (with comments and imports):
: line>cards ( line -- winning-nums player-nums ) ":|" split rest [ [ CHAR: space = ] trim split-words harvest [ string>number ] map ] map first2 ; : points ( winning-nums player-nums -- n ) intersect length dup 0 > [ 1 - 2^ ] when ; : part1 ( -- ) "vocab:aoc-2023/day04/input.txt" utf8 file-lines [ line>cards points ] map-sum . ; : follow-card ( i commons -- n ) [ 1 ] 2dip 2dup nth swapd over + (a..b] [ over follow-card ] map-sum nip + ; : part2 ( -- ) "vocab:aoc-2023/day04/input.txt" utf8 file-lines [ line>cards intersect length ] map dup length <iota> swap '[ _ follow-card ] map-sum . ;
Python
Questions and feedback welcome!
import collections import re from .solver import Solver class Day04(Solver): def __init__(self): super().__init__(4) self.cards = [] def presolve(self, input: str): lines = input.rstrip().split('\n') self.cards = [] for line in lines: left, right = re.split(r' +\| +', re.split(': +', line)[1]) left, right = map(int, re.split(' +', left)), map(int, re.split(' +', right)) self.cards.append((list(left), list(right))) def solve_first_star(self): points = 0 for winning, having in self.cards: matches = len(set(winning) & set(having)) if not matches: continue points += 1 << (matches - 1) return points def solve_second_star(self): factors = collections.defaultdict(lambda: 1) count = 0 for i, (winning, having) in enumerate(self.cards): count += factors[i] matches = len(set(winning) & set(having)) if not matches: continue for j in range(i + 1, i + 1 + matches): factors[j] = factors[j] + factors[i] return count
I enjoyed this one. It was a nice simple break after Days 1 and 3; the type of basic puzzle I expect from the first few days of Advent of Code. Pretty simple logic in this one, I don’t think I would change too much. I’m sure I’ll find a way to clean up how it’s written a bit, but I’m happy with this one today.
https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day04.rs
struct Scratchcard { winning_numbers: HashSet, player_numbers: HashSet, } impl Scratchcard { fn from(input: &str) -> Scratchcard { let (_, numbers) = input.split_once(':').unwrap(); let (winning_numbers, player_numbers) = numbers.split_once('|').unwrap(); let winning_numbers = winning_numbers .split_ascii_whitespace() .filter_map(|number| number.parse::().ok()) .collect::>(); let player_numbers = player_numbers .split_ascii_whitespace() .filter_map(|number| number.parse::().ok()) .collect::>(); Scratchcard { winning_numbers, player_numbers, } } fn matches(&self) -> u32 { self.winning_numbers .intersection(&self.player_numbers) .count() as u32 } } pub struct Day04; impl Solver for Day04 { fn star_one(&self, input: &str) -> String { input .lines() .map(Scratchcard::from) .map(|card| { let matches = card.matches(); if matches == 0 { 0 } else { 2u32.pow(matches - 1) } }) .sum::() .to_string() } fn star_two(&self, input: &str) -> String { let cards: Vec = input.lines().map(Scratchcard::from).collect(); let mut card_counts = vec![1usize; cards.len()]; for card_number in 0..cards.len() { let matches = cards[card_number].matches(); if matches == 0 { continue; } for i in 1..=matches { card_counts[card_number + i as usize] += card_counts[card_number]; } } card_counts.iter().sum::().to_string() } }
APL
I’m using this years’ AoC to learn (Dyalog) APL, so this is probably terrible code. I’m happy to receive pointers for improvement, particularly if there is a way to write the same logic with tacit functions or inner/outer products that I missed.
input←⊃⎕NGET'inputs/day4.txt'1 num_matches←'Card [ \d]+: ([ 0-9]+) \| ([ 0-9]+)'⎕S{≢↑∩/0~⍨¨{,⎕CSV⍠'Separator' ' '⊢⍵'S'3}¨⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} input ⎕←+/2*1-⍨0~⍨num_matches ⍝ part 1 ⎕←+/{⍺←0 ⋄ ⍺=≢⍵:⍵ ⋄ (⍺+1)∇⍵ + (≢⍵)↑∊((⍺+1)⍴0)(num_matches[⍺]⍴⍵[⍺])((≢⍵)⍴0)}(≢num_matches)⍴1 ⍝ part 2
I just posted a solution in Uiua, which is also probably equally terrible, but if you squint you can see some similarities in our approaches.
I haven’t heard of Uiua before, but I can read some things :D I like the idea of rotating the vector instead of manually padding it with the required number of leading zeroes!
I think it’s only a few months old. I’ve enjoyed playing with it because it allows me to use stack manipulation as an alternative to combinators and every symbol has a fixed arity both of which make it feel a lot more accessible to me.
I was very pleased with myself when I thought of that rotation trick :-)
Dart Solution
Okay, that’s more like it. Simple parsing and a bit of recursion, and fits on one screen. Perfect for day 4 :-)
int matchCount(String line) => line .split(RegExp('[:|]')) .skip(1) .map((ee) => ee.trim().split(RegExp(r'\s+')).map(int.parse)) .map((e) => e.toSet()) .reduce((s, t) => s.intersection(t)) .length; late List matches; late List totals; int scoreFor(int ix) { if (totals[ix] != 0) return totals[ix]; return totals[ix] = [for (var m in 0.to(matches[ix])) scoreFor(m + ix + 1) + 1].sum; } part1(List lines) => lines.map((e) => pow(2, matchCount(e) - 1).toInt()).sum; part2(List lines) { matches = [for (var e in lines) matchCount(e)]; totals = List.filled(matches.length, 0); return matches.length + 0.to(matches.length).map(scoreFor).sum; }
Ruby
Somehow took way longer on the second part than the first part trying a recursive approach and then realizing that was dumb.
https://github.com/snowe2010/advent-of-code/blob/master/ruby_aoc/2023/day04/day04.rb
Edit: Sorry, should have read your code first, you made it work too. if it works it works, Recursive solutions just click for me over other solutions.
I made the recursion work, went to a depth of 24 for my input set.
Recursive C#
internal class Day4Task2 : IRunnable { private Regex _regex = new Regex("Card\\s*\\d*: ([\\d\\s]{2} )*\\|( [\\d\\s]{2})*"); private Dictionary _matchCountCache = new Dictionary(); private int _maxDepth = 0; public void Run() { var inputLines = File.ReadAllLines("Days/Four/Day4Input.txt"); int sumScore = 0; for (int i = 0; i < inputLines.Length; i++) { sumScore += ScoreCard(i, inputLines, 0); Console.WriteLine("!!!" + i + "!!!"); } Console.WriteLine("Sum:"+sumScore.ToString()); Console.WriteLine("Max Recursion Depth:"+ _maxDepth.ToString()); } private int ScoreCard(int lineId, string[] inputLines, int depth) { if( depth > _maxDepth ) { _maxDepth = depth; } if(lineId >= inputLines.Length) { return 0; } int matchCount = 0; if (!_matchCountCache.ContainsKey(lineId)) { var winningSet = new HashSet(); var matches = _regex.Match(inputLines[lineId]); foreach (Capture capture in matches.Groups[1].Captures) { winningSet.Add(capture.Value.Trim()); } foreach (Capture capture in matches.Groups[2].Captures) { if (winningSet.Contains(capture.Value.Trim())) { matchCount++; } } _matchCountCache[lineId] = matchCount; } matchCount = _matchCountCache[lineId]; int totalCards = 1; while(matchCount > 0) { totalCards += ScoreCard(lineId+matchCount, inputLines, depth+1); matchCount--; } //Console.WriteLine("Finished processing id: " + lineId + " Sum is: " + totalCards); return totalCards; } }
(python) Much easier than day 3.
code
import pathlib base_dir = pathlib.Path(__file__).parent filename = base_dir / "day4_input.txt" with open(base_dir / filename) as f: lines = f.read().splitlines() score = 0 extra_cards = [0 for _ in lines] n_cards = [1 for _ in lines] for i, line in enumerate(lines): _, numbers = line.split(":") winning, have = numbers.split(" | ") winning_numbers = {int(n) for n in winning.split()} have_numbers = {int(n) for n in have.split()} have_winning_numbers = winning_numbers & have_numbers n_matches = len(have_winning_numbers) if n_matches: score += 2 ** (n_matches - 1) j = i + 1 for _ in range(n_matches): if j >= len(lines): break n_cards[j] += n_cards[i] j += 1 answer_p1 = score print(f"{answer_p1=}") answer_p2 = sum(n_cards) print(f"{answer_p2=}")
Python
Part 1: https://github.com/porotoman99/Advent-of-Code-2023/blob/main/Day 4/part1.py
Part 2: https://github.com/porotoman99/Advent-of-Code-2023/blob/main/Day 4/part2.py
I found out about this event for the first time yesterday and was able to get caught up in time for day 4.
Language: C
Another day of parsing, another day of
strsep()
to the rescue. Today was one of those satisfying days where the puzzle text is complicated but the solution is simple once well understood.Code (29 lines)
int main() { char line[128], *rest, *tok; int nextra[200]={0}, nums[10], nnums; int p1=0,p2=0, id,val,nmatch, i; for (id=0; (rest = fgets(line, sizeof(line), stdin)); id++) { nnums = nmatch = 0; while ((tok = strsep(&rest, " ")) && !strchr(tok, ':')) ; while ((tok = strsep(&rest, " ")) && !strchr(tok, '|')) if ((val = atoi(tok))) nums[nnums++] = val; while ((tok = strsep(&rest, " "))) if ((val = atoi(tok))) for (i=0; i
Looks like Lemmy’s odd parsing broke your comment at the less-than sign.
That’s unfortunate, although it looks good on my instance (SDF). Anything I could do?
Ohh that’s interesting, I’ve seen a few comments about mishandling of special chars in code blocks and assumed it was a server issue, maybe it’s fixed in newer releases or perhaps it’s client side.
Nice and easy.
Lua
-- SPDX-FileCopyrightText: 2023 Jummit -- -- SPDX-License-Identifier: GPL-3.0-or-later local function nums(str) local res = {} for num in str:gmatch("%d+") do res[num] = true end return res end local cards = {} local points = 0 for line in io.open("4.input"):lines() do local winning, have = line:match("Card%s*%d+: (.*) | (.*)") winning = nums(winning) have = nums(have) local first = true local score = 0 local matching = 0 for num in pairs(have) do if winning[num] then matching = matching + 1 if first then first = false score = score + 1 else score = score * 2 end end end points = points + score table.insert(cards, {have=have, wins=matching, count=1}) end print(points) local cardSum = 0 for i, card in ipairs(cards) do cardSum = cardSum + card.count for n = i + 1, i + card.wins do cards[n].count = cards[n].count + card.count end end print(cardSum)