Advent of Code 2019 Solution Megathread - Day 8: Space Image Format

Hooray! A reason to make cool gifs^TM.

Day 8 - The Problem

In order to finish booting a Elvish Mars Rover, they sent us a picture of the password. Credit where credit is due, the elves managed to at least encrypt the image file, so they have some security sensibility at least. Unfortunately, we have to build our own decryptor.

Humblebrag: I was out partying all day (playing board games!), and I want people to have a place to post. I'll update with a snappy summary when I finish the problem (probably tomorrow).

Part 1 was a simple counting problem. The main hurdle seemed to be correctly chunking the input data into the proper layers.

Part 2 also seemed strangely straightforward compared to Day 07, but maybe the list comprehension sugar of my chosen language simplified more than I realized.

Phew! I'm catching back up to where I wanted to be faster than I expected.

Ongoing Meta

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Languages Seen On Day 07

• javascript x 3
• python x 2
• c
• clojure
• haskell
• kotlin
• swift

Comments

[Sarah]

Such a big contrast with yesterday and especially friday.

Quick and dirty Python solution:

# Get the input
from input import puzzle_input

# Set the width and height
width = 25
height = 6

# Split the input up in layers
layers = []
layer = ""
for index in range(0,len(puzzle_input) + 1):
    if index % (width * height) == 0:
        if layer:
            layers.append(layer)
        layer = ""

    if index < len(puzzle_input):
        layer += puzzle_input[index]

# Loop through the colors
index = 0
colors = ""
while index < len(layers[0]):
    for layer in layers:
        if layer[index] != "2":
            if layer[index] == "0":
                colors += " "
            else:
                colors += "1"
            break
    index += 1

    if index % width == 0:
        colors += "\n"


print(colors)

[RobertCram]

Hi Sarah,

this one is driving me crazy. I've got exact the same solution you have, but I don't know how to submit it.

I've tried submitting the solution as a string of "0" and "1", but that doesn't work. Same for a string of spaces and "1".

Is there something I'm not seeing?

Any help would be appreciated :)

[Sarah]

If you print it like in my example, it should display letters. For example

 11    
1  1 
1      
1      
1  1 
 11   

Would be a C. Just type the letters in as a solution :)

[RobertCram]

Thanks Sarah. That did the trick. Glad to be past this one. Lots of catching up to do :)

[Sarah]

Glad I could help :) I’m very far behind as well, have been out sick the past week and a half so didn’t get much done lately. Good thing I have two weeks of vacation coming up.

[Jon Bristow]

Part 1:

is the number of 1 digits multiplied by the number of 2 digits

Should be an integer number. Mine was in the 10e4 range.

Part 2

What message is produced after decoding your image?

This answer should be a string of capital letters. (Regex: [A-Z]+) Mine was 5 letters long

You’ll have to use your monkey meat based ocr system unless you’re a maniac who has a python one on hand.

[RobertCram]

Thanks Jon. A bit of squinting helped :)

[Rizwan]

Finally somthing which doesn't involve with opcode :P

Solution in swift

import Cocoa

let width = 25
let tall = 6

let digits = input.compactMap{ Int(String($0))}
let numberOfLayer = digits.count/(width * tall)

var startIndex = 0
let layers = (1...numberOfLayer).map{ layerNumber -> Array<Int> in
    let count = (width * tall) * layerNumber
    let layer = digits[startIndex..<count]
    startIndex = count
    return Array(layer)
}

func partTwo() {
    var result: [Int] = Array.init(repeating: 0, count: width * tall)

    let first = layers.first!

    for (index,value) in first.enumerated() {
        if value == 0 || value == 1 {
            result[index] = value
        }
        else {
            for layer in layers.dropFirst() {
                if (layer[index] == 0 || layer[index] == 1) {
                    result[index] = layer[index]
                    break
                }
            }
        }
    }

    startIndex = 0
    while true {
        let count = width + startIndex
        let value = result[startIndex..<count]
        startIndex = count
        print(value)
        if startIndex >= result.count {
            break
        }
    }
}

func partOne() {
    var low:[Int] = []
    var lowestCount: Int = Int.max
    for layer in layers {
        let dict = layer.reduce(into: [:]) { counts, number in
            counts[number, default: 0] += 1
        }
        let count = dict[0]
        if let count = count {
            if count < lowestCount {
                lowestCount = count
                low = layer
            }
        }
    }
    let dict = low.reduce(into: [:]) { counts, number in
        counts[number, default: 0] += 1
    }
    let result = (dict[1] ?? 0) * (dict[2] ?? 0)
    print("Result is : \(result)")
}

partOne()
partTwo()

[Johnny]

Finally, a problem made for FP again.
First, a small utility function to partition an encoded image into its layers:

; Returns a sequence of the layers in an encoded image starting from the bottom layer. Not lazy
(defn layers [image dimensions]
  (reverse (partition (apply * dimensions) image)))

Part 1:

; For an encoded image (sequence of chars or string) and dimensions in the format [x y],
; finds the layer that has the least '0' pixels and calculates the value required to solve part 1.
(defn corruption-test [image dimensions]
  (let [least-zeros-layer (apply min-key #(% \0) (map frequencies (layers image dimensions)))]
    (* (least-zeros-layer \1) (least-zeros-layer \2))))

Part 2:

; Layers a pixel onto a base pixel. If the new pixel is transparent, returns the base pixel, else the new pixel.
(defn layer [base-pixel new-pixel]
  (if (= \2 new-pixel) base-pixel new-pixel))

; Returns a suited string representation for an encoded pixel.
(defn pixel-to-str [pixel]
  (if (= pixel \0) " " "█"))

; Decodes an encoded image (raw string or sequence of chars).
; Splits the input into layers, reduces them by layering them on top of each other,
; maps each pixel to an according string representation, partitions the result into rows
; (depicted by the provided dimensions) and returns them as a string joined with new lines.
(defn decode [image dimensions]
  (apply str (flatten (interpose "\n" (partition (dimensions 0) (map pixel-to-str (reduce (partial map layer) (layers image dimensions))))))))

(Full code: github.com/jkoenig134/AdventOfCode...)

[Stephanie Hope]

This one was pretty straightforward for me, aside from a silly mistake at the end which was making my image a mess. I'm much happier about the puzzles now that I've given myself permission to skip any that involve the word 'intcode'!

$width = 25;
$height = 6;

$input = file_get_contents("input8.txt");
$num_layers = strlen($input) / ($width * $height);
$layer_size = strlen($input) / $num_layers;
$layers = str_split($input, $layer_size);

$min = get_fewest_zero($layers);
echo "Part 1: ".substr_count($layers[$min], "1")*substr_count($layers[$min], "2")."\n";

$image = decode_image($layers, $width, $height);
display_image($image);

function display_image($image){
    foreach ($image as $lines){
        foreach ($lines as $pixel){
            if ($pixel=="1"){
                echo "#";
            } else echo " ";
        }
        echo "\n";
    }
}

function decode_image($layers, $width, $height){
    $final_image = array_fill(0, $height, array_fill(0, $width, " "));
    foreach ($layers as $layer){
        $lines = str_split($layer, $width);
        foreach ($lines as $k=>$line){
            $chars = str_split($line);
            foreach ($chars as $m=>$char){
                if ($char != "2"){
                    if ($final_image[$k][$m] == " "){
                        $final_image[$k][$m] = $char;
                    }
                }
            }
        }
    }
    return $final_image;
}

function get_fewest_zero($layers){
$zeros_per_layer = array();
    foreach ($layers as $num=>$layer){
        $zeros_per_layer[$num] = substr_count($layer, "0");
    }
    return min(array_keys($zeros_per_layer, min($zeros_per_layer)));
}

[Ali Spittel]

This felt like a big step down in difficulty from graph traversals and CPU madness!

def get_layer(x, y, data):
    start = 0
    while start < len(data):
        yield data[start:start + (x * y)]
        start += x * y


LAYER_HEIGHT = 6
LAYER_WIDTH = 25

with open('input.txt') as _file:
    data = _file.read()
    layers = [layer for layer in get_layer(LAYER_HEIGHT, LAYER_WIDTH, data)]
    least_zeroes = sorted(layers, key=lambda x: x.count("0"))[0]
    print(f'Part 1: {least_zeroes.count("1") * least_zeroes.count("2")}')

    stacked_pixels = ""
    for coordinate in range(LAYER_HEIGHT * LAYER_WIDTH):
        done = False
        starting_idx = 0
        while not done:
            if layers[starting_idx][coordinate] == "2":
                starting_idx += 1
            else:
                done = True
                stacked_pixels += " " if layers[starting_idx][coordinate] == "0" else "1"

    start = 0
    print("Part 2: ")
    while start < len(stacked_pixels):
        print(stacked_pixels[start:start + LAYER_WIDTH])
        start += 25

[Neil Gall]

Felt like a Kotlin day today. Pretty simple compared to yesterday.

import java.io.File

typealias Pixel = Char

const val BLACK: Char = '0'
const val WHITE: Char = '1'
const val TRANSPARENT: Char = '2'

data class Size(val width: Int, val height: Int) {
    val pixels: Int = width * height
}

data class Layer(val pixels: List<Pixel>)

data class SpaceImageFormat(val size: Size, val layers: List<Layer>)

fun String.decode(size: Size): SpaceImageFormat =
    SpaceImageFormat(
        size = size,
        layers = trim().asIterable().chunked(size.pixels).map(::Layer)
    )

fun transparentLayer(size: Size): Layer =
    Layer(List<Pixel>(size.pixels) { TRANSPARENT })

fun Layer.countPixels(pixel: Pixel): Int =
    pixels.count { p -> p == pixel }

fun Pair<Pixel, Pixel>.merge() =
    if (first == TRANSPARENT) second else first

fun Layer.merge(next: Layer): Layer =
    Layer(pixels.zip(next.pixels).map { p -> p.merge() })

fun Layer.render(size: Size): String =
    pixels.map { p -> if (p == WHITE) '#' else ' ' }
        .chunked(size.width)
        .map { row -> row.joinToString("") }
        .joinToString("\n")

fun part1(image: SpaceImageFormat): Int {
    val layerWithLeastZeros = image.layers.minBy { layer -> layer.countPixels('0') }!!
    val ones = layerWithLeastZeros.countPixels('1')
    val twos = layerWithLeastZeros.countPixels('2')
    return ones * twos
}

fun part2(image: SpaceImageFormat): String =
    image.layers.fold(transparentLayer(image.size), Layer::merge)
        .render(image.size)

fun main() {
    val image = File("input.txt").readText().decode(Size(25, 6))
    println("Part 1... ${part1(image)}")
    println("Part 2...\n${part2(image)}")
}

[E. Choroba]

Using my native programming language, Perl:

Part 1

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

my $SIZE = 25 * 6;

open my $in, '<', shift or die $!;

my $min = $SIZE;
my $result;
while ($SIZE == read $in, my $layer, $SIZE) {
    my $zeros = $layer =~ tr/0//;
    if ($zeros < $min) {
        my $ones = $layer =~ tr/1//;
        my $twos = $layer =~ tr/2//;
        $result = $ones * $twos;
        $min = $zeros;
    }
}
say $result;

Part 2

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

my $WIDTH = 25;
my $SIZE = $WIDTH * 6;

open my $in, '<', shift or die $!;

my $result = '2' x $SIZE;
while ($SIZE == read $in, my $layer, $SIZE) {
    for my $i (0 .. $SIZE - 1) {
        my $front = substr $result, $i, 1;
        next if $front != 2;

        my $back  = substr $layer,  $i, 1;
        substr $result, $i, 1, $back;
    }
}
say $result =~ s/.{$WIDTH}\K/\n/gr =~ tr/01/ #/r;

Both solutions use the transliteration operator tr/// a lot. It's because it not only replaces characters one for one, but also returns the number of given characters in a string.

[Matt Ellen-Tsivintzeli]

SO much less difficult than yesterday. It took me a while to read the instructions correctly (need to sleep), but then I was away :D

function Pic(width, height, pixels)
{
    this.layers = [];
    let layerPixelCount = width * height;
    for(let pi = 0; pi < pixels.length; pi += layerPixelCount)
    {        
        let layerpixels = pixels.slice(pi, layerPixelCount+pi);
        let layer = new Layer(width, height, layerpixels)
        this.layers.push(layer);
    }
    this.width = width;
    this.height = height;
    this.pixels = pixels;
}

Pic.prototype.crc = function()
{
    let zerocount = Number.MAX_SAFE_INTEGER;
    let result = 0;
    for(let li = 0; li < this.layers.length; li++)
    {
        let layer = this.layers[li];
        let zc = layer.nCount(0);
        if(zc < zerocount)
        {
            zerocount = zc;
            let ones = layer.nCount(1);
            let twos = layer.nCount(2);
            result = ones*twos;
        }
    }
    return result;
};

Pic.prototype.render = function()
{
    let renderedLayer = new Layer(this.width, this.height, this.layers[0].pixels.slice(0, this.layers[0].pixels.length));
    for(let li = 1; li < this.layers.length; li++)
    {
        renderedLayer.replaceTransparent(this.layers[li].pixels);
    }

    console.log(renderedLayer.toString());
}

function Layer(width, height, pixels)
{
    this.width = width;
    this.height = height;
    this.pixels = pixels;
}

Layer.prototype.getRow = function(y)
{
    let start = y * this.width;
    let end = (y+1) * this.width;
    return this.pixels.slice(start, end);
};

Layer.prototype.nCount = function(n)
{
    return this.pixels.reduce((acc, p) => p === n ? (acc+1) : acc, 0);
}

Layer.prototype.replaceTransparent = function(newPixels)
{
    for(let pi = 0; pi < this.pixels.length; pi++)
    {
        if(this.pixels[pi] == 2)
        {
            this.pixels[pi] = newPixels[pi];
        }
    }
}

Layer.prototype.toString = function()
{
    let str = '';
    for(let y = 0; y < this.height; y++)
    {
        str += this.getRow(y).map(p =>
                                  {
                                      let result = '';
                                      switch(p)
                                      {
                                          case 0: result = '\u25af'; break;
                                          case 1: result = '\u25ae'; break;
                                      }
                                      return result;
                                  }).join('');
        str += '\n';
    }
    return str;
};

function day8()
{
    let pixels = document.querySelector('pre').innerHTML.trim().split('').map(s => parseInt(s));
    let pic = new Pic(25, 6, pixels);
    console.log('crc', pic.crc());
    pic.render();
}

[Linda Thompson]

Horray, a day I could finish! ;) I've been quite as I'm still struggling to solve part 2 for both day 6 and day 7....taking a break from those for a few days! (So I say, anyways lol)

JavaScript solution below - I used the Chalk library to colorize my text so the image was easier to read, and grabbed a screenshot. A little sad my image didn't spell out anything obvious, like I saw some other people's on the subreddit! My little terminal snowman makes me happy though. lol :)

Also certain this could have been done in fewer passes through the layers, but it was still very fast so not concerned about it.

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

const data = fs.readFileSync('../2019 Solutions/inputs/day08input.txt').toString();

const input = data.split('').map(Number);

// image will be 25 px wide (rows) by 6 px tall (cols)
// so each layer is 25x6 - need to know how many of each digit (0,1,2) exist on ea layer
// find layer with the fewest 0s, then find # of 1s x # of 2s
let width = 25;
let height = 6;

let layers = [];
let zeros = 0;
let ones = 0;
let twos = 0;

let lowestZeros = 0;
let multi = 0;

let currRow = [];
let currLayer = [];
let currCol = 1;

// build out the layers
for (let i = 0; i <= input.length; i++) {
  if (currRow.length < width) {
    currRow.push(input[i]);
  } else if (currRow.length === width) {
    if (currCol < height) {
      currLayer.push(currRow);
      currRow = [];
      currRow.push(input[i]);
      currCol++;
    } else if (currCol === height) {
      currLayer.push(currRow);
      layers.push(currLayer);
      currLayer = [];
      currRow = [];
      currCol = 1;
      currRow.push(input[i]);
    }
  }
}

// part 1 - count the values
layers.forEach(arr => {
  for (let i = 0; i < arr.length; i++) {
    let currArr = arr[i];
    for (let c = 0; c < currArr.length; c++) {
      let val = currArr[c];
      if (val === 0) {
        zeros++;
      } else if (val === 1) {
        ones++;
      } else if (val === 2) {
        twos++;
      }
    }
  }
  if (lowestZeros === 0) {
    lowestZeros = zeros;
      multi = ones * twos;
  } else if (zeros < lowestZeros) {
      lowestZeros = zeros;
      multi = ones * twos;
    }
    ones = 0;
    twos = 0;
    zeros = 0;
});

console.log(`Part 1: ones * twos is ${multi}`);

let finalImage = [];
let singleRow = [];

// part 2 - determine which pixels show up
layers.forEach(layer => {
  for (let y = 0; y < layer.length; y++) {
    for (let x = 0; x < layer[y].length; x++) {
      if (finalImage[y]) {
        singleRow = finalImage[y];
        let data = singleRow[x];
        if (data === 2) {
          if (layer[y][x] === 0) {
            singleRow.splice(x, 1, 0);
          } else if (layer[y][x] === 1) {
            singleRow.splice(x, 1, 1);
          }
        }
        } else {
          singleRow = layer[y];
        } 
      }
    finalImage.splice(y, 1, singleRow);
  }
})

// colorize each pixel to read message
finalImage.forEach(row => {
  for (let h = 0; h < row.length; h++) {
    if (row[h] === 0) {
      row[h] = chalk.black(0);
    } else if (row[h] === 1) {
      row[h] = chalk.white.bgWhite(1);
    } else if (row[h] === 2) {
      row[h] = chalk.hidden(2);
    }
  }
  row.join();
  console.log(`${row}`);
})

[Christopher Kruse]

Nice to have an easier problem after 2/5/7. :)

Did it in Ruby this time (I'm a few days behind, so I'm working on catching up):

module Day8
  WIDTH = 25
  HEIGHT = 6

  def self.image_layers(input)
    layer_counts = []
    input.split('').each_slice(WIDTH*HEIGHT) do |layer|
      layer_counts << layer
    end
    layer_counts
  end

  def self.fewest_zeroes(layers)
    frequencies = layers.map do |layer|
      layer.inject(Hash.new(0)) {|hash, n| hash[n] += 1; hash}
    end
    frequencies.sort_by {|l| l['0']}
  end

  def self.merge_layers(layers)
    layers.inject([]) do |top, layer|
      top = layer if top.empty?
      top.zip(layer).map do |p1, p2|
        if ['0','1'].include? p1
          p1
        elsif ['0','1'].include? p2
          p2
        else
          p1
        end
      end
    end
  end

  def self.print_layer(layer)
    layer.each_slice(WIDTH) {|line| puts line.join.gsub('0',' ')}
  end
end

# Execution
layers = Day8.image_layers(File.read('resources/2019-08-input').strip)
lowest = Day8.fewest_zeroes(layers)[0]

puts lowest['1'] * lowest['2']
puts ""
Day8.print_layer(Day8.merge_layers(layers))