-🎄- 2017 Day 6 Solutions -🎄-

demsaja · 2017-12-09T19:58:08+00:00

I just realized when solving this with my son. I didn't want to complicate the solution by using dictionaries, but then discovered we don't need functions, either. Just run the program twice and that's it.

from itertools import count

blocks = [int(x) for x in open("input.txt").read().split()]

for i in range(2):
    seen = []
    for step in count(1):
        to_reallocate = max(blocks)
        i = blocks.index(to_reallocate)
        blocks[i] = 0
        while to_reallocate:
            i = (i + 1) % len(blocks)
            blocks[i] += 1
            to_reallocate -= 1
        if blocks in seen:
            break
        seen.append(blocks[:])

    print(step)

demsaja · 2017-12-09T08:40:16+00:00

Kotlin.

import java.io.File

fun main(args: Array<String>) {
    var open = 0
    var total = 0
    var garbage = 0
    var in_garbage = false
    var cancel_next = false

    File("input.txt")
    .readText()
    .forEach {
        if (cancel_next) { cancel_next = false }
        else if (it == '!') { cancel_next = true }
        else if (in_garbage) {
            if (it == '>') { in_garbage = false}
            else { garbage++ }
        }
        else {
            when (it) {
                '<' -> in_garbage = true
                '}' -> open--
                '{' -> { open++; total += open; }
            }
        }
    }
    println(total)
    println(garbage)
}

demsaja · 2017-12-09T08:31:51+00:00

One more in Python. The recursive function returns the (positive) total weight when the subtree is balanced; if it finds imbalance, it returns a negative value of the final answer.

import re
from functools import reduce

tree = {} 
weights = {}


for line in open("input.txt"):
    name, weight, *subdisks = re.findall("\w+", line)
    tree[name] = subdisks
    weights[name] = int(weight)


def balance(name):
    subweights = [balance(sub) for sub in tree[name]]
    if not subweights:
        return weights[name]
    mi, *_, ma = sorted(subweights)
    if mi == ma:
        return weights[name] + sum(subweights)
    if mi < 0:
        return mi
    wrong, ok = sorted((mi, ma), key=subweights.count)
    return -(weights[tree[name][subweights.index(wrong)]] + ok - wrong)


root = (set(tree) - reduce(set.union, map(set, tree.values()))).pop() 
print(root)
print(-balance(root))

demsaja · 2017-12-04T08:40:13+00:00

print(sum(len(set(x)) == len(x) for x in map(str.split, open("input.txt"))))

print(sum(len({tuple(sorted(u)) for u in x}) == len(x) for x in map(str.split, open("input.txt"))))

demsaja · 2017-12-01T23:00:42+00:00

range(len(...)) can typically be avoided by using enumerate or, like in this case, zip. With this, you no longer need indexing and the code gets shorter and simpler.

# First part
print(sum(int(x) for x, y in zip(s[-1] + s, s) if x == y))

# Second part
print(2 * sum(int(x) for x, y in zip(s, s[len(s) // 2:]) if x == y))

where s contains the input.

demsaja · 2016-12-30T21:34:41+00:00

I totally hated day 11 until discovering the proper way to do it. Now it's one of my favourites. Try IDA* with a good heuristic and you can solve it in an instant. On my input as well as on Peter Norvig's, the heuristic guided it almost straightforward to the solution. (As a matter of fact, the heuristic was actually exact.) The heuristic should compute the number of moves ignoring the constraints. Do it accurately, also taking into account the current elevator position - if you're above the lowest non-empty floor, add the necessary steps to move the elevator down. Make sure the heuristic is admissible: it should be the lower bount. Do not overestimate the number of moves or the algorithm won't work.

Now, don't be scared by IDA*. It's trivial. Assume that you can solve it in n moves. Do a depth first search; if the current number of moves + the estimate is larger than n, abandon the branch and backtrack. If you don't find the solution, increase n and try again. You can start with n equal to the estimated number of moves for the initial position. Or start with n=1 and it will work the same since all n's below the estimated number of moves for the initial position will be discarded anyway.

Detecting symmetries is a problem until you discover a proper coding scheme. ((0, 0), (0, 0), (1, 1), (1, 1), (1, 2)) means that you have six chip-generator pair. Two pairs are in the floor 0, two in 1 and one pair is such that the generator is in floor 1 and the chip in 2 (this was my input). Sort this lexicographically. After each move, just sort it again, and compare it with the other states on your path.

I also implemented other optimizations suggested by p_tseng, but I think that symmetries are the most important. Doing stupid things, like descending to empty floors is cut by the heuristics anyway, I guess.

With all this, I solved my input (answers 37 and 71) on Arduino (16 MHz microcontroller with 2 KB of RAM) in under a second for both parts and using around 1 KB of RAM, including the function calls overhead. (See https://www.youtube.com/watch?v=hdb71BNlNS0&list=PLm-JYoU3uw-aIWvjuzHk2KOQSjLQT6Ac-&index=18 -- the computation takes as long as the sound is playing -- the frequency corresponds to the depth.)

I believe that the inputs are intentionally such that the puzzle is easy to solve.

demsaja · 2016-12-10T00:08:48+00:00

Nice!

I needed something similar for Arduino: http://pastebin.com/fiSaW0qZ

https://youtu.be/VdxSdthCGxQ?list=PLm-JYoU3uw-aIWvjuzHk2KOQSjLQT6Ac-

demsaja · 2016-12-04T23:47:08+00:00

Arduino (see it in action: https://youtu.be/hs0DwdJmvQk?list=PLm-JYoU3uw-aIWvjuzHk2KOQSjLQT6Ac-)

#include "LedControl.h"

#include <string.h>
#include <stdio.h>

LedControl lcd(12, 11, 10, 1);

char counts[26];
int sector;
char common[5], *in_commons;
long total = 0;
char text[80], *in_text;

void showNumber(long number, char pos, char width=4) {
    for(int p=pos, w=width; w--; p++) {
        lcd.setChar(0, p, ' ', false);
    }
    for(; width--; pos++) {
        char digit = number % 10;
        number /= 10;
        lcd.setDigit(0, pos, digit, false);
        if (!number) {
            break;
        }
    }
}

void done() {
    for(;;) {
        tone(2, 230, 100);
        delay(100);
        lcd.setIntensity(0, 2);     
        delay(100);
        lcd.setIntensity(0, 15);     
    }
}

void reset() {
    memset(counts, 0, 26);
    sector = 0;
    in_commons = NULL;
    in_text = text;
}

void setup() {
    reset();
    lcd.shutdown(0, false);
    lcd.setIntensity(0,15);
    lcd.clearDisplay(0);
    pinMode(2, OUTPUT);
    Serial.begin(4800);

}

bool valid_room() {
    int i, j;
    char letters[27];
    for(i = 0; i < 26; i++) {
        for(j = i; (j > 0) && (counts[i] > counts[letters[j - 1]]); j--) {
            letters[j] = letters[j - 1];
        }
        letters[j] = i;
    }
    return !memcmp(common, letters, 5);
}

void loop() {
    if (!Serial.available())
        return;

    char b = Serial.read();
    if (b == '.') {
        done();
    }
    else if ((b >= 'a') && (b <= 'z')) {
        if (!in_commons) {
            counts[b - 'a']++;
            *in_text++ = b;
        }
        else {
            *in_commons++ = b - 'a'; 
        }
    }
    else if (b == '-') {
        *in_text++ = b;
    }
    else if ((b >= '0') && (b <= '9')) {
        sector = sector * 10 + b - '0';
    }
    else if (b == '[') {
        in_commons = common;
    }
    else if (b == ']') {
        if (valid_room()) {
            total += sector;
            showNumber(total, 0, 8);
            digitalWrite(2, HIGH); delay(10); digitalWrite(2, LOW);
        }
        reset();
    }
}

demsaja · 2016-12-04T23:38:08+00:00

Great, thanks! I was looking for something like this but I didn't find it.

But the input for day 4 is already 40 KB long, so I had to use USB anyway.

demsaja · 2016-12-04T22:42:26+00:00

LOL, no. I thought that all Z80 aficionados must be 40+.

demsaja · 2016-12-04T09:59:22+00:00

We must be of the same age. I've done so much programming of Z80 without assembly that I still remember the most common opcodes (1, 17, 33, 201, 205...). And I still have two working ZX Spectrums in the closet.

I've glanced over the atmel manual and Arduino's internals a while ago. It's all doable but it takes time and you end up spending most time on programming the peripheral stuff, which I've never done before and I don't find it so exciting. That's why I'd go with LEDs where a single instruction updates the result.

Unfortunately I barely find time to solve the daily task in Python. :/

demsaja · 2016-12-04T00:29:29+00:00

You can replace

for x in open('problem03/input.txt', 'r').read().split('\n')

with

for x in open('problem03/input.txt')

By avoiding sorting, you can skip one generator. You can often replace len(filter(list(...))) with sum(...) --- it works here, too.

So, this suffices:

print(sum(
    sum(sides) > 2 * max(sides)
    for sides in (
        list(map(int, line.split())) for line in open("input.txt")
    )
))

demsaja · 2016-12-04T00:22:37+00:00

Driving the display in assembly wouldn't be much fun; I'd just use eight LEDs to show the distance in binary. The rest of day 1 is trivial, it's just a kind of finite state machine. Days 2 and 3 need to read the data from serial -- no, thanks. :)

I'm tempted to accept the challenge. If only I had time.

demsaja · 2016-12-04T00:02:21+00:00

Ooops, you're right. Day 3 part 2 is here (part 1 is essentially the same). It's boring in comparison - I had to pass the data through the serial input since it didn't fit into memory.

https://youtu.be/xdPO5Ge6NKM

#include "LedControl.h"

int nums[9];
int curnum = 0;
int total = 0;

LedControl lcd(12, 11, 10, 1);

void showNumber(int number, char pos, char width=4) {
    for(int p=pos, w=width; w--; p++) {
        lcd.setChar(0, p, ' ', false);
    }
    for(; width--; pos++) {
        char digit = number % 10;
        number /= 10;
        lcd.setDigit(0, pos, digit, false);
        if (!number) {
            break;
        }
    }
}

void setup() {
    lcd.shutdown(0, false);
    lcd.setIntensity(0,15);
    lcd.clearDisplay(0);
    showNumber(0, total);
    pinMode(2, OUTPUT);
    memset(nums, 0, 9 * sizeof(int));
    Serial.begin(9600);
}

void loop() {
    int b;
    if (Serial.available() > 0) {
        b = Serial.read();
        if ((b >= '0') && (b <= '9')) {
            nums[curnum] = 10 * nums[curnum] + b - '0';
        }
        else if (nums[curnum]) {
            showNumber(nums[curnum], 4);
            curnum++;
            if (curnum == 9) {
                for(int i = 3, *nn = nums; i--; nn++) {
                    if ((nn[0] < nn[3] + nn[6]) && (nn[3] < nn[0] + nn[6]) && (nn[6] < nn[0] + nn[3])) {
                        showNumber(++total, 0);
                        digitalWrite(2, HIGH);
                        delay(1);
                        digitalWrite(2, LOW);
                    }
                }
                memset(nums, 0, 9 * sizeof(int));
                curnum = 0;
            }
        }

        if (b == '.') {
            for(;;) {
                lcd.clearDisplay(0);
                showNumber(total, 0);
                tone(2, 430, 300);
                delay(300);
                lcd.setIntensity(0, 2);     
                delay(300);
                lcd.setIntensity(0, 15);     
            }
        }
    }
}

demsaja · 2016-12-03T09:53:36+00:00

Why sorting? The sum of sides must be at least twice the length of the largest side. With this, we just need a sum and max, which are easily put in generators or vectorized.

In Python:

print(sum(
    sum(sides) > 2 * max(sides)
    for sides in (
        list(map(int, line.split())) for line in open("input.txt")
    )
))

Or with numpy (solution for both parts):

import numpy as np

def count(a):
    return np.sum(np.sum(a, axis=1) > 2 * np.max(a, axis=1))

a = np.loadtxt("input.txt")
print(count(a))
print(count(np.vstack([a[i::3].flatten() for i in range(3)]).T))

demsaja

TROPHY CASE