I've done a lot of maze solving and grid based puzzles before, and this is one of the most amazing methods I've seen in a long time. It's awesome to learn something new.

Golang even supports this as a native type: https://golang.org/pkg/builtin/#complex128

In Python3 (code):

~/project/advent2018/python $ ./advent.py time 9 Day 09, part a: mean: 15.62 ms median: 15.61 ms stdev: 0.36 ms Day 09, part b: mean: 1631.86 ms median: 1625.05 ms stdev: 23.01 ms

I am pretty sure all 25 were made in advance of December, so wishes of changes may not happen this year.

So far there is a pretty good mix. I can understand math ones not being all that enjoyed by many though, because unless you have the math background, they might seem otherwise impossible.

If you want pure logic/math ones, I'd direct you towards http://projecteuler.net. There are hundreds of problems, most of which are pure logic/math.

Python one-liner:

>![int(''.join(p)) for p in __import__('itertools').permutations('123456789') if all(int(''.join(p[:x]))%x==0 for x in range(1,10))][0]!<

Try it online!

J, both parts:

steps=. 4 2 $ 1 0 0 _1 _1 0 0 1 coords=. 0 0 , [: +/\ [: ; [: (] <@(# ,:)"0 1 steps $~ #) 2 # 1 + i.@>.@%: part1 =. [: +/ <: { coords

neighbors=. (0 0 -.~ > , { ;~ 1 0 1) +"1 ] next_neighbor_sum=. [: +/ ] ({~ ::0:)" 0 [ i. [: neighbors #@] { [ part2=. [: {: ] (] , coords@[ next_neighbor_sum ])^:([ > {:@])^:_ 1:

(part1 ; part2) 277678

We consider a coordinate system with 1 at location 0,0. Positive x goes rightward; positive y goes downward. We generate a flat list of the coordinates, in their correct spiral order. With this approach, part 1 becomes trivial (taking the correct element from the list) and part 2 becomes easier.

Try it online!

Just finished my Warming up with 2015's tasks using <strong>Nim</strong>, and I'm considering to continue using it for this year.

If not Nim, I'll fall back to Python, which I'm the most familiar with.

Rust (beginner)

Not cleaned up in any way

Not particularly proud of this one. I think it probably couldn't be much less rust-like. I wasted like 10 minutes at the end messing with the logic on that ugly c-style loop which is probably why the language doesn't include a for(;;) in the first place

I placed on the leaderboard a few times, but my main goal here was getting solutions running as quickly as possible. I updated many of my solutions based on what others have done, but the repo does have the full history for any day.

I have all 25 days running in 2759.28ms total. For some days I had to resort to parallelization and highly optimized MD5 implementations. For other days, replacing a set or map with a vector or array shaved off tens of milliseconds.

All compilation done was -O3 -march=native -flto (clang) running on my 2016 15" MacBook Pro on battery (not plugged in). The repo's README has loads more information including file sizes, time to solution, and header files utilized.

Asciinema recording: https://asciinema.org/a/c43xa3f9u2uh3830x6qysf7va

Python Bad/Bad

link! for all those people who don't like long code blocks.

One thing I noticed was that you needed an instruction pointer, which I don't believe was stated in the text. I also assumed that an instruction pointer cannot visit the same index twice, but I assume that this challenge, reminiscent of assembly, would have conditionals meaning indexes would be repeated.

For the part 2, I just created a generator to generate different code inputs(no need for deep copy cause strings are immutable!) and a Loader to try out all the different inputs.

Scratch

<strong>https://scratch.mit.edu/projects/458997045/</strong>

Today's big challenge was figuring out how to separate the passports. Originally I was going to do it in a single pass but decided to use one pass to separate passports and another to validate!

Scratch

<strong>https://scratch.mit.edu/projects/457561092/</strong>

Had a lot of fun writing this one! Uses a handwritten implementation of C's `strtok` to do most of the heavy lifting.

I had done just about the same thing, playing the <code>snd</code>s, having missed both today's easter egg as well as this entire thread (at first). D'oh!

PS. I did adjust the frequences slightly to the lower end to make them a wee bit more pleasant.

PS. "Sonification" would've been my choice of words.

I always wanted to use container/ring for something...

import "container/ring"

func ShortCircuitSpinLock(steps, finalOperation int) int { spinLock := ring.New(1) spinLock.Value = 0 for i := 1; i <= finalOperation; i++ { elem := &ring.Ring{Value: i} spinLock.Move(steps).Link(elem) spinLock = elem } return spinLock.Next().Value.(int) }

func AngrySpinLock(steps, finalOperation int) int { var afterZero int var pos int for i := 1; i <= finalOperation; i++ { pos = (pos + steps) % i if pos == 0 { afterZero = i } pos++ } return afterZero }

By the time I figured out this faster solution to part 2, my brute force version (like part 1, but keeping another pointer to the initial element) had long returned the correct answer after about 12 minutes...

There is Project Euler and it has likes hundreds of different coding challenges. It's similar to advent of code in the way it tells you what place you came in 'you were the 10345th user to complete this challenge' for example and it's the same as advent of code where instead of giving in your code to be ran against test cases, they give you the puzzle input. Although it's quite a bit more mathy than AoC, I'd still recommend giving it a try.

This is stunningly beautiful!

About stitching the larger image: did you try a panorama software like hugin?

http://hugin.sourceforge.net/download/

I have used it only for photos so far that had overlapping parts.

For displaying, I found a Photoshop plugin that exports a large image in smaller tiles of different zoom levels that can then be used with an open source map viewer. I use that on my website to show panoramas. I'd be happy to help with that later today if you don't have Photoshop at hand.

Here's a visualization that a colleague made, with ASCIIart: https://asciinema.org/a/XgRN13OQLRkZl8P970dufqbZd.

The viewport doesn't change as in your visual -- which is a nice effect too -- but it's fun to watch.

Went with a more obscure language today - here's my solution for part 2 in io:

file := File with("12-input.txt") lines := file readLines file close

dict := Map clone lines foreach(i, v, nums := v split(" <-> ") dict atPut(nums first, nums last split(", ")) )

start := "0" set := Map clone check := method(x, dict at(x) foreach(i, v, set hasKey(v) ifFalse( set atPut(v) check(v) ) ) )

groups := 0 dict keys foreach(i, v, set hasKey(v) ifFalse( groups = groups + 1 set atPut(v) check(v) ) )

groups println

In Crystal.

First part:

input = File.read("input.txt") count = input.each_line.count do |line| a, b, c = line.split.map(&.to_i) (a + b > c) && (a + c > b) && (b + c > a) end puts count

Second part:

input = File.read("input.txt") count = input.each_line.each_slice(3).sum do |slice| slice.map(&.split.map(&.to_i)).transpose.count do |(a, b, c)| (a + b > c) && (a + c > b) && (b + c > a) end end puts count

/u/brskbk has also developed a less minimalistic clone of Paste called NoPaste that has syntax highlighting (and a few other features) as well.

I'll mention these forks in Day 1's megathread. :)

Leetcode >
> > LeetCode OJ is a platform for preparing technical coding interviews. Pick from an expanding library of more than 190 questions, code and submit your solution to see if you have solved it correctly. It is that easy! > > Our platform currently supports a total of 9 languages: C, C++, Java, Python, C#, JavaScript, Ruby, Bash, MySQL.

aaand here we go:

https://kotlinlang.org/docs/reference/lambdas.html#anonymous-functions

> One other difference between lambda expressions and anonymous functions is the behavior of non-local returns. A return statement without a label always returns from the function declared with the fun keyword. This means that a return inside a lambda expression will return from the enclosing function, whereas a return inside an anonymous function will return from the anonymous function itself.

Python 3

link Wasn't particularly difficult, I just had a hard time understanding what "mask" meant.

For both parts, I created a result array to store the resulting number(shocking I know!) as python gets real fussy with index errors. I just loaded the corresponding number into the result(right to left) and applied the mask.

To write to an array, I just created a recursive function that isn't particularly efficient but it can get the job done. It just goes down through the bin of the number and if there's an X, diverge into 2 paths.

Python 3

link Modified from my original code, I thought originally that I somehow got the correct answer by a fluke, but I was wrong. Current code gives humans more of an intuitive sense of how you would solve it.

Part 1 and Part 2 were relatively simple, there wasn't much to them.

A small interesting bit that I found was that as waypoints are relative to the ship, you don't actually need to move them with the ship. It makes life a lot easier, and somehow I managed to spagetti myself into it! Another small interesting tidbit is that for an [x,y], to rotate it 90 degrees clockwise it is [y, -x] and to rotate it counter clockwise 90 degrees it would be [-y, x].

Python 3 - I spent some time attempting to make it faster

link Today's problem was like Conway's Game of Life.

Part 1 and Part 2 were pretty straight forwards, as you only had to have 2 for loops (and a while one thrown in for part 2!) Then just loop over until no extra changes happen, and then you're done!

I tried to make some optimizations for Part 2 by pre-calculating all the visible seats for each position. However, it didn't really speed the program up by much :c. Any further suggestions for optimization would be appreciated!

C# solution: https://hastebin.com/bolucodacu.csharp

Part 1 took me more time to read than to code. Part 2 I first tried the recursive version of this same algorithm and got a stack overflow, then I had to change it to a long because I was overflowing ints.

Perl

Full Code: hastebin or paste

I made plenty of off-by-one errors and probably overdid array slices, but I didn't feel like writing more c-style for loops. Will hopefully learn some ways to do this without all the nested loops.

Part 1 - Validation:

for (my $i = $preamble; $i < @data; $i++) { my $valid = 0;

VALIDATE: for my $a (@data[$i-$preamble..$i-1]) { for my $b (@data[$i-$preamble..$i-1]) { next if $a == $b;

if ($a + $b == $data[$i]) { $valid = 1; last VALIDATE; } } }

Part 2 - Weakness:

for (my $i = 0; $i < $invalid; $i++) { my $j = $i; my $sum = $data[$j];

$sum += $data[++$j] while $sum < $data[$invalid];

if ($sum eq $data[$invalid]) { my ($a, $b) = [ sort @data[$i..$j] ]->@[0,-1]; say "Part 2: ", $a + $b; last; } }

For Java, you could be using Ideone an online IDE. Works in the browser and stores the compiled programs if you register an account.

Ideone is more than sufficient for the AdventOfCode problems.

It does, but it's funky, you need one argument to be a string, like:

std::string a = "a"; char b = 'b'; std::string ab = a + b;

Here's some practical examples you can run in your browser! http://ideone.com/bLmzdU

TypeScript

Not very performant but it works. Luckily I could re-use 95% of the code for part2. unfortunately Part2 takes a while though.

https://codesandbox.io/s/advent-day7-hunj6?file=/src/part2.ts

TypeScript

I have to say part 2 took way too long but it was fun. I left part 1 as that was my working solution for the first part but obviously I had to re-think the logic a bit for part 2..

https://codesandbox.io/s/advent-day6-4xl3y?file=/src/part2.ts

My SQLite solution

Try it online!

CREATE TABLE input(
  data VARCHAR
);

INSERT INTO input(data)
VALUES('3,4,3,1,2');

WITH split_input(fish, data_str) AS (
  SELECT 
    '',
    data
  FROM input

  UNION ALL

  SELECT
    SUBSTR(data_str, 1, 1),
    SUBSTR(data_str, 3)
  FROM split_input
  WHERE data_str != ''
),
school AS (
  SELECT CAST(fish AS TINYINT) AS fish
  FROM split_input
  WHERE fish != ''
),
day_hist(d0, d1, d2, d3, d4, d5, d6, d7, d8, day) AS (
  SELECT
    SUM(CASE WHEN fish=0 THEN 1 ELSE 0 END),
    SUM(CASE WHEN fish=1 THEN 1 ELSE 0 END),
    SUM(CASE WHEN fish=2 THEN 1 ELSE 0 END),
    SUM(CASE WHEN fish=3 THEN 1 ELSE 0 END),
    SUM(CASE WHEN fish=4 THEN 1 ELSE 0 END),
    SUM(CASE WHEN fish=5 THEN 1 ELSE 0 END),
    SUM(CASE WHEN fish=6 THEN 1 ELSE 0 END),
    0,
    0,
    0
  FROM school

  UNION ALL

  SELECT
    d1, d2, d3, d4, d5, d6, d7 + d0, d8, d0, day + 1
  FROM day_hist
  WHERE day < 256
)

SELECT
  d0 + d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 
FROM
  day_hist
WHERE
  day = 256

sed

• Topaz paste
• Try it online!

If saved as 6.sed, and your input is in 6.txt, you can run it like so: sed -f 6.sed 6.txt.

New blog post "Advent of Code in Kotlin: Day 5, 2021" explaining my proposed solution:
https://dev.to/ericlloyd/advent-of-code-in-kotlin-day-5-2021-37c8

Go. The full sorting logic is here. Its sort package requires a very simple interface but consequently makes you do some extra work if you need to sort by multiple attributes. Thankfully they provide a good example (SortMultiKeys) of how to do so in the docs. I stole it shamelessly. :)

This would be a good case for writing unit tests in your code. You are even given a few examples of inputs and outputs which you can run through your code and see what answers you get vs what you expect. If you don't want to go as far as full unit tests, you could just set i = "2x3x4".splitlines() at the top and see what your result is for that single line. You can see this works and gives an output of 58, which is what they expect in the explanation.

In your inner loop you are not taking into account things with the same size side (ie 3x3x3) If 2 sides are the same in your implementation then you will end up with a massive value for one of the variables. Eg when I run "2x3x4" through your system I get 58, but when I run "1x1x10" which is the second example on the page I get 220000000030 instead of 42.

Ooh, that grep is slick! Nice work. I just used the traditional permute from the Cookbook:

while (<>) { my ($a, $b, $c) = /(\S+) to (\S+) = (\d+)/; $cache{$a}{$b} = $c; $cache{$b}{$a} = $c; }

my ($fastest, $slowest); permute([keys %cache], []);

print "fastest: $fastest\n"; print "slowest: $slowest\n";

sub permute { my @items = @{ $[0] }; my @perms = @{ $[1] };

unless (@items) { my $t = 0; for (my $i = 0; $i < @perms - 1; $i++) { $t += $cache{$perms[$i]}{$perms[$i+1]}; } $fastest = $t if (!$fastest || $t < $fastest); $slowest = $t if (!$slowest || $t > $slowest); } else { my (@newitems, @newperms, $i); foreach $i (0 .. $#items) { @newitems = @items; @newperms = @perms; unshift(@newperms, splice(@newitems, $i, 1)); permute([@newitems], [@newperms]); } } }

...but of course I left out Arbre because I assumed all the cities would be in the departure column and populated $uniq{$a}++ instead of just using keys %cache. Sigh.

Nix: Part 1:

{ input ? builtins.readFile ./input }: let inherit (builtins) filter length head split foldl' elemAt; quickElem = f: xs: let i = elemAt xs; in f i; mod = a: b: if a < b then a else mod (a - b) b; lines = filter (x: x != [] && x != null && x != "") (split "\n" input); charList = string: filter (x: x != [] && x != "") (split "" string); chars = map charList lines; output = foldl' (a: quickElem (i: { pos = mod (a.pos + 3) (length (head chars)); value = if i a.pos == "#" then a.value + 1 else a.value; })) { pos = 0; value = 0; } chars; in output // { inherit chars lines mod quickElem; }

Part 2:

let inherit (import ./part1.nix {}) chars mod quickElem; inherit (builtins) elemAt foldl' head length; product = foldl' (a: b: a * b) 1; calculateTrees = tuple: let j = elemAt tuple; right = j 0; down = j 1; in foldl' (a: quickElem (i: if a.down > 1 then a // { down = a.down - 1; } else { inherit down; pos = mod (a.pos + right) (length (head chars)); value = if i a.pos == "#" then a.value + 1 else a.value; })) { pos = 0; down = 1; value = 0; } chars; outList = map calculateTrees [[1 1] [3 1] [5 1] [7 1] [1 2]]; output = product (map (x: x.value ) outList); in { inherit outList output; }

Golang https://github.com/A-UNDERSCORE-D/aoc2020/blob/main/2020/11/solution.go

Pretty fun, yet again using maps as planes. But it works well

It can render as it goes, though its ascii based, you can see that here: https://asciinema.org/a/W9lntg7WqXg5QeuzH0sPNkXw3

Python3

Classic stack based solution. Evaluating expressions inside parenthesis using eval():

part1:

def evalltr_p1(expr): nums, signs = re.split("*|+", expr), re.split("[0-9]+", expr)[1:-1] l = [nums[0]] + [signs[i] + nums[i + 1] for i in range(0, len(signs))] return reduce(lambda x, y: eval(str(x) + y), l)

part2:

def evalltr_p2(expr): return math.prod(eval(x) for x in expr.split("*"))

GO with regexp and recursion - part 2

Very satisfying solving this without lexers and stuff

first, replace all values inside parentheses with it's calculated value (using recursion)

then, the same for all values surrounding the +-sign, also using recursion

finally, multiplying them all, the logic remains from part 1 so it's not as clean as it could be

Python

It's not the fastest (1.5s) but it works for all dimensions n>=2 :)
I used a set to keep track of all active points and also used the fact that the grid is symmetric in z (and w) so I only need to consider a fraction of the grid and then mirror all active cubes

Javascript solution

Runs directly from the puzzle input ✨

Java
nopaste

I think I read the problem and my brain just went WTF. I tried BFS at one point to predictable results >!Exception in thread "main" java.lang.OutOfMemoryError: Java heap space!<
Figured it out in the end. My solution is a bit of a mess but I'll post it since there's no other Java one up yet.
Input from stdin.

Python

After getting through the parsing stuff, this is really well suited for networkx:

# part1: print(len(nxa.dfs_tree(G, "shinygold").nodes) - 1)

H = G.reverse() def get_sum(H, node): if H.out_degree(node) == 0: return 1

return sum(G[n][node]['weight'] * get_sum(H, n) for n in H.neighbors(node)) + 1

# part2 print(get_sum(H, "shinygold") - 1)

Java
nopaste

Scanner sc = new Scanner(System.in); sc.useDelimiter(Pattern.compile("\n\n", Pattern.MULTILINE)); int part1 = 0; long part2 = 0; while (sc.hasNext()) { String[] responses = sc.next().strip().split("\n"); Map<Character, Integer> m = new HashMap<>(); int personCount = responses.length; for (String response : responses) { for (int i = 0; i < response.length(); ++i) { char c = response.charAt(i); m.putIfAbsent(c, 0); m.put(c, m.get(c) + 1); } } part1 += m.size(); part2 += m.entrySet().stream().filter(e -> { return e.getValue() == personCount; }).count();

} System.out.println("Part1: " + part1); System.out.println("Part2: " + part2);

Input from stdin.

Java

with syntax highlighting

BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); List<String> lines = in.lines().collect(Collectors.toList()); int validPart1 = 0; int validPart2 = 0; for (String line : lines) { Matcher m = Pattern.compile("(\d+)-(\d+) (\w): (\w+)").matcher(line); if (!m.find()) { throw new IllegalArgumentException("Unable to parse: " + line); } int lower = Integer.parseInt(m.group(1)); int upper = Integer.parseInt(m.group(2)); char c = m.group(3).charAt(0); String pass = m.group(4);

int count = 0; for (int i = 0; i < pass.length(); ++i) { if (pass.charAt(i) == c) ++count; } if (count >= lower && count <= upper) ++validPart1;

boolean l = pass.charAt(lower - 1) == c; boolean u = pass.charAt(upper - 1) == c; if (l ^ u) ++validPart2; } System.out.println(validPart1 + " valid Part1 passwords."); System.out.println(validPart2 + " valid Part2 passwords."); }

Input from stdin. I'm new to Java so feedback is very welcome.

relatively straightforward C#: https://nopaste.ml/?l=csh#XQAAAQDIBgAAAAAAAAA6nMlWi076alCx9N1TtsVNiXedWuC8a4E8PBRGJWeHJ1Xw9VnWZ9hzPCBMAN8frpI4qp6F0f40VUL107PGt/hXMhnQg7DT2Y3XY8E+ayfvDxvEHNcaC7JZ5vlpQVBhm+7+73rUsxedmPJ7iXJYulSiQOk91UH2nlfANuHalEVRvGdYuR5WRFTn+PRMVnh4rHlj2rd9av+bx...

Silly mistake #1: Not learning C#'s version of regex before the month started. It comes up every year!

Silly mistake #2: Getting Select and Where mixed up so that my first validation function was just measuring the length of the string

J, both parts:

under_rot=. 2 :'(u@(] |. [) (-@] |. [) ]) v' NB. utility verb

f=. ([: +/ (}: , 0:) , -@# ]\ 1 $~ >./) under_rot (1 + ] i. >./) g=. (] , f@{:)^:({: . }:)^:_

part1=. [: <:@# g part2=. (<:@# - (i. {:))@g

Try it online!

J:

p1=. [: +/ (>./ - <./)"1 p2=. [: +/ (#~ >&1 * ]=<.)@,@(%/~)"1

(p1 ; p2) d

where d is your input.

Try it online!

A solution in the D programming language.

Start with a few constant arrays which introduce skew coordinates, along with distance calculating function:

import std.algorithm, std.math, std.stdio, std.string;

immutable int dirs = 6; immutable int [dirs] dRow = [+1, +1, 0, -1, -1, 0]; immutable int [dirs] dCol = [ 0, +1, +1, 0, -1, -1]; immutable string [dirs] dName = ["n", "ne", "se", "s", "sw", "nw"];

int dist (int row, int col) { if ((row > 0) == (col > 0)) return max (abs (row), abs (col)); return abs (row) + abs (col); }

The first part (read from stdin, write to stdout):

void main () { int row = 0, col = 0; foreach (c; readln.strip.split (",")) { auto dir = dName[].countUntil (c); row += dRow[dir], col += dCol[dir]; } writeln (dist (row, col)); }

The second part, quite similar:

void main () { int row = 0, col = 0, res = 0; foreach (c; readln.strip.split (",")) { auto dir = dName[].countUntil (c); row += dRow[dir], col += dCol[dir]; res = max (res, dist (row, col)); } writeln (res); }

Stumbled with lack of [] in dName[] for a while, but managed to get 79-th on part 2.

fun test(): String { return "qzmt-zixmtkozy-ivhz".map { char -> if (char == '-') { return " " } else { return char.toString() } }.joinToString(separator = "") }

Let's take that function, return char.toString() will return from test() as map will inline the lambda so the unqualified return will apply to test()

You can qualify what scope to return

return@map char.toString() should work but is an odd way to type it, if you don't want to use when just remember that if is also a valid expression in kotlin, so

fun test(): String { return "qzmt-zixmtkozy-ivhz".map { char -> if (char == '-') { " " } else { char.toString() } }.joinToString(separator = "") } works fine

Doc about the return behaviour

I've been tackling ProjectEuler on Hackerrank. They've added 197 problems (not sure how frequently new ones are added).

What I like about it:

• The constraints are generalised and usually increased. This has the effect of making some 'trivial' problems much harder. For example, Euler #29 is much harder on Hackerrank
• You don't get to 'cheat' by leaving a bruteforce solution running for hours+
• A large suite of test cases means you can be more confident that you've worked out all the details in your solution

Thanks. I like how we each have our languages of choice, but most of us agree on regex, and even use the same pattern. While you're learning, I second the recommendations for http://regex101.com. It helps tremendously to play around with examples/counterexamples.

Without regex, I'd probably write it like this (using Data.List.Split)

parse :: String -> [(String, Int)] parse s = map (pair . splitOn ":") . splitOn "," . tail . dropWhile (/=':') . filter (/=' ') $ s where pair [k, v] = (k, read v) pair _ = error $ "could not parse: " ++ s

Your parser's not too shabby either. The complication comes from the extra colons and commas, so you can filter them out first. Then it becomes

parse :: String -> (Int, [(String, Int)]) parse s = (read n, [(k1,read v1), (k2,read v2), (k3,read v3)]) where (_:n: k1:v1: k2:v2: k3:v3:[]) = words $ filter (notElem ":,") s

which I think is quite readable.

Pick up Ray Tracing In One Weekend, Author's Blog & Amazon. It's a fun little ebook that walks you through building a very small, fun path tracer. He codes his version in C++, but you can build it in any language!

I got the book over Thanksgiving and used it as an exercise to learn OCaml. I'll be revisiting the book anytime I want to a new language again.

> "Dynamic Programming", "Linear Programming" or "Operations Research", that were mentioned in some threads, are terms I've never even heard about.

If you haven't heard of dynamic programming, then it's not surprising you're struggling. Many of the later problems are easy to solve if you know the trick, and for most of us, most of the time, knowing the trick comes down to recognizing something we read in a textbook.

People who do well on the later days have, pretty much without fail, gone through at least one algorithms textbook and really mastered the material there. Jumping into the later days of AoC is a lot like taking a multi-day exam in algorithms. It would be pretty nuts if you could do well on that without studying it first.

If you do want to learn this stuff, get a textbook! I really like Skiena's Algorithm Design Manual. I've never taken a comp-sci class in my life, but most of the later days in AoC I'm basically just using one of the things I learned from that book.

If you're concerned about interviewing, and haven't already worked through it Cracking the Coding Interview is a fantastic resource. It'll also help you do better on AoC. Read Skiena first though - Cracking the Coding Interview is more of a practice resource for people who have already studied algorithms, not a first course.

Complex coordinates only work for 2d. Well, unless you use quaternions which aren't natively supported in Python.

Using tuples is great for 3d, although there aren't a ton of cases where you have a filled-in 3d grid since the space constraint gets very big very fast. And yes tuples are immutable which is probably good for code correctness but bad for speed-writing solutions. That said, you wouldn't really want mutable dictionary keys anyway.

That said, I sort of wish AOC would try some higher dimensional stuff (e.g. 4d). I'd like to think I didn't read Hamming's The Art of Doing Science and Engineering for nothing :D

When I'm too lazy to dig out the "standard" CLRS Algorithms Book, I just look them up on Wikipedia, and they tend to have decent summaries with examples and pseudocode. The pseudocode won't be python, but it should be easy enough to follow.

For example, Depth First Search. If you look in the box on the right, you'll see links to many other search algorithms, including the ones you mentioned.

Well, depending on how you look at it, it's either Boolean algebra or black magic.

&#x200B;

TL;DR: You can click through to play with it and see what happens ;)

&#x200B;

The idea is that you set one of the A/B/C inputs and one of the X/Y/Z inputs.

There are 9 outputs corresponding to 9 different score values for a specific game.

Once you set the inputs, one of those outputs will be set to 1, denoting the score.

&#x200B;

The circuit uses fairly basic logic gates - AND and OR, plus one NOT.

Fourth Edition came out this year! https://www.amazon.com/Introduction-Algorithms-fourth-Thomas-Cormen/dp/026204630X

It's a huge, expensive tome, though. Only a very small percentage will be relevant to Advent of Code.

Clojure's got a line-seq function that I tried to use, but was not successful. Going to have to try again tonite.

I played around with Racket during a Coursera course. https://www.coursera.org/course/proglang. Damned good course, btw. Racket was pretty slick. Really liked DrRacket.

But we're a Clojure shop at work, and I'm digging Clojure as well. Never would have thought a few years back that I'd be an Emacs fan ;)

Wow, would love to read this syllabus of yours! I even considered doing one myself, but I'm still very new to programming and probably would miss a lot of stuff.

Have you considered using Notion? I've just finished my first Notion page with my notes on Shell, it's very resourceful and easy to use.

C++

Here's my code (hastebin), nothing terribly novel here but I did find a really nice guide on coordinate systems for hexagonal grids: Hexagonal Grids (redblobgames.com)

Python 3

1318 / 785

Slightly better day than the last 2, but still poor from me.

Could've been much much better for part 2 if I understood the whole anti-infinite recursion thing properly.

Solution

I made an attempt for part 2: https://hastebin.com/donojazunu.php

Unfortunately, it only matches 6 of the 12 valid messages in the example. I'm not sure what the error is... if you can find it, I'd be grateful!

If you want to know what I tried to do: rule 8 and 11 are used only in rule 0, so my idea was to simply hard-code the behavior of those rules.

Haskell, link

Went to look up the docs on combinators and came across this, which killed the problem instantly...I feel bad lol

Scala. <1 sec, ~60 lines. Scala is fine for writing sims for AOC, the code ends up being no better/worse than a random imperative language, and on this size of input basically anything you do performs, but it doesn't really feel very much like Scala.

https://hastebin.com/lavadeteti.php

PHP

https://hastebin.com/giqiyujemo.php

More than 340 clumsy lines of php for an execution time of about 90 seconds. It works, but it's not great...

Would be happy if someone could tell me where I could be faster, and more elegant. I'm a beginner.

Have a nice day! :)

Typescript

I'm grasping TypeScript with AoC2020, so for practice, I've decided to try making the code easily readable, but also flexible for any given constraints. Works fine, although I feel like it could be done much better (:

I'm open to your comments

Not doing anything fancy, just keeping 8 neighbour directions (NB) and walk the floors from current position:
https://hastebin.com/qejilabisu.swift

Maybe that's why this solution is not fast.

[Scala](https://hastebin.com/qejilabisu.swift)

Repeating myself a lot for now, but I hope it is still readable.

Updating in parallel using future really helps here, maybe I could've done it with parallel collection but using ammonite with 2.13 so it's another import I don't feel like doing.

I think my solution counts:

https://hastebin.com/bolucodacu.csharp

I looped backwards from the end so it was almost like a memoized recursive solution but without the recursion. I've also seen versions that created an empty array of length (max_value) and started from the lower end instead.

Scala solution:

Admittedly I had a lot of help with today's part 2. I couldn't visualise how to do this efficiently and at the same time functionally.

Anyways, here is my answer!

https://hastebin.com/qolotibaye.scala

Here is the new code I set up. I think the recursion idea is starting to click. I'm still not even close to the right answer. I think I have the math wrong/ the multipliers are not making it to the inner bags.

Thanks! That was exactly what was wrong. If anyone is wondering how I solved it, I just made so that it would skip slope.fall amount of lines, because when using step_by, it includes the first line of the input and throws off my calculations again. That's why I had the skip there in the first place. So I have to skip to the line where my slope should end up on the first calculation, because of how my x_pos increments. Here's my final code if anyone wants to look at it: https://hastebin.com/qutoxureme.rust

Even better is adding at most 2 new points of interest for the next round (the point that moved, and the first neighbor to the left or above that can claim the space just vacated). I also sped things up by pre-computing the computations for neighbor indices; instead of lots of incr($1) passed to an ifelse for bounds check, which requires a conversion from string to decimal and back, the precomputed form is used directly. Overall, this means I now complete in about 6.2s. Here is my updated day25.m4.

As promised, I updated the code to perform less work per iteration. In the new day20.m4, I toggle between two grids (g0 and g1) rather than a new grid for each iteration (g0 through g50), for less memory usage. I also precomputed the initial conditions for each grid and the formulas for a point's neighbors so that the hot loop can be unconditional; now instead of performing a bounds check on every invocation of point, all points use the same unconditional code. While there are still 1181700 define calls during the 50 rounds (so the work is still O(n^3), I reduced from over 10 million eval to just 773. Runtime drops to ~6.9s. Any further speedups would require a larger refactoring job to compute points in parallel using bitwise math tricks.

Thanks to the megathread, I've rewritten an optimized version that runs in just 5s (2 orders of magnitude faster). Instead of messing around with partitions and comparing instructions on the inner loop, the code now tracks instructions as the outer loop, and tracks negative volumes to offset intersections with any prior instruction.

While my regular expressions aren't efficient here, it does help, since if I made the whole program run in 2ms then it would make it much less efficient to use threading, and also this makes it a much more visible thing :)

I also used no optimization with the compiler, so I could have done that too, I suppose.

As for the platform thing, I was using Windows 10 (obviously, as you can see from the border), and it returns the time is millis. I timed it with a timer, and where it says 10,000 on clock(), the timer was at 10s. I suppose that you could just do a simple test of #ifdef _WIN32, etc. to see what platform you are on and then define a different conversion factor for each platform, which means you could still show all of them in seconds or milliseconds.

Thanks for the feedback, and it's also interesting to hear about it on Linux! What compiler did you use, out of curiosity?

EDIT: I used this IDEONE test to see what happened. IIRC, they use GCC for C++14 (they don't have 11 as an option, so I used 14), and it ran the whole thing in 0.01s, which would imply that it was not using millis. It's most likely that Windows uses millis for clock() whereas everyone else uses nanos.

EDIT2: Confirmed, they use gcc-5.1 apparently.

Javascript

github - codesandbox

import _ from 'lodash'; import { LineReader } from '@libs';

function solve() { const reader = new LineReader(${__dirname}/input); let line = reader.read(); const fish = .chain(line).split(',').map(.parseInt).countBy().value(); let count = _.times(9, (i) => fish[i] || 0);

let day = 0;

while (day < 256) { const adders = count.map((n, i) => { switch (i) { case 0: return [-n, 0, 0, 0, 0, 0, n, 0, n]; case 1: return [n, -n, 0, 0, 0, 0, 0, 0, 0]; case 2: return [0, n, -n, 0, 0, 0, 0, 0, 0]; case 3: return [0, 0, n, -n, 0, 0, 0, 0, 0]; case 4: return [0, 0, 0, n, -n, 0, 0, 0, 0]; case 5: return [0, 0, 0, 0, n, -n, 0, 0, 0]; case 6: return [0, 0, 0, 0, 0, n, -n, 0, 0]; case 7: return [0, 0, 0, 0, 0, 0, n, -n, 0]; case 8: return [0, 0, 0, 0, 0, 0, 0, n, -n]; } }); adders.push(count);

count = _.zipWith(...adders, (...args) => _.sum(args)); day = day + 1; } const solution = _.sum(count); console.log('6.2: ', solution); }

export default { solve };

If I understood this thread correct, they are not unlimited. But in theory, if we could use bitmasks to represent the seen numbers, we would manage with much fewer lists. Unfortunately, Scratch doesn't have bit operations or remainders, so that we would have to implement that by hand.

Solution in MIT Scratch

For visualization there's a 1 sec delay, but if it's removed, the first part will take few mins to complete. The second part is obviously out of question :)

Scratch

Hi! I solved part 1 of day 13 in scratch. here you see my solution. you can look at code from the inside. Here are my steps:

1) I put all numbers in a list first in this puzzle. if I see a space it puts the numbers before the space and after the previous space in a list

2) he goes through the list 1 by 1. he checks whether the (start time + how long he should wait) is divisible by one of the numbers in the list

3) If that is not true, he changes how long to wait with 1 and does step 2 again

4) if that is true then he does how long he has to wait times the found number. that's the answer!

Scratch

hello my name is Luca and im 10 years old. My father was doing aoe. He liked it and does it every day. I saw the puzzle from day 1 and i think: maybe i can do that in Scratch. So here is the answer of day 1. part 1: https://scratch.mit.edu/projects/460138367/ part 2: https://scratch.mit.edu/projects/461104926/

Scratch

<strong>https://scratch.mit.edu/projects/457375336/</strong>

Meant to post this yesterday but forgot! My goal is to do as many of these as possible in Scratch this year. (I'm writing in Python for the leaderboards)

Python 3

Link to AOC 2019 archive

Not the shortest code, but I made it generic enough to cope with grids of any size, rather than just 5x5, and any number of rounds. The state for each round is the set of bugs, which makes counting the number of bugs at the end very easy! I'm sure there are much shorter ways to generate the neighbour links, but at least I only compute the links once...

<strong>Javascript</strong> in repl.it

Figuring out how to use >!Math.atan2!< took a bit, as well as coming up with the math for converting asteroids to relative co-ordinates to the base and changing it back. But mostly figuring out the angles and how to re-order them and the asteroids in a way that made it so I could shoot them in order. Satisfied with how much I've learned from this (multiple) day in coding.

My Python code is here. The program draws the maze at it is being solved and redraws it at each step as the oxygen is flowing in.

To solve the maze, I keep track of every successful step I take in a list of steps. At every point, I check to see if there's an unexplored location next to me. If it's a wall, I mark it explored. If it's a hall, I step in that direction. If there's no unexplored square, then I'm at a dead end and I move back a step and remove that step from my history list. When I can't back up any further, then I know that the whole maze is covered.

<strong>Javascript</strong> in repl.it

Late to the party, but submitting to keep myself accountable. The most difficult thing in Part One was generating the possible Phase Sequence orders. After adapting code to Part Two and bashing my head against it for two days, I figured out that my code was passing the initial array through all Amplifiers instead of keeping each Amplifier's command set separate. Very educational!

TypeScript

For some reason, my first instinct was to find how long it took each planet to loop back to an initial state and then find the LCM of the steps for each loop. Luckily, once I realized the axis trick, most of the code was pretty easy to clean up and adjust appropriately.

[POEM]

>for years i have gazed upon empty skies
while moons have hid and good minds died,
and i wonder how they must have shined
upon their first inception.
now their mouths meet other atmospheres
as my fingers skirt fleeting trails
and eyes trace voided veils
their whispers ever ringing.
i cling onto their forgotten things
papers and craters and jupiter's rings
quivering as they ghost across my skin
as they slowly lumber home.

Late to the party, but I'm glad I kept at it.

<strong>Javascript</strong> in repl.it

I originally wanted to the storage to be one giant object wherein the property was the planet name, and its value was another object that contained more planet objects and their children, but iterating through the structure to place planets and get depth were difficult.

&#x200B;

{ 'COM' : {'B': {'C': {}}}}

I switched storage over to an array of objects and was able to do everything much easier (see below). I broke out the classes for this one, though I'm sure it would have been better for performance not to do so. I just wanted my operations to be easier to read in the command function that returns the desired result. c&c welcome, any questions, just ask.

&#x200B;

Galaxy planets: [{name: 'COM', children: ['B'], parent: null}, {name: 'B', children: ['C', 'G'], parent: 'COM'}]

I did it sort of like this. I made 4 lists of slopes. The first one was to points directly up from origin, the second was for slopes to the right, the third was points directly below the origin, and the fourth was for slopes to the left.

Sorry about the delay in responding. I figured out how to use repl.it for a Node project, and made some edits to my utility functions. SPOILER: My repl, along with my input.txt

Edit: anyone know what flavor of markdown r/adventofcode uses for the spoiler tag?

Hey there! I did day three in Java but had the same problem -- looked at what was seemed to be a clear graphing problem with zero idea how to map it out and solve it. Now, this is certainly not the best method of solving it (it was slow as HECK!) but mine progressed like this:

&#x200B;

1. Find every single point in line one, add to a list/array.
2. Find every point in line two, add to a list/array.
3. Find every point the two lines had in common.
4. Add the X and Y coordinates in each point, and find that with the smallest (absolute) value.

I also used repl.it, and besides a 137s runtime I had no major issues! Hope this helps :D

<strong>Javascript</strong> in repl.it

I went kinda lazy with it and stored 3 parameters every time a command was found. Still worked, though. The instructions were a little confusing for operations 5 and 6 what with the whole "otherwise it does nothing" wording. I figured that meant not to increment at all, but that was just silly.

<strong>Javascript</strong> in repl.it (Bruteforce)

This was considerably easier than day 3, by miles. Part B only required changing an if-statement to generate the correct answer. c&c welcome, any questions, let me know.

Javascript in repl.it

I stored the lines as vertical/horizontal segments in objects like so:

Line { x: {x-value: [y-min,y-max]}, y: {y-value: [x-min,x-max]}}

Part B introduced some challenges that lead to me adding more information to the array values: direction, number of steps, total number of steps taken by the end of the segment.

I haven't seen any solutions posted that stored the lines the way I did (and probably for good reason) but I would like c&c on my code anyway. Any questions, just ask.

I'm still a novice at python but I was pretty happy with my solution to part 1. Part 2 was pretty brutish, but worked. I thought I had it quickly but then there were a few outliers that had to be removed that made it through my method. https://repl.it/@tsoutham/Day-4-AOC

From a quick glance at your code, it looks like the issue is not so much an "error" in your code, it's that you need to carefully read the requirements.

I would suggest paying attention to the explanation of the example inputs in the problem statement, and then running your code on the same inputs to see where the behavior differs. It might also help to make your console.log statements a bit more verbose, in order to make the output more readable.

For instance, here's your code with some slight modifications to the logging, running on the first two example inputs: https://repl.it/repls/PriceyBitesizedArgument

The first input should require 2 units of fuel, and the second should require 966 units, for a total of 968. Does this make it a bit more clear where your code is going wrong?

Part one and two in Clojure. Also runnable version on repl.it. Pretty new to Clojure so let me know if you see any anti-patterns.

(ns day-1 (:require [clojure.string :as str] [clojure.pprint :as pp]))

;; Stolen from https://github.com/dgrnbrg/spyscope just without the puget pretty printing (defn spy [form] `(doto ~form pp/pprint))

(defn calculate-fuel "Calculate the fuel needed to launch a module" [mass] (-> mass (/ 3) int ;; Round down (- 2)))

(defn calculate-fuel-recursive "Calculate the fuel needed to launch a module. Recursivly calculate the fuel need to launch the fuel as well" [mass] (loop [fuel (calculate-fuel mass) total fuel] (let [the-fuels-fuel (calculate-fuel fuel)] (if (>= 0 the-fuels-fuel) total (recur the-fuels-fuel (+ total the-fuels-fuel))))))

(defn parse "Parse the input into a vector of numbers" [input] (->> input ;; Read the file slurp ;; Split it into lines str/split-lines ;; Convert each line to a number (map read-string)))

(defn part-1 "Calculates the fuel requement of each module from the input and sums them" [] (->> "input.txt" ;; Parse the input file parse ;; Calculate the fuel requirement (map calculate-fuel) ;; Add them up (reduce +)))

(defn part-2 "Calculates the fuel requement of each module (with it's fuel included) from the input and sums them" [] (->> "input.txt" ;; Parse the input file parse ;; Calculate the fuel requirement (map calculate-fuel-recursive) ;; Add them up (reduce +)))

(printf "Part 1: %d\n" (part-1)) (printf "Part 2: %d\n" (part-2))

>I thought << came before &...

It does in a lot of other languages (e.g. C), but not in Go.