AoC Day 3: No Matter How You Slice It

Day three! Our DEV leaderboard is up to 44 people, which is awesome!

Also, check out the much classier cover images for these posts that @aspittel came up with! 🎅🥇💻

Anyways, today's challenge asks us to calculate which cells are or are not overlapped as it gives us a bunch of grid rectangles (x, y, height, width) to plot out.

How did everybody do?

Comments

[rohmanovich]

#Part 1

from collections import defaultdict
claims = defaultdict(list)
i = 1
for line in film.split('\n'):
    if line is None or line == '':
        continue
    _, _, offset, size = line.split(' ')

    l, t = map(int, offset[:-1].split(','))
    w, h = map(int, size.split('x'))

    claims.update({(l+x,t+y): claims.get((l+x,t+y),[]) + [i] for x in range(1,w+1) for y in range(1,h+1)})
    i += 1
print(len([claim for claim in claims.values() if len(claim) > 1]))

#Part 2
overlapping_claims = []
for x in claims.values():
    if len(x) > 1:
        overlapping_claims += x
print(set(range(1,1360)).difference(set(overlapping_claims)))

[Jason Steinhauser]

I've been solving all of these in Elixir thus far, and it's been pretty fun! Day 3 is the first time I dealt with "off by one" errors...

parse_claim = fn line ->
  line
  |> String.split(~r/[#@,:x\n ]/, trim: true)
  |> Enum.map(&Integer.parse/1)
  |> Enum.map(& elem(&1,0))
end  

claims =
  File.stream!("day3.txt")
  |> Enum.map(parse_claim)

grid = 
  claims
  |> Enum.flat_map(fn [claim, left, top, width, height] -> 
        for x <- left..left+width-1, y <- top..top+height-1, do: {claim, x, y} end)
  |> Enum.reduce(%{}, fn {claim, x, y}, acc -> Map.update(acc, {x,y}, [claim], &[claim | &1]) end)

part1 = fn ->
  grid
  |> Enum.count(fn {_k,v} -> Enum.count(v) > 1 end)
end

IO.puts "Part 1: #{part1.()}"

part2 = fn ->
  singles = 
    grid
    |> Enum.filter(fn {_k,v} -> Enum.count(v) == 1 end)
    |> Enum.group_by(fn {_k,[v]} -> v end, fn _ -> true end)
    |> Enum.map(fn {k, v} -> {k, Enum.count(v, & &1)} end)
    |> Map.new()

  claims
  |> Enum.find(fn [claim, _, _, w, h] -> Map.get(singles, claim) == w * h end)
  |> hd()
  |> Integer.to_string()
end

IO.puts "Part 2: #{part2.()}"

[Antonio Radovcic]

My solution (Elixir) for the first part was:

• Make a list of every data-point's coords and size [((x,y), (w,h)), ...]
• Transform each entry to a list of coords (all coords of this rect) [(x,y), ...], so now I have a list of lists with w * h coordinate-pairs
• Concatenate all lists into one, so now I have a huge list of every occupied field.
• Count every coordinate in a map, %{(x,y) => count, (x,y) => count, ...}
• Throw out every entry where count < 2
• Count entries in resulting list

Takes about a second. The first version used lists and list-diffing to find duplicates, but this took minutes to compute. Maps were much faster at this size (hundeds of thousands of entries).

I should mention I'm just learning Elixir, so this is not to be understood as "good code" or "knows what he's doing".

Here's the code:

defmodule Ac3 do
  def doit do
    filly =
      getFilledList()
      |> Enum.reduce(%{}, &count/2)

    :maps.filter(fn _, v -> v != 0 end, filly)
    |> Enum.reduce(0, fn i, acc -> acc + 1 end)
    |> IO.inspect()
  end

  def count(item, acc) do
    acc
    |> Map.update(item, 0, &(&1 + 1))
  end

  def getFilledList() do
    File.stream!("input.txt")
    |> Enum.to_list()
    |> Enum.map(&String.trim_trailing/1)
    |> Enum.map(&parse/1)
    |> Enum.map(&to_coords/1)
    |> Enum.reduce([], fn i, acc -> i ++ acc end)
  end

  def to_coords(unit) do
    x = elem(elem(unit, 0), 0)
    y = elem(elem(unit, 0), 1)
    x2 = x + elem(elem(unit, 1), 0) - 1
    y2 = y + elem(elem(unit, 1), 1) - 1
    fill(x, y, x, y, x2, y2)
  end

  def fill(x, y, _x1, _y1, x2, y2) when x === x2 and y === y2 do
    [{x, y}]
  end

  def fill(x, y, x1, y1, x2, y2) when x < x2 do
    [{x, y} | fill(x + 1, y, x1, y1, x2, y2)]
  end

  def fill(x, y, x1, y1, x2, y2) when x === x2 do
    [{x, y} | fill(x1, y + 1, x1, y1, x2, y2)]
  end

  def parse(str) do
    {
      unwrap(Enum.at(split(str), 3)),
      unwrap(Enum.at(split(str), 5))
    }
  end

  def split(str) do
    String.split(str, [" ", ":", "#"])
  end

  def unwrap(str) do
    {
      str
      |> String.split([",", "x"])
      |> Enum.at(0)
      |> String.to_integer(),
      str
      |> String.split([",", "x"])
      |> Enum.at(1)
      |> String.to_integer()
    }
  end
end

Ac3.doit()

[Ryan Palo]

Cool! Thanks for sharing!

Just a heads up, you can put the word “elixir” immediately after the opening triple backtick, and your code will show up with syntax highlighting. 😁

[JavaScript Room]

Hi guys! Here is my solution on #typescript.

Repo: github.com/room-js/adventOfCode201...

[Ian Kirker]

This seemed like a natural job for Fortran!

Part 1

No, really, it has nice array operation and slicing syntax! I've just stretched out a big array, added 1 everywhere there's a claim, and then counted the number of elements where there's an element greater than 1.

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

Part 2

Part 2 was trickier, and I had to use a similar solution to @rpalo , going over each claim again; but then I checked whether the sum of the cut elements was the same as its area to determine whether it was a unique claim. I could have done a similar count-based method to part 1, but I thought of this way first.

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

I don't write a lot of Fortran, and peering at about 7 descriptions of how advanced IO worked didn't get me very far, so I used sed to strip out everything that wasn't a number or a space and that made it much more amenable to Fortran's read input preferences.

[Ryan Palo]

Woah, this is super cool! The right tool for the right job, huh? 😎 thanks for sharing!

[Russ Hammett]

c# again

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>();
    }

Tests:

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

[Neil Gall]

Ah, regexes and string splitting. The One True Way to parse text is with parser combinators.

import org.jparsec.Parser
import org.jparsec.Parsers.*
import org.jparsec.Scanners.*

data class Origin(val left: Int, val top: Int)
data class Size(val width: Int, val height: Int)
data class Claim(val id: origin: Origin, size: Size)

val integer: Parser<Int> = INTEGER.map(String::toInt)

fun <T> integerPair(sep: Char, c: (Int, Int) -> T): Parser<T> =  
    sequence(integer.followedBy(isChar(sep)), integer, c)

val claimId: Parser<Int> = isChar('#').next(integer)

val origin: Parser<Origin> = WHITESPACES.followedBy(isChar('@')).followedBy(WHITESPACES).next(integerPair(',', ::Origin))

val size: Parser<Size> = isChar(':').followedBy(WHITESPACES).next(integerPair('x', ::Size))

val claim: Parser<Claim> = sequence(claimId, origin, size, ::Claim)

val input: List<Claim> = File("input.txt").readLines().map(claim::parse)

Part 1

I really wanted to do Part 1 geometrically by splitting and merging claims into non-overlapping regions. It would be O(N²) however, and I was short of actual time to build it so went for the big map of positions like many others:

fun part1(claims: List<Claim>): Int {
    val material = mutableMapOf<Pos, Int>()
    claims.forEach { claim ->
        claim.positions().forEach { pos ->
            material[pos] = (material[pos] ?: 0) + 1
        }
    }
    return material.filterValues { it >= 2 }.size
}

That uses a modified Claim class as follows:

data class Claim(val id: Int, val x: IntRange, val y: IntRange) {
    constructor(id: Int, origin: Origin, size: Size):
        this(id, (origin.left .. origin.left + size.width - 1), (origin.top .. origin.top + size.height - 1))

    fun positions(): Sequence<Pos> = x.asSequence().flatMap { x ->
        y.asSequence().map { y -> Pos(x, y) }
    }
}

Part 2

Fairly simple extension. The tricky bit was remembering to remove both overlapping claims from the candidate result set:

fun part2(claims: List<Claim>): Set<Int> {
    val material = mutableMapOf<Pos, Int>()
    val nonOverlapping: MutableSet<Int> = claims.map { c -> c.id }.toMutableSet()

    claims.forEach { claim ->
        claim.positions().forEach { pos ->
            val claimed = material[pos]
            if (claimed == null) {
                // unclaimed position, now claimed
                material[pos] = claim.id
            } else {
                // overlapping position, remove both claims from result set
                nonOverlapping -= setOf(claimed, claim.id)
            }
        }
    }
    return nonOverlapping
}

[Matt Morgis]

Node.js

Reused my work for part 1 in part 2.

I make the 1000 x 1000 array and fill it every slot with a *.
First time a claim is added, it gets a #
If a claim overlaps with another, those cells get marked with an X.

Part 1: Filter matrix for all X values.

Part 2: Check every coordinate for each claim. If every coordinate is a #, then that claim is the answer.

const generateFabricMatrix = () => {
  const fabric = [];

  for (const i of Array(1000).keys()) {
    fabric_columns = [];
    for (const j of Array(1000).keys()) {
      fabric_columns.push("*");
    }
    fabric.push(fabric_columns);
  }
  return fabric;
};

const claimData = input => {
  claimChars = [...input];

  const at = claimChars.indexOf("@");
  const colon = claimChars.indexOf(":");

  const id = Number(input.substr(1, at - 2));
  const xPosition = Number(input.substr(at + 1, colon - at - 1).split(",")[0]);
  const yPosition = Number(input.substr(at + 1, colon - at - 1).split(",")[1]);
  const xLength = Number(input.substr(colon + 1).split("x")[0]);
  const yLength = Number(input.substr(colon + 1).split("x")[1]);

  return {id, xPosition, yPosition, xLength, yLength};
};

const addToFabric = (claimData, fabric) => {
  for (const i of Array(claimData.xLength).keys()) {
    for (const j of Array(claimData.yLength).keys()) {
      if (fabric[claimData.xPosition + i][claimData.yPosition + j] === "*") {
        fabric[claimData.xPosition + i][claimData.yPosition + j] = "#";
      } else if (
        fabric[claimData.xPosition + i][claimData.yPosition + j] === "#"
      ) {
        fabric[claimData.xPosition + i][claimData.yPosition + j] = "X";
      }
    }
  }

  return fabric;
};

const blocked = fabric => {
  let numberBlocked = 0;
  for (let i = 0; i < fabric.length; i++) {
    const arr = fabric[i].filter(val => val === "X");
    numberBlocked += arr.length;
  }
  return numberBlocked;
};

const overlap = async stream => {
  let fabric = generateFabricMatrix();

  for await (const claim of streamToClaim(stream)) {
    fabric = addToFabric(claimData(claim), fabric);
  }

  return blocked(fabric);
};

const unique = async stream => {
  let fabric = generateFabricMatrix();
  const cloned = stream.pipe(new PassThrough({encoding: "utf-8"}));

  for await (const claim of streamToClaim(stream)) {
    fabric = addToFabric(claimData(claim), fabric);
  }

  for await (const claim of streamToClaim(cloned)) {
    const data = claimData(claim);

    const totalLength = data.xLength * data.yLength;
    let checkUnique = 0;

    for (const i of Array(data.xLength).keys()) {
      for (const j of Array(data.yLength).keys()) {
        if (fabric[data.xPosition + i][data.yPosition + j] === "#") {
          checkUnique++;
        }
      }
    }
    if (checkUnique === totalLength) {
      return data.id;
    }
  }
};

Main.js:

const claimStream = () => {
  return fs.createReadStream(__dirname + "/input.txt", {
    encoding: "utf-8",
    highWaterMark: 256
  });
};

const main = async () => {
  try {
    const part1 = await overlap(claimStream());
    console.log({part1});
    const part2 = await unique(claimStream());
    console.log({part2});
  } catch (e) {
    console.log(e.message);
    process.exit(-1);
  }

[Paula Gearon]

I did my part 1 similarly: I wrote the ID to each cell in it’s rectangle, unless the cell wasn’t zero, in which case I wrote -1. At the end, I counted the -1 values.

The second step was a little different. First of all, I added the ID to a set of IDs that were OK. Then I went through each cell of its rectangle. If the cell is zero, then update it to the current row’s ID. If it had a number in it, then that’s the ID of the most recent rectangle to overlap that cell; so remove the found ID and the current ID from the set of good IDs. Then set all the cells in the entire rectangle to its ID. At the end, the set of good IDs has a single element.

It sounds tricky, but it’s literally just a couple of lines of code

[Bjarne Magnussen]

Puh, that was a tough one for me today. I started out by counting the number of claims for each square on the "canvas" which gave me a correct aswer. However, I later misunderstand part 2 thinking I should find completely unclaimed squares that could be filled out by one claim...

After cheating a little and getting inspirations for solutions I have implemented a Golang solution for today. At least I am happy that I could implement it in Golang without any prior experience using Golang:

Part 1 and 2 together:

package main

import (
    "bufio"
    "fmt"
    "os"
    "regexp"
    "strconv"
)

type coord struct {
    l int
    t int
}

// readLines reads a whole file into memory
// and returns a slice of its lines.
func readLines(path string) ([]string, error) {
    file, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer file.Close()

    var lines []string
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        lines = append(lines, scanner.Text())
    }
    return lines, scanner.Err()
}

func mapClaims(data []string) (map[coord][]int, map[int][]int) {
    m := make(map[coord][]int)
    claims := make([][]int, len(data))
    overlaps := make(map[int][]int)
    r, _ := regexp.Compile("-?[0-9]+")
    for i, d := range data {
        claimsVal := r.FindAllString(d, -1)
        for _, valStr := range claimsVal {
            val, _ := strconv.Atoi(valStr)
            claims[i] = append(claims[i], val)
        }
        id := claims[i][0]
        startX := claims[i][1]
        startY := claims[i][2]
        width := claims[i][3]
        height := claims[i][4]
        overlaps[id] = []int{}
        for l := startX; l < startX+width; l++ {
            for t := startY; t < startY+height; t++ {
                claimSet := m[coord{l, t}]
                for _, number := range claimSet {
                    overlaps[number] = append(overlaps[number], id)
                    overlaps[id] = append(overlaps[id], number)
                }
                claimSet = append(claimSet, id)
                m[coord{l, t}] = claimSet
            }
        }

    }
    return m, overlaps
}

func main() {
    start := time.Now()
    data, err := readLines("input")
    if err != nil {
        panic(err)
    }

    m, overlaps := mapClaims(data)

    partA := 0
    for _, v := range m {
        if len(v) >= 2 {
            partA++
        }
    }
    fmt.Println(partA)

    partB := []int{}
    for k, v := range overlaps {
        if len(v) == 0 {
            partB = append(partB, k)
        }
    }
    fmt.Println(partB[0])
    elapsed := time.Since(start)
}

[E. Choroba]

Perl solutions. The first part was easy, just counting how many times each square occurred. The second part was trickier and the naive solution was too slow, so I summoned some regular expressions to help me:

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my %grid;
while (<>) {
    my ($x, $y, $w, $h) = /#\d+ @ (\d+),(\d+): (\d+)x(\d+)/;
    for my $j ($y .. $y + $h - 1) {
        for my $i ($x .. $x + $w - 1) {
            ++$grid{"$i $j"};
        }
    }
}

say scalar grep $grid{$_} > 1, keys %grid;

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my %grid;
while (<>) {
    my ($id, $x, $y, $w, $h) = /(#\d+) @ (\d+),(\d+): (\d+)x(\d+)/;
    for my $j ($y .. $y + $h - 1) {
        for my $i ($x .. $x + $w - 1) {
            $grid{"$i $j"} .= $id;
        }
    }
}

my $all = join ':', values %grid;
my %uniq;
undef @uniq{ $all =~ /(?:^|:)(#\d+)(?:$|:)/g };
for my $id (keys %uniq) {
    say($id), last if $all !~ /\d$id/ && $all !~ /$id#/;
}