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


🔒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

  • Gobbel2000@feddit.de
    link
    fedilink
    arrow-up
    4
    ·
    11 months ago

    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.

  • Leo Uino@lemmy.sdf.org
    link
    fedilink
    arrow-up
    4
    ·
    11 months ago

    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
    
  • __init__@programming.dev
    link
    fedilink
    arrow-up
    3
    ·
    11 months ago

    (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 &amp; 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=}")
    
      • cacheson@kbin.social
        link
        fedilink
        arrow-up
        1
        ·
        11 months ago

        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 call f with x 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.

        • Andy@programming.dev
          link
          fedilink
          arrow-up
          1
          ·
          11 months ago

          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.

          • cacheson@kbin.social
            link
            fedilink
            arrow-up
            2
            ·
            11 months ago

            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.

  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    11 months ago

    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;
    }
    
  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    3
    ·
    edit-2
    11 months ago

    LANGUAGE: Nim

    Welcome to the advent of parsing!
    Took me a lot more time than it should (Please, don’t check prior commits 😅).

    day_04.nim

  • hades@lemm.ee
    link
    fedilink
    arrow-up
    3
    ·
    11 months ago

    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) &amp; set(having))
          if not matches:
            continue
          points += 1 &lt;&lt; (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) &amp; set(having))
          if not matches:
            continue
          for j in range(i + 1, i + 1 + matches):
            factors[j] = factors[j] + factors[i]
        return count
    
  • Andy@programming.dev
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    10 months ago

    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  swap '[ _ follow-card ]
      map-sum .
    ;
    
  • Jummit@lemmy.one
    link
    fedilink
    arrow-up
    2
    ·
    11 months ago

    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)
    
  • sjmulder@lemmy.sdf.org
    link
    fedilink
    arrow-up
    2
    ·
    11 months ago

    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.

    GitHub link

    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<nnums; i++)
    					nmatch += nums[i] == val;
    
    		for (i=0; i<nmatch; i++)
    			nextra[id+1+i] += nextra[id]+1;
    
    		p1 += nmatch ? 1 << (nmatch-1) : 0;
    		p2 += nextra[id]+1;
    	}
    
    	printf("%d %d\n", p1, p2);
    	return 0;
    }
    

        • mykl@lemmy.world
          link
          fedilink
          arrow-up
          1
          ·
          11 months ago

          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.

  • UlrikHD@programming.dev
    link
    fedilink
    English
    arrow-up
    2
    ·
    11 months ago

    Feels like the challenges are getting easier than harder currently. Fairly straightforward when doing it the lazy way with python.

    Python
    import re
    
    winning_number_pattern: re.Pattern = re.compile(r' +([\d ]*?) +\|')
    lottery_number_pattern: re.Pattern = re.compile(r'\| +([\d ]*)')
    
    
    def get_winning_numbers(line: str) -> set[str]:
        return set(winning_number_pattern.search(line).group(1).split())
    
    
    def get_lottery_numbers(line: str) -> set[str]:
        return set(lottery_number_pattern.search(line).group(1).split())
    
    
    def get_winnings(winning_numbers: set[str], lottery_numbers: set[str]) -> int:
        return int(2 ** (len(winning_numbers.intersection(lottery_numbers)) - 1))
    
    
    def puzzle_1() -> int:
        points: int = 0
        with open('day4_scratchcards.txt', 'r', encoding='utf-8') as file:
            for line in file:
                points += get_winnings(get_winning_numbers(line), get_lottery_numbers(line))
        return points
    
    
    class ScratchCard:
        def __init__(self, line: str):
            self.amount: int = 1
            self.winnings: int = len(get_winning_numbers(line).intersection(get_lottery_numbers(line)))
    
        def update(self, extra: int) -> None:
            self.amount = self.amount + extra
    
        def __radd__(self, other):
            return self.amount + other
    
    
    def puzzle_2() -> int:
        scratch_card_list: list[ScratchCard] = []
        with open('day4_scratchcards.txt', 'r', encoding='utf-8') as file:
            for line in file:
                scratch_card_list.append(ScratchCard(line))
    
        for i, scratch_card in enumerate(scratch_card_list):
            for j in range(1, scratch_card.winnings + 1):
                try:
                    scratch_card_list[i + j].update(scratch_card.amount)
                except IndexError:
                    pass
        return sum(scratch_card_list)
    
    
    if __name__ == '__main__':
        print(puzzle_1())
        print(puzzle_2())
    
    • bob_lemon@feddit.de
      link
      fedilink
      arrow-up
      1
      ·
      11 months ago

      That int-call on the return value for the point value is a good idea. I manually returned 0 if there were no matches.

    • Leo Uino@lemmy.sdf.org
      link
      fedilink
      arrow-up
      1
      ·
      11 months ago

      Puzzles on the weekend are usually a bit more involved than weekdays. 23 is probably going to be a monster this year…

  • pnutzh4x0r@lemmy.ndlug.org
    link
    fedilink
    English
    arrow-up
    2
    ·
    11 months ago

    Language: Python

    Part 1

    Sets really came in handy for this challenge, as did recognizing that you can use powers of two to compute the points for each card. I tried using a regular expression to parse each card, but ended up just doing it manually with split :|

    Numbers = set[int]
    Card    = list[Numbers]
    
    def read_cards(stream=sys.stdin) -> Iterator[Card]:
        for line in stream:
            yield [set(map(int, n.split())) for n in line.split(':')[-1].split('|')]
    
    def main(stream=sys.stdin) -> None:
        cards  = [numbers &amp; winning for winning, numbers in read_cards(stream)]
        points = sum(2**(len(card)-1) for card in cards if card)
        print(points)
    
    Part 2

    This took me longer than I wished… I had to think about it carefully before seeing how you can just keep track of the counts of each card, and then when you get to that card, you add to its copies your current count.

    def main(stream=sys.stdin) -> None:
        cards  = [numbers &amp; winning for winning, numbers in read_cards(stream)]
        counts = defaultdict(int)
    
        for index, card in enumerate(cards, 1):
            counts[index] += 1
            for copy in range(index + 1, index + len(card) + 1):
                counts[copy] += counts[index]
    
        print(sum(counts.values()))
    

    GitHub Repo

  • pngwen@lemmy.sdf.org
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    11 months ago

    PHP

    Today was the easiest day so far IMHO. Today, I coded in PHP, a horrible language that produces even worse code. (Ok, full confession, I fed my family for about half a decade on PHP. I seemed to have gotten stuck with it, and so I earned a PhD to escape it.)

    Anyway, the only trouble I had was I forgot about the explode function’s capacity to return empty strings. Once I filtered those I had the correct answer on the first one, and then 10 minutes later I had the second part. I wrote my code true to raw php’s awful idioms, though I didn’t make it web based. I read from stdin.

    My code is linked on github: