Skip to content

My solutions to the Advent of Code challenges for 2018 (mostly in PHP).

License

Notifications You must be signed in to change notification settings

spytheman/aoc2018

Repository files navigation

December 2018: Advent of Code Solutions

Delyan Angelov

I am doing the Advent of Code puzzles for 2018. This repo contains my solutions of the challenges, as I solve them.

I will push my solutions ONLY AFTER the leaderboard for the day is already full (even though I have not scored so far, and judging by the times of the top 100 performers, it is not likely that I will score at all this year ... most people give their answers before I finish reading and understanding the task, lol).

Contents:

./cookie - NB: You should create this file yourself. It is NOT included in this repo. The file contains a single line like this: session=74506ff802.... You can get it by logging into the https://adventofcode.com website, then seeing your cookies.

./prepare_for_day - A helper script, that prepares a new folder for a given day. It will produce a draft solution in folder dayXX/ , then it will download the input for this day for you. All that remains for you to do then, is the fun part - solving the problem.

    Usage: ./prepare_for_day 2                  

./common.php - This file contains utility functions used by all solutions.

./day*/ - The folders contain the solutions for a given AOC problem.

Common way to do an exercise in Advent of Code:

    0. After the start time of the contest, read the task description on the site.
    1. ./prepare_for_day 17
    2. edit day17/solution.php
    3. ./day17/solution.php 
    4. Cycle through steps 2 and 3, until solution works.
    5. Submit your answer to the site.

Misc.

You can run all the solutions so far like that:

    for i in day*/solution.php; do echo "$i : "; time $i; echo ;done

Solutions and notes about them so far:

Task Solution Comment
Day 1: Chronal Calibration day1/solution.php After implementing Arepeat/2 the rest was very easy.
Day 2: Inventory Management System day2/solution.php Histograms FTW!
Day 3: No Matter How You Slice It day3/solution.php Just extract all numbers without worrying about regexpes and clean parsing...
Day 4: Repose Record day4/solution.php This one took much more time than I expected.
Day 5: Alchemical Reduction day5/solution.php Using range/2 and Azip2/2 to make the pairs that had to be removed in advance, was easy and quick ... In retrospect, a simple scanner would be quicker though.
Day 6: Chronal Coordinates day6/solution.php NB: in future I really should iterate and do testing on the given example input first, because each run on the full input took >10s. Also 'Manhattan distance' = abs(dx) + abs(dy) , and NOT abs(dx+dy) .
Day 7: The Sum of Its Parts day7/solution.php NB: topological sorting and graphs in general are NOT my strong suit. Should exercise them more.
Day 8: Memory Maneuver day8/solution.php Parsing a serialized tree do not always involve an explicit state machine.
Day 9: Marble Mania day9/solution.php Reimplemented the whole solution in C for part 2, since PHP array_slice is slow. In C, I used a doubly linked circular buffer to implement the circle, in which the marbles are placed, which made traversing easy and fast.
*Deque for Day 9) day9/solution.deque.php After seeing a wonderful Python collections.deque based solution, I ported it to PHP using the new Data Structures PHP extension (deque specifically). Result: it works acceptably (i.e. works in linear time. For my input both parts are done in ~13s ... Well it is 51 times slower than the C solution :-) )
Day 10: The Stars Align day10/solution.php NB: PHP is not very good at plotting points, but spreadsheets are.
Day 11: Chronal Charge day11/solution.php Using a precalculated integral image is the key to speeding up part 2 (or recoding in C ... or both). NB: even with the integral image optimization, the PHP solition takes ~5700ms, the C solution takes ~23ms ...
Day 12: Subterranean Sustainability day12/solution.php A cellular (pot) automaton simulator. Did not solve part 2 in code, just eyeballed the output for a 1000 iterations, and derived a formula for the end result, given an unlimited grid.
Day 13: Mine Cart Madness day13/solution.php Works for all inputs now. The problem was the order of checking for crashes with the other cars. (it printed different collision coords than the other solutions, and I had no clue why that happened ... I guessed it is something related to the elimination order of the carts ... "Madness" indeed...).
Day 14: Chocolate Charts day14/solution.php The part 2 calculation takes ~32-33 seconds in PHP. I have no idea for a faster way so far. Update: batching of recipe generation, and then checking for termination once per batch helps very much - runtime reduced to ~17s .
Day 15: Beverage Bandits day15/solution.php WIP
Day 16: Chronal Classification day16/solution.php An emulated VM/CPU, although with very limited capabilities :-) . The solution runs in ~50ms .
Day 17: Reservoir Research day17/solution.php WIP
Day 18: Settlers of The North Pole day18/solution.php Bruteforcing for part 2 was waaayy too slow (~25ms/1 simulated minute => > estimated 289 days realtime waiting time :-( ). The grids does seem to repeat ... So the main optimization was to find the cycle of repetition first, then use it to predict the future grid.
Day 19: Go With The Flow day19/solution.php Reusing the VM instructions from day 16, did not save much, since as always part 2 required heuristcs and actual understanding of the goal of the emulated program. Bruteforcing (even using a fast C emulator it would take ~209 hours for 1 core of my PC ... and it could not be paralelized easily also) was out of the question.
Day 20: A Regular Map day20/solution.php A neat exercise combining parsing and grid walking. Note to self: most problems here do not need full blown lexer/parser/compiler stages... Simple direct interpreters are fine, since the time is too short to do anything else.
Day 21: Chronal Conversion day21/solution.php Rank 810/703 ... best so far, but I really should think more and do not immediately jump to brute forcing first... The essence of the task was to find which r0 values could cause the input program to terminate. The problem is that happens usually after many iterations. Thus it was important to actually understand the part of the input responsible for checking for termination (instruction 28), and also to speed up the whole process by eliminating dummy delay loops (thrown in to discourage bruteforcing).
Day 22: Mode Maze day22/solution.php WIP (runs very slow and after optimization no longer works for all inputs ... NB: need to work on my graph walking and maze path skills).
Day 23: Experimental Emergency Teleportation day23/solution.php Rank 1059/329 (best for me so far)... Learned about how to use Z3 constraint solver - generate a z3 lisp program, and then run z3 over it. Brute forcing was completely out of the question for this day's part 2.
Day 24: Immune System Simulator 20XX day24/solution.php WIP (another game simulation).
Day 25: Four-Dimensional Adventure day25/solution.php A nice little clustering task.

About

My solutions to the Advent of Code challenges for 2018 (mostly in PHP).

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published