Day 4: Ceres Search

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

  • @Hammerheart@programming.dev
    link
    fedilink
    1
    edit-2
    7 months ago

    Part 1:

    with open('input') as data:
        lines = [l.strip() for l in data.readlines()]
    # Remove empty line
    class Result():
        def __init__(self):
            self.count = 0
    
    
    def analyze_lines(lines: list[str]):
        ans.count += get_rights(lines)
        ans.count += get_ups(lines)
        ans.count += get_downs(lines)
        ans.count += get_down_rights(lines)
        ans.count += get_down_lefts(lines)
        ans.count += get_up_lefts(lines)
        ans.count += get_up_rights(lines)
        for line in lines:
            ans.count += get_lefts(line)
    
    
    
    
    def get_ups(lines: list[str]) -> int:
        up_count = 0
        for i_l, line in enumerate(lines):
            result = ""
            if i_l < 3:
                continue
            for i_c, char in enumerate(line):
                if char == "X":
                    result = char
                    result += "".join([lines[i_l - n][i_c] for n in range(1, 4)])
                    if result == "XMAS":
                        up_count += 1
                    else:
                        result = ""
        return up_count
    
    
    def get_downs(lines: list[str]) -> int:
        down_count = 0
        for i_l, l in enumerate(lines):
            result = ""
            for i_c, c in enumerate(l):
                if c == "X":
                    result += c
                    try:
                        result += "".join([lines[i_l + n][i_c] for n in range(1, 4)])
                    except IndexError:
                        result = ""
                        continue
                    finally:
                        if result == "XMAS":
                            down_count += 1
                        result = ""
        return down_count
    
    
            
    def get_lefts(line: str) -> int:
        left_count = 0
        for i, char in enumerate(line):
            if i < 3:
                continue
            elif char == "X" and line[i-1] == "M" and line[i-2] == "A" and line[i-3] == "S":
                left_count += 1
        return left_count
    
    
    def get_rights(lines: list[str]) -> int:
        right_counts = 0
        for l in lines:
            right_counts += l.count("XMAS")
        return right_counts
    
    def get_down_rights(lines: list[str]) -> int:
        down_right_count = 0
        for i_l, l in enumerate(lines):
            result = ""
            for i_c, c in enumerate(l):
                if c == "X":
                    result += c
                    try:
                        result += "".join(
                                [lines[i_l + n][i_c + n] for n in range(1,4)]
                                )
                    except IndexError:
                        result = ""
                        continue
                    finally:
                        if result == "XMAS":
                            down_right_count += 1
                        result = ""
        return down_right_count
    
    def get_down_lefts(lines: list[str]) -> int:
        down_left_count = 0
        for i_l, l in enumerate(lines):
            result = ""
            for i_c, c in enumerate(l):
                if i_c < 3:
                    continue
                if c == "X":
                    result += c
                    try:
                        result += "".join(
                                [lines[i_l + n][i_c - n] for n in range(1,4)]
                                )
                    except IndexError:
                        result = ""
                        continue
                    finally:
                        if result == "XMAS":
                            down_left_count += 1
                        result = ""
        return down_left_count
    
    def get_up_rights(lines: list[str]) -> int:
        up_right_count = 0
        for i_l, l in enumerate(lines):
            result = ""
            if i_l < 3:
                continue
            for i_c, c in enumerate(l):
                if c == "X":
                    result += c
                    try:
                        result += "".join(
                                [lines[i_l - n][i_c + n] for n in range(1,4)]
                                )
                    except IndexError:
                        result = ""
                        continue
                    finally:
                        if result == "XMAS":
                            up_right_count += 1
                        result = ""
        return up_right_count
    
    
    def get_up_lefts(lines: list[str]) -> int:
        up_left_count = 0
        for i_l, l in enumerate(lines):
            result = ""
            if i_l < 3:
                continue
            for i_c, c in enumerate(l):
                if i_c < 3:
                    continue
                if c == "X":
                    result = c
                    try:
                        result += "".join(
                                [lines[i_l - n][i_c - n] for n in range(1,4)]
                                )
                    except IndexError as e:
                        result = ""
                        continue
                    finally:
                        if result == "XMAS":
                            up_left_count += 1
                        result = ""
        return up_left_count
    
    ans = Result()
    analyze_lines(lines)
    print(ans.count)
    

    Part 2:

    with open('input') as data:
        lines = list(filter(lambda x: x != '', [l.strip() for l in data.readlines()]))
        
    xmases = 0
    for i in range(1, len(lines)):
        for j in range(1, len(lines[i])):
            if lines[i][j] == "A":
                try:
                    up_back = lines[i-1][j-1]
                    down_over = lines[i+1][j+1]
                    up_over = lines[i-1][j+1]
                    down_back = lines[i+1][j-1]
                except IndexError:
                    continue
                else:
                    if {up_back, down_over} == set("MS") and {up_over, down_back} == set("MS"):
                        xmases += 1
    
    print(xmases)
    

    I actually found part two A LOT easier than part 1.

  • Amy
    link
    fedilink
    57 months ago

    Haskell

    Popular language this year :)

    I got embarrassingly stuck on this one trying to be clever with list operations. Then I realized I should just use an array…

    import Data.Array.Unboxed (UArray)
    import Data.Array.Unboxed qualified as A
    import Data.Bifunctor
    
    readInput :: String -> UArray (Int, Int) Char
    readInput s =
      let rows = lines s
          n = length rows
       in A.listArray ((1, 1), (n, n)) $ concat rows
    
    s1 `eq` s2 = s1 == s2 || s1 == reverse s2
    
    part1 arr = length $ filter isXmas $ concatMap lines $ A.indices arr
      where
        isXmas ps = all (A.inRange $ A.bounds arr) ps && map (arr A.!) ps `eq` "XMAS"
        lines p = [take 4 $ iterate (bimap (+ di) (+ dj)) p | (di, dj) <- [(1, 0), (0, 1), (1, 1), (1, -1)]]
    
    part2 arr = length $ filter isXmas innerPoints
      where
        innerPoints =
          let ((i1, j1), (i2, j2)) = A.bounds arr
           in [(i, j) | i <- [i1 + 1 .. i2 - 1], j <- [j1 + 1 .. j2 - 1]]
        isXmas p = up p `eq` "MAS" && down p `eq` "MAS"
        up (i, j) = map (arr A.!) [(i + 1, j - 1), (i, j), (i - 1, j + 1)]
        down (i, j) = map (arr A.!) [(i - 1, j - 1), (i, j), (i + 1, j + 1)]
    
    main = do
      input <- readInput <$> readFile "input04"
      print $ part1 input
      print $ part2 input
    
  • janAkali
    link
    fedilink
    English
    4
    edit-2
    7 months ago

    Nim

    Could be done more elegantly, but I haven’t bothered yet.

    proc solve(input: string): AOCSolution[int, int] =
      var lines = input.splitLines()
    
      block p1:
        # horiz
        for line in lines:
          for i in 0..line.high-3:
            if line[i..i+3] in ["XMAS", "SAMX"]:
              inc result.part1
    
        for y in 0..lines.high-3:
          #vert
          for x in 0..lines[0].high:
            let word = collect(for y in y..y+3: lines[y][x])
            if word in [@"XMAS", @"SAMX"]:
              inc result.part1
    
          #diag \
          for x in 0..lines[0].high-3:
            let word = collect(for d in 0..3: lines[y+d][x+d])
            if word in [@"XMAS", @"SAMX"]:
              inc result.part1
    
          #diag /
          for x in 3..lines[0].high:
            let word = collect(for d in 0..3: lines[y+d][x-d])
            if word in [@"XMAS", @"SAMX"]:
              inc result.part1
    
      block p2:
        for y in 0..lines.high-2:
          for x in 0..lines[0].high-2:
            let diagNW = collect(for d in 0..2: lines[y+d][x+d])
            let diagNE = collect(for d in 0..2: lines[y+d][x+2-d])
            if diagNW in [@"MAS", @"SAM"] and diagNE in [@"MAS", @"SAM"]:
              inc result.part2
    

    Codeberg repo

  • @hades@lemm.ee
    link
    fedilink
    27 months ago

    C#

    public class Day04 : Solver
    {
      private int width, height;
      private char[,] data;
    
      public void Presolve(string input) {
        var lines = input.Trim().Split("\n").ToList();
        height = lines.Count;
        width = lines[0].Length;
        data = new char[height, width];
        for (int i = 0; i < height; i++) {
          for (int j = 0; j < width; j++) {
            data[i, j] = lines[i][j];
          }
        }
      }
    
      private static readonly string word = "XMAS";
    
      public string SolveFirst()
      {
        int counter = 0;
        for (int start_i = 0; start_i < height; start_i++) {
          for (int start_j = 0; start_j < width; start_j++) {
            if (data[start_i, start_j] != word[0]) continue;
            for (int di = -1; di <= 1; di++) {
              for (int dj = -1; dj <= 1; dj++) {
                if (di == 0 && dj == 0) continue;
                int end_i = start_i + di * (word.Length - 1);
                int end_j = start_j + dj * (word.Length - 1);
                if (end_i < 0 || end_j < 0 || end_i >= height || end_j >= width) continue;
                for (int k = 1; k < word.Length; k++) {
                  if (data[start_i + di * k, start_j + dj * k] != word[k]) break;
                  if (k == word.Length - 1) counter++;
                }
              }
            }
          }
        }
        return counter.ToString();
      }
    
      public string SolveSecond()
      {
        int counter = 0;
        for (int start_i = 1; start_i < height - 1; start_i++) {
          for (int start_j = 1; start_j < width - 1; start_j++) {
            if (data[start_i, start_j] != 'A') continue;
            int even_mas_starts = 0;
            for (int di = -1; di <= 1; di++) {
              for (int dj = -1; dj <= 1; dj++) {
                if (di == 0 && dj == 0) continue;
                if ((di + dj) % 2 != 0) continue;
                if (data[start_i + di, start_j + dj] != 'M') continue;
                if (data[start_i - di, start_j - dj] != 'S') continue;
                even_mas_starts++;
              }
            }
            if (even_mas_starts == 2) counter++;
          }
        }
        return counter.ToString();
      }
    }
    
  • Ananace
    link
    fedilink
    17 months ago

    I tried to think of some clever LINQ to do this one, but was blanking entirely.

    So naïve search it is.

    C#
    string wordsearch = "";
    int width;
    int height;
    
    public void Input(IEnumerable<string> lines)
    {
      wordsearch = string.Join("", lines);
      height = lines.Count();
      width = lines.First().Length;
    }
    
    public void Part1()
    {
      int words = 0;
      for (int y = 0; y < height; y++)
        for (int x = 0; x < width; x++)
          words += SearchFrom(x, y);
    
      Console.WriteLine($"Words: {words}");
    }
    public void Part2()
    {
      int words = 0;
      for (int y = 1; y < height - 1; y++)
        for (int x = 1; x < width - 1; x++)
          words += SearchCross(x, y);
    
      Console.WriteLine($"Crosses: {words}");
    }
    
    public int SearchFrom(int x, int y)
    {
      char at = wordsearch[y * width + x];
      if (at != 'X')
        return 0;
    
      int words = 0;
      for (int ydir = -1; ydir <= 1; ++ydir)
        for (int xdir = -1; xdir <= 1; ++xdir)
        {
          if (xdir == 0 && ydir == 0)
            continue;
    
          if (SearchWord(x, y, xdir, ydir))
            words++;
        }
    
      return words;
    }
    
    private readonly string word = "XMAS";
    public bool SearchWord(int x, int y, int xdir, int ydir)
    {
      int wordit = 0;
      while (true)
      {
        char at = wordsearch[y * width + x];
        if (at != word[wordit])
          return false;
    
        if (wordit == word.Length - 1)
          return true;
    
        wordit++;
    
        x += xdir;
        y += ydir;
    
        if (x < 0 || y < 0 || x >= width || y >= height)
          return false;
      }
    }
    
    public int SearchCross(int x, int y)
    {
      if (x == 0 || y == 0 || x == width - 1 || y == width - 1)
        return 0;
    
      char at = wordsearch[y * width + x];
      if (at != 'A')
        return 0;
    
      int found = 0;
      for (int ydir = -1; ydir <= 1; ++ydir)
        for (int xdir = -1; xdir <= 1; ++xdir)
        {
          if (xdir == 0 || ydir == 0)
            continue;
    
          if (wordsearch[(y + ydir) * width + (x + xdir)] != 'M')
            continue;
          if (wordsearch[(y - ydir) * width + (x - xdir)] != 'S')
            continue;
    
          found++;
        }
    
      if (found == 2)
        return 1;
    
      return 0;
    }
    
    • @CameronDev@programming.devOPM
      link
      fedilink
      17 months ago

      I haven’t quite started yet, and this one does feel like a busy work kinda problem. I was wondering if I could write something to rotate the board and do the search, but I think that might be not worth the effort

  • @hosaka@programming.dev
    link
    fedilink
    17 months ago

    Zig

    const std = @import("std");
    const List = std.ArrayList;
    
    const tokenizeScalar = std.mem.tokenizeScalar;
    const parseInt = std.fmt.parseInt;
    const print = std.debug.print;
    const eql = std.mem.eql;
    
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const alloc = gpa.allocator();
    
    const Point = struct {
        x: isize,
        y: isize,
        fn add(self: *const Point, point: *const Point) Point {
            return Point{ .x = self.x + point.x, .y = self.y + point.y };
        }
    };
    
    // note: i have no idea how to use this or if it's even possible
    // const DirectionType = enum(u8) { Up, Down, Left, Right, UpLeft, UpRight, DownLeft, DownRight };
    // const Direction = union(DirectionType) {
    //     up: Point = .{ .x = 0, .y = 0 },
    // };
    
    const AllDirections = [_]Point{
        .{ .x = 0, .y = -1 }, // up
        .{ .x = 0, .y = 1 }, // down
        .{ .x = -1, .y = 0 }, // left
        .{ .x = 1, .y = 0 }, // right
        .{ .x = -1, .y = -1 }, // up left
        .{ .x = 1, .y = -1 }, // up right
        .{ .x = -1, .y = 1 }, // down left
        .{ .x = 1, .y = 1 }, // down right
    };
    
    const Answer = struct {
        xmas: u32,
        mas: u32,
    };
    
    pub fn searchXmas(letters: List([]const u8), search_char: u8, position: Point, direction: Point) u32 {
        const current_char = getChar(letters, position);
        if (current_char == search_char) {
            const next = position.add(&direction);
            if (current_char == 'M') {
                return searchXmas(letters, 'A', next, direction);
            } else if (current_char == 'A') {
                return searchXmas(letters, 'S', next, direction);
            } else if (current_char == 'S') {
                return 1; // found all letters
            }
        }
        return 0;
    }
    
    pub fn countXmas(letters: List([]const u8), starts: List(Point)) u32 {
        var counter: u32 = 0;
        for (starts.items) |start| {
            for (AllDirections) |direction| {
                const next = start.add(&direction);
                counter += searchXmas(letters, 'M', next, direction);
            }
        }
        return counter;
    }
    
    pub fn countMas(letters: List([]const u8), starts: List(Point)) u32 {
        var counter: u32 = 0;
        for (starts.items) |start| {
            const a_char = getChar(letters, start) orelse continue;
            const top_left_char = getChar(letters, start.add(&AllDirections[4])) orelse continue;
            const down_right_char = getChar(letters, start.add(&AllDirections[7])) orelse continue;
            const top_right_char = getChar(letters, start.add(&AllDirections[5])) orelse continue;
            const down_left_char = getChar(letters, start.add(&AllDirections[6])) orelse continue;
    
            const tldr = [3]u8{ top_left_char, a_char, down_right_char };
            const trdl = [3]u8{ top_right_char, a_char, down_left_char };
            if ((eql(u8, &tldr, "MAS") or eql(u8, &tldr, "SAM")) and (eql(u8, &trdl, "MAS") or eql(u8, &trdl, "SAM"))) {
                counter += 1;
            }
        }
        return counter;
    }
    
    pub fn getChar(letters: List([]const u8), point: Point) ?u8 {
        if (0 > point.x or point.x >= letters.items.len) {
            return null;
        }
        const row = @as(usize, @intCast(point.x));
    
        if (0 > point.y or point.y >= letters.items[row].len) {
            return null;
        }
        const col = @as(usize, @intCast(point.y));
        return letters.items[row][col];
    }
    
    pub fn solve(input: []const u8) !Answer {
        var rows = tokenizeScalar(u8, input, '\n');
    
        var letters = List([]const u8).init(alloc);
        defer letters.deinit();
        var x_starts = List(Point).init(alloc);
        defer x_starts.deinit();
        var a_starts = List(Point).init(alloc);
        defer a_starts.deinit();
    
        var x: usize = 0;
        while (rows.next()) |row| {
            try letters.append(row);
            for (row, 0..) |letter, y| {
                if (letter == 'X') {
                    try x_starts.append(.{ .x = @intCast(x), .y = @intCast(y) });
                } else if (letter == 'A') {
                    try a_starts.append(.{ .x = @intCast(x), .y = @intCast(y) });
                }
            }
            x += 1;
        }
    
        // PART 1
        const xmas = countXmas(letters, x_starts);
    
        // PART 2
        const mas = countMas(letters, a_starts);
    
        return Answer{ .xmas = xmas, .mas = mas };
    }
    
    pub fn main() !void {
        const answer = try solve(@embedFile("input.txt"));
        print("Part 1: {d}\n", .{answer.xmas});
        print("Part 2: {d}\n", .{answer.mas});
    }
    
    test "test input" {
        const answer = try solve(@embedFile("test.txt"));
        try std.testing.expectEqual(18, answer.xmas);
    }
    
    
  • @wer2@lemm.ee
    link
    fedilink
    17 months ago

    Lisp

    Not super happy with the code, but it got the job done.

    Part 1 and 2
    (defun p1-process-line (line)
      (to-symbols line))
    
    (defun found-word-h (word data i j)
      "checks for a word existing from the point horizontally to the right"
      (loop for j2 from j 
            for w in word
            when (not (eql w (aref data i j2)))
              return nil
            finally (return t)))
    
    (defun found-word-v (word data i j)
      "checks for a word existing from the point vertically down"
      (loop for i2 from i 
            for w in word
            when (not (eql w (aref data i2 j)))
              return nil
            finally (return t)))
    
    (defun found-word-d-l (word data i j)
      "checks for a word existsing from the point diagonally to the left and down"
      (destructuring-bind (n m) (array-dimensions data)
        (declare (ignorable n))
        
        (and (>= (- i (length word)) -1)
             (>= m (+ j  (length word)))
             (loop for i2 from i downto 0
                   for j2 from j
                   for w in word
                   when (not (eql w (aref data i2 j2)))
                     return nil
                   finally  (return t)))))
    
    (defun found-word-d-r (word data i j)
      "checks for a word existing from the point diagonally to the right and down"
      (destructuring-bind (n m) (array-dimensions data)
        (and (>= n (+ i (length word)))
             (>= m (+ j  (length word)))
             (loop for i2 from i
                   for j2 from j
                   for w in word
                   when (not (eql w (aref data i2 j2)))
                     return nil
                   finally  (return t)))
        ))
    
    (defun count-word-h (data word)
      "Counts horizontal matches of the word"
      (let ((word-r (reverse word))
            (word-l (length word)))
        (destructuring-bind (n m) (array-dimensions data)
          (loop for i from 0 below n 
                sum (loop for j from 0 upto (- m word-l)
                          count (found-word-h word data i j)
                          count (found-word-h word-r data i j))))))
    
    (defun count-word-v (data word)
      "Counts vertical matches of the word"
      (let ((word-r (reverse word))
            (word-l (length word)))
        (destructuring-bind (n m) (array-dimensions data)
          (loop for j from 0 below m 
                sum (loop for i from 0 upto (- n word-l)
                          count (found-word-v word data i j)
                          count (found-word-v word-r data i j))))))
    
    (defun count-word-d (data word)
      "Counts diagonal matches of the word"
      (let ((word-r (reverse word)))
        (destructuring-bind (n m) (array-dimensions data)
          (loop for i from 0 below n
                sum (loop for j from 0 below m
                          count (found-word-d-l word data i j)
                          count (found-word-d-l word-r data i j)
                          count (found-word-d-r word data i j)
                          count (found-word-d-r word-r data i j)
                          )))))
    
    
    (defun run-p1 (file)
      "cares about the word xmas in any direction"
      (let ((word '(X M A S))
            (data (list-to-2d-array (read-file file #'p1-process-line))))
        (+
         (count-word-v data word)
         (count-word-h data word)
         (count-word-d data word))))
    
    
    (defun run-p2 (file) 
      "cares about an x of mas crossed with mas"
      (let ((word '(M A S))
            (word-r '(S A M))
            (data (list-to-2d-array (read-file file #'p1-process-line))))
        (destructuring-bind (n m) (array-dimensions data)
          (loop for i from 0 below (- n 2)
                sum (loop for j from 0 below (- m 2)
                          count (and (found-word-d-r word data i j)
                                     (found-word-d-l word data (+ i 2) j))
                          count (and (found-word-d-r word-r data i j)
                                     (found-word-d-l word data (+ i 2) j))
                          count (and (found-word-d-r word data i j)
                                     (found-word-d-l word-r data (+ i 2) j))
                          count (and (found-word-d-r word-r data i j)
                                     (found-word-d-l word-r data (+ i 2) j))
                            )))))
    
  • @Quant@programming.dev
    link
    fedilink
    27 months ago

    Uiua

    This one was nice. The second part seemed quite daunting at first but wasn’t actually that hard in the end.

    Run with example input here

    Row    ← ⌕ "XMAS"
    RevRow ← ⌕"SAMX"
    Sum    ← /+/+
    Count  ← +∩Sum⊃Row RevRow
    
    PartOne ← (
      &rs ∞ &fo "input-4.txt"
      ⊜∘≠@\n.
      ⊙+⟜∩Count⟜⍉ # horizontal and vertical search
      ⟜(/+⧈(Count⍉≡⬚@ ↻⇡⧻.)4)
      /+⧈(Count⍉≡⬚@ ↻¯⇡⧻.)4
      ++
    )
    
    Mask ← °⊚×2⇡5
    # Create variations of X-MAS
    Vars ← (
      ["M S"
       " A "
       "M S"]
      ≡♭[∩⟜⍉]≡⇌.
      Mask
      ⊏0⊞▽¤
    )
    
    PartTwo ← (
      &rs ∞ &fo "input-4.txt"
      ⊜∘≠@\n.
      ⧈(/+♭⊞≍⊙¤Vars▽Mask♭)3_3
      Sum
    )
    
    &p "Day 4:"
    &pf "Part 1: "
    &p PartOne
    &pf "Part 2: "
    &p PartTwo
    
  • @VegOwOtenks@lemmy.world
    link
    fedilink
    47 months ago

    I struggled a lot more when doing list slices that I would’ve liked to

    Haskell

    
    import Data.List qualified as List
    
    collectDiagonal :: [String] -> Int -> Int -> String
    collectDiagonal c y x
            | length c > y && length (c !! y) > x = c !! y !! x : collectDiagonal c (y+1) (x+1)
            | otherwise = []
    
    part1 c = do
            let forwardXMAS  = map (length . filter (List.isPrefixOf "XMAS") . List.tails) $ c
            let backwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse) $ c
            let downwardXMAS  = map (length . filter (List.isPrefixOf "XMAS") . List.tails ) . List.transpose $ c
            let upwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse ) . List.transpose $ c
            let leftSideDiagonals = map (\ y -> collectDiagonal c y 0) [0..length c]
            let leftTopDiagonals = map (\ x -> collectDiagonal c 0 x) [1..(length . List.head $ c)]
            let leftDiagonals = leftSideDiagonals ++ leftTopDiagonals
            let rightSideDiagonals = map (\ y -> collectDiagonal (map List.reverse c) y 0) [0..length c]
            let rightTopDiagonals = map (\ x -> collectDiagonal (map List.reverse c) 0 x) [1..(length . List.head $ c)]
            let rightDiagonals = rightSideDiagonals ++ rightTopDiagonals
            let diagonals = leftDiagonals ++ rightDiagonals
    
            let diagonalXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails) $ diagonals
            let reverseDiagonalXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse) $ diagonals
    
            print . sum $ [sum forwardXMAS, sum backwardXMAS, sum downwardXMAS, sum upwardXMAS, sum diagonalXMAS, sum reverseDiagonalXMAS]
            return ()
    
    getBlock h w c y x = map (take w . drop x) . take h . drop y $ c
    
    isXBlock b = do
            let diagonal1 = collectDiagonal b 0 0
            let diagonal2 = collectDiagonal (map List.reverse b) 0 0
    
            diagonal1 `elem` ["SAM", "MAS"] && diagonal2 `elem` ["SAM", "MAS"]
    
    part2 c = do
            
            let lineBlocks = List.map (getBlock 3 3 c) [0..length c - 1]
            let groupedBlocks = List.map (flip List.map [0..(length . head $ c) - 1]) lineBlocks
    
            print . sum . map (length . filter isXBlock) $ groupedBlocks
    
            return ()
    
    main = do
            c <- lines <$> getContents
    
            part1 c
            part2 c
    
            return ()
    
  • @Gobbel2000@programming.dev
    link
    fedilink
    17 months ago

    Rust

    One of those with running through tricky grid indices. The vector types from the euclid crate helped in dealing with positions.

    Code
    use euclid::{vec2, default::*};
    
    fn count_xmas(grid: &[&[u8]], pos: (usize, usize)) -> u32 {
        if grid[pos.1][pos.0] != b'X' {
            return 0
        }
    
        let bounds = Rect::new(Point2D::origin(), Size2D::new(grid[0].len() as i32, grid.len() as i32));
        const DIRS: [Vector2D<i32>; 8] = [
            vec2(1, 0), vec2(-1, 0), vec2(0, 1), vec2(0, -1),
            vec2(1, 1), vec2(1, -1), vec2(-1, 1), vec2(-1, -1),
        ];
        let mut count = 0;
        for dir in DIRS {
            let mut cur = Point2D::from(pos).to_i32();
            let mut found = true;
            for letter in [b'M', b'A', b'S'] {
                cur += dir;
                if !bounds.contains(cur) || grid[cur.y as usize][cur.x as usize] != letter {
                    found = false;
                    break
                }
            }
            if found {
                count += 1;
            }
        }
        count
    }
    
    fn part1(input: String) {
        let grid = input.lines().map(|l| l.as_bytes()).collect::<Vec<_>>();    
        let count = (0..grid.len()).map(|y| {
                (0..grid[y].len()).map(|x| count_xmas(&grid, (x, y))).sum::<u32>()
            })
            .sum::<u32>();
        println!("{count}");
    }
    
    fn is_x_mas(grid: &[&[u8]], pos: (usize, usize)) -> bool {
        if grid[pos.1][pos.0] != b'A' {
            return false
        }
    
        const DIRS: [Vector2D<i32>; 4] = [vec2(1, -1), vec2(1, 1), vec2(-1, 1), vec2(-1, -1)];
        let pos = Point2D::from(pos).to_i32();
        (0..4).any(|d| {
            let m_pos = [pos + DIRS[d], pos + DIRS[(d + 1) % 4]]; // 2 adjacent positions of M
            let s_pos = [pos + DIRS[(d + 2) % 4], pos + DIRS[(d + 3) % 4]]; // others S
            m_pos.iter().all(|p| grid[p.y as usize][p.x as usize] == b'M') &&
            s_pos.iter().all(|p| grid[p.y as usize][p.x as usize] == b'S')
        })
    }
    
    fn part2(input: String) {
        let grid = input.lines().map(|l| l.as_bytes()).collect::<Vec<_>>();    
        let count = (1..grid.len() - 1).map(|y| {
                (1..grid[y].len() - 1).filter(|&x| is_x_mas(&grid, (x, y))).count()
            })
            .sum::<usize>();
        println!("{count}");
    }
    
    util::aoc_main!();
    

    (also on github)

  • TunaCowboy
    link
    fedilink
    2
    edit-2
    7 months ago

    python

    solution
    import aoc
    
    def setup():
        return (aoc.get_lines(4, padded=(True, '.', 3)), 0)
    
    def one():
        lines, acc = setup()
        for row, l in enumerate(lines):
            for col, c in enumerate(l):
                if c == 'X':
                    w = l[col - 3:col + 1]
                    e = l[col:col + 4]
                    n = c + lines[row - 1][col] + \
                        lines[row - 2][col] + lines[row - 3][col]
                    s = c + lines[row + 1][col] + \
                        lines[row + 2][col] + lines[row + 3][col]
                    nw = c + lines[row - 1][col - 1] + \
                        lines[row - 2][col - 2] + lines[row - 3][col - 3]
                    ne = c + lines[row - 1][col + 1] + \
                        lines[row - 2][col + 2] + lines[row - 3][col + 3]
                    sw = c + lines[row + 1][col - 1] + \
                        lines[row + 2][col - 2] + lines[row + 3][col - 3]
                    se = c + lines[row + 1][col + 1] + \
                        lines[row + 2][col + 2] + lines[row + 3][col + 3]
                    for word in [w, e, n, s, nw, ne, sw, se]:
                        if word in ['XMAS', 'SAMX']:
                            acc += 1
        print(acc)
    
    def two():
        lines, acc = setup()
        for row, l in enumerate(lines):
            for col, c in enumerate(l):
                if c == 'A':
                    l = lines[row - 1][col - 1] + c + lines[row + 1][col + 1]
                    r = lines[row + 1][col - 1] + c + lines[row - 1][col + 1]
                    if l in ['MAS', 'SAM'] and r in ['MAS', 'SAM']:
                        acc += 1
        print(acc)
    
    one()
    two()
    
  • @sjmulder@lemmy.sdf.org
    link
    fedilink
    27 months ago

    C

    What can I say, bunch of for loops! I add a 3 cell border to avoid having to do bounds checking in the inner loops.

    Code
    #include "common.h"
    #define GZ 146
    
    int main(int argc, char **argv) {
    	static char g[GZ][GZ];
    	static const char w[] = "XMAS";
    	int p1=0,p2=0, x,y, m,i;
    
    	if (argc > 1) DISCARD(freopen(argv[1], "r", stdin));
    	for (y=3; y<GZ && fgets(g[y]+3, GZ-3, stdin); y++) ;
    
    	for (y=3; y<GZ-3; y++)
    	for (x=3; x<GZ-3; x++) {
    		for (m=1,i=0; i<4; i++) {m &= g[y+i][x]==w[i];} p1+=m;
    		for (m=1,i=0; i<4; i++) {m &= g[y-i][x]==w[i];} p1+=m;
    		for (m=1,i=0; i<4; i++) {m &= g[y][x+i]==w[i];} p1+=m;
    		for (m=1,i=0; i<4; i++) {m &= g[y][x-i]==w[i];} p1+=m;
    		for (m=1,i=0; i<4; i++) {m &= g[y+i][x+i]==w[i];} p1+=m;
    		for (m=1,i=0; i<4; i++) {m &= g[y-i][x-i]==w[i];} p1+=m;
    		for (m=1,i=0; i<4; i++) {m &= g[y+i][x-i]==w[i];} p1+=m;
    		for (m=1,i=0; i<4; i++) {m &= g[y-i][x+i]==w[i];} p1+=m;
    
    		p2 += g[y+1][x+1]=='A' &&
    		      ((g[y][x]  =='M' && g[y+2][x+2]=='S')  ||
    		       (g[y][x]  =='S' && g[y+2][x+2]=='M')) &&
    		      ((g[y+2][x]=='M' && g[y][x+2]  =='S')  ||
    		       (g[y+2][x]=='S' && g[y][x+2]  =='M'));
    	}
    
    	printf("04: %d %d\n", p1, p2);
    }
    

    https://github.com/sjmulder/aoc/blob/master/2024/c/day04.c

  • @LeixB@lemmy.world
    link
    fedilink
    3
    edit-2
    7 months ago

    Haskell

    import Control.Arrow
    import Data.Array.Unboxed
    import Data.List
    
    type Pos = (Int, Int)
    type Board = Array Pos Char
    data Dir = N | NE | E | SE | S | SW | W | NW
    
    target = "XMAS"
    
    parse s = listArray ((1, 1), (n, m)) [l !! i !! j | i <- [0 .. n - 1], j <- [0 .. m - 1]]
      where
        l = lines s
        (n, m) = (length $ head l, length l)
    
    move N = first pred
    move S = first succ
    move E = second pred
    move W = second succ
    move NW = move N . move W
    move SW = move S . move W
    move NE = move N . move E
    move SE = move S . move E
    
    check :: Board -> Pos -> Int -> Dir -> Bool
    check b p i d =
        i >= length target
            || ( inRange (bounds b) p
                    && (b ! p) == (target !! i)
                    && check b (move d p) (succ i) d
               )
    
    checkAllDirs :: Board -> Pos -> Int
    checkAllDirs b p = length . filter (check b p 0) $ [N, NE, E, SE, S, SW, W, NW]
    
    check2 :: Board -> Pos -> Bool
    check2 b p =
        all (inRange (bounds b)) moves && ((b ! p) == 'A') && ("SSMM" `elem` rotations)
      where
        rotations = rots $ (b !) <$> moves
        moves = flip move p <$> [NE, SE, SW, NW]
    
        rots xs = init $ zipWith (++) (tails xs) (inits xs)
    
    part1 b = sum $ checkAllDirs b <$> indices b
    part2 b = length . filter (check2 b) $ indices b
    
    main = getContents >>= print . (part1 &&& part2) . parse
    
  • @mykl@lemmy.world
    link
    fedilink
    4
    edit-2
    7 months ago

    Uiua

    Just part1 for now as I need to walk the dog :-)

    [edit] Part 2 now added, and a nicer approach than Part 1 in my opinion, if you’re able to keep that many dimensions straight in your head :-)

    [edit 2] Tightened it up a bit more.

    Grid ← ⊜∘⊸≠@\n "MMMSXXMASM\nMSAMXMSMSA\nAMXSXMAAMM\nMSAMASMSMX\nXMASAMXAMM\nXXAMMXXAMA\nSMSMSASXSS\nSAXAMASAAA\nMAMMMXMMMM\nMXMXAXMASX"
    
    ≡⍉⍉×⇡4¤[1_0 0_1 1_1 1_¯1]         # Use core dirs to build sets of 4-offsets.
    ↯∞_2⇡△ Grid                       # Get all possible starting points.
    &p/+♭⊞(+∩(≍"XMAS")⇌.⬚@.⊡:Grid≡+¤) # Part 1. Join the two into a table, use to pick 4-elements, check, count.
    
    Diags   ← [[¯. 1_1] [¯. 1_¯1]]
    BothMas ← /×≡(+∩(≍"MS")⇌.)⬚@.⊡≡+Diags¤¤ # True if both diags here are MAS.
    &p/+≡BothMas⊚="A"⟜¤Grid                 # Part 2. For all "A"s in grid, check diags, count where good.
    
      • @mykl@lemmy.world
        link
        fedilink
        27 months ago

        The operators have all got ascii names you can type, and the formatter converts them to the symbols. It’s a bit odd but really worthwhile, as you get access to the powerful array handling functionality that made solving today’s challenges so much more straightforward than in other languages.

  • @SteveDinn@lemmy.ca
    link
    fedilink
    English
    17 months ago

    C#

    namespace Day04;
    
    static class Program
    {
        public record struct Point(int Row, int Col);
    
        static void Main(string[] args)
        {
            var sample = File.ReadAllLines("sample.txt");
            var data = File.ReadAllLines("data.txt");
    
            Console.WriteLine($"Part 1 (sample): {SolvePart1(sample)}");
            Console.WriteLine($"Part 1 (data): {SolvePart1(data)}");
    
            Console.WriteLine($"Part 2 (sample): {SolvePart2(sample)}");
            Console.WriteLine($"Part 2 (data): {SolvePart2(data)}");
        }
    
        private static readonly string Search = "XMAS";
    
        private static readonly Func<Point, Point>[] DirectionalMoves =
        {
            p => new Point(p.Row + 1, p.Col),
            p => new Point(p.Row + 1, p.Col + 1),
            p => new Point(p.Row, p.Col + 1),
            p => new Point(p.Row - 1, p.Col + 1),
            p => new Point(p.Row - 1, p.Col),
            p => new Point(p.Row - 1, p.Col - 1),
            p => new Point(p.Row, p.Col - 1),
            p => new Point(p.Row + 1, p.Col - 1),
        };
    
        private static readonly Func<Point, Point>[] ForwardSlashMoves =
        {
            p => new Point(p.Row - 1, p.Col - 1),
            p => new Point(p.Row + 1, p.Col + 1),
        };
        
        private static readonly Func<Point, Point>[] BackSlashMoves =
        {
            p => new Point(p.Row + 1, p.Col - 1),
            p => new Point(p.Row - 1, p.Col + 1),
        };
    
        static long SolvePart1(string[] data)
        {
            return Enumerable
                .Range(0, data.Length)
                .SelectMany(row => Enumerable.Range(0, data[row].Length)
                    .Select(col => new Point(row, col)))
                .Where(p => IsMatch(data, p, Search[0]))
                .Sum(p => DirectionalMoves
                    .Count(move => DeepMatch(data, move(p), move, Search, 1)));
        }
    
        static long SolvePart2(string[] data)
        {
            return Enumerable
                .Range(0, data.Length)
                .SelectMany(row => Enumerable.Range(0, data[row].Length)
                    .Select(col => new Point(row, col)))
                .Where(p => IsMatch(data, p, 'A'))
                .Count(p => CheckDiagonalMoves(data, p, ForwardSlashMoves)
                            && CheckDiagonalMoves(data, p, BackSlashMoves));
        }
    
        static bool CheckDiagonalMoves(string[] data, Point p, Func<Point, Point>[] moves)
            => (IsMatch(data, moves[0](p), 'S') && IsMatch(data, moves[1](p), 'M'))
               || (IsMatch(data, moves[0](p), 'M') && IsMatch(data, moves[1](p), 'S'));
    
        static bool DeepMatch(string[] data, Point p, Func<Point, Point> move, string search, int searchIndex) =>
            (searchIndex >= search.Length) ? true :
            (!IsMatch(data, p, search[searchIndex])) ? false :
            DeepMatch(data, move(p), move, search, searchIndex + 1);
    
        static bool IsMatch(string[] data, Point p, char searchChar)
            => IsInBounds(data, p) && (data[p.Row][p.Col] == searchChar);
    
        static bool IsInBounds(string[] data, Point p) =>
            (p.Row >= 0) && (p.Col >= 0) && (p.Row < data.Length) && (p.Col < data[0].Length);
    }