AoC Day 3: No Matter How You Slice It

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')))

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
        }

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
    }
}

const fs = require('fs');
const readline = require('readline');

const readLines = (file, onLine) => {
    const reader = readline.createInterface({
        input: fs.createReadStream(file),
        crlfDelay: Infinity
    });

    reader.on('line', onLine);

    return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
    const lines = [];
    await readLines(file, line => lines.push(line));  
    return lines;
}

module.exports = {
    readLines,
    readFile
};

const { readFile } = require('./readLines');

const buildClaims = lines => {
    const claims = new Map();
    const regex = /^#(?<id>\d*)\s@\s(?<left>\d*),(?<top>\d*):\s(?<width>\d*)x(?<height>\d*)$/;
    for (let line of lines) {
        const { id, left, top, width, height } = line.match(regex).groups;
        claims.set(id, { 
            left: +left, 
            top: +top, 
            width: +width, 
            height: +height
        });
    }
    return claims;
};

const calculateOverlaps = claims => {
    const fabric = [];

    let overlaps = 0;

    for (let [id, claim] of claims.entries()) {
        const { left, top, width, height } = claim;
        const bottom = top + height;
        const right = left + width;
        for (let row = top; row < bottom; row++) {
            for (let col = left; col < right; col++) {
                if (!fabric[row]) {
                    fabric[row] = [];
                }
                if (!fabric[row][col]) {
                    fabric[row][col] = 0;
                }
                else if (fabric[row][col] === 1) {
                    overlaps++;
                }
                fabric[row][col]++;
            }
        }
    }

    return overlaps;
};

(async () => {
    const lines = await readFile('03-input.txt');

    const claims = buildClaims(lines);
    const overlaps = calculateOverlaps(claims);

    console.log(`Overlaps are ${overlaps} square inches`);
})();

const { readFile } = require('./readLines');

const buildClaims = lines => {
    const claims = new Map();
    const regex = /^#(?<id>\d*)\s@\s(?<left>\d*),(?<top>\d*):\s(?<width>\d*)x(?<height>\d*)$/;
    for (let line of lines) {
        const { id, left, top, width, height } = line.match(regex).groups;
        claims.set(id, { 
            left: +left, 
            top: +top, 
            width: +width, 
            height: +height
        });
    }
    return claims;
};

const findNonOverlappingClaimID = claims => {
    const fabric = [];

    // Marking entries
    for (let [id, claim] of claims.entries()) {
        const { left, top, width, height } = claim;
        const bottom = top + height;
        const right = left + width;
        for (let row = top; row < bottom; row++) {
            for (let col = left; col < right; col++) {
                if (!fabric[row]) {
                    fabric[row] = [];
                }
                if (!fabric[row][col]) {
                    fabric[row][col] = 0;
                }
                fabric[row][col]++;
            }
        }
    }

    // Finding ID for the claim that doesnt overlap
    for (let [id, claim] of claims.entries()) {
        const { left, top, width, height } = claim;
        const bottom = top + height;
        const right = left + width;

        let doesClaimOverlap = false;
        for (let row = top; row < bottom; row++) {
            for (let col = left; col < right; col++) {
                if (fabric[row][col] > 1) {
                    doesClaimOverlap = true; 
                }
            }
        }

        if (!doesClaimOverlap) {
            return id;
        }
    }
};

(async () => {
    const lines = await readFile('03-input.txt');

    const claims = buildClaims(lines);
    const id = findNonOverlappingClaimID(claims);

    console.log(`The ID of the only claim that doesn't overlap is ${id}`);
})();

import numpy as np

with open("input.txt") as f:
    claims = []
    for line in f:
        _, _, coords, dim = line.split()
        x, y = coords.split(",")[0], coords.split(",")[1][:-1]
        a, b = dim.split("x")
        claims.append((int(x), int(y), int(a), int(b)))

max_x = max(t[0]+t[2]+1 for t in claims)
max_y = max(t[1]+t[3]+1 for t in claims)

fabric = np.zeros((max_x, max_y), dtype=int)
for x, y, a, b in claims:
    fabric[x:x+a, y:y+b] += 1

print(len(fabric[fabric > 1]))

candidates = set(list(range(len(claims))))

fabric = np.zeros((max_x, max_y), dtype=int)
for i, (x, y, a, b) in enumerate(claims):
    f = fabric[x:x+a, y:y+b]
    uniques = np.unique(f)
    if list(uniques) != [0]:
        for u in uniques:
            candidates.discard(u)
        candidates.discard(i)
    fabric[x:x+a, y:y+b] = i

print(candidates.pop()+1)

(ns aoc.aoc3
  (:require [clojure.string :as s]
            [clojure.set :as set]))

(defrecord Claim [claim-number squares])

(defn convert-to-grid
  "Converts a claim into a sequence of 'taken' squares."
  [claim grid-width]
  ;; Named groups would be great here, but Clojure doesn't support this natively.
  (let [matcher #"#(?<claim>\d+)\s@\s(?<x>\d+),(?<y>\d+):\s(?<width>\d+)x(?<height>\d+)$"
        matches (re-find matcher claim)
        [_ claim horiz vert width height] matches
        x (Integer. horiz)
        y (Integer. vert)
        w (Integer. width)
        h (Integer. height)
        rows (take h (iterate inc y))]
    (->> (map #(range (+ x (* grid-width %)) (+ (+ x w) (* grid-width %))) rows)
         (flatten)
         (set)
         (Claim. (Integer. claim) ))))

(defn get-overlap
  "returns the amount of overlap based on calculated inputs.
   Answer provided in square units matching the units entered
   (for the case of the problem, square inches)."
  [claims]
  ;; Perform intersection to find any matches, then union to combine; repeat through the list.
  (loop [mapped-area (map #(convert-to-grid % 1000) claims)
         shared-fabric #{}
         intersections #{}]
    (if (empty? mapped-area)
      intersections
      (let [intersect (set/intersection shared-fabric (:squares (first mapped-area)))
            union (set/union shared-fabric (:squares (first mapped-area)))]
        (recur (rest mapped-area) union (set/union intersections intersect))))))

(defn overlapping-claim [c1 c2]
  (cond
    (= (:claim-number c1) (:claim-number c2)) nil
    (not-empty (set/intersection (:squares c1) (:squares c2))) c2))

(defn find-no-overlap
"given a set of input claims, find the claim that has no overlap
  with any other claims."
[claims]
(let [grid-claims (map #(convert-to-grid % 1000) claims)]
  (loop [idx 0 ignores #{}]
    (if-not (contains? (:claim-id (nth grid-claims idx)) ignores)
      (if-let [overlap (some #(overlapping-claim (nth grid-claims idx) %) grid-claims)]
        (recur (inc idx) (conj ignores (:claim-number overlap)))
        (:claim-number (nth grid-claims idx)))
      (recur (inc idx) ignores)))))

<?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);

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))