AoC Day 3: No Matter How You Slice It

import re

with open('input.txt', 'r') as f:
    data = []
    for line in f:
        nums = [int(n) for n in re.findall(r'\d+', line)]
        data.append({'id': nums[0], 'coordinates': [nums[1], nums[2]], 'dimensions': [nums[3], nums[4]]})


def get_coordinates(coordinates, dimensions):
    for x in range(dimensions[0]):
        for y in range(dimensions[1]):
            yield str(x + coordinates[0]) + "," + str(y + coordinates[1])


def get_overlaps(data):
    overlaps = set()
    filled = set()
    for line in data:
        for coord in get_coordinates(line['coordinates'], line['dimensions']):
            if coord in filled:
                overlaps.add(coord)
            else:
                filled.add(coord)
    return overlaps


def no_overlaps(coordinates, dimensions, overlaps):
    for coord in get_coordinates(coordinates, dimensions):
        if coord in overlaps: 
            return False
    return True


def find_no_overlaps(data, overlaps):
    for line in data:
        if no_overlaps(line['coordinates'], line['dimensions'], overlaps):
            return line['id']


overlaps = get_overlaps(data)
# Q1
print(len(overlaps))

# Q2
print(find_no_overlaps(data, overlaps))

typealias Point = Pair<Int, Int>

val Point.x get() = first
val Point.y get() = second

private fun String.parseRect(): Rectangle {
    val result = Regex("""#(\d+) @ (\d+),(\d+): (\d+)x(\d+)""").find(this)
    val groups = result!!.groups
    return Rectangle(
        groups[1]!!.value,
        groups[2]!!.value.toInt(),
        groups[3]!!.value.toInt(),
        groups[4]!!.value.toInt(),
        groups[5]!!.value.toInt()
    )
}

class Rectangle(val id: String, val tl: Point, val br: Point) {
    constructor(id: String, x: Int, y: Int, width: Int, height: Int) :
            this(id, x to y, x + width to y + height)
}

private fun Rectangle.overlaps(b: Rectangle) = when {
    this.id == b.id -> false
    b.br.x <= tl.x || b.tl.x >= br.x -> false
    b.br.y <= tl.y || b.tl.y >= br.y -> false
    else -> true
}

fun Rectangle.intersection(b: Rectangle): Set<Point> =
    (max(tl.x, b.tl.x) until min(br.x, b.br.x)).flatMap { x ->
        (max(tl.y, b.tl.y) until min(br.y, b.br.y)).map { y -> x to y }
    }.toSet()

fun answer1(input: List<String>) =
    input
        .cartesian { a, b -> a.parseRect() to b.parseRect() }
        .filter { (a, b) -> a.overlaps(b) }
        .map { (a, b) -> a.intersection(b) }
        .reduce { set, other -> set.union(other) }
        .count()

fun answer2(input: List<String>) =
    input.asSequence()
        .map(String::parseRect)
        .let { rects ->
            rects.find { a -> rects.none(a::overlaps) }?.id
        }

import re

def claims(input):
    c = input.read().splitlines()
    side = 1000
    matrix = [["O" for x in range(side)] for y in range (side)]
    idx = r'\d*(,)\d*'
    dim = r'\d*(x)\d*'
    cl = r'(#)\d*'
    for claim in c:
        claimant = int(re.search(cl, claim).group(0)[1:])
        inidicies = [int(i) for i in re.search(idx, claim).group(0).split(',')]
        dimensions = [int(i) for i in re.search(dim, claim).group(0).split('x')]
        x = inidicies[0]
        y = inidicies[1]
        width = dimensions[0]
        height = dimensions[1]
        for _ in range(height):
            for _ in range(width):
                space = matrix[y][x]
                if space == "O":
                    matrix[y][x] = claimant
                else:
                    matrix[y][x] = "X"
                x += 1
            x = inidicies[0]
            y += 1
        check_overlap = 0
    for x in matrix:
        check_overlap += x.count("X")

    return check_overlap

print(claims(open('input.txt', 'r')))

import re

def claims(input):
    c = input.read().splitlines()
    side = 1000
    matrix = [["O" for x in range(side)] for y in range (side)]
    idx = r'\d*(,)\d*'
    dim = r'\d*(x)\d*'
    cl = r'(#)\d*'
    all_ids = set()
    overlap_ids = set()
    for claim in c:
        claimant = int(re.search(cl, claim).group(0)[1:])
        all_ids.add(claimant)
        inidicies = [int(i) for i in re.search(idx, claim).group(0).split(',')]
        dimensions = [int(i) for i in re.search(dim, claim).group(0).split('x')]
        x = inidicies[0]
        y = inidicies[1]
        width = dimensions[0]
        height = dimensions[1]
        for _ in range(height):
            for _ in range(width):
                space = matrix[y][x]
                if space == "O":
                    # first claim to this space
                    matrix[y][x] = claimant
                elif space == 'X':
                    # claim overlaps with existing overlapped claim
                    overlap_ids.add(claimant)
                else:
                    # claim overlaps with exactly one preexisting claim
                    overlap_ids.add(claimant)
                    overlap_ids.add(space)
                    matrix[y][x] = "X"
                x += 1
            x = inidicies[0]
            y += 1
    return all_ids.difference(overlap_ids)

print(claims(open('input.txt', 'r')))

(ns day3
  (:require [clojure.string :refer [split]]
            [clojure.core.matrix :refer :all]))
(set-current-implementation :ndarray)

(defn lines [input-file]
  (split (slurp input-file) #"\n"))

(defn as-long [s] (Long/parseLong s))

(defn destruct [s]
  (let [[all & params] (re-find #"#(\S+) @ (\d+),(\d+): (\d+)x(\d+)" s)]
    (when all (map as-long params))))

(defn star
  [input-file]
  (let [ll (lines input-file)
        field (new-matrix 1000 1000)]
    (loop [[[id col row w h] & xlines] (map destruct ll)]
      (if-not id
        field
        (let [sm (submatrix field row h col w)]
          (emap! #(if (zero? %) id -1) sm)
          (recur xlines))))
    (ereduce + (eq field -1))))

(defn star2
  [input-file]
  (let [ll (lines input-file)
        field (new-matrix 1000 1000)]
    (loop [[[id col row w h] & xlines] (map destruct ll) ids #{}]
      (if-not id
        (first ids)
        (let [sm (submatrix field row h col w)
              ids' (ereduce #(if (zero? %2) %1 (disj %1 %2 id)) (conj ids id) sm)]
          (assign! sm id)
          (recur xlines ids'))))))

use regex::Regex;
use std::collections::HashMap;

/// An X, Y grid of Santa's fabric that elves can lay claim to
struct Fabric {
    squares: HashMap<(usize, usize), usize>,
}

/// The data for a rectangular claim an elf makes on a section of fabric
struct Claim {
    id: usize,
    left: usize,
    top: usize,
    width: usize,
    height: usize,
}

impl Fabric {
    fn new() -> Self {
        Self { squares: HashMap::new() }
    }

    /// Increments the amount of claims covering each of the cells inside
    /// the rectangle.
    fn claim(&mut self, claim: &Claim) {
        for x in claim.left..(claim.left + claim.width) {
            for y in claim.top..(claim.top + claim.height) {
                if x > 999 || y > 999 {
                    continue;
                }
                *self.squares.entry((x, y)).or_insert(0) += 1;
            }
        }
    }

    /// Counts how many cells have more than one claim on them
    fn count_conflicts(&self) -> usize {
        self.squares.values().filter(|count| **count >= 2).count()
    }

    /// Counts the total squares claimed
    /// 
    /// A helper function I wrote to help with debugging... #didnthelp
    fn total_squares(&self) -> usize {
        self.squares.iter().count()
    }
}



/// Processes a claim string into an actual Claim
/// 
/// claim string pattern is #<id> @ <left>,<top>: <width>x<height>
/// Since all the numbers are disjoint, we can just match all the 
/// separated numbers in order.
fn process_claim(claim_text: &str) -> Claim {
    // This makes it so we only compile the regex once
    lazy_static! {
        static ref claim_re: Regex = Regex::new(r"#(?P<id>\d+) @ (?P<left>\d+),(?P<top>\d+): (?P<width>\d+)x(?P<height>\d+)").unwrap();
    }

    let claim_parts = claim_re.captures(claim_text).unwrap();
    Claim {
        id: claim_parts["id"].parse().unwrap(),
        left: claim_parts["left"].parse().unwrap(),
        top: claim_parts["top"].parse().unwrap(),
        width: claim_parts["width"].parse().unwrap(),
        height: claim_parts["height"].parse().unwrap(),
    }
}

/// Counts the number of squares with more than one claim on them
pub fn count_conflicting_squares(text: &str) -> usize {
    let mut fabric = Fabric::new();

    for line in text.lines() {
        let claim = process_claim(line);
        fabric.claim(&claim);
    }

    fabric.count_conflicts()
}

impl Fabric {
    /// Checks whether or not a given claim has any overlapping cells
    fn check_overlap(&self, claim: &Claim) -> bool {
        for x in claim.left..(claim.left + claim.width) {
            for y in claim.top..(claim.top + claim.height) {
                if self.squares.get(&(x, y)) != Some(&1) {
                    return true;
                }
            }
        }
        false
    }
}

/// Finds out if a claim in a group of claims doesn't overlap.  Returns
/// the first one that doesn't.
pub fn find_unconflicting_id(text: &str) -> usize {
    let mut fabric = Fabric::new();
    let mut claims: Vec<Claim> = Vec::new();

    // Load all the claims in
    for line in text.lines() {
        let claim = process_claim(line);
        fabric.claim(&claim);
        claims.push(claim);
    }

    // Check them all for overlaps
    for claim in claims {
        if !fabric.check_overlap(&claim) {
            return claim.id;
        }
    }
    return 0;
}

import Fs from "fs"
import Path from "path"

const input = Fs.readFileSync(Path.join(__dirname, "input.txt"))
    .toString()
    .split("\n")

interface Range {
    start: number
    end: number
}

interface LineProperties {
    id: string
    rows: Range
    columns: Range
}

type ID = string
interface Pixel {
    ids: ID[]
    hasOverlap: boolean
}

type Coordinates = string

let overlaps = 0
const canvas = new Map<Coordinates, Pixel>()
const idsWithOverlappingStatus: Map<string, boolean> = new Map()

function parseLine(line: string): LineProperties {
    const [
        _ = "",
        id = "",
        columnStart = "",
        rowStart = "",
        width = "",
        height = "",
    ] = line.match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/) || []

    return {
        id,
        columns: {
            start: parseInt(columnStart, 10),
            end: parseInt(columnStart, 10) + parseInt(width, 10),
        },
        rows: {
            start: parseInt(rowStart, 10),
            end: parseInt(rowStart, 10) + parseInt(height, 10),
        },
    }
}

input.forEach(line => {
    const lineProperties: LineProperties = parseLine(line)

    idsWithOverlappingStatus.set(lineProperties.id, false)

    for (
        let row = lineProperties.rows.start;
        row < lineProperties.rows.end;
        row++
    ) {
        for (
            let column = lineProperties.columns.start;
            column < lineProperties.columns.end;
            column++
        ) {
            const coordinnates = `${row}x${column}`
            let pixel: Pixel = { ids: [lineProperties.id], hasOverlap: false }

            // not overlapping yet
            if (canvas.has(coordinnates) === false) {
                canvas.set(coordinnates, pixel)
                continue
            }

            pixel = canvas.get(coordinnates) || pixel
            pixel.ids = [...pixel.ids, lineProperties.id]

            canvas.set(coordinnates, pixel)
            // drop it, it has already been counted
            if (pixel.hasOverlap) {
                continue
            }

            overlaps++
            pixel.ids.forEach(id => idsWithOverlappingStatus.set(id, true))
            canvas.set(coordinnates, {
                ...pixel,
                hasOverlap: true,
            })
        }
    }
})

// part 1
console.log(overlaps)

// part 2
for (const [id, overlapping] of idsWithOverlappingStatus) {
    if (overlapping === false) {
        console.log(id)
        break
    }
}

program aoc31
      use ISO_FORTRAN_ENV
      implicit none
      integer, dimension(0:1023,0:1023) :: cloth
      logical, dimension(0:1023,0:1023) :: cloth_mask
      integer :: id, cut_x, cut_y, cut_width, cut_height
      integer :: overlaps
      integer :: io_status

      cloth = 0

      io_status = 0

      do
        read (*,*,iostat=io_status) id, cut_x, cut_y, cut_width, cut_height
        if (io_status /= 0) then
          exit
        end if
        cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) = &
         cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) + 1
      end do

      cloth_mask = (cloth > 1)
      overlaps = count(cloth_mask)

      write(*,*) "Overlaps: ", overlaps
end program aoc31

program aoc32
      use ISO_FORTRAN_ENV
      implicit none
      integer, dimension(0:1023,0:1023) :: cloth
      logical, dimension(0:1023,0:1023) :: cloth_mask
      integer :: id, cut_x, cut_y, cut_width, cut_height
      integer :: overlaps
      integer :: io_status

      cloth = 0

      io_status = 0

      open (unit=5, file="input.simplified")
      do
        read (5,*,iostat=io_status) id, cut_x, cut_y, cut_width, cut_height
        if (io_status /= 0) then
          exit
        end if
        cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) = &
         cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) + 1
      end do
      close(5)

      open (unit=5, file="input.simplified")
      do
        read (5,*,iostat=io_status) id, cut_x, cut_y, cut_width, cut_height
        if (io_status /= 0) exit
        if (sum(cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1)) == &
         cut_width * cut_height) then
         write(*,*) "Unique ID: ", id
         exit
        end if
      end do
      close(5)

end program aoc32

<?php
$input = file_get_contents($argv[1]);
$claims = explode("\n", trim($input));
$fabric = array_fill(0, 1000, array_fill(0, 1000, 0));
foreach($claims as $claim) {
  preg_match('/\#[0-9]+ \@ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)/', $claim, $data);
  $x = intval($data[1]);
  $y = intval($data[2]);
  $w = intval($data[3]);
  $h = intval($data[4]);

  for ($i = $y; $i < $y+$h; $i++) {
    $slice = array_slice($fabric[$i], $x, $w);
    $slice = array_map(function($x) {
      return $x+1;
    }, $slice);
    array_splice($fabric[$i], $x, $w, $slice);
  }
}

$twoplus = 0;

foreach ($fabric as $row) {
  $claimcounts = array_count_values($row);
  foreach ($claimcounts as $val=>$count) {
    if ($val >= 2) {
      $twoplus += $count;
    }
  }
}
echo $twoplus;
die(1);

<?php
$input = file_get_contents($argv[1]);
$claims = explode("\n", trim($input));
$fabric = array_fill(0, 1000, array_fill(0, 1000, 0));
foreach($claims as $j=>$claim) {
  preg_match('/\#([0-9]+) \@ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)/', $claim, $data);
  $claims[$j] = $data;
  $c = $data[1];
  $x = intval($data[2]);
  $y = intval($data[3]);
  $w = intval($data[4]);
  $h = intval($data[5]);

  for ($i = $y; $i < $y+$h; $i++) {
    $slice = array_slice($fabric[$i], $x, $w);
    $slice = array_map(function($x) {
      return $x+1;
    }, $slice);
    array_splice($fabric[$i], $x, $w, $slice);
  }
}

foreach ($claims as $claim) {
  $c = $claim[1];
  $x = $claim[2];
  $y = $claim[3];
  $w = $claim[4];
  $h = $claim[5];

  $arr = array();

  for ($i = $y; $i < $y+$h; $i++) {
    $slice = array_slice($fabric[$i], $x, $w);
    array_push($arr, array_product($slice));
  }

  if (array_product($arr) == 1) {
    echo $c;
    break;
  }
}
die(1);

public class FabricSlicing
    {
        public int GetOverlap(int width, int height, IEnumerable<string> fabricClaims)
        {
            var fabric = GetFabricLayout(width, height, fabricClaims);
            return fabric.GetOverlapArea();
        }

        public IEnumerable<FabricSegments> GetNoOverlap(int width, int height, IEnumerable<string> fabricClaims)
        {
            var fabric = GetFabricLayout(width, height, fabricClaims);
            return fabric.GetNoOverlap();
        }

        protected Fabric GetFabricLayout(int width, int height, IEnumerable<string> fabricClaims)
        {
            var fabric = new Fabric(width, height, PopulateFabricClaims(fabricClaims));

            return fabric;
        }

        protected IEnumerable<FabricSegments> PopulateFabricClaims(IEnumerable<string> fabricClaims)
        {
            List<FabricSegments> fabricSegments = new List<FabricSegments>();

            // #1 @ 1,3: 4x4
            Regex regex = new Regex(@"^#(?<id>\d*)\s@\s(?<x>\d*),(?<y>\d*):\s(?<width>\d*)x(?<height>\d*)$");

            foreach (var claim in fabricClaims)
            {
                var matches = regex.Match(claim);

                fabricSegments.Add(new FabricSegments()
                {
                    ClaimId = int.Parse(matches.Groups["id"].Value),
                    Height = int.Parse(matches.Groups["height"].Value),
                    Width = int.Parse(matches.Groups["width"].Value),
                    StartCoordinateX = int.Parse(matches.Groups["x"].Value),
                    StartCoordinateY = int.Parse(matches.Groups["y"].Value)
                });
            }

            return fabricSegments;
        }
    }

    public class Fabric
    {
        private readonly Point[,] _points;

        public Fabric(int width, int height, IEnumerable<FabricSegments> fabricClaims)
        {
            Width = width;
            Height = height;
            FabricClaims = fabricClaims;

            _points = new Point[Width,Height];

            // Instantiate all the points (is there a better way to do this?)
            for (var row = 0; row < Width; row++)
            {
                for (var column = 0; column < Height; column++)
                {
                    _points[row, column] = new Point();
                }
            }

            PopulatePoints();
        }

        public int Width { get; }
        public int Height { get; }

        public IEnumerable<FabricSegments> FabricClaims { get; }

        public int GetOverlapArea()
        {
            int count = 0;
            for (var row = 0; row < Width; row++)
            {
                for (var column = 0; column < Height; column++)
                {
                    if (_points[row, column].HasOverlap)
                    {
                        count++;
                    }
                }
            }

            return count;
        }

        public IEnumerable<FabricSegments> GetNoOverlap()
        {
            var overlap = GetOverlap();
            return FabricClaims.ToList().Except(overlap);
        }

        private void PopulatePoints()
        {
            foreach (var fabricClaim in FabricClaims)
            {
                for (var width = 0; width < fabricClaim.Width; width++)
                {
                    for (var height = 0; height < fabricClaim.Height; height++)
                    {
                        var point = _points[
                            fabricClaim.StartCoordinateX + width,
                            fabricClaim.StartCoordinateY + height
                        ];

                        point.Occupied.Add(fabricClaim);
                    }
                }
            }
        }

        private IEnumerable<FabricSegments> GetOverlap()
        {
            List<FabricSegments> list = new List<FabricSegments>();

            for (var row = 0; row < Width; row++)
            {
                for (var column = 0; column < Height; column++)
                {
                    var point = _points[row, column];
                    if (point.HasOverlap)
                    {
                        list.AddRange(point.Occupied);
                    }
                }
            }

            return list;
        }
    }

    public class FabricSegments
    {
        public int ClaimId { get; set; }

        public int Width { get; set; }
        public int Height { get; set; }

        public int StartCoordinateX { get; set; }
        public int StartCoordinateY { get; set; }
    }

    public class Point
    {
        public bool IsOccupied => Occupied.Count > 0;
        public bool HasOverlap => Occupied.Count > 1;
        public List<FabricSegments> Occupied { get; set; } = new List<FabricSegments>();
    }

public class FabricSlicingTests
    {
        private readonly FabricSlicing _subject = new FabricSlicing();

        private class PopulateFabricClaims_FabricSlicing : FabricSlicing
        {
            public IEnumerable<FabricSegments> GetFabricClaims(
                IEnumerable<string> fabricClaims)
            {
                return PopulateFabricClaims(fabricClaims);
            }
        }

        public static IEnumerable<object[]> SampleData =>
            new List<object[]>()
            {
                new object[]
                {
                    new[]
                    {
                        "#1 @ 1,3: 4x4",
                        "#2 @ 3,1: 4x4",
                        "#3 @ 5,5: 2x2"
                    },
                    8,
                    8,
                    4
                }
            };

        [Theory]
        [MemberData(nameof(SampleData))]
        public void ShouldValidateSample(string[] fabricClaims, int width, int height, int expectedOverlap)
        {
            var result = _subject.GetOverlap(width, height, fabricClaims);

            Assert.Equal(expectedOverlap, result);
        }

        [Theory]
        [MemberData(nameof(SampleData))]
        public void ShouldValidateSampleNoOverlap(string[] fabricClaims, int width, int height, int expectedOverlap)
        {
            var result = _subject.GetNoOverlap(width, height, fabricClaims).ToList();

            Assert.Equal(3, result[0].ClaimId);
        }

        [Fact]
        public void ShouldParseClaimsProperly()
        {
            var claim = "#1 @ 2,3: 4x5";

            var subject = new PopulateFabricClaims_FabricSlicing();
            var result = subject.GetFabricClaims(new[] { claim }).ToList();

            Assert.True(result.Count == 1, nameof(result.Count));
            Assert.True(result[0].ClaimId == 1, nameof(FabricSegments.ClaimId));
            Assert.True(result[0].StartCoordinateX == 2, nameof(FabricSegments.StartCoordinateX));
            Assert.True(result[0].StartCoordinateY == 3, nameof(FabricSegments.StartCoordinateY));
            Assert.True(result[0].Width == 4, nameof(FabricSegments.Width));
            Assert.True(result[0].Height == 5, nameof(FabricSegments.Height));
        }

        [Fact]
        public void DoTheThing()
        {
            var file = Utilities.GetFileContents("./Day3/fabricSlicingData.txt");
            var result = _subject.GetOverlap(1000, 1000, file);

            Assert.Equal(110383, result);
        }

        [Fact]
        public void DoTheThingVersion2()
        {
            var file = Utilities.GetFileContents("./Day3/fabricSlicingData.txt");
            var result = _subject.GetNoOverlap(1000, 1000, file).ToList();

            Assert.Equal(129, result[0].ClaimId);
        }
    }