Advent of PBT 2021 - Day 21

/**
 * For the Christmas market, Santa is looking for a place.
 *
 * For each market of the world, he has to check if it can land with
 * his 8 reindeers and his sleigh. He is looking for help to compute
 * that quickly as Christmas is coming really really soon.
 *
 * Check whether there is an area of consecutive true that can
 * contain requestedArea and return its upper-left corner.
 *
 * @param map - A map of boolean value, true for available, false
 *              otherwise. Indexed by map[y][x]
 * @param requestedArea - The area to look for
 *
 * map.length corresponds to the height of the map
 * map[0].length corresponds to the width of the map
 *
 * @returns
 * - the upper-left corner of the area,
 *   whenever there is one place in the map having with
 *   rectangular width x height surface with only true
 * - undefined if no such area exists
 */
declare function findPlaceForSanta(
  map: boolean[][],
  requestedArea: { width: number; height: number }
): { x: number; y: number } | undefined;

it("should find a place for santa given the map has one with exact size", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, false, true, true, true],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 2 });

  // Assert
  expect(location).toEqual({ x: 3, y: 0 });
});

it("should find a place for santa given the map has one larger", () => {
  // Arrange
  const map = [
    [false, false, true, true, true, true],
    [false, true, false, true, true, true],
    [false, false, false, true, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 2 });

  // Assert
  expect(location).toEqual({ x: 3, y: 0 });
});

it("should not find the requested place if height is too small", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, false, true, true, true],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 3 });

  // Assert
  expect(location).toBe(undefined);
});

it("should not find the requested place if width is too small", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, false, true, true, true],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 4, height: 2 });

  // Assert
  expect(location).toBe(undefined);
});

it("should not find the requested place if place is not rectangular", () => {
  // Arrange
  const map = [
    [false, false, false, true, true, true],
    [false, false, true, true, true, false],
    [false, false, false, false, false]
  ];

  // Act
  const location = findPlaceForSanta(map, { width: 3, height: 2 });

  // Assert
  expect(location).toBe(undefined);
});