Rules: no spoilers.

The other rules are made up as we go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

  • Sailor Sega Saturn
    link
    English
    7
    edit-2
    1 year ago

    Just when I think I’m out, awful systems pulls me right back in.

    C++, Horrifying C++ for day 1b check it out ;)

    Day 1: https://www.animeprincess.net/blog/?p=55

    One day is enough for me though, writing deliberately off-the-wall code is surprisingly mentally taxing, and normally I make sure to never program outside of work.

    • @selfMA
      link
      English
      41 year ago

      // Where we're going we won't need regexes.

      fuck yes

      • @froztbyte
        link
        English
        41 year ago

        honestly I considered writing a parser-based approach

        then I was too tired and thought “hmm, doing this with grok would be funny”, but I didn’t have logstash handy and fuck dealing with containers at midnight

        I will, however, do that today

        • @froztbyte
          link
          English
          41 year ago

          Status report: grok allows for non-greedy matching but still captures greedily for term assignment. I think I have a workaround that might work (recursively pipe data back to itself, gated on length for action), need to test later

          This particular flavour of parsecrime is near guaranteed to be of interest to very few, but I want to see if I can make it work nonetheless. That’s just how my brainworms work.

  • @200fifty
    link
    English
    7
    edit-2
    1 year ago

    day 1

    part 1

    perl
    #!/usr/bin/env perl
    
    use strict;
    use warnings;
    use 5.010;
    
    my $total = 0;
    
    for my $line (<>) {
        my @nums = ($line =~ /\d/g);
        $total += $nums[0] * 10 + $nums[-1];
    }
    
    say $total;
    

    part 2

    perl
    #!/usr/bin/env perl
    
    use strict;
    use warnings;
    use v5.010;
    
    my %nums = (one => 1, two => 2, three => 3, four => 4, five => 5, six => 6, seven => 7, eight => 8, nine => 9);
    $nums{$_} = $_ for 1..9;
    
    my $regex = join "|", keys %nums;
    
    my $total = 0;
    
    for my $line (<>) {
        $line =~ /($regex)/;
        my $first_num = $nums{$1};
    
        my $window = 1;
        my $sub = substr $line, -1;
        while ($sub !~ /($regex)/) {
            $window ++;
            $sub = substr $line, -$window;
        }
    
        $sub =~ /($regex)/;
        my $second_num = $nums{$1};
    
        $total += $first_num * 10 + $second_num;
    }
    
    say $total;
    

    Part 2 gave me a surprising amount of trouble. I resolved it by looking at longer and longer substrings from the end of the line in order to find the very last word even if it overlapped, which you can’t do with normal regex split. I doubt this is the most efficient possible solution.

    Also Lemmy is eating my < characters inside code blocks, which seems wrong. Pretend the “&lt;>” part says “<>”, lol

    • @froztbyte
      link
      English
      41 year ago

      lemme is an incredibly hungry little shit, it eats so much

    • @200fifty
      link
      English
      41 year ago

      day 2

      perl
      #!/usr/bin/env perl
      
      use strict;
      use warnings;
      use v5.010;
      use List::Util qw/ max /;
      
      # Parse the input
      
      my %games = ();
      
      for my $line (&lt;>) {
          $line =~ /Game (\d+): (.+)/;
          my $game_id = $1;
          my $game_str = $2;
      
          my @segments = split '; ', $game_str;
          my @game = ();
          for my $segment (@segments) {
              my @counts = split ', ', $segment;
      
              my %colors = (red => 0, blue => 0, green => 0);
              for my $count (@counts) {
                  $count =~ /(\d+) (\w+)/;
                  $colors{$2} = $1;
              }
      
              push @game, { %colors };
          }
      
          $games{$game_id} = [ @game ];
      }
      
      # Part 1
      
      my $part1 = 0;
      
      game: for my $game_id (keys %games) {
          for my $segment (@{$games{$game_id}}) {
              next game if $segment->{red} > 12 || $segment->{green} > 13 || $segment->{blue} > 14;
          }
      
          $part1 += $game_id;
      }
      
      say "Part 1: $part1";
      
      # Part 2
      
      my $part2 = 0;
      
      for my $game (values %games) {
          my ($red, $green, $blue) = (0, 0, 0);
      
          for my $segment (@$game) {
              $red = max $segment->{red}, $red;
              $green = max $segment->{green}, $green;
              $blue = max $segment->{blue}, $blue;
          }
      
          $part2 += $red * $green * $blue;
      }
      
      say "Part 2: $part2";
      

      Found this much easier than day 1 honestly…

  • @datarama
    link
    English
    51 year ago

    deleted by creator

  • @datarama
    link
    English
    5
    edit-2
    1 year ago

    deleted by creator

  • @datarama
    link
    English
    5
    edit-2
    1 year ago

    deleted by creator

  • Sailor Sega Saturn
    link
    English
    4
    edit-2
    1 year ago

    I have come up with a more horrifying way to solve Day 1 Part 1 involving C++ implementation defined behavior, but it requires launching two subprocesses for every test case so I’m not sure I have the motivation right now.

    Proof of concept: https://www.animeprincess.net/blog/?p=60

    • @swlabr
      link
      English
      11 year ago

      I believe you’ve posted in the wrong thread. This is the awful systems thread, not the awesome systems thread.

  • @geriksonOP
    link
    English
    41 year ago

    Day 14: Parabolic Reflector Dish

    I only managed part 1 today. My enthusiasm for index fiddling is waning rapidly.

    • @zogwarg
      link
      English
      41 year ago

      How about not fiddling with indices?

      JQ Notfiddlingwithindexification

      https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/14-a.jq

      #!/usr/bin/env jq -n -R -f
      
      # Dish to grid
      [ inputs / "" ]
      
      # Tilt UP
      | transpose                       # Transpose, for easier RE use
      | map(                            #
        ("#" + add) | [                 # For each column,   replace '^' with '#'
          scan("#[O.]*") | [            # From '#' get empty spaces and 'O' rocks
            "#", scan("O"), scan("\\.") # Let gravity do it's work.
          ]                             #
        ] | add[1:]                     # Add groups back together
       )                                #
      | transpose                       # Transpose back
      
      # For each row, count  'O'  rocks
      | map(add | [scan("O")] | length)
      
      # Add total load on "N" beam
      | [0] + reverse | to_entries
      | map( .key * .value ) | add
      

      Similarly tired with index fiddling, I was pretty happy with my approach, which led to satisfying transpose cancelling in part 2. Not the fastest code out there, but it works. Day 14 was actually my favorite one so far ^^.

  • @zogwarg
    link
    English
    41 year ago

    Back to a more straightfoward day, do they make them harder on the weekends?

    Day 4 Scratchcards

    Part 1
    #!/usr/bin/env jq -n -R -f
    [
      inputs
      # Split winning numbers | card
      | split(" | ")
      # Get numbers, remove game id
      | .[] |= [ match("\\d+"; "g").string | tonumber ] | .[0] |= .[1:]
      # Get score for each line
      | .[1] - (.[1] - .[0]) | length | select(. > 0) | pow(2; . - 1)
    ]
    
    # Output total score sum
    | add
    

    Very suited to JQ, extra trick learned using: [ match("\\d+"; "g").string | tonumber ] as a parse all ints in line.

    Part 2
    #!/usr/bin/env jq -n -R -f
    [
      inputs
      # Split winning numbers | card
      | split(" | ")
      # Get numbers, remove game id
      | .[] |= [ match("\\d+"; "g").string | tonumber ] | .[0] |= .[1:]
      # Set number of cards to 1, and further cards count
      | .[1] - (.[1] - .[0]) | [ 1, length ]
    ]
    
    | { cards: ., i: 0, l: length } | until (.i == .l;
      # Get number for current card
      .cards[.i][0] as $num
      # Increase range of futher cards, by current number
      | .cards[.i + range(.cards[.i][1]) + 1 ][0] += $num
      | .i += 1
    )
    
    # Output total sum of cards
    | [ .cards[][0] ] | add
    

    Not too much of an edit compared to part one, being able to easily do operations on range of indices is convenient.

    • @geriksonOP
      link
      English
      41 year ago

      I liked today’s puzzle. It was meaty but not frustrating.

    • @geriksonOP
      link
      English
      41 year ago

      Historically problems on Sat/Sun have been more challenging than weekdays. However given that the first 7 days are usually “warmup” problems, I’d say this years edition of AoC is more challenging than at least since 2019.

  • @zogwarg
    link
    English
    41 year ago

    Have been mostly using jq for fun.

    Day 1

    Part 1
    #!/usr/bin/env jq -n -R -f
    
    # Get and reduce every "pretty" line
    reduce inputs as $line (
      0;
      # Add extracted number
      . + ( $line / "" | [ .[] | tonumber? ] | [first * 10 , last] | add )
    )
    

    First part was easy, and very suited to jq

    Part 2
    #!/usr/bin/env jq -n -R -f
    
    # Define string to num value map
    {
      "one":   1,  "1": 1,
      "two":   2,  "2": 2,
      "three": 3,  "3": 3,
      "four":  4,  "4": 4,
      "five":  5,  "5": 5,
      "six":   6,  "6": 6,
      "seven": 7,  "7": 7,
      "eight": 8,  "8": 8,
      "nine":  9,  "9": 9
    } as $to_num |
    
    # Get and reduce every "pretty" line
    reduce inputs as $line (
      0;
      . + (
        $line |
        # Try two capture two numbers
        capture("(^.*?(?(one|two|three|four|five|six|seven|eight|nine|[1-9])).*(?(one|two|three|four|five|six|seven|eight|nine|[1-9])).*?$)?") |
        # If no capture, get one number twice
        if .f == "" then $line | capture("^.*?(?(one|two|three|four|five|six|seven|eight|nine|[1-9]))") | .l = .f else . end |
        # Add extracted number
        $to_num[.f] * 10 + $to_num[.l]
      )
    )
    

    Second part was harder than expected, i had to resort to regex.

    Day 2

    Part 1
    #!/usr/bin/env jq -n -R -f
    
    # For each game: Is 12 red cubes, 13 green cubes, and 14 blue cubes possible ?
    # Line Format =
    # Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
    [
      # Splitting input game id and content
      inputs / ": " |
      # Saving id
      (.[0] / " " | .[1] | tonumber ) as $id |
      # Parsing game
      .[1] / "; " | [
        .[] / ", " | [ .[] / " " | {(.[1]): .[0] | tonumber} ] | add |
        # Is given sample possible ?
        .red &lt;= 12 and .green &lt;= 13 and .blue &lt;= 14
      ] |
      # If all samples possible, return id, else 0
      if all then $id else 0 end
    ] |
    
    # Return sum of all possible game ids
    add
    

    Not too much trickery in this example.

    Part 2
    #!/usr/bin/env jq -n -R -f
    
    # Line Format =
    # Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
    [
      # Splitting input game id and content
      inputs / ": " |
      # Parsing game
      .[1] / "; " |
        [ .[] / ", " | [ .[] / " " | {(.[1]): .[0] | tonumber} ] | add ] |
        # Getting minimum required mumber for each color,
        # and computing the power
        {
          r: ([.[].red]   | max),
          g: ([.[].green] | max),
          b: ([.[].blue]  | max)
        } | .r * .g * .b
    ] |
    
    # Return sum of all powers
    add
    

    Satisifyingly straightfoward edit form part one.

    Day 3

    Part 1
    #!/usr/bin/env jq -n -R -f
    
    # Getting input with padding, and padded width
    [ "." + inputs + "." ] as $inputs | ( $inputs[0] | length ) as $w |
    
    # Working with flattened string, convert all symbols to '#'
    [
      ([range($w) | "."]|join("")), # Padding
      $inputs[],
      ([range($w) | "."]|join(""))  # Padding
    ] | join("") | gsub("[^0-9.]";"#") as $inputs |
    
    reduce (
      # Get all indices for symbols, in box pattern around symbols
      $inputs | indices("#")[] |
      . - $w -1  , . - $w , . - $w + 1 ,
      . - 1      , empty  , . + 1      ,
      . + $w - 1 , . + $w , . + $w + 1
    ) as $i (
      # Numbers containes bounding indices,
      # of numbers bordering symbols
      {numbers: []};
    
      # Test if current index isn't included in any found number
      def new_number($i): [ .numbers[] | .[0] &lt;= $i and $i &lt;= .[1] ] | any | not ;
      # Make "number" as bounding indices, by extending left and right
      def make_number($i):
        {a: $i, b: ($i+1 )}
          | until( $inputs[.a:.b] | test("^[^0-9]"); .a -= 1 )
          | until( $inputs[.a:.b] | test("[^0-9]$"); .b += 1 )
          | [ .a +1 , .b -1 ]
      ;
    
      # Add numbers if bordering symbol and new
      if ($inputs[$i:$i+1] | test("[0-9]")) and new_number($i) then .numbers += [ make_number($i) ] else . end
    ) |
    
    # Output sum of all found numbers
    [ .numbers[] | $inputs[.[0]:.[1]] | tonumber ] | add
    

    Took More time than i expected, glad i had the idea early to search by the indices of the symbols and not the digits. Not super well suited to jq, unless I’m missing a better solution.

    Part 2
    #!/usr/bin/env jq -n -R -f
    
    # Getting input with padding, and padded width
    [ "." + inputs + "." ] as $inputs | ( $inputs[0] | length ) as $w |
    
    # Working with flattened string, only keep gear '*' symbols
    [
      ([range($w) | "."]|join("")), # Padding
      $inputs[],
      ([range($w) | "."]|join(""))  # Padding
    ] | join("") | gsub("[^0-9*]";".") as $inputs |
    
    # Iterate over index positions of all gears
    reduce ($inputs | indices("*")[]) as $i (
      0;
      # Re-use part-1 functions
      def new_number($i):
        [ .numbers[] | .[0] &lt;= $i and $i &lt;= .[1] ] | any | not
      ;
      def make_number($i):
        {a: $i, b: ($i+1 )}
          | until( $inputs[.a:.b] | test("^[^0-9]"); .a -= 1 )
          | until( $inputs[.a:.b] | test("[^0-9]$"); .b += 1 )
          | [ .a +1 , .b -1 ]
      ;
      # Reset and add numbers for each "box" ids
      def add_numbers($box_idx):
        reduce $box_idx[] as $i ({numbers:[]};
          if ($inputs[$i:$i+1] | test("[0-9]")) and new_number($i) then
            .numbers += [ make_number($i) ]
          else
            .
          end
        )
      ;
      add_numbers([
        $i - $w -1 , $i - $w , $i -$w + 1 ,
        $i - 1     , empty   , $i + 1     ,
        $i + $w - 1, $i + $w , $i + $w + 1
      ]).numbers as $numbers |
    
      if $numbers | length == 2 then
        # Add product if exactly two bordering numbers
        . += ( $numbers | map($inputs[.[0]:.[1]]|tonumber) | .[0] * .[1] )
      else
        .
      end
    )
    

    Not too far of an edit from part one.

    • @geriksonOP
      link
      English
      41 year ago

      Perl: https://github.com/gustafe/aoc2023/blob/main/d01-Trebuchet.pl

      thoughts

      I found this really tough for a day 1 problem. Because I don’t really know regex, I did not know the secret to finding overlapping patterns. I quickly figured out that “twone” was a possibility, because it was in the example, but then I had to find other examples and hardcode them into my split pattern.

      This isn’t general, my input doesn’t have ‘sevenine’ for example.

      • @datarama
        link
        English
        41 year ago

        deleted by creator

        • @geriksonOP
          link
          English
          41 year ago

          Abso-fucking-lutly. I just find sharing a link easier than wrangling code blocks.

          There are also hipster “forges” like Sourcehut, if that’s your jam.

        • @selfMA
          link
          English
          31 year ago

          absolutely — removing my dependency on GitHub has actually been a blocker on me releasing code lately, and it’s something I want to tackle when we launch that open source community. if it helps collaboration, I can provide some ultra-janky git hosting on awful.systems with the same service that hosts our infrastructure code, though this’d be just basic git and gitweb with ssh public key auth

          • @datarama
            link
            English
            4
            edit-2
            1 year ago

            deleted by creator

            • @selfMA
              link
              English
              41 year ago

              fuck yes scheme. you might have just inspired me to write some Lisp Machine Lisp solutions, since I might need a Lisp Machine codebase to test one of my side projects

              • @datarama
                link
                English
                41 year ago

                deleted by creator

            • @geriksonOP
              link
              English
              41 year ago

              Re Perl findall, I used this regex in my “clean” solution which I didn’t post because I figure it’s more honest to submit what worked, not the smart stuff you found out later.

              regex

              # find all numerals and number in English from the string $line and put them into the array @spelled my @spelled = ( $line =~ (m/(?=(\d{1}|one|two|three|four|five|six|seven|eight|nine))/g );

              • @datarama
                link
                English
                41 year ago

                deleted by creator

            • @froztbyte
              link
              English
              31 year ago

              I like your condensed solve method, yay for concise code

      • @datarama
        link
        English
        1
        edit-2
        1 year ago

        deleted by creator

  • @Architeuthis
    link
    English
    41 year ago

    Day 4: Scratchcards

    Late to the party and never done advents before, I liked how this problem reminded me that tree traversal is thing, almost as much as I don’t that so much of my career involves powershell now.

    I’m putting everything up at https://github.com/SpaceAntelope/advent-of-code-2023 except the input files.

    Using command abbreviations like % and ? to keep the horizontal length friendly to lemmy post areas, they are expanded in git.

    Part 2 in Powershell
    function calculate([string]$data) {
      # code for parsing data and calculating matches from pt1 here, check the github link if you like banal regexps
      # returns objects with the relevant fields being the card index and the match count
    }
    
    function calculateAccumulatedCards($data) {
        $cards = calculate $data # do pt1 calculations
    
        $cards 
        | ? MatchCount -gt 0 # otherwise the losing card becomes its own child and the search cycles to overflow
        | % { 
            $children = ($_.Index + 1) .. ($_.Index + $_.MatchCount)  # range of numbers corresponding to indices of cards won
            | % { $cards[$_ - 1] } # map to the actual cards
            | ? { $null -ne $_ }  # filter out overflow when index exceeds input length
    
            $_ | Add-Member -NotePropertyName Children -NotePropertyValue $children # add cards gained as children property
        }
    
        # do depth first search on every card and its branching children while counting every node
        # the recursive function is inlined in the foreach block because it's simpler than referencing it 
        # from outside the parallel scope
        $cards | % -Parallel {
            function traverse($card) {
                $script:count++        
                foreach ($c in $card.Children) { traverse($c) }
            }
            
            $script:count = 0 # script: means it's basically globally scoped
            traverse $_ 
            $script:count # pass node count to pipeline     
        } 
        | measure -sum    
        | % sum
    }
    
  • @geriksonOP
    link
    English
    41 year ago

    Day 11: Cosmic Expansion

    https://adventofcode.com/2023/day/11

    discussion

    After yesterday’ fiddle-fest we are back with a straight-forward puzzle. Today we get the return of Manhattan distance, an AoC fav, but this time not spelled out to fool the crafty LLMs.

    I made the initial decision not to “move” the galaxies in the initial map, but instead to store an offset that was increased whenever an empty row or column preceding the object was detected. This turned out to make part 2 really easy once I figured out the off-by-one error.

    • @zogwarg
      link
      English
      21 year ago
      discussion

      In retrospect that would have been far better for runtime, my dist function ended up being a tad expensive.

      I substituted the rows/columns, with multiplication by the expansion rate if they were all numbers. And then for each galaxy pair do a running sum by going “down” the “right” and adding the distance for each row and column crossed.

      https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/11-b.jq

      transpose is nice to have in that approach.

    • @froztbyte
      link
      English
      41 year ago

      Nice, I’ll be reading :D

      (Possibly have some dart coming up on a thing soon)

      • @swlabr
        link
        English
        41 year ago

        I’ll be honest: so far, Dart is pretty rubbish for this kind of exercise for the simple reason that their Strings aren’t just arrays of chars. There’s no native isDigit, for example. Otherwise, I’ve been using it with Flutter and have been happy with my experience.

        I’m only posting code when I think I’ve done something interesting or if there’s a notable language feature to show off, but so far, no dice.

    • @swlabr
      link
      English
      41 year ago
      1 a,b:

      as a professional software engineer, I know that googling regex syntax and getting it right will take longer than manually writing string comparisons, so… here’s all you need to see of my final solution.

        int? check3(String line, int index) {
          if (line.length &lt; index + 3) {
            return null;
          }
      
          String sub = line.substring(index, index + 3);
          return sub == "one"
              ? 1
              : sub == "two"
                  ? 2
                  : sub == "six"
                      ? 6
                      : null;
        }
      
    • @swlabr
      link
      English
      31 year ago
      3 a

      I read this wrong initially and thought that you only needed to check adjacency on the same line. Whoops! Then I wrote a bad algorithm that finds numbers THEN searches for symbols. That alg isn’t inherently bad, except…

      3 b

      If I had chosen a symbol first approach, I would not have had as much pain as I did here. Also, I probably under and overthought this one. I went with my first idea, which was guaranteed to work.

      The approach this time was:

      1. iterate through the characters to find a * symbol
      2. Search the characters around it for a digit.
      3. Get the value of the number associated with that digit by searching backwards until you find the start of a number
      4. Use union-find to track whether or not you’ve seen this number before (because you can’t assume that the same value is the same number)

      A simpler approach would consider that you only have two numbers on the same line for the same gear if the character in the gear column is a non-digit; otherwise, if a number is adjacent to a gear, there is only one on that row. Union-find is completely overkill, but I like using it even when I don’t need to.

      Anyway, upon reflecting on this, while the general approach is fine, I didn’t think too hard about the implementation and just ended up with globs of overly memoized spaghetti. I probably should check if Dart has a python-like tuple object or similar. Whatever. Behold!

      void day3s() {
        List lines = [
          for (String? line = stdin.readLineSync();
              line != null;
              line = stdin.readLineSync())
            line
        ];
      
        List> digs = [for (int i = 0; i &lt; lines.length; i++) Map()];
        int? isDigitMem(int r, int c) {
          return digs[r].putIfAbsent(c, () => isDigit(lines[r][c]));
        }
      
        // first entry is parentc, second is size
        List>> uf = List.generate(
            lines.length, (i) => List.generate(lines[0].length, (j) => [j, 1, -1]));
      
        int find(int r, int c) {
          if (uf[r][c][0] != c) {
            uf[r][c][0] = find(r, uf[r][c][0]);
            return uf[r][c][0];
          }
          return uf[r][c][0];
        }
      
        void union(int r, int cp, int c) {
          cp = find(r, cp);
          c = find(r, c);
      
          if (c == cp) {
            return;
          }
      
          if (uf[r][cp][1] >= uf[r][c][1]) {
            uf[r][c][0] = cp;
            uf[r][cp][1] += uf[r][c][1];
          } else {
            uf[r][cp][0] = c;
            uf[r][c][1] += uf[r][cp][1];
          }
        }
      
        int stoi(int row, int col) {
          int acc = 0;
          for (int i = col; i &lt; lines[0].length; i++) {
            int? d = isDigitMem(row, i);
            if (d != null) {
              acc = (acc * 10) + d;
              union(row, col, i);
            } else {
              break;
            }
          }
          return acc;
        }
      
        int? stoiSearch(int row, int col) {
          assert(row >= 0 &amp;&amp; col >= 0 &amp;&amp; row &lt; lines.length &amp;&amp; col &lt; lines[0].length);
          if (isDigitMem(row, col) == null) {
            return null;
          }
          int i = col - 1;
          while (i >= 0) {
            if (isDigitMem(row, i) == null) {
              return stoi(row, i + 1);
            }
            i--;
          }
          return stoi(row, 0);
        }
      
        List> s2i = [for (int i = 0; i &lt; lines.length; i++) Map()];
        int? stoiSearchMem(int row, int col) {
          return s2i[row].putIfAbsent(col, () => stoiSearch(row, col));
        }
      
        int count = 0;
        for (int i = 0; i &lt; lines.length; i++) {
          for (int j = 0; j &lt; lines[0].length; j++) {
            if (lines[i][j] != "*") {
              continue;
            }
      
            List gearVals = List.empty(growable: true);
            for (int x = -1; x &lt;= 1; x++) {
              if (i + x &lt; 0 || i + x > lines.length) {
                continue;
              }
      
              Set parents = {};
              for (int y = -1; y &lt;= 1; y++) {
                if (j + y &lt; 0 || j + y > lines[0].length) {
                  continue;
                }
      
                int? cur = stoiSearchMem(i + x, j + y);
      
                int parent = find(i + x, j + y);
                if (parents.contains(parent)) {
                  continue;
                }
      
                parents.add(parent);
      
                if (cur != null) {
                  gearVals.add(cur);
                }
              }
            }
      
            if (gearVals.length == 2) {
              count += gearVals[0] * gearVals[1];
            }
          }
        }
      
        print(count);
      }
      
      • @swlabr
        link
        English
        3
        edit-2
        1 year ago
        3b redux

        I took out the union find, the code is simpler and more readable now. I also leaned in to using null values, which is gross but whatever, it works.

        void day3s() {
          List lines = [
            for (String? line = stdin.readLineSync();
                line != null;
                line = stdin.readLineSync())
              line
          ];
        
          // lazy processing + memoization
          List> digs = [for (int i = 0; i &lt; lines.length; i++) Map()];
          int? isDigitMem(int r, int c) {
            if (r &lt; 0 || r > lines.length || c &lt; 0 || c > lines[0].length) return null;
            return digs[r].putIfAbsent(c, () => isDigit(lines[r][c]));
          }
        
          int stoi(int row, int col) {
            int acc = 0;
            for (int i = col; i &lt; lines[0].length; i++) {
              int? d = isDigitMem(row, i);
              if (d != null) {
                acc = (acc * 10) + d;
              } else {
                break;
              }
            }
            return acc;
          }
        
          int? stoiSearch(int row, int col) {
            assert(row >= 0 &amp;&amp; col >= 0 &amp;&amp; row &lt; lines.length &amp;&amp; col &lt; lines[0].length);
            if (isDigitMem(row, col) == null) {
              return null;
            }
            int i = col - 1;
            while (i >= 0) {
              if (isDigitMem(row, i) == null) {
                return stoi(row, i + 1);
              }
              i--;
            }
            return stoi(row, 0);
          }
        
          List> s2i = [for (int i = 0; i &lt; lines.length; i++) Map()];
          int? stoiSearchMem(int row, int col) {
            if (row &lt; 0 || row >= lines.length) return null;
            if (col &lt; 0 || col >= lines[0].length) return null;
            return s2i[row].putIfAbsent(col, () => stoiSearch(row, col));
          }
        
          int count = 0;
          for (int i = 0; i &lt; lines.length; i++) {
            for (int j = 0; j &lt; lines[0].length; j++) {
              if (lines[i][j] != "*") {
                continue;
              }
        
              List gearVals = List.empty(growable: true);
              for (int x = -1; x &lt;= 1; x++) {
                int? left = stoiSearchMem(i + x, j - 1);
                int? mid = stoiSearchMem(i + x, j);
                int? right = stoiSearchMem(i + x, j + 1);
        
                if (isDigitMem(i + x, j) == null) {
                  if (left != null) {
                    gearVals.add(left);
                  }
        
                  if (right != null) {
                    gearVals.add(right);
                  }
                } else if (left != null) {
                  gearVals.add(left);
                } else if (mid != null) {
                  gearVals.add(mid);
                } else if (right != null) {
                  gearVals.add(right);
                }
              }
        
              if (gearVals.length == 2) {
                count += gearVals[0] * gearVals[1];
              }
            }
          }
        
          print(count);
        }
        
    • @swlabr
      link
      English
      31 year ago
      4 a

      Not so bad today. I bit the bullet and tried to see if dart has tuples or similar. It does, by the name of “records”. Now instead of pretending I’m writing in C/C++, I can pretend I’m writing in python.

      Anyway, a) is a pretty straightforward job-interview style question, except AoC doesn’t care about efficiency. Still, we all have our own versions of pride, so I did it with a set (Though whether or not dart’s native Set is tree or hash based is not known to me right now).

      code
      int matches(String line) {
        ({List wn, List n}) card = getNumbers(line);
        Set wn = Set.from(card.wn);
      
        return card.n.fold(0, (prev, e) => prev + (wn.contains(e) ? 1 : 0));
      }
      
      void day4a(List lines) {
        print(lines.fold(0, (acc, line) {
          int m = matches(line);
          return acc + (m != 0 ? (1 &lt;&lt; (m - 1)) : 0);
        }));
      }
      
      4b

      b) was a little harder, and definitely a possible trap for overthinking. I think the easiest way to think about solving this is as if it is a dynamic programming problem (though it kinda isn’t).

      So the general approach is to formulate it like this:

      T_n(total cards won by card n) = M_n(total matches for card n) + CW_n(total cards won by the copies that card n wins).

      and

      CW_n =

      • 0 if M_n = 0
      • sum of T_i, where i = n + 1 … n + M_n

      Caching T_n is the DP trick to making this performant (though once again, it does not need to be)

      Anyway, the above approach is the top-down version of the DP; the bottom-up version is what I actually started with in my head. I gave up on that approach because I felt like the logic was too hard for me to figure out.

      code:
      void day4b(List lines) {
        List totalMatches = lines.map((e) => matches(e)).toList();
      
        // total copies won, including copies won from copies.
        List cachedWins = List.filled(totalMatches.length, -1);
        int totalWins(int i) {
          // return cached result if it exists
          if (cachedWins[i] > 0) {
            return cachedWins[i];
          }
      
          int count = totalMatches[i];
          // count the copies won from the subsequent copied cards
          for (int j = 1; j &lt;= totalMatches[i]; j++) {
            count += totalWins(i + j);
          }
      
          // cache the result
          cachedWins[i] = count;
          return count;
        }
      
        int totalCards = totalMatches.length; // count all the originals
        // count all the wins
        for (int i = 0; i &lt; totalMatches.length; i++) {
          totalCards += totalWins(i);
        }
        print(totalCards);
      }
      
    • @swlabr
      link
      English
      3
      edit-2
      1 year ago
      2 a,b:

      This one is just a test of whether or not your language lets you split strings.

      Only novel thing I did here was recognise that red, green and blue end in different letters, so no need to string match the whole world, just check the last letter of the colour.

    • @swlabr
      link
      English
      21 year ago
      1. Not my best work. No code in this comment, just check 5.dart if you want to see it in the github repo linked above.
      General

      I used a class this time because it looked like it might be helpful. I don’t think it turned out to be that useful. Still, you can see Dart’s interesting constructor and getter syntax on display.

      a.

      Pretty straightforward, though I didn’t read the format correctly and had the destination/source data reversed. Oops! Luckily, my performance here will in no way affect my future career.

      b.

      I didn’t read the prompt correctly, which tripped me up. Also, while my solution is correct, it assumes that the input could be trickier than what the problem threw at me. Specifically, the edge case I had in mind was a range of values split into many subintervals and needing to track those mappings. I threw in some print statements to discover that intervals were never split beyond two subintervals, which was disappointing. Oh well- being correct is the best feeling you can have if you are otherwise empty inside.

      Other than processing the input in the form of intervals, I don’t think there were any notable tricks at play here, so this was more of an exercise in implementing code cleanly, which I struggle with.

    • @swlabr
      link
      English
      2
      edit-2
      1 year ago
      6 a,b

      Very easy today. You don’t need any programming to solve this; it’s a series of inequalities. That said, the brute force calculation is fast enough if you don’t want to think and is quite honestly faster than solving this mathematically.

      So that being said, here’s the mathematic solution:

      The inequality to solve is just: x = time holding the button

      x^2 - tx + d < 0

      which occurs when x is between (t/2) +/- (t^2 - 4d). The total ways are the total integers between those two numbers, exclusive.

      Writing that all in code is a little tricky thanks to int/double rounding/truncation intricacies, so the brute force solution is “better”.

    • @swlabr
      link
      English
      21 year ago

      7 Camel Cards

      a, b

      I decided to write some classes and enums for this, which paid off a little in part b) when I could reuse most of my code.

    • @swlabr
      link
      English
      1
      edit-2
      1 year ago

      8

      Hint for b

      The brute solution will take ~100 hours on my machine. You will need (to fudge) some very basic number theory to make it faster.

      a

      A straightforward implementation of the traversal was sufficient for performant code.

      b

      As suggested by the hint, I tried running the brute force solution. The pseudocode is something like this:

      count = 0
      while(all ghosts not on endpoint):
         for (all ghosts):
          move ghost to next node
        count++
      
      print count
      

      I put a timestamp for every 100mil iterations, which ticked once every two seconds.

      So, how do we solve it? As mentioned in my hint, some fudged number theory is required.

      Long story short, each ghost will eventually reach an end node. They could reach K endpoints, where K is the total number of end nodes available. They will follow the same path in a loop if they traverse infinitely.

      The fudge is this: assume each ghost only hits one end node repeatedly. In this case, the solution is just the LCM of the number of steps it takes for each ghost to reach its end node from the initial state.

      If given a case where a ghost hits multiple unique endpoints, you can probably find the configuration of counts and LCMs to yield the smallest one, but that proof is left to the reader.

      The answer that I got was in the magnitude of 10 trillion, close to 20 trillion.

    • @swlabr
      link
      English
      1
      edit-2
      1 year ago

      9

      a,b

      This was another implementation exercise, i.e., can you implement this algorithm as specified? So pretty easy. a) took me about 30 minutes or so to code up, b) took like a minute after that since the problem is so similar.

      Interestingly, the problem itself is based on a method for finding closed-form general formulae for progressions of integers. You can use it to develop a formula for sums of squares, cubes, quartics etc. or any progression that doesn’t seem to have an obvious closed form.

      Anyway, there is probably a language where this problem can be solved with a one-liner, I got kinda close, see 9.dart. Check the commits if it’s unreadable.

    • @zogwarg
      link
      English
      4
      edit-2
      1 year ago

      I liked the slight trickiness of part 2, that the naive implementation would never complete in time.

      As always doing a JQ implementation:

      Part 1
      #!/usr/bin/env jq -n -R -f
      
      # Get seeds
      input | [ match("\\d+"; "g").string | tonumber ] as $seeds |
      
      # Collect maps
      reduce inputs as $line ({};
        if $line == "" then
          .
        elif $line | test(":") then
          .k = ( $line / " " | .[0] )
        else
          .[.k] += [[ $line | match("\\d+"; "g").string | tonumber ]]
        end
      )
      
      # For each map, apply transformation to all seeds.
      # seed -> ... -> location
      | reduce ( to_entries[] | select(.key != "k") .value) as $map ({s:$seeds};
        .s[] |= (
          # Only attempt transform if element is in one of the ranges
          [ . as $e | $map[] | select(. as  [$d,$s,$l] | $e >= $s and $e$s + $l) ] as $range |
          if ($range | length ) > 0 then
            $range[0] as [$d,$s] |
            . - $s + $d
          else
            .
          end
        )
      )
      
      # Get lowest location
      | .s | min
      

      Some comments:

      • A nice use of input first to get the seeds, then inputs to get remaining lines.
      Part 2
      #!/usr/bin/env jq -n -R -f
      
      # Utility function
      def group_of($n):
        ( length / $n ) as $l |
        . as $arr |
        range($l) | $arr[.*$n:.*$n+$n]
      ;
      
      # Get all seed ranges
      input | [ match("\\d+"; "g").string | tonumber ] | [group_of(2)] as $seeds |
      
      # Collect maps
      reduce inputs as $line ({};
        if $line == "" then
          .
        elif $line | test(":") then
          .k = ( $line / " " | .[0] )
        else
          .[.k] += [[ $line | match("\\d+"; "g").string | tonumber ]]
        end
      )
      
      # For each map, apply transformation to all seeds ranges.
      # Producing new seed ranges if applicable
      # seed -> ... -> location
      | reduce (to_entries[] | select(.key != "k") .value) as $map ({s:$seeds};
        .s |= [
          # Only attempt transform if seed range and map range instersect
          .[] | [.[0], add, .[1] ] as [$ea, $eb, $el] | [
            $map[] | select(.[1:] | [.[0], add ] as [$sa,$sb] |
              ( $ea >= $sa and $ea$sb ) or
              ( $eb >= $sa and $eb$sb ) or
              ( $sa >= $ea and $sa$eb )
            )
          ] as $range |
          if $range | length > 0 then
            $range[0] as [$d,$s,$l] |
            # ( only end ) inside map range
            if $ea$s and $eb$s + $l then
              [$ea, $s - $ea], [$d, $eb - $s ]
            # ( both start, end ) outside map range
            elif $ea$s then
              [$ea, $s - $ea], [$d, $l], [ $s + $l, $eb ]
            # ( only start ) inside map range
            elif $eb$s + $l then
              [$ea + $d - $s, $l - $ea + $s ], [$s + $l, $eb - $s - $l]
            # ( both start, end ) inside map range
            else
              [$ea + $d - $s , $el]
            end
          else
            .
          end
        ]
      )
      
      # Get lowest location
      | [.s[][0]] | min
      

      Some comments:

      • Since iterating across all seeds naively would take forever, iterating over seed ranges instead.
      • It’s nice that JQ can neatly produce extra elements: [1,2,3] | [ .[] | if . == 2 then . * 10 + 1 , . * 10 + 2 else . end ] -> [1, 21, 22, 3]
      • There is probably a more compact way of expressing all the conditions and produced outputs.

      Replaced less-than (and greater-than for symmetry) symbols with full-width version, since lemmy apparently doesn’t handle them well within a code block: replacing less than with &lt;

      • @geriksonOP
        link
        English
        31 year ago

        Part 2 is a classic AoC move, where suddenly the problem space becomes much larger.

      • @swlabr
        link
        English
        21 year ago

        JQ looks like magic. So short! So clean! What’s the catch?

        • @zogwarg
          link
          English
          31 year ago

          The main catch is it would often be faster to use a “real” programming langage ^^, both in writing the code, and in execution time for some loop heavy examples: equivalent code that completes say in 1 second in python, completing in 1 minute in jq. Also missing a way to call native libraries, to do stuff like say “md5” (relevant) in past years advents-of-code.

          That being said i like the general “pipe”, map-reduce feel of the language. Like bash one-liners It can make for very terse implementations. I like to add comments, and indentation to make it readable though.

          • @swlabr
            link
            English
            11 year ago

            Thanks for the insight!