Advent of Code 2019 D08

Первая половина задачи

Изображения отправляются как последовательность цифр, каждая из которых обозначает цвет пикселя. Пиксели заполняют изображение слева направо и сверху вниз. Каждое изображение состоит из слоёв одинакового размера, которые заполняются таким образом. Первое число представляет из себя левый верхний угол первого слоя, а последнее — правый нижний последнего слоя.

Принимаемое изображение размером 25×6. Чтобы убедиться, что сообщение не повреждено, эльфы просят найти слой, в котором меньше всего нулей, и сообщить число, являющееся результатом умножения числа единиц на число двоек в этом слое.

В качестве исходных данных мы получаем литерал чисел длиной 15000 значений. Рассмотрение показало, что в списке возможны всего три значения: 0, 1 и 2.

Для начала определим две важных константы:

let imgSize = 25 * 6
let imgLayers = inputData.Length / imgSize

Теперь порежем этот поток данных на куски, равные размеру изображения. Возьмём число слоёв, и передадим в функцию отображения, которая из исходного потока будет выкусывать фрагменты. Формула подсчёта местоположения левой и правой границ проста и понятна.

let layers =
    [ 0 .. imgLayers - 1 ] |> List.map (fun x -> inputData.[(x * imgSize)..((x * imgSize) + imgSize - 1)])

Если бы исходные данные не были бы кратны размеру изображения, было бы чуть более интересно.

Для решения первой половины задачи каждый из полученных слоёв мы превратим в структуру, в которой поля отвечают за число нулей, единиц и двоек. Я поначалу думал, что такую структуру можно определить анонимно на месте, но пришлось объявить тип.

Механика функции вполне проста: исходные слои функция List.map отображает в список вышеупомянутых структур, а в качестве функции для отображения выступает лямбда с функцией свёртки (мы сворачиваем слой чисел в одну-единственную структуру, каждый раз возвращая новую её копию).

В конце мы сортируем список структур по значению одного поля — X.

type layerInfo =
    { X : int
      Y : int
      Z : int }

let sortByX =
    layers
    |> List.map (fun x ->
        List.fold (fun acc y ->
            match y with
            | 0 -> { acc with X = acc.X + 1 }
            | 1 -> { acc with Y = acc.Y + 1 }
            | 2 -> { acc with Z = acc.Z + 1 })
            { X = 0
              Y = 0
              Z = 0 } (Array.toList x))
    |> List.sortBy (fun i -> i.X)

Ответ на первую половину задачи:

let answer1 = (List.head sortByX).Y * (List.head sortByX).Z

Вторая половина задачи

Теперь можно расшифровать изображение. Изображение выводится сложением слоёв. Числа означают следующее: 0 соответствует чёрному цвету, 1 белому, а 2 — прозрачности.

Первый слой располагается «впереди», а последний — «позади», так что если в заданной позиции первых двух слоёв пиксель прозрачный, а в третьем чёрный, то в итоговом изображении в этом месте будет чёрный пиксель.

Какое сообщение написано на присланной картинке?

Алгоритмически решение очевидно: проход по первому слою с занесением в итоговое изображение значений 0 или 1, и уход «вглубь» структуры с поиском в той же позиции первого нужного значения.

Для этого создадим рекурсивную функцию, которая принимает список списков (исходную структуру изображения), номер слоя в списке и позицию пикселя в этом слое.

Если находим в слое двойку, переходим на слой ниже (lst + 1) в той же структуре данных с той же позицией. Понятно что тут я поленился поставить проверку — теоретически нужна проверка на глубину слоя в структуре изображения, ведь вполне возможно, что все слои вплоть до последнего будут прозрачными, и на последнем слое программа упадёт, потому что обращение к следующему слою станет невозможным. Но мы просто решаем весёлые задачки.

let rec get (metalist : int [] list) (lst : int) position =
    match metalist.[lst].[position] with
    | 0 -> 0
    | 1 -> 1
    | 2 -> get metalist (lst + 1) (position)

После этого пропускаем число пикселей в изображении через List.map, который в качестве лямбды вызывает нашу рекурсивную функцию и возвращает список из всех значений итогового изображения.

let answer2 = [ 0 .. imgSize - 1 ] |> List.map (fun x -> get layers 0 x)

Вывести итоговый список размером 25×6 — тривиально.