this post was submitted on 02 Dec 2024
8 points (100.0% liked)

NotAwfulTech

6 readers
5 users here now

a community for posting cool tech news you don’t want to sneer at

non-awfulness of tech is not required or else we wouldn’t have any posts

founded 1 year ago
MODERATORS
 

copy pasting the rules from last year's thread:

Rules: no spoilers.

The other rules are made up aswe go along.

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

top 21 comments
sorted by: hot top controversial new old
[–] swlabr@awful.systems 2 points 8 hours ago (1 children)

4:

4-1I tried something clever and was punished for my hubris, but it turned out ok.

I treated the input as a list of strings and searched for "XMAS" and "SAMX", rotating and transposing the list to scan for vertical and diagonal words.

In my arrogance, I thought I could do the diagonal rotation easily, but I was very wrong. I got it out in the end, though.

4-2this was easier than 4-1. An O(n^2^) solution just scanning for X-MAS was good enough. Maybe there was a more clever solution that used, i dunno, string hashing or something but whatever.

[–] gerikson@awful.systems 2 points 5 hours ago (1 children)

re: 4-2

is it really n^2 tho? You have to do a constant check around each element, but that does not increase with the number of elements. And you can optimize a bit by marking already seen 'A's as illegal states and don't have to check them when the next row is processed.

[–] swlabr@awful.systems 2 points 5 hours ago

i am a simple manI see square input, i say n^2^

[–] gerikson@awful.systems 4 points 10 hours ago* (last edited 10 hours ago) (1 children)

Day 4 - Ceres Search

discussion

There's probably a smarter way to do this...

For part 1, I dumped everything into a matrix. Then I scanned it element by element. If I found an X, I searched in 8 directions from there and counted up if I found M A S in sequence.

For part 2 I searched for an A, checked each diagonal corner, and counted up if the opposites were M S or S M

https://github.com/gustafe/aoc2024/blob/main/d04-Ceres-Search.pl

[–] Architeuthis@awful.systems 2 points 8 hours ago* (last edited 7 hours ago)

discussionSame, except in 4-1 I used a recursive function to traverse each direction according to the offset decided by the selected direction (like SW is row++,col--) , due to functional programming induced brain damage.

Would have been pretty useful too if 4-2 turned out to be about finding longer patterns, instead of smaller and in half the directions.

4-1Inlined some stuff to fit everything in one function:

let rec isXmas (row:int) (col:int) (dir:int) (depth:int) (arr: char array2d) : bool =
    let value = arr.[row,col]
    if depth = 3
    then value = 'S'
    else if  [|'X';'M';'A';'S'|].[depth] = value
    then
        let (nextRow, nextCol) =
            match dir with
            | 1 -> row + 1, col - 1
            | 2 -> row + 1, col
            | 3 -> row + 1, col + 1
            | 4 -> row, col - 1
            | 6 -> row, col + 1
            | 7 -> row - 1, col - 1
            | 8 -> row - 1, col
            | 9 -> row - 1, col + 1
            | _ -> failwith $"{dir} isn't a numpad direction." 

        let rowCount = arr |> Array2D.length1
        let colCount = arr |> Array2D.length2
       
        if nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount
        then isXmas nextRow nextCol dir (depth+1) arr
        else false
    else false

Then you run this for every appropriately pruned 'X' times every direction and count the trues.

[–] sailor_sega_saturn@awful.systems 2 points 17 hours ago* (last edited 17 hours ago)

I would do day 3 today except

spoilerI'd stubbornly insist on using SIMD instructions to scan for the keyword now that I've thought of that. Even though this doesn't make any sense. And I'm not ready to dive into all that today.

Maybe this weekend or if I can't sleep again or if I get especially bored at work.

[–] mii@awful.systems 3 points 22 hours ago

Advent of Code is one of these things I wanna do every year and then I end up in fucking end-of-the-year crunch time every December and work for 10-12 hours and really don't wanna code after work anymore.

But hey, here's a quick solution for day 1. Let's see how far I make it.

Day 1

use strict;
use List::Util qw( min max );

open(FH, '<', $ARGV[0]) or die $!;

my @left;
my @right;

while () {
	my @nums = split /\s+/, $_;
	push(@left, $nums[0]);
	push(@right, $nums[1]);
}

@left = sort { $b <=> $a } @left;
@right = sort { $b <=> $a } @right;

my $dist = 0;
my $sim = 0;
my $i = 0;

foreach my $lnum (@left) {
	$sim += $lnum * grep { $_ == $lnum } @right;

	my $rnum = $right[$i++];
	$dist += max($lnum, $rnum) - min($lnum, $rnum);
}

print 'Part 1: ', $dist, "\n";
print 'Part 2: ', $sim, "\n";

close(FH);

[–] Architeuthis@awful.systems 4 points 1 day ago* (last edited 8 hours ago)

Got stuck forever on 2-2 because of an edge case that only showed up in 7/1000 reports, ended up just brute forcing it, just ran the fitness function after removing one element at a time sequentially.

Then solved 3.x in like minutes because I could be worse at regex, posting code mostly because no-one else posted F# yet.

edited to fix spoiler header formatting

3-2 in F#

"./input.actual"
|> System.IO.File.ReadAllText
|> fun source -> 
    System.Text.RegularExpressions.Regex.Matches(source, @"don't\(\)|do\(\)|mul\((\d+),(\d+)\)")
    |> Seq.fold
        (fun (acc, enabled) m ->
            match m.Value with
            | "don't()" -> acc, false
            | "do()" -> acc, true
            | mul when enabled && mul.StartsWith("mul") ->
                let (x, y) = int m.Groups.[1].Value, int m.Groups.[2].Value
                acc + x * y, enabled
            | _ -> acc, enabled ) 
        (0, true)
    |> fst
|> printfn "The sum of all valid multiplications with respect to do() and don't() is %A"

commentsNot much to say, the regex grabs all relevant strings and the folding function propagates a flag that flips according to do/don't and an accumulator that is increased when a mul() is encountered and parsed.

[–] gerikson@awful.systems 4 points 1 day ago (2 children)

Day 3

3-2

I expect much wailing and gnashing of teeth regarding the parsing, which of course is utterly trivial if you know a bit if regex.

I got bit by the input being more than one line. Embarrasing.

I wonder if any input starts with a "don't()" or if it's too early for Erik to pull such trickery.

[–] autumnal@awful.systems 2 points 1 day ago

InputOne of the lines of my input had a don't() first, but I got bit by it being more lines as well.

[–] swlabr@awful.systems 3 points 1 day ago

same

I got bit by the input being more than one line. Embarrasing.

[–] swlabr@awful.systems 3 points 1 day ago* (last edited 1 day ago)

For 3: I made dart one-liners for both. Pasting the juicy parts.

3:1RegExp(r"mul\((\d*),(\d*)\)").allMatches(input).fold( 0, (p, e) => p + e.groups([1, 2]).fold(1, (p, f) => p * int.parse(f!))));

3:2My original solution found do, don't and mul entries, then stepped through them to get the solve. I decided to try regex my way through it. What I realised was that you want to ignore strings starting with don't() and ending at the first do(). Some amount of trial and error later, I figured out the (ecma*) regex to do it, which I am proud of:

RegExp(r"(?:don\'t\(\)(?:.(?( 0, (p, e) => p + (e.group(0)![0] != 'd' ? e.groups([1, 2]).fold(1, (p, f) => p * int.parse(f!)) : 0))

*ecma balls

[–] zogwarg@awful.systems 3 points 1 day ago

Day 3 well suited to JQ

Part 2#!/usr/bin/env jq -n -R -f

reduce (
  inputs |   scan("do\\(\\)|don't\\(\\)|mul\\(\\d+,\\d+\\)")
         | [[scan("(do(n't)?)")[0]], [ scan("\\d+") | tonumber]]
) as [[$do], [$a,$b]] (
  { do: true, s: 0 };
    if $do == "do" then .do = true
  elif $do         then .do = false
  elif .do         then .s = .s + $a * $b end
) | .s

[–] gerikson@awful.systems 4 points 2 days ago

It's that time of the year again. Last year was tough for me, i got laid off in the middle of dec and it kinda killed the vibe. I'll see how long I keep up this year. My historical backlog is growing but I've made peace with it.

[–] sailor_sega_saturn@awful.systems 5 points 2 days ago (1 children)

I can't sleep, so here's 1-1 and 1-2, unfortunately I couldn't think of any silly solutions this time, so it's straightforward instead:

spoiler

#include 
#include 
#include 
#include 
#include 
#include 

int main() {
  std::multiset l, r;
  int a, b;
  while (std::cin >> a >> b) {
    l.insert(a); r.insert(b);
  }
  std::vector delta;
  std::transform(l.begin(), l.end(), r.begin(), std::back_inserter(delta),
    [](int x, int y) { return std::abs(x-y); }
  );
  std::cout << std::accumulate(delta.begin(), delta.end(), 0) << std::endl;
}

spoiler

#include 
#include 
#include 

int main() {
  std::multiset l, r;
  int a, b;
  while (std::cin >> a >> b) {
    l.insert(a); r.insert(b);
  }
  std::cout << std::accumulate(l.begin(), l.end(), 0, [&r](int acc, int x) {
    return acc + x * r.count(x);
  }) << std::endl;
}

[–] sailor_sega_saturn@awful.systems 5 points 2 days ago* (last edited 2 days ago) (1 children)

2-1: I have quickly run out of hecks to give. This is the sort of problem that gives prolog programmers feelings of smug superiority.

spoiler

#include 
#include 
#include 

int main() {
  int safe = 0;
  std::string s;
  while (std::getline(std::cin, s)) {
    std::istringstream iss(s);
    int a, b, c;
    if (!(iss >> a >> b)) {
      safe++; continue;
    }
    if (a == b || std::abs(a-b) > 3) continue;
    bool increasing = b > a;
    while (iss >> c) {
      if (b == c || std::abs(b-c) > 3) goto structuredprogrammingisfornerds;
      switch (increasing) {
        case false:
          if (c < b) { b = c; continue; }
          goto structuredprogrammingisfornerds;
        case true:
          if(c > b) { b = c; continue; }
          goto structuredprogrammingisfornerds;
      }
    }
    safe++;
    structuredprogrammingisfornerds:;
  }
  std::cout << safe << std::endl;
}

As usual the second part has punished me for my cowboy code, so I'll have to take a different more annoying tack (maybe tomorrow). Or you know I could just double down on the haphazard approach...

[–] sailor_sega_saturn@awful.systems 5 points 2 days ago* (last edited 2 days ago) (1 children)

I decided to double down on 2-2, since bad code is one of life's little pleasures. Where we're going we won't need big-oh notation

spoiler

#include 
#include 
#include 
#include 
#include 

template 
bool seemslegit(It begin, It end) {
    if (std::distance(begin, end) == 1) {
      return true;
    }
    int a = *begin++;
    int b = *begin++;
    if (a == b || std::abs(a-b) > 3) return false;;
    bool increasing = b > a;
    while (begin != end) {
      int c = *begin++;
      if (b == c || std::abs(b-c) > 3) return false;;
      switch (increasing) {
        case false:
          if (c < b) { b = c; continue; }
          return false;
        case true:
          if(c > b) { b = c; continue; }
          return false;
      }
    }
    return true;
}

template 
void debug(It begin, It end) {
  bool legit = seemslegit(begin, end);
  while (begin != end) {
    std::cout << *begin++ << " ";
  }
  //std::cout << ": " << std::boolalpha << legit << std::endl;
}

int main() {
  int safe = 0;
  std::string s;
  while (std::getline(std::cin, s)) {
    std::istringstream iss(s);
    std::vector report((std::istream_iterator(iss)),
                            std::istream_iterator());
    debug(report.begin(), report.end());
    if (seemslegit(report.begin(), report.end())) {
      safe++;
      std::cout << "\n\n";
      continue;
    }
    for (int i = 0; i < report.size(); ++i) {
      auto report2 = report;
      auto it = report2.erase(report2.begin()+i);
      debug(report2.begin(), report2.end());
      if (seemslegit(report2.begin(), report2.end())) {
        safe++;
        break;
      }
    }
    std::cout << "\n\n";
 }
  std::cout << safe << std::endl;
}

CommentaryDoing this "efficiently" should be possible. since you only need ~2-ish look-back you should be able to score reports in O(n) time. One complication is you might get the direction wrong, need to consider that erasing one of the first two elements could change the direction. But that requires thinking, and shoving all the permutations into a function with ungodly amounts of copying does not.

[–] swlabr@awful.systems 4 points 2 days ago (1 children)

re: 2-2yeah that’s what I ended up thinking. Just try the brute force and if it’s too slow, maybe I’ll try be smarter about it.

[–] gerikson@awful.systems 5 points 2 days ago (1 children)

re: 2-2

I was convinced that some of the Perl gods in the subreddit would reveal some forgotten lore that solved this in one line but looks like my brute force method of removing one element at a time was the way to go.

[–] sailor_sega_saturn@awful.systems 5 points 1 day ago* (last edited 1 day ago)

I am now less sleep deprived so can say how to do better somewhat sensibly, albeit I cannot completely escape from C++s verbosity:

2-2

  1. Don't worry about the sequences changing direction. Just call the check function both assuming it is increasing and assuming it is decreasing. This is cheap enough because the wrong branch will fail after 3 elements or so.
  2. When encountering an element that fails, you only need to consider removing the previous element, or the current element. If you can get to the next element removing one of those then you can continue on without any real backtracking.

Updated code:

2-2

#include 
#include 
#include 
#include 
#include 

bool valid_pair(const std::vector &arr, int i, int j, bool direction) {
  if (i < 0) return true;
  if (j == arr.size()) return true;
  return    !(arr[i] == arr[j])
         && (direction ? arr[i] < arr[j] : arr[j] < arr[i])
         && (std::abs(arr[j]-arr[i]) <= 3);
}

bool valid(const std::vector &arr, bool direction) {
  int checks = 1;
  for (int i = 1; i < arr.size(); ++i) {
    if (valid_pair(arr, i-1, i, direction)) continue;
    if (checks == 0) return false;
    if (   valid_pair(arr, i-2,  i, direction)
        && valid_pair(arr, i,  i+1, direction)) {
      checks -= 1; i += 1;
    } else if (valid_pair(arr, i-1, i+1, direction)) {
      checks -= 1; i += 1;
    } else return false;
  }
  return true;
}

int main() {
  int safe = 0;
  std::string s;
  while (std::getline(std::cin, s)) {
    std::istringstream iss(s);
    std::vector report((std::istream_iterator(iss)),
                            std::istream_iterator());
    safe += (valid(report, true) || valid(report, false));
  }
  std::cout << safe << std::endl;
}

[–] swlabr@awful.systems 2 points 2 days ago

Ah thanks for reminding me that time progresses and that it is now December.

I have done 1.1 through 2.2 and have nothing interesting to say about them.