🌟 Advent of Code (AoC) 2023 🌟

I ← ⊜(⊜⋕≠@\s.)≠@\n.&fras "9.txt"
/+;⍥⊃(↘¯1-:↻1.)(+⊢⇌)-1⧻.:0 /+I
/+;⍥⊃(↘¯1-:↻1.)(+⊢⇌)-1⧻.:0 ⇌/+I

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define HISTORYLEN 21
#define NUMLINES 200

int predict(int l[], int length);
int predict_backwards(int l[], int length);
int zeroes(int list[], int length);
void* parseinput(char* filename);
void readlist(char* str, int* list);

int main()
{
    int (*history)[HISTORYLEN] = parseinput("input");
    int part1 = 0, part2 = 0;
    for (int h=0; h<NUMLINES; ++h) {
        part1 += predict(history[h], HISTORYLEN);
        part2 += predict_backwards(history[h], HISTORYLEN);
    }
    printf("Part 1: %i\nPart 2: %i\n", part1, part2);
    assert(part1 == 1772145754);
    assert(part2 == 867);
}

int predict(int l[], int length)
{
    if (zeroes(l, length))
        return 0;
    int tmp[HISTORYLEN];
    for (int i=0; i<length-1; ++i)
        tmp[i] = l[i+1] - l[i];
    return l[length-1] + predict(tmp, length-1);
}

int predict_backwards(int l[], int length)
{
    if (zeroes(l, length))
        return 0;
    int tmp[HISTORYLEN];
    for (int i=0; i<length-1; ++i)
        tmp[i] = l[i+1] - l[i];
    return l[0] - predict_backwards(tmp, length-1);
}

int zeroes(int list[], int length)
{
    for (int i=0; i<length; ++i)
        if (list[i] != 0)
            return 0;
    return 1;
}

void* parseinput(char* filename)
{
    int (*h)[HISTORYLEN] = calloc(NUMLINES*HISTORYLEN, sizeof (int));
    FILE* fptr = fopen(filename, "r");
    int i = 0;
    char line[220];
    while (fgets(line, sizeof line, fptr)) {
        readlist(line, h[i++]);
    }
    return h;
}

// Read list of numbers from string: "1 2 3" -> {1, 2, 3}
void readlist(char* str, int* list)
{
    int i = 0, num_read;
    while (1) {
        if (sscanf(str, "%i %n", &list[i++], &num_read) != 1)
            break;
        str += num_read;
    }
}

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAZESIZE 150

enum direction { UP, DOWN, LEFT, RIGHT };
char mazechar(char (*maze)[MAZESIZE], int row, int col);
void setfloodchar(char (*flood)[MAZESIZE], int row, int col, char c);
void floodfill(char (*flood)[MAZESIZE], int row, int col, char c);
void* parseinput(char* filename);
void findstart(char (*maze)[MAZESIZE], int* startrow, int* startcol);

// for part 1, just find the starting location and walk
// along the pipes until returning to the starting point.
// Half the final distance will be the furthest point.

// When walking along the pipe, also keep marking the pipe
// locations as well as left and right sides of the path.
// This will help in part 2.
int main()
{
    char (*maze)[MAZESIZE] = parseinput("input");

    // Make a blank copy of the maze for part 2.
    char (*flood)[MAZESIZE] = malloc(MAZESIZE* (MAZESIZE+1) * sizeof (char));
    for (int i=0; i<MAZESIZE; ++i) {
        memset(flood[i], ' ', MAZESIZE);
        flood[i][MAZESIZE-1] = '\0';
    }
    int row, col, distance = 0;
    enum direction dir;
    
    findstart(maze, &row, &col);

    setfloodchar(flood, row, col, 'P'); // Mark as pipe in flood map.
    char at = mazechar(maze, row, col);
    char above = mazechar(maze, row-1, col);
    char below = mazechar(maze, row+1, col);
    char left = mazechar(maze, row, col-1);
    char right = mazechar(maze, row, col+1);
    if (above == '|' || above == 'F' || above == '7') {
        dir = UP;
        --row;
        setfloodchar(flood, row, col, 'P');
    }
    else if (below == '|' || below == 'J' || below == 'L') {
        dir = DOWN;
        ++row;
        setfloodchar(flood, row, col, 'P');
    }
    else if (left == '-' || left == 'F' || left == 'L') {
        dir = LEFT;
        --col;
        setfloodchar(flood, row, col, 'P');
    }
    else if (right == '-' || right == 'J' || right == '7') {
        dir = RIGHT;
        ++col;
        setfloodchar(flood, row, col, 'P');
    }
    do {
        at = mazechar(maze, row, col);
        above = mazechar(maze, row-1, col);
        below = mazechar(maze, row+1, col);
        left = mazechar(maze, row, col-1);
        right = mazechar(maze, row, col+1);
        if (dir==UP && at=='|') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row, col-1, 'L');
            setfloodchar(flood, row, col+1, 'R');
            dir = UP;
            --row;
        }
        else if (dir==LEFT && at=='L') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row+1, col, 'L');
            setfloodchar(flood, row, col-1, 'L');
            dir = UP;
            --row;
        }
        else if (dir==RIGHT && at=='J') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row+1, col, 'R');
            setfloodchar(flood, row, col+1, 'R');
            dir = UP;
            --row;
        }
        else if (dir==DOWN && at=='|') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row, col+1, 'L');
            setfloodchar(flood, row, col-1, 'R');
            dir = DOWN;
            ++row;
        }
        else if (dir==LEFT && at=='F') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row-1, col, 'R');
            setfloodchar(flood, row, col-1, 'R');
            dir = DOWN;
            ++row;
        }
        else if (dir==RIGHT && at=='7') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row-1, col, 'L');
            setfloodchar(flood, row, col+1, 'L');
            dir = DOWN;
            ++row;
        }
        else if (dir==UP && at=='7') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row-1, col, 'R');
            setfloodchar(flood, row, col+1, 'R');
            dir = LEFT;
            --col;
        }
        else if (dir==DOWN && at=='J') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row+1, col, 'L');
            setfloodchar(flood, row, col+1, 'L');
            dir = LEFT;
            --col;
        }
        else if (dir==LEFT && at=='-') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row+1, col, 'L');
            setfloodchar(flood, row-1, col, 'R');
            dir = LEFT;
            --col;
        }
        else if (dir==UP && at=='F') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row-1, col, 'L');
            setfloodchar(flood, row, col-1, 'L');
            dir = RIGHT;
            ++col;
        }
        else if (dir==DOWN && at=='L') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row+1, col, 'R');
            setfloodchar(flood, row, col-1, 'R');
            dir = RIGHT;
            ++col;
        }
        else if (dir==RIGHT && at=='-') {
            setfloodchar(flood, row, col, 'P');
            setfloodchar(flood, row-1, col, 'L');
            setfloodchar(flood, row+1, col, 'R');
            dir = RIGHT;
            ++col;
        }
        ++distance;
    } while (at != 'S');

    // Part 2. For each character that has been marked as R,
    // flood fill around it to cover then entire area between
    // the pipes.
    int p2 = 0;
    for (int i=0; i<MAZESIZE; ++i)
        for (int j=0; j<MAZESIZE-1; ++j)
            if (mazechar(flood, i, j) == 'R') {
                floodfill(flood, i-1, j, 'R');
                floodfill(flood, i+1, j, 'R');
                floodfill(flood, i, j-1, 'R');
                floodfill(flood, i, j+1, 'R');
            }
    // Then count all the Rs.
    for (int i=0; i<MAZESIZE; ++i)
        for (int j=0; j<MAZESIZE-1; ++j)
            if (mazechar(flood, i, j) == 'R')
                ++p2;

    printf("Part 1: %i\nPart 2: %i\n", distance/2, p2);
    assert(distance/2 == 6768);
    assert(p2 == 351);
}

char mazechar(char (*maze)[MAZESIZE], int row, int col)
{
    if (row < 0 || row >= strlen(maze[0]) || col < 0 || col > strlen(maze[0]))
        return '\0';
    return maze[row][col];
}

void setfloodchar(char (*flood)[MAZESIZE], int row, int col, char c)
{
    if (row < 0 || row >= strlen(flood[0]) || col < 0 || col > strlen(flood[0]))
        return;
    if (flood[row][col] != 'P' && flood[row][col] != '\0') // Don't overwrite pipe.
        flood[row][col] = c;
}

void floodfill(char (*flood)[MAZESIZE], int row, int col, char c)
{
    if (row < 0 || row >= strlen(flood[0]) || col < 0 || col > strlen(flood[0]))
        return;
    if (flood[row][col] != ' ')
        return;
    flood[row][col] = c;
    floodfill(flood, row-1, col, c);
    floodfill(flood, row+1, col, c);
    floodfill(flood, row, col-1, c);
    floodfill(flood, row, col+1, c);
}

void* parseinput(char* filename)
{
    char (*maze)[MAZESIZE] = calloc(MAZESIZE*(MAZESIZE+1), sizeof (char));
    FILE* fptr = fopen(filename, "r");
    int i = 0;
    while (fgets(maze[i++], MAZESIZE+1, fptr))
        ;
    return maze;
}

// Find starting point.
void findstart(char (*maze)[MAZESIZE], int* startrow, int* startcol)
{
    char* cpt;
    for (int l=0; l<MAZESIZE; ++l) {
        if (cpt = strchr(maze[l], 'S')) {
            *startrow = l;
            *startcol = cpt - maze[l];
            return;
        }
    }
}

import { readFileSync } from 'fs'

import _ from 'underscore'

const FILE_PATH = './src/resources/11.txt'

const GALAXY_SYMBOL = '#'

// 1 for part 1, 1000000 for part 2
const SPACE_EXPANSION_COEFFICIENT = 1000000

type Map = string[][]

interface Galaxy {
  x: number
  y: number
}

interface GalaxyPair {
  galaxyOne: Galaxy
  galaxyTwo: Galaxy
}

export default function (): void {
  const lines = readFileSync(FILE_PATH, 'utf-8').trim().split('\n')

  const [map, galaxies, galaxyPairs] = buildGalaxyMap(lines, SPACE_EXPANSION_COEFFICIENT)

  const allShortestPaths: number[] = getShortestPathForPairs(galaxyPairs)
  console.log('Sum of shortest paths: ', allShortestPaths.reduce((acc, next) => acc + next))
}

function getShortestPathForPairs (pairs: GalaxyPair[]): number[] {
  const paths: number[] = []
  pairs.forEach((pair) => {
    const shortestPath: number = Math.abs(pair.galaxyOne.x - pair.galaxyTwo.x) + Math.abs(pair.galaxyOne.y - pair.galaxyTwo.y)
    paths.push(shortestPath)
  })
  return paths
}

function buildGalaxyMap (lines, spaceExpansionCoefficient: number): [Map, Galaxy[], GalaxyPair[]] {
  let map: Map = []
  const galaxies: Galaxy[] = []
  const pairs: GalaxyPair[] = []

  // Creates the map
  lines.forEach((line) => {
    const row: string[] = []
    const values = line.split('').filter(Boolean)

    values.forEach((val) => {
      if (val !== '\r') {
        row.push(val)
      }
    })

    map.push(row)
  })

  // Maps all the galaxies
  for (let y = 0; y < map.length; y++) {
    for (let x = 0; x < map[y].length; x++) {
      if (map[y][x] === GALAXY_SYMBOL) {
        galaxies.push({ x, y })
      }
    }
  }

  // Creates all possible pairs
  for (let i = 0; i < galaxies.length - 1; i++) {
    for (let j = i + 1; j < galaxies.length; j++) {
      const pair: GalaxyPair = { galaxyOne: galaxies[i], galaxyTwo: galaxies[j] }
      pairs.push(pair)
    }
  }

  // Get points where space expands on Y axis
  let expansionPoints: number[] = getSpaceExpansionCoordsForRow(map)

  // Updates all the galaxy Y coords with space expansion in account
  let passes = 0
  expansionPoints.forEach((point) => {
    const p = point + passes * (spaceExpansionCoefficient - (spaceExpansionCoefficient === 1 ? 0 : 1))
    galaxies.filter((g) => g.y >= p).forEach((g) => {
      g.y += spaceExpansionCoefficient - (spaceExpansionCoefficient === 1 ? 0 : 1)
    })
    passes++
  })

  // Inverts our map, to get expansion points for X
  map = _.zip(...map)

  // Get points where space expands on original X axis
  expansionPoints = getSpaceExpansionCoordsForRow(map)

  // Updates all the galaxy X coords with space expansion in account
  passes = 0
  expansionPoints.forEach((point) => {
    const p = point + passes * (spaceExpansionCoefficient - (spaceExpansionCoefficient === 1 ? 0 : 1))
    galaxies.filter((g) => g.x >= p).forEach((g) => {
      g.x += spaceExpansionCoefficient - (spaceExpansionCoefficient === 1 ? 0 : 1)
    })
    passes++
  })

  // Reverts the 2D array back to it's original
  map = _.zip(...map)

  return [map, galaxies, pairs]
}

function getSpaceExpansionCoordsForRow (map: Map): number[] {
  const expansionsRows: number[] = []
  for (let y = 0; y < map.length; y++) {
    let rowHasGalaxy = false
    for (let x = 0; x < map[y].length; x++) {
      if (map[y][x] === GALAXY_SYMBOL) {
        rowHasGalaxy = true
        break
      }
    }
    if (!rowHasGalaxy) {
      expansionsRows.push(y)
    }
  }
  return expansionsRows
}

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

// Macros.
#define SIZE 140
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))

// Data structures.
typedef struct Galaxy {
    int row;
    int col;
} Galaxy;
typedef struct Universe {
    Galaxy* galaxies;
    char* occupiedrows;
    char* occupiedcols;
} Universe;

// Function declarations.
long int distance(Universe* u, int g1, int g2, int expansionfactor);
Universe* parseinput(char* filename);

int main()
{
    Universe* u = parseinput("input");
    long int part1 = 0, part2 = 0;
    // Row and column coordinates start at (1, 1) in the upper
    // left corner. A row coordinate of 0 marks the end of the
    // initialized galaxies. Assert that there is at least one
    // uninitialized galaxy at the end of the list.
    assert(!u->galaxies[SIZE*SIZE-1].row);
    for (int i=0; u->galaxies[i].row; ++i)
        for (int j=i+1; u->galaxies[j].row; ++j) {
            part1 += distance(u, i, j, 2);
            part2 += distance(u, i, j, 1000000);
        }
    printf("Part 1: %li\nPart 2: %li\n", part1, part2);
    assert(part1 == 9918828);
    assert(part2 == 692506533832);
}

long int distance(Universe* u, int g1, int g2, int expansionfactor)
{
    int maxrow = MAX(u->galaxies[g1].row, u->galaxies[g2].row);
    int maxcol = MAX(u->galaxies[g1].col, u->galaxies[g2].col);
    int minrow = MIN(u->galaxies[g1].row, u->galaxies[g2].row);
    int mincol = MIN(u->galaxies[g1].col, u->galaxies[g2].col);
    long int distance = maxrow + maxcol - minrow - mincol;
    for (int i=minrow+1; i<maxrow; ++i)
        distance += u->occupiedrows[i] ? 0 : expansionfactor - 1;
    for (int i=mincol+1; i<maxcol; ++i)
        distance += u->occupiedcols[i] ? 0 : expansionfactor - 1;
    return distance;
}

Universe* parseinput(char* filename)
{
    Universe* u = malloc(sizeof (Universe));
    u->galaxies = calloc(SIZE*SIZE, sizeof (Galaxy));
    u->occupiedrows = calloc(SIZE+1, sizeof (char));
    u->occupiedcols = calloc(SIZE+1, sizeof (char));
    int c, row = 1, col = 1, gnum = 0;
    FILE* fptr = fopen(filename, "r");
    while ((c = fgetc(fptr)) != EOF) {
        if (c == '#') {
            u->occupiedrows[row] = 1;
            u->occupiedcols[col] = 1;
            u->galaxies[gnum].row = row;
            u->galaxies[gnum++].col = col;
        }
        else if (c == '\n') {
            ++row;
            col = 0; // Will be 1 at end of loop.
        }
        ++col;
    }
    return u;
}

I ← ⊜(=@#)≠@\n.&fras "11.txt"
Cols ← ⊚¬/↥ I
Rows ← ⊚¬≡/↥ I
Coords ← ≡(+⊙×:⊙⊙(-1)⍜°⊟⊓(/+>Rows|/+>Cols)).⊚
Dist ← ÷2/+♭⊠(/+⌵-).

Dist Coords I 2
Dist Coords I 1e6

Benchmark    Mode  Cnt    Score    Error  Units
both         avgt    5  601,310 ± 18,722  us/op
dist         avgt    5  163,994 ±  4,245  us/op
rowsCols     avgt    5  188,437 ± 20,510  us/op
transpose    avgt    5  184,193 ± 12,004  us/op
cols         avgt    5  191,901 ± 12,678  us/op
rows         avgt    5    1,725 ±  0,166  us/op

import scala.collection.immutable.ArraySeq
import scala.io.Source
import scala.util.Using

object Day11:
   val path = """11.txt"""
   val input = Using.resource(Source.fromFile(path))(_.getLines().to(ArraySeq))

   final case class Point(x: Long, y: Long):
      def distTo(that: Point) =
         Math.abs(that.x - x) + Math.abs(that.y - y)

   def points(input: ArraySeq[String], exp: Int, rows: ArraySeq[Int], cols: ArraySeq[Int]) =
      val buf = ArraySeq.newBuilder[Point]
      for
         y <- input.indices
         x <- input.head.indices
         if input(y)(x) == '#'
      do
         val r = rows.count(_ < y)
         val c = cols.count(_ < x)
         buf += Point(x + c * (exp -1), y + r * (exp - 1))
      buf.result()

   def dist(p: ArraySeq[Point]): Long =
      var acc = 0L
      for
         i1 <- p.indices
         i2 <- i1 until p.length
      do
         acc += p(i1).distTo(p(i2))
      acc

   def both =
      val rows = input.zipWithIndex.collect:
         case (line, y) if !line.contains('#') => y

      val cols = input.transpose.zipWithIndex.collect:
         case (line, x) if !line.contains('#') => x

      val p1 = points(input, 2, rows, cols)
      val p2 = points(input, 1_000_000, rows, cols)

      (dist(p1), dist(p2))

   def main(args: Array[String]): Unit =
      println(both)

lines = open('input12.txt', 'rt').read().split('\n')

combinations_cache = {}

def combinations_cache_lookup(pos, group_index, group_len):
    v = combinations_cache.get((pos, group_index, group_len))
    if v is None:
        v = combinations(pos, group_index, group_len)
        combinations_cache[(pos, group_index, group_len)] = v
    return v

def combinations(pos, group_index, group_len):
    if pos == len(row):
        if group_len == 0:
            return 1 if group_index == len(groups) else 0
        else:
            return 1 if group_index == len(groups) - 1 and groups[group_index] == group_len else 0

    valid = 0

    if row[pos] == '.' or row[pos] == '?':
        if group_len == 0:
            valid += combinations_cache_lookup(pos+1, group_index, 0)
        elif groups[group_index] == group_len:
            valid += combinations_cache_lookup(pos+1, group_index+1, 0)

    if row[pos] == '#' or row[pos] == '?':
        if group_index < len(groups) and group_len < groups[group_index]:
            valid += combinations_cache_lookup(pos+1, group_index, group_len+1)

    return valid

res = 0

for l in lines:
    row, groups = l.split()
    groups = [int(x) for x in groups.split(',')]

    row = '?'.join([row] * 5)
    groups = groups * 5

    combinations_cache.clear()
    valid = combinations(0, 0, 0)
    res += valid

print(res)