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
/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. :)
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
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
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.
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
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
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.
I am currently writing my first Haskell CLI. One of the functionality I need is asking the user for given inputs using forms (similar to enquirer/enquirer.
I designed this API similar to some APIs I've seen around parsers. Is this idiomatic? It's hard to tell since I do not have a lot of Haskell experience. Are there maybe better approaches? I'd love to introduce theming support as well, but I don't think that the current design makes that easy.
Anche nella mia le D non erano bloccate, uhm ...
Qui la sequenza con i passaggi che ho fatto, direttamente da Vim:
Bah, ci ho rinunciato e ho guardato i suggerimenti sul megathread.
Alla fino ho implementato una soluzione a cui avevo in realtà già pensato ma che non sapevo come realizzare.
Elaboro le istruzioni in ordine inverso. Tutti i cubi dell'ultima istruzione per definizione sono ON, dato che non possono essere oscurati da successive istruzioni OFF. Questo è il mio totale di base.
Poi per ogni altra istruzione ON vado a aggiungere il totale, da cui però prima tolgo i cubi che sono già stati coperti da una delle istruzioni già processate.
Se non altro mi sembra che sia venuta abbastanza pulita, e ci mette circa un secondo sul mio laptop.
Oramai sono veramente cotto, alle 06:00 non riesco più a ragionare ...
La prima parte lineare ma ho commesso una sequenza infinita di errori prima di andare a termine.
La seconda mi sono lanciato in ragionamenti astrusi pensando che non sarei mai riuscito ad avere codice sufficientemente veloce.
Alla fine mi sono deciso a provare una semplice memoizzazione degli stati ed con una implementazione base ho ottenuto il risultato in 4 secondi.
Lo stato è dato da; la posizione del primo giocatore, la posizione del secondo, il punteggio del primo, il punteggio del secondo, e la fase, che varia da 1 a 6 a seconda del prossimo giocatore che deve tirare il dado e a quale tiro è arrivato.
Codice per la seconda parte: NoPaste snippet
Ieri notte sono stato su fino alle 3 a risolvere il problema, oggi alle 6 non ci ho neanche provato a risolvere quello di oggi.
Affrontato con calma nelle pause e a pranzo, anche a me ha fregato le regola nell'input che se i 9 punti sono a zero allo il risultato è 1.
Ho provato a trovare qualche modo intelligente di risolvere la cosa ma poi ho lasciato perdere e gestito a mano tutti i casi. Determino il valore di tutti gli elementi esterni alla grid che traccio andando a verificare sia il valore dell'algoritmo per l'input 1 sia se siamo in una iterazione pari e dispari. Non sono sicuro che sia robustissimo, ma basta per i due casi che contano.
Ecco il codice, con alcune ottimizzazioni e shortcut tempo di esecuzione circa 1,1 secondi, me lo faccio bastare: NoPaste snippet.
Ora dovrei tornare a cercare di capirci qualcosa sul problema di ieri ...
Uhhh, lungo ma da una certa soddisfazione !
Posizione 1556/1856, di gran lunga il mio miglior risultato di quest'anno.
Ecco il codice, ancora molto molto grezzo: NoPaste snippet.
Abbastanza lineare, sono sicuro che con le regex avanzate si sarebbe potuto fare di molto meglio.
Solo un paio di bachi perché non avevo letto bene i termini del problema mi hanno portato via parecchio tempo.
"Error, this is a private paste or is pending moderation. If this paste belongs to you, please login to Pastebin to view it."
If you use https://nopaste.ml/ instead, you won't be at the mercy of pastebin timing out your post or blocking it from other readers.
Ecco il codice, dopo una bella ripulita: NoPaste snippet.
Decisamente troppo arzigogolato, se ci puntacaso ci fosse da espanderlo nei prossimi giorni saran dolori ...
Mah, dopo averci perso anche troppo tempo, sono giunto alla conclusione che:
A* effettivamente è inutile, Dijkstra va più che bene
le priority queue con min_heap sono qualcosa che oggi non c'ho proprio voglia di implementare da zero
alla fine una priority queue dei poveri costruita con un array Perl e tenuta ordinata con il comando splice mi risolve il problema in 18 secondi, me li posso far bastare
Ecco il codice NoPaste snippet.
Concordo con quanto detto da altri, problemi come quello di oggi dove la difficoltà sta quasi solo nel conoscere l'algoritmo da usare non sono granché per i miei gusti. Meglio qualcosa di un più arzigogolato da implementare ex novo.
Ho usato esattamente la struttura dati che hai indicato.
Qui c'è il codice ripulito: NoPaste snippet.
Esecuzione in 22/26 millisecondi ...
@points_next è sempre un array.
So cosa stai per dirmi: in questo modo il numero dei punti ad ogni fold rimane costante, e non si riduce quando un punto presente sotto la riga di fold va a coincidere con uno già sopra.
Questo è verissimo, ma nella pratica avevo provato ad applicare alcuni metodi di deduplicazione (passando da una mappa) ma i tempi di esecuzione erano sempre leggermente peggiorati ! Ovvero il tempo perso a ciclare su punti duplicati era comunque inferiore al tempo necessario a deduplicare.
Adesso ho provato in un altro modo ancora e sembra aver migliorato un po' le cose.
I max posso effettivamente calcolarli alla fine, dato che usando l'array di points e non più la griglia non ne ho bisogno nella parte intermedia. Questo tra l'altro mi semplifica un altro po' la logica ... In ogni caso però non davano luogo a spreco di spazio, dato che l'occupazione è sempre solo data dal numero di punti.
Ecco una versione che viene eseguita sotto i 5 millesimi di secondo (I/O incluso, tempo di startup escluso): NoPaste snippet.
> Ho tenuto un insieme dei punti, mappandolo ad ogni fold in un insieme nuovo
Ah, ottima idea, in questo modo crolla l'occupazione di memoria ed il numero di controlli da fare. Reimplementando in Perl con questo approccio il tempo di esecuzione mi scende a 5/6 millesimi di secondo (anche se il codice diventa più difficile da seguire).
Updated day7.m4
Optimized to 75ms runtime (10x faster) by computing the median in O(max(m,n)) time (m=number of elements in list, n=difference between min and max of list; the input files I've seen have m=1000 and n=2000). Basically, by populating a hash table (linear O(m) time) with the frequency of each element, I've performed a radix sort, at which point the median is easy to find by accumulating those frequencies starting from the minimum bucket (linear O(n) time).
Stamattina avrei fatto meglio a dormire un'altra ora, avevo il cervello completamente in palla, continuavo a sbagliare il verso dei confronti e non mi capacitavo che non funzionasse.
L'assurdo è che poi invece la seconda parte m'è venuta in scioltezza, senza neanche dovrei andare a vedere gli algoritmi da usare. Probabilmente non la soluzione più efficiente, ma finché stiamo intorno al decimo di secondo direi che può bastare.
Ecco l'implementazione dopo una bella ripulita e razionalizzazione:
Rust (beginner)
Had a weird experience today. My part 2 result for the test input was consistently off by two no matter how many different ways I calculated the answer. Eventually in frustration I just ran it with the real input and threw the number in and it was accepted. Cannot for the life of me figure out what was happening.
C'è anche un'altra soluzione oltre al rotate.
Ad ogni iterazione l'unica operazione da fare in realtà è una somma. Si può lasciare l'array as is, e calcolare le posizioni dei due elementi della somma facendo il modulo 9 del numero dell'iterazione.
Rust (beginner)
Bit of a late start resulting from a difference of opinion with my alarm clock this morning.
Did the naïve way way for part 1 at first but much happier with what I ended up with after part 2. I feel that having those two seperate variables for sevens and eights feels super clunky but having them in the deque would be worse? Didn't really come up with any good ideas there but there must be a neater way.
Rust (beginner)
Fairy happy with how this turned out. I picked up the whole leave it in a vector and just index in with an offset trick from a previous year and I think it really helps cut down the complexity. I feel like the naming of the loop variables should be better but it's hard to be descriptive when you're using them for two different things. Looking forward to seeing what everyone else did.
Rust (beginner)
I have the feeling I'm about to see other people do this in like one line
Topaz's paste tool is great but lacks syntax highlighting which makes code hard to read IMO...
May I suggest NoPaste instead?
Runs directly from the puzzle input ✨
Rust (beginner)
Nice gentle start thanks to slice::Windows.
Wondering how many days before Rust overwhelms me :)
Please post a video of you manufacturing the part ala my mechanics style :D
Nim
NoPaste snippet
There really is more work to do per round (so even though this is one-third the iterations as day 15, each iteration takes longer). But just as I did in day 15, rewriting the loop to minimize macro calls and length of text that m4 must parse speeds things up; execution dropped from 4.5m to 2m59s. The loop is now as dense as I could make it: helper macros, plus a 3-deep mutual recursion on:
define(r',
i(r$1',
r$1',R')($1,P($2))')
define(
R', S($1,d(b($2),$3,$4,$5),$2,$3,$5,n($5))')
define(
S', D(
n$5',n($2))D(n$2',$4)D(
n$3',$6)r(I($1),$6)')
I'd like to mention https://nopaste.ml/ as an alternative.
It's similar to pastebin where you can just paste your script, but it does not save your script on the website so you don't have to worry about whether the site will disallow porn in the future. What it does is it converts the script into code appended to a URL, so that when you visit the URL, the site decodes it back into a script. Your script becomes the link itself pretty much.
I've now had a chance to refactor the code, using what I learned from day 24. Now both parts are run at once, and instead of running a 3- or 4-nested loop over the growing list of every possible cell in each generation, I now track just the active cells and their neighbors. The bulk of the code is shared by letting $4 be blank for part 1, and the w coordinate for part 2. Runtime is now drastically improved, at 1.4s.
Tracking only two dimensions in doubled coordinates turns out to be more efficient than three dimensions in cubic coordinates. My speed is now improved up to 4.7s.
I revisited this in light of day 25 also benefiting from the use of (32-bit) modmul; resulting in a few tweaks to further optimize things: _modmul() had a dead assignment to a, and up until a 64-bit computation is actually needed, we can use simpler 32-bit math for *, +, and even the computation of bits() thanks to eval($1, 2). The updated day13.m4 now completes in about 90ms.
Ah, ecco il codice.
Quanto di più becero immaginabile ...
Ed ecco il codice, riscritto come sarebbe dovuto essere evidente per usare una hashmap con l'elenco delle mattonelle nere, e non una mappa completa della stanza.
Ho scoperto che Perl ha native le chiavi delle hashmap multivariate, molto comodo per questo esercizio.
Java
nopaste (part 2)
Made a lot of stupid mistakes that led to an age spent debugging. Probably would have been faster to just write something clean from the start.
Codice per la seconda parte, estremamente ripulito ma sostanzialmente identico dal punto di vista logico da quello originale.
0m5.973s ma la voglia di ottimizzarlo non c'è ....
Java
nopaste
This is so ugly and primitive but I'm posting it because when I wrote Part 2 and ran it it somehow worked first time and I was so shocked I just stood up and stared at it for a minute.
Python 3.9
First time attempting AoC!
I spent quite a bit of time creating a solution for both parts which utilizes one function. I don't think it's as efficient as just using 2/3 nested for loops but it was still fun to make nonetheless.
With syntax highlighting
BTW you input file is called 'input-11.txt', is that intended?
Code --->here<---.
What a gnarly problem today! I had a hard time keeping everything straight, and I'm sure I probably did some redundant things, but the code runs quickly so I'm happy about that. I was surprised that the hardest part of the problem wasn't alluded to in the problem description or covered by the test cases. (Or maybe I'm just dense?) Took me a while to figure it out.
C#
Two methods:
2.43 sec using Dictionary, 0.7 sec using an array of numbers
Dictionary makes sense as you only have the numbers you get in the sequence.
Array method, requires me to initialize an array of arbitrary length.
If someone has a better method for running it in less than a second, please do help!!
C, brute-force with recursion for part2
Java
nopaste
Used character arrays when generating the mask and had a bug which didn't affect the test input but led to me spending an hour before I figured out I was setting characters to 0 instead of '0'. 🤦🏼♀️
Then I generated the rest of the addresses from a mask string recursively -- calling the function each time I encountered an X with the X replaced by 0 or 1.
Result is an absolute mess but I'm not sure how to clean it up really. Input from stdin.
Code --->here<---.
Super proud of my solution today. I realized that not only do single buses have fixed cycles, but pairs of buses also have (much longer!) fixed cycles. Hence, you can decrease your search space exponentially with each new input you add. It kinda reminds me of certain algorithms that converge very quickly for finding infinite sums.
Mah, alla fine ecco una soluzione ripulita per entrambe le parti.
Nulla di eccitante ma ci mette 0.676 millisecondi, non vien voglia di ottimizzarla.
shaving ~10ms is pointless on some of the longer days, but for this day, it's a 16% improvement ;) I'm down to 25ms for 'm4' and 50ms for 'm4 -G'. Here's the same solution refactored to perform both parts in one pass, by tracking part1 in x/y, part2 in X/Y/w/z, renaming the macros in each part, and having the parser target the new act(A, value) instead of the former A_(value):
define(act',
$1_1($2)$1_2($2)')
JavaScript/Node.js
Found Part 1 easy to come up with a solution for, but easily the most code I've written for a part 1, and the logic took a couple of goes to get my logic just right
But for part 2 I wrote a better solution, that made me feel a little less pleased with my part 1 solution.
JavaScript/Node.js
Been trying to get away from using reduce in places where I don't need to go over a whole array, so I've got some loops I have mixed feelings on. My solution sits in a funny spot where it's a little too verbose for my liking, but not quite verbose enough to look professional.
NoPaste snippet
As always, a Factor solution --->here<---.
After seeing some of the clever solutions that interpret the input as binary numbers, I couldn't resist translating them into Factor. Credit to /u/smokebath whose solution I saw first.
USING: io.encodings.ascii io.files kernel literals math.order math.parser math.ranges math.statistics multiline peg.ebnf prettyprint sequences sets ; IN: aoc.2020.05clever
CONSTANT: input $[ "resource:work/aoc/2020/05/input.txt" ascii file-lines ]
EBNF: id [=[ zero = [FL] => [[ drop CHAR: 0 ]] one = [BR] => [[ drop CHAR: 1 ]] bin = (zero|one)+ => [[ bin> ]] ]=]
: part1 ( -- ) input [ id ] [ max ] map-reduce . ;
: part2 ( -- ) input [ id ] map dup minmax [a,b] swap diff first . ;
document.body.innerText
is enough actually (check out my solution)
Happy cake day by the way!
USING: fry io.encodings.ascii io.files kernel literals math math.order math.parser prettyprint sequences splitting ; IN: aoc.2020.02simple
CONSTANT: input $[ "resource:work/aoc/2020/02/input.txt" ascii file-lines ]
: parse ( str -- low high password char ) " -:" split harvest first4 [ [ string>number ] bi@ ] 2dip swap first ;
: valid1? ( str -- ? ) parse [ = ] curry count -rot between? ; : valid2? ( str -- ? ) parse '[ 1 - _ nth _ = ] bi@ xor ; : part1 ( -- ) input [ valid1? ] count . ; : part2 ( -- ) input [ valid2? ] count . ;
Also, here's an over-engineered solution where we explore the wild world of parser combinators, tuples, running code at parse time, and cleave combinators.
One line of JavaScript for each part, running directly from the puzzle input 🎉
Dumb JavaScript solution, designed to be run directly in the browser from the puzzle input page
Also, thanks for featuring NoPaste !
Python3 183 / 85
I got lucky enough to get my input before the crash but could submit afterwards only. I really hope scores won't get deleted from personal stats at least, I've been fighting for my first aoc scores for years (and in my country it starts at 6 am local time).
EDIT: As code is short, I paste directly too.
import itertools
INPUT_FILE = "1.in"
with open(INPUT_FILE, 'r') as f: inp = f.read().splitlines()
inp = list(map(int, inp))
for each in itertools.combinations(inp, r = 3): if sum(each) == 2020: print(each[0] * each[1] * each[2])
NoPaste can generate markdown, which is great to share code snippets in reddit comments!
You can even generate Markdown which is supported in reddit comments