oliverpdaniel - Tumblr blog

oliverpdaniel · 1 year

Text

Advent of Code 2022: Days 11-14

This is going out on December 20. Why, then, does this post only contain my notes for days up to the 14th, you ask? Well, because AoC haaaaaaaaaard. As of writing, I still haven't progressed past Part 1 of Day 15. But, I'm officially done with both school and work for the semester, so I'm gonna have a little bit of time and energy to tackle these, alongside the myriad other tasks I punted off until this time of year.

Please enjoy my writings while I suffer. I'm going to get all 50 stars this year, hard problems be damned!!!

Day 11

Every year, I expect there to be a Math Knowledge problem, and at least one "heat death of the universe" runtime problem. I didn't expect both of them to arrive on the same day, and so soon! In any case, I don't feel to bad about Part 2 being a two-seater here, nor about getting some insights from my much-mathier roommate. The most irritating part of the day was when I, not feeling up to optimizing my solution, just tried to chug my naive, OOP-based solution along while I took a shower. Well, I came back and it was finally done... except I'd forgotten to switch my input from the test data. Anyhow, the larger input would have taken even longer -- and may not have even terminated before running out of memory on my laptop. Whatever. Onward!

Day 12

Yup. This is why you don't talk a big game about your computer-sciencey brain when you *checks notes* dropped out of computer science during the plague. Although my fingers can practically write out DFS without my conscious intervention at this point, the test input was very cleverly formulated to make that take an unreasonable amount of time, so I was forced to open a Wikipedia tab with my tail between my legs. At this pont, I really ought to commit one of the UCS algorithms -- Dijkstra, A* -- to memory, even if exclusively for AoC problems.

Opening the subreddit revealed some interesting optimizations I could have done, like searching for the nearest a tile from the endpoint in Part 2, but... meh. Brute-forcing A* takes like two seconds on my machine, and I like pretty shiny stars more than that kind of yak-shaving. Speaking of, today better damn be a productive day for me if I want to keep on schedule to enjoy my winter vacation. What incentives lie in store for me over the winter? Why, the chance to work unimpeded on my portfolio site and side project, of course! What else would I be doing?

P.S. I will have to check with one of the more CS-y of my peers as to why my algorithm didn't work when the edge 'weight' between two nodes was 0 rather than 1 (as opposed to inf i.e., if the two nodes differed inadmissibly in altitude). And people on the subreddit are smack-talking using A* on this problem, so maybe I'm the dummy here.

Day 13

Today hit the trifecta of competitive-programming hackery: eval, match-case structures, and the walrus operator! Until I realized it wasn't actually necessary, I had a for-else loop in my comparison function for good measure, too. This morning's puzzles were much more manageable than the last few, and I'm pretty happy with the solution I came up with. Of course, years of Javascript dev have thoroughly rotted my brain: as soon as I saw that part 2 required sorting, and I had already written an (a, b) comparator, I thought I was done! Of course, these days Python doesn't use comparators, but rather a key. Luckily, a quick Google search (well, DuckDuckGo, because I'm like that) revealed that functools has a happy little cmp_to_key converter that made my life easy. No parsing and no custom logic: can every day be like this??

I'm quite curious as to what these nifty new match-case structures can do. I found it somewhat strange that the syntax for checking the type of values was an empty constructor in the case statement -- e.g., match a: / case int(): rather than the match type(a): / case 'int': I intuitively wrote. I'll have to see what the underlying logic is there. In either case, I've yet to really discover a use case where they're truly more useful than if structures (other than saving my precious fingies a handful of keystrokes), but I'm sure I will.

Day 14

An accidental midnight solve, which certainly would have gone more smoothly had I, y'know, not done that. A few things I'm proud of:

Recognizing pretty quickly that the inputs (i.e., walls) can be defined left-right or down-up, as well as vice versa. I made a simple smart_range helper that would prevent range from breaking if its start argument was greater than its stop.

My input-parsing is pretty baller, not gonna lie. Writing this writeup a few days removed from having written it, I'm slightly struggling to understand what it does! Itertools for the win.

Using a for-loop to represent falling, at the end of which was the "floor" of the sandpit.

I was a little bit scared of this one when I first saw it involved particle physics, but it turned out to be okay.

0 notes

oliverpdaniel · 1 year

Text

Advent of Code 2022: Days 6-10

The calm before the storm. These puzzles were still one-seaters, but I don't imagine that'll be lasting much longer. My brain is abuzz with compsci stuff like it hasn't been in a good long while, which makes me happy. I also briefly attended a social with some of my old classmates and professors, which made me long juuuuust a little bit for the olden days. (If one of you happens to be reading this, maybe you can prod me enough into finishing my B.Sc someday.)

Let's get into it!

Day 6

Not much to say. Python slices and sets make this easy peasy. I probably spent more time copying test data than solving.

Day 7

Now THAT'S more like it. I just so happen to have been up at midnight (ahem, definitely trying to solve my Kryptonite, Day 19 with my roommate), so I decided to give this a crack at the stroke of midnight. Again, don't talk to me if you're not top 1000 in this problem!

The real tough part about the day's puzzle was parsing the input, and understanding what needed to be done; from there it wasn't actually too bad. At first, the directory-structure idea had me worried that some kind of recursive parsing would be necessary. Instead I was able to just manage the stack externally (i.e., a list representing how many folders deep we were), using a clever little match-case structure (thank you 3.10!) to pop off the top value whenever cd .. was called. One early mistake I made was only summing up the weights (i.e., file sizes) of only the current directory whenever ls was called, instead of remembering to also add those weights to all parent directories as well. From there it was fairly smooth sailing.

I appreciated that Part 2 called for input from Part 1. I always like days that do that, whether you're feeding in a numerical value or maybe reading some ASCII art from a visualized version of Part 1. (Well... the way I refactored my Part 1 after reading Part 2, the directory sizes were actually calculated at the top-level of the script, but...) Again, the real difficulty here wasn't recognizing that some form of arithmetic needed to be done: it was just parsing the instructions to understand what arithmetic went where.

My brain is officially alight, and that's not just from the 3-hour midterm I had today. I've got a fever only AoC can fix, and I've got a prescription for 3.5 more weeks of nonstop Christmas-saving action. (I'll stop now. Goodnight.)

Day 8

Oh yeah it's grid time babey. A good solve, and it's definitely making all the de-rusting I did on previous problems feel at least a little worth it. Python's slicing notation remains unbeaten. Although I did another morning solve (i.e., no rush for the leaderboards), I got in my own way by trying to be too cutesy with things like itertools.takewhile() to calculate the length of sitelines. That's one place where a good old for-if structure will be juuuuust fine, methinks. However, if Eric Wastl continues his typical obsession with 2D grids, having it.product(range(H), range(W)) in my back pocket will be helpful if for no other reason than to help keep my code clean. Speaking of, I'm quite glad that I've started to 'prematurely' refactor my code by creating explicit helper functions that handle a given part's primary logic, rather than shoving everything into Part 1 and needing to awkwardly pull it out later. For some reason, when I copy and paste Python in VSCode, the indentation always seems to have something funny with it, so this is always a time loss (or potentially a logic error, if I somehow manage to make an atomic typo with my indentation rather than causing a compile error). Anywho, I'm planning on delivering an impromptu lecture about Day 7 today, so wish me luck.

Day 9

Man, this one felt good. After relatively minimal print-debugging, I managed to finish both parts in a single morning sitting, with my logic for Part 1 slotting real nicely into Part 2. This puzzle used a bunch of idioms I've developed over my competitive-programming 'career': getting a number's unit-sign by floor-dividing numbers by their abs (or 1, in the case of 0); doing pairwise computations down a chain by zipping offset lists together; and my current-favourite thing, Python dataclasses. I used the classic example of a Point(x, y) to keep track of each knot's location on the chain, and added a few convenience methods to extract e.g., hashable versions of each location for storage in my visited set. I'm quite proud of my solution here.

Day 10

I "accidentally" solved this one at midnight, though I had no delusions about making the leaderboard. The toughest thing to grok about the problem was the meaning of 'cycles' in the instructions. At first, I'd thought the 'program counter' of the script incremented every cycle, e.g., the addx operations were a sort of synchronous effect. So, I tried to use a queue to handle what "effects" would occur at the beginning of each cycle. In any event, my love affair with generators continues, even if I did finish with something short but janky.

I do love a visualizer. Understanding exactly what was being asked of me at ~1:00 AM was growing difficult, which would lead you, dear reader, to assume I went to bed to deal with it in the morning, right? Wrong! The head-scratcher here was remembering to handle the modular conversion between cycle counts and CRT column, but still using the prior value as the basis of comparison with the value of the X register. We're getting into the goods now! And I finally tackled the last of 2015 later on in the day!!! Christmas was saved, just under 7 years late.

0 notes

oliverpdaniel · 1 year

Text

Advent of Code 2022: Days 1-5

Welcome back, party people, to Days 19-25 of the 2021 Advent of Code! Hmm, wait, no... Those are just items that have been sitting and going stale in my to-do list since last year, since I still can't figure out how to visualize rotating beacons or prioritize movements in a hallway. Grr. I've been doing lots of AoC problems in anticipation to keep my skills sharp, so hopefully I'll be approaching the 400-star club sooner rather than later™.

In seriousness, I could not be more amped to get this year's batch of puzzles underway. I am joined on my leaderboard this year not only by my roommate of yore, but a new friend, whom I've taken under my wing to help introduce them to the god-awful world of software development. I'm wishing her all the best in this year's challenge, and I can't wait for your Icarian hubris to melt like waxen wings after Day 10 or so.

These first few days proved more than trivial to solve. I have a new-and-improved workflow with VSCode, which means that I should be able to write about each solution immediately after getting that all-important gold star. Let's get right into it!

Day 1

Don't talk to me unless you're top 1000 on at least one day of AoC. I'd probably be even higher-ranked than #511 if I hadn't made a dumb slicing mistake. Looking forward to another exciting year of challenges, this time with friends!

Day 2

Well, that was absolutely embarrassing. I think this officially marks the end of my staying up to work on puzzles: as satisfying as it was getting another top-1000 finish for the first part (which should have been even faster, tbh), it took me entirely too long to finish the second part, because I kept rushing to submit rather than taking the two seconds to think things through. As I tried to solve while also preparing a pot of pasta and maintaining a phone conversation, I am somewhat reminded of this classic scene, although I really shouldn't be. Anyhow, morning solves it is from now on, even if I'm up at midnight.

UPDATE: While groggily making coffee in the morning, my roommate pointed out that, ALL THESE YEARS, I never realized that modulo worked with negative arguments as well, completing the symmetry of the circular list. ARRRRRRGH. Well, glad to know AoC has already proven educational.

Day 3

Despite telling myself that I was going to start going to bed before midnight and thus doing challenges in the morning, I did find myself awake at 12:10, though I hadn't even noticed the date change. Oh well, works for me. This challenge went much more according to plan: I quickly recognized what needed to be done, and my solution for both days worked first-try. Looks like sets and modular indices will be flavours of the month. (Hopefully not too many cellular automata or convolutions...)

Day 4

I was just barely awake at midnight, but I opened the puzzle and decided to go to bed anyway, which I think was very brave of me. The solution to part 1, which I more or less dreamed up, worked as expected: Python's chained comparator operations (a <= c <= d <= a) really are quite delightful. However, I had a little more trouble than expected figuring for any sort of overlap, so rather than have another day 2 situation, I took advantage of the megabytes of memory God gave me by porting both ranges to sets and checking for nonempty intersections. Once I had the right answer, I decided to amend my solution to include the "correct" way of doing it: there are planar intersection problems every year.

Day 5

Stacks! Honestly, the toughest conceptual part of this puzzle was parsing all the input. I wrote a bash command to create all the template files I need for the day -- test input, puzzle input, and solution script -- the latter of which includes a line to read in one of those files, break it into lines, and strip off trailing whitespace. That last step proved to be problematic today, as if a particular line of input, say, didn't contain any boxes in the first few columns, then I wouldn't have any way of knowing. Luckily, all the ~~procrastination~~ practice I did with previous years' puzzles mean that my cursed cursor-fu is top-tier, and I was able to bash out a line (first-try!) that automatically broke down each line into the correct tokens. Also different from most puzzle inputs, the file was broken down into three sections -- the stacks themselves, column names, and instructions. You could argue the second section isn't inherently useful (especially since I don't program in a language with static array lengths), but I did end up employing it just to make my life a little easier.

This puzzle is also the first time in a while I've meaningfully used a del statement in Python, since I was a newbie way back when. In this case, I used it in Part 2 to quickly lop off the last n values when I remove them from one stack and extend them onto another. I considered doing something similar for Part 1 in hopes of a minor speed-boost, but everything ran in, like, a millisecond anyway, so I didn't see much point.

One more thing...

As crypto culture (finally) crashes and burns around us, a new and ugly era rears its head: idiots thinking that "prompting" (i.e., writing inputs specific enough for GPT3 or similar to produce desired outcomes) is the future of programming/art/whatever, and is just as meaningful of a skill. Yes, sweetie, it's very impressive that a gigantic AI system was able to solve your AoC puzzle in 10 seconds after having consumed terabytes worth of other people's code, and yes, you pushed the button to make it go! And now your name is permanently on top of the leaderboard, because you think that you deserve all the credit for those solutions! Your family must be so proud of their little genius.

Yes, things like the AoC leaderboard aren't important in the grand scheme of things, and yes, it ultimately doesn't matter if it gets polluted with GPT solvers, because the rest of us still had fun and learned things working on the puzzles ourselves. But, if you truly believe that the ends justify the means (i.e., second-hand plagiarism on a supermassive scale), and the rest of us should just have to deal with the fact that you don't understand the concept of fair competition and should -- I don't know -- have to start a separate leaderboard with a human-verification system... you're not the future, you're the obstacle the rest of us have to get around to continue being a humanocentric society. I have no doubt that conversational AI systems like GPT are going to be here to stay, and the rest of the tech world is going to have to enter crunchtime to more effectively protect things like people's art from getting hoovered up by completely unattended systems. But hey, as long as you make a buck, I'm the idiot for not doing it first, right?

Anyway, all this to say, if you think it's cool that GPT-3 can solve programming puzzles just by reading a prompt, fantastic. I think it's awesome, and the possibilities are very exciting! Just wait fifteen goddamn minutes before submitting your solution. It's not cute, and as much as there aren't any rules to AoC, it's very clearly being done for the purpose of getting your username at the top of the leaderboard, not for 'raising awareness' or showcasing the power of AI everyone already knows is ridiculously powerful. It's for you and your ego.

Rant over; let's save Christmas.

0 notes

oliverpdaniel · 2 years

Text

Advent of Code 2021: Reflection on Days 11-15

Another interesting week! Sorry for the lateness on this one -- and lateness always begets poorer reflection, as I'm further removed from when I actually wrote each solution —- but it's here now, and you should be grateful for that. I know I have at least one (1) dedicated reader, so this one's for you; also, we need eggs.

Day 11 Writing this in retrospect, holy wow there have been a lot of 2D-grid questions this year, especially in this narrow band of days. I think I need to stop using ranges in my _neighbours toolkit function, and just pre-calculate a list of relevant deltas. It eliminates the needless double for-loop, and immediately makes it obvious whether or not corners are going to be included.

A simple, fun cellular-automaton-style problem. I realized that the logic -- of an overfilled tile 'exploding' out by incrementing its neighbours, potentially leading to a chain reaction, is very similar to an old Android game – Clonium something or other? – I once re-implemented in Java Swing as an afternoon project in high school, after said game alleviated many boring History classes. (Sorry Ms. Lee.) Although I certainly didn't remember any of the logic I used for that game directly to-hand (and I seem to have taken down the Github repository, if I ever made one for it), I remembered that some kind of while-true loop would be needed. So, the _evolve() method I made didn't give me too much trouble, save for a little bit of troubleshooting when I didn't realize that flashing octopuses^[1] would only reset to 0 after the chain reaction was done, meaning that their tiles could hypothetically 'absorb' lots of extra flashes before the end, then just flush that value out to 0.

A single step (i.e., convoluting and updating the board) ended up being pseudo-instant, so no performance updates were needed for Part 2. One thing I've been doing more of lately is returning/yielding tuples of values of interest, rather than just one: in this case, I was able to kill a few birds with one stone by returning both the modified copy of the board after each step, as well as how many octopuses flashed that round. Doing that meant my P1 and P2 functions were just a handful of lines each. Just had one itsy little off-by-one error to take care of in Part 2, as I somehow forgot that itertools.count takes a start parameter.

Day 12

E N T E R T H E G R A P H

I don't have too much to say about my solution, as it's just boring old DFS.^[2] So, I took the opportunity to piss off my roommate as much as possible by totally abusing modern Python syntax (unlike Numpy, ahem ahem). Fun fact, the new yield from operator for generators ignores returned values, so when you need to generate a lot of valid paths, you can just yield when you find the goal and return when you get lost.

As for Part 2, I just wanted to get it over with and get on with my last few school assignments, so I added a special paramater to my traversal function which checked if a particular cave was 'reserved' (i.e., the one I chose to visit twice); then, if the cave – say, c – had already been visited once, I just added c. as the second visit, and added an extra check to avoid third visits. Then, just reserve each small cave, except for start and end, one by one and calculate from there. Ezpz gg no re.

Day 13 Lucky number 13. This was my last day of class, and I managed to solve the entire thing in a noisy lunchroom, where my classmates were running a White Elephant, all the while maintaining a few conversations with friends.

Even with a few blank lines for readability, my code for the whole day clocks in at just 50 linres, which I'm quite proud of. I could probably run my Part 2 a little faster if I used a more memory-efficient method of storing points than a dense array of zeroes, and if I was a little more clever in terms of determining which points I needed to copy. But honestly, two seconds to get a fun secret message is fine. To my knowledge, this is the first AoC puzzle where you needed to visualize your (textual) puzzle answer, that I actually solved on the day of.

Day 14 I woke up in another bed, cuddled up close to my partner, who then brought me coffee while I snoozed. Doesn't get much better than that. After a brief fiasco involving a Bounty-commercial level of liquid spillage in the span of about two seconds, we changed the sheets and I tucked into today's problem. Even through my bleary eyes, I somehow immediately recognized a few important insights: 1. Since every pair converts a pair into a single molecule, every molecule except the first and last will be involved in exactly two reactions. 2. The actual order of the string doesn't matter, since you can determine which rule will apply next based on what rule is applying now. So, you can store the polymer as a counter of pairs, rather than trying to brute-force the whole thing in memory, and count the number of times each molecule appears by just summing up all pair counts where the molecule appears. 3. The last molecule never changes; it just gets "pumped" out (see the $z$ in that first example).

So, the implementation phase was only as complicated as visualizing how to keep track of the number of pairs on a particular turn, and where those pair counts would get "sent" based on what the next applicable rule was. I did briefly forget Insight 3 above when I was finishing up P1, leading to a minor off-by-one error that could have invisible consequences (i.e., by the second-smallest value being chosen by accident), but I fixed that up right after seeing my first submission fail. Then, since I already had a working, memory-efficient solution, P2 was literally a copy-paste, replacing the number 10 with 40, and ran just as fast.

Day 15 Yeesh, another 2D-grid traversal problem!? Hopefully, this combines the AoC tropes of the 'weighted-grap traversal' and 'hard math it's usually easier to Google the O(1) formula for than figure out yourself' problems, so I don't have to see either of them again this year.

I guess I can consider this day a 'sweat', i.e., having difficulty with a type of problem I don't see very often, but then having the experience to quickly dispatch of similar problems in the future. Frustratingly, I immediately knew what the solution was – Dijkstra's Algorithm, or any similar min-cost path search – but don't have an implementation to mind. I ended up using a simple Uniform Cost Search (UCS) algorithm off Google, which is literally just BFS with a priority queue (thanks, heapq!). I'm not gonna lie, I still don't entirely grok why such a simple change to a greedy algorithm creates guaranteedly-optimal behaviour, but hopefully my roommate will explain it to me in a future whiteboard session.

Well, that's it for this block. As of writing, I'm almost through the next block, and... boy. That'll be a fun one to write up.

Ciao!

[1]: Don't come for me. I literally wrote a whole paper on the special plurals of words like 'octopus'. TL;DR: use whatever you want, but shut up about other people using a different variant than you. There's no 'logic' to be had in English declension, so don't think you can pick a most logical option.

[2]: Though, DFS' recursive calls run into the unique issue of pass-by-reference causing accidental mutations, but once you recognize it it's just a matter of .copy()ing your visited-nodes array/set.

0 notes

oliverpdaniel · 2 years

Text

Advent of Code 2021: Reflection on Days 6-10

A pretty interesting group of problems, again laying down some of the groundwork for classic AoC problems (and competitive-programming concepts in general). They do a great job introducing new players to some of the classic problem-to-solution translations: what phrases imply certain algorithms, data structures, etc. Here are my thoughts:

Day 6 One of the metrics my roommate and I have come up with for the difficulty of a given problem is the number of sittings it takes to complete. This was my first two-sitting problem: after the naive simulation proved too much for my poor CPU to handle, even after letting it run while I brewed my pre-class coffee, I had to use my subway ride to think up a solution. And just as I stepped onto the train, it hit me -- circular lists. Why is it that whenever an aquatic-animal-themed AoC problem resists brute-forcing, the answer is always circular lists!?

Anyway, a little bit of simple list arithmetic later, I have a solution that runs even P2 in pseudo-instant time. Looking on the subreddit for what others did, especially to solve the googol challenge, I was shocked to see people using powers of adjacency matrices. Abstract computer science concepts!? In my Advent of Code!?

Day 7 A fun one, and the first math-category problem of the year. This day is a particularly great case study in the importance of good computer-science vocabulary fpr solving problems. In P2, for example, it may seem like a for-loop is the only way to summatively add the crabs' fuel cost but, of course, knowing Gauss' famous formula for the triangular numbers made the day a snap. Unfortunately, I'm never going to beat my roommate for speed as long as I'm writing Python, because the bastard has access to the deep magics, but I had some fun trying to shave off microseconds where I could:

small brain: dividing each individual triangular number by 2 bc that's the formula big brain: only dividing the whole sum of fuel by 2 for each hypothesis galaxy brain: finding the minimum fuel and then dividing the answer by 2 just before printing

Day 8 RTFI, Oliver. And maybe GTFTB (Go.. To Bed), Oliver, and don't try to solve problems while:

a) intoxicated;

b) sleep-deprived after grinding multiple final assignments all week; and

c) still thinking about said assignments, which you put off doing to write silly little programs.

Another two-seater. I just know that there's a beautiful, intelligent solution to instantly decode which light segment is which; but, as my roommate pointed out, 7 segments is small enough that you can just brute-force every possible permutation. (I, myself, am beautiful and intelligent; just my solution isn't.) As a result, though, this is my first problem of the year to take more than a second to run.

It also helps not to have a f*cking typo in your list of actual segments, before you spend an hour scratching your head wondering why none of the decodings seem to work.

Day 9 If I ever become one of those cool kids who makes his own AOC toolkit, replete with commonly-used tools and maybe a cronjob or two to automatically download my inputs at midnight, this would be the first tool on my belt:

def _neighbours(G, r, c): for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]: if not 0 <= (y:= r + dy) < H: continue elif not 0 <= (x := c + dx) < W: continue yield G[y][x]

(well, that or the eight-neighbour variant, which I used – to surprising sucess – in P1. Whether a coincidence or an intentional move by the input generator, RTFI!) Eric Wastl seems to love cellular-automaton- or convolution-based questions, where the properties of one item (cell) in a grid is affected by the simultaneous properties of its adjacent neighbours.

This problem was actually slightly different than those, being a flood fill question instead, which means that the second thing I add to my toolkit would be a recursive traversal method like DFS.

Although I sometimes chuckle at the innocence of people in the subreddit posting "I'm new to programming but my input is DEFINITELY wrong!!! My solution works on the test, so CLEARLY there's a bug on your end!", this is the first time in a while I have to stick my nose up slightly at the problem statement itself:

A basin is all locations that eventually flow downward...

Based on this description, in combination with the fact that all examples have smoke flowing "downward" to a tile with a height one less than the tile it started on, I initially thought that smoke could only flow that way (i.e., if two tiles differed in height by exactly one). It took me semi-frustratedly breaking my rule by opening the subreddit and watching a few visualizations to understand what I was doing wrong. Luckily, with the way I had organized my code, it only took changing one quick line, and didn't affect performance practically at all, but I still think my objection to the problem statement's clarity stands. I think Eric could have specified what "downward" meant a little better, which would have made Parts 1 and 2 just a little bit easier to grok.

Day 10 My toxic trait is not listening to myself, apparently. Once again, I did a problem at midnight while slightly intoxicated, which was not a smart move, making for my third two-sitting problem.

I'm currently having a love affair with the unexpected speedup of using generators instead of lists, which resulted in a pretty cute P1 solution: not even bothering to get incorrect characters by line, I simply issued a stream of the first incorrect character per line, then summed them up using a score dictionary.

Part 2 is what took me until the morning to solve, and also which took me realizing I need to RTFI!!!! – I was trying to analyze the incorrect lines, not the incomplete (i.e., remaining) lines. Aaaaaargh!

Anyway, once I had that figured out, the solution is pretty straightforward, and I imagine that most solvers who aren't first-time programmers probably used a relatively similar solution to mine. I wonder if anyone solved theirs using Vim macros or similar, along with an auto-bracket extension. That would be pretty funny.

See you in 4!

0 notes

oliverpdaniel · 2 years

Text

Advent of Code 2021: Reflection on Days 1-5

It's the most wonderful time of the year...

After such a difficult and tiring year, I'm not even ashamed of how my roommate and I counted down to Advent of Code once the leaves started falling. I consider it a kind of sport that we both share a love for: we chat about our solutions, problems we found easy or hard, and how neither of us can ever read the other's Python for all the differences in our styles. (One of these days I'll have to learn Numpy, just to show him up.) Our leaderboard has never been more full of interested friends, which is like its own kind of Christmas lighting to me :)

Anyhow, with that in mind, I'm glad to keep up this little tradition of commenting my thoughts and findings from all 25 problems, in five-day instalments. And, if you're reading this after checking out my BI portfolio, hello! One thing I learned from last year is that spoilers don't work very well with my blog theme, which I'm too lazy to update. So, I just won't use them this year. Browse at your own risk. And, if you really want to ruin each day's puzzles, you can find my code here.

Without further ado, let's save Christmas!

Day 1 As usual, just a good chance to stretch my legs and make sure my workflow is good for this year -- I've got a nice template file, I'm opting to return values from each of p1() and p2() for printing, and I know how to set my working directory so input and test files are read appropriately. One 'resolution' for this year's AoC was to start saving the test inputs in their own folder, so that I didn't have to awkwardly copy-paste them in when I needed them and comment them out once I didn't.

Part 2 required a little bit more thinking than I was expecting, but I ended up just splitting up the calculations into a two-phase pass, one to build the prefix-sum array and one to check for decreases. No biggie, and I slightly beat my roommate to the second star after waiting until midnight. Won't be doing too much of that until the term is over.

Day 2 To entertain myself on the first few days, I often attempt the meta-Advent of Code challenge: trying to figure out what basic AoC concept Eric Wastl is trying to teach first-timers. Here, it's quite simply the extremely common pattern of parsing a series of command-like tokens. I decided to be cute and, after downloading Python 3.10, use the new match-case syntax to solve the problem. As it turns out, it didn't make it much shorter, and technically made it more inefficient since the parser has to look up the int function more than once! Oh well; programming swag is always more important than good code[^ This does not apply if you are my boss. Then good code is more important.].

Day 3 Good luck reading my code on this one. This definitely constitutes write-only code, but becomes a little easier to read once you notice a coouple of my favourite tricks:

"01"[condition] is a shorthand form of "1" if condition else "0";

gamma ^ ((1 << K) - 1) gets the "negated" form of gamma, (i.e., the epsilon value), relative to its number of bits.

Part 2 gave me a few moments of head-scratching, but I decided to get an answer out by copy-and-pasting code rather than creating an elegant, DRY solution.

Day 4 The importance of RTFI (reading the instructions) rears its ugly head again. Luckily, this time I didn't fall prey to the trap, sleepy as I was in the morning, and did see not to account for diagonals. It shows how much I've progressed as a programmer that as soon as I saw that it was a simulation-style problem, my pre-coffee brain still immediately went to pre-calculating all the winning combinations as sets, asssociated with their relative index. I'm not sure how fast set.issuperset() is (here shown as the equivalent set.__geq__) or if it has any smart controls for exiting early if, say, the set in question is smaller than its argument, but all the code runs effectively instantly for both days, so whatever.

Also quite proud of my usage of generators to yield successively-completed bingos in a memory-efficient fashion, which means that my P2 only has to run through as many draws as it takes for the final board to win.

Day 5 After some initial difficulty with parsing the data into the desired format -- a list of tuples -- P1 went off (mostly) without a hitch, except for two things:

Forgetting to exclude non-orthogonal lines; and

Not realizing that lines were not always given in ordered pairs.

Once I fixed those two things, P2 was a function of just porting the code over and -- oops! A nested for-loop was okay in P1, since one of them was always guaranteed to run exactly once, but in P2 it ended up covering a whole rectangle instead of just the diagnonal. I really wish Python would do away with requiring step=-1 when the range start is greater than the range stop, and just do what I want it to do. Don't you know I have precious bytes to save!? In truth, I probably should have just calculated the (Manhattan) length of the diagonal and used a single for-loop to mark spots along its length, considering that all diagonals were 45°.

Using a dictionary as a memory-efficient sparse array was a smart idea, but wasn't nearly fast enough to handle this challenge code.

See you on or after the 10th, where I'll be continuing this series with the next instalment of puzzles. Until then, stay warm and good luck on finals!

0 notes

oliverpdaniel · 3 years

Text

Advent of Code 2020: A (very timely and not late at all) Reflection on Days 15-25

...Um. Oops?

Honestly, everything has been happening so much lately, I'm not super frustrated that it's been a clean month between finishing these puzzles and commenting on them. During these weeks, along with finally finishing my first-ever Advent of Code (as did my roommate! Well done, buddy.), I also wrapped up my second semester in quarantine, including a few brutal final projects and exams. After a nail-biting few weeks of awaiting grades, I finally had the confidence to withdraw for the second semester, and to begin hunting for work. (If you're reading this and I'm not hired yet, hire me!)

Anyway, the obvious downside to the sheer magnitude of the delay is that most of these puzzles aren't super fresh in my head, and thus my commentaries may not be as detailed as I would like. Hey - if I ever get such a massive executive-dysfunction-killing buzz as I did over the winter break to finally clean and redecorate my room, maybe I'll revisit these too.

Day 15: Now we're seeing some REAL slowness! The primary data structure for both parts here was the dictionary, mapping "seen" (spoken) numbers to the last turn on which they were spoken. That being said, I don't know what I was thinking in Part 1, with code like this:

Code ``` for k in seen.keys(): seen[k] += 1 ```

As soon as I saw the spicy thirty million in Part 2, I knew my naive solution wouldn't even touch it. [1] I had to do my least favourite thing - off-by-one debugging, but I ultimately came up with a relatively clever insight:

Spoilers Storing not just the last turn on which a number was spoken, but the last *two* numbers (if they exist). Doing this allows for a three-case scenario, for some current number `curr`: 1. `seen[curr]` is empty or doesn't exist. This is the base case of a new number; output 0, as stated in the problem. 2. `seen[curr]` has 1 value. It's only been seen once, so we can calculate the number of turns since it was last seen. 3. `seen[curr]` has 2 values. This number has been seen twice, so we can simply subtract the first- and second-most recent turn numbers to get the gap between them!

This problem took a bit of fiddling, but runs okay. Python really shows its ugly side here, as even a fairly efficient solution like this one, using efficient data structures, takes quite a while on Part 2.

Day 16: Boy oh boy. I spent far too long on this one, and perhaps if there are any to revisit for a future post, it's this one. My solution for this one features no less than:

regex;

closure functions;

constraint satisfaction;

functions that return tuples of variable length; and

walrus operators.

I consider this problem a 'sweat' for future years; I learned a lot about what makes constraint-satisfaction engines tick, and how it's important to assign constraints to the smallest possible element of a search space (here a column, rather than an entire permutation of columns). I think there's a much more concise and semantic way of outlining this problem, that lets the solver do much more of the work than I did.

Day 17: Not much to say here; it's a cellular automaton with extra for loops. I'll share two cute things that I'm proud of:

Spoilers 1. I experimented with various thresholds for the size of the 'infinite' space, making specifically sure not to to index checks, so that I could have the smallest possible subspace to check over. I ended up settling on a value of `20` units in each direction from: 2. the origin I specified, which is simply `LIMIT // 2 - H // 2` (where `H` is just the dimension of the input grid).

My roommate complained that it took him a long time to parse and understand the problem; I'll confess that I barely read it. I guess that's the advantage of experience, in that I saw "Conway" and "space" and knew immediately what needed to be done.

I didn't do anything special for Part 2; it's just my Part 1 code, copied and pasted, with an extra for loop here and a variable there. sum(sum(sum(sum())))s for everyone!

Day 18: I think that, out of all 49 unique problems in this year's Advent of Code, I'm most proud of my solution to this one. It's (relatively) fast; the code is pretty easy to read and works for both parts (and more! [2]); and I came up with a solution before knowing the name for what I had built. (Update: it's a shift-reduce parser. Hooray for stacks!) One especially cute thing, that incidentally ended up defining my approach to a lot of the later problems, was

Spoilers creating a lookup table between a certain input symbol, here math operators, and an internal function, here the builtin `int` math functors. This allowed for a dead-simple evaluator function, for when the top of the stack was ready to be converted from an expression to a workable number. Also, I had the bright idea to recursively evaluate bracketed expressions, in such a way that an expression like `(((1 + 2)))` would quickly reduce down to `1 + 2` before the rest of the parser got to it.

Day 19: Aaaaaaaaargh! Herein begin the Two Days of Terror - the two hardest problems. Lucky I had returned from my partner's by now, as I think they would have been quite upset with how much I was ignoring them to code. After solving Part 1 in the morning I finally finished Part 2 at around 7pm, having forgotten to otherwise eat or attack my household responsibilities, and only after my roommate sat down with me and pair-programmed for a while. This one stung the most, because... I'm a linguist, for crying out loud! No generative grammar problem, especially ones over a finite search space like this, should be causing me such grief.

Day 20: I am still emotionally recovering from this problem. My roommate somehow managed to get both parts to run instantly, using the most cursed CSP setup I've ever seen. I still need to study his code better to understand just how he did it. Also, his usage of scientific Python packages finally shows its rewards, as convolution over a matrix is a friggin' builtin function. Grr.

Day 21: I consider this day an apology for the previous Days of Terror. Some fun, but not terribly difficult, set-fu. My relative inexperience with set theory shows its stripes here; I'm sure there are much more semantically sound ways of accomplishing what I tried to do here (e.g., manually removing an allergen from each ingredient's list of hypotheses once it was confirmed to go with a certain ingredient).

Day 22: Spicy spicy numbers! It would have served me much better to read the instructions before starting, as then I would have known that

Spoilers in Part 2, players don't take their entire deck with them. Since, y'know, that would just cause an infinite race to the bottom.

Day 23: Even spicier numbers! If you're going to be cute like me and establish 9 as a constant, make sure that you don't use it in Part 2 when constructing the initial circle, or you'll wonder why 9,999,990 of the cups aren't attached to anything.

Day 24: I couldn't sleep, so I solved this problem at 3 in the morning. Not going to lie, a little disappointing for a penultimate problem, especially Part 2. Part 1 required at least a modicum of cleverness to develop a meaningful coordinate system, but then Part 2 just felt like a relative rehash of the Conway Cubes problem. 3 cellular automaton problems out of 25 is a little bit much, considering how formulaic they can be.

Day 25: As true evidence of how much I learned over this Advent of Code, I was able to finish Day 25 on the couch without even bothering my partner. Utilizing what I had learned about pow made defining the transform (i.e., repeated multiplication and mod) incredibly easy. Though, I did get a little bit lucky, due to a small oversight in problem setting...

Spoilers Rather than having to generate and test a whole bunch of different pairs of loop sizes for the card and the door, it turns out that if you `zip` together two streams of all such valid loop sizes for the card and door, respectively, the correct size for both (i.e, the solution) appears at the same time; for me, just the second such pair of sizes.

Day 25 Part 2, as always, was a delight and a pleasure. If you've never clicked that final button before, crack open a text editor and start solving challenges until you can. It's deeply satisfying.

I cannot sufficiently express my gratitude to the entire AoC team, setters, testers, and maintainers alike, for all that they do. A daily stream of bite-sized (or, sometimes, sea-monster-sized) challenges is just what I need to keep me going, and my skills sharp, over the dreary holiday season. Especially in a year like this, it was just what I needed to keep me moving, motivated, and thinking about code. I can't wait for next year's challenges and, hopefully, I'll convince the roomies to do it with me again.

Sorry about the little delay, and the relative lack of detail. But, the enemy of perfect is good enough. If you're reading these at some point in the distal future, I hope you've enjoyed watching my journey through these problems, and maybe learned a little bit about what it means to think like a programmer. Thanks for tuning in!

[1]: I tried it anyway; it obviously didn't work. And, once my roommate turned me onto tqdm, I was able to see just how long before the Heat Death of the Universe for it to run. It was about 3 days. Lol.

[2]: The way I constructed the code, it would be extremely easy to add in the remaining integer operations.

0 notes

oliverpdaniel · 3 years

Text

Advent of Code 2020: Reflection on Days 8-14

A really exciting week, with a good variety of challenges and relative difficulties. Something tells me that this year, being one where people are waking up later and staying at home all day, the problems have been specifically adapted to be more engaging and interesting to those of us working from home. Now that we've run the gamut of traditional AoC/competitve-programming challenges, I'm excited to see what the last 10 days have in store!

First things first, I have started posting my solutions to GitHub. I hope you find them useful, or at least not too nauseating to look at.

Day 8: To me, this is the quintessential AoC problem: you have a sequence of code-like instructions, along with some metadata the programmer has to keep track of, and there's some minor snit with the (usually non-deterministic) execution you have to identify. Some people in the subreddit feared this problem, thinking it a harbinger of Intcode 2.0. (Just look at that first line... somebody wasn't happy.)

Effectively, I got my struggles with this kind of problem out of the way several years ago: the first couple days of Intcode were my How I Learned to Stop Worrying and Love The While Loop, so this problem was a breeze. It also helps that I've been living and breathing assembly instructions these past few weeks, owing to a course project. I truly must learn, though, to start these problems after I finish my morning coffee, lest I wonder why my code was never executing the "jump" instruction...

Luckily, from here on out, there will be no more coffee-free mornings for me! Part of my partner's Christmas present this year was a proper coffee setup, so as to liberate them from the clutches of instant coffee. I'm not a coffee snob – or, at least, that's what I tell myself – but I was one more half-undrinkable cup of instant coffee away from madness.

Day 9: Bright-eyed, bushy-tailed, and full of fresh-ground and French-pressed coffee, I tackled today's problem on the sofa, between bites of a toasted homemade bagel.

This is a competitive programmer's problem. Or, at least, it would have been, if the dataset was a few orders of magnitude bigger. As of writing, every problem thus far has had even the most naïve solution, so long as it did not contain some massive bottleneck to performance, run in under a second. At first, I complained about this to my roommate, as I felt that the problem setters were being too lenient to solutions without any significant forethought or insight. But, after some thinking, I've changed my tune. Not everything in competitive programming[1] has to be punitive of imperfections in order to be enjoyable. The challenges so far have been fun and interesting, and getting the right answer is just as satisfying if you get it first try or fiftieth.

First off, if I really find myself languishing from boring data, I can always try to make the day more challenging by trying it in an unfamiliar language, or by microprofiling my code and trying to make it as efficient as possible. For example, I'm interested in finding a deterministic, graph theory-based solution to Day 7, such that I don't just search every kind of bag to see which kind leads to the target (i.e., brute-forcing). Maybe I'll give it a shot on the weekend, once MIPS and MARS is just a distant memory. A distant, horrible memory.

Second, even I – a grizzled, if not decorated, competitive and professional programming veteran – have been learning new concepts and facts about my own languages from these easy days. For example, did you know that set membership requests run in O(1) time in Python? That's crazy fast! And here I was, making dictionaries with values like {'a': True} just to check for visitation.

Part 1 was pretty pish-posh. Sure, in worst-case it ran in O(n^2), but when you have a constant search factor of 25 (and not, say, 10^25), that's really not a big deal.

Part 2 is what made me think that today's problem was made for competitive programmers. Whenever a problem mentions sums of contiguous subsets, my brain goes straight for the prefix sum array. They're dead simple to implement: I don't think I've so much as thought about PSAs in years, and I was able to throw mine together without blinking. I did have to use Google to jog my memory as to how to query for non-head values (i.e., looking at running sums not starting from index 0), but the fact that I knew that they could be queried that way at all probably saved me a lot of dev time. Overall complexity was O(nlogn) or thereabouts, and I'm sure that I could have done some strange dynamic programming limbo to determine the answer while I was constructing the PSA, but this is fine. I get the satisfaction of knowing to use a purpose-built data structure (the PSA), and of knowing that my solution probably runs a bit faster than the ultra-naive O(n^3)-type solutions that novice programmers might have come up with, even if both would dispatch the input quickly.

Faffing around on the AoC subreddit between classes, I found a lovely image that I think is going to occupy space in my head for a while. It's certainly easy to get stuck in the mindset of the first diagram, and it's important to centre myself and realize that the second is closer to reality.

Day 10: FML. Path-like problems like this are my bread and butter. Part 1 was easy enough: I found the key insight, that the values had to monotonically increase and thus the list ought to be sorted, pretty quickly, and the only implementation trick was keeping track of the different deltas.

Part 2, on the other hand, finally caught me on my Day 9 hubris: the naïve DFS, after ten minutes and chewing through all of my early-2014 MacBook's RAM, I still didn't have an answer. I tried being creative with optimizing call times; I considered using an adjacency matrix instead of a dictionary-based lookup; and I even considered switching to a recursion-first language like Haskell to boost performance. Ultimately, I stumbled onto the path of

spoilermemoization using `@functools.cache`

which frankly should have been my first bet. After some stupid typo problems (like, ahem, commenting out the function decorator), I was slightly embarrassed by just how instantly things ran after that.

As we enter the double-digits, my faith in the problem-setters has been duly restored: just a measly 108-line input was enough to trigger a Heat Death of the Universe execution time without some intelligent intervention. Well done, team!

Day 11: Good ol' Game of Life-style state transition problem. As per usual, I've sweated this type of problem out before, so for the actual implementation, I decided to go for Good Code as the real challenge. I ended up developing – and then refactoring – a single, pure state-transition function, which took in a current state, a neighbour-counting function, and a tolerance for the one element that changes between Parts 1 and 2 (you'll see for yourself), then outputting a tuple of the grid, and whether or not it had changed in the transition. As a result, my method code for Parts 1 and 2 ended up being identical, save for replacing some of the inputs to that state function.

Despite my roommate's protestations, I'm quite proud of my neighbour-counting functions. Sure, one of them uses a next(filter()) shorthand[2] – and both make heavy (ab)use of Python's new walrus operator, but they do a pretty good job making it obvious exactly what conditions they're looking for, while also taking full advantage of logical short-circuiting for conciseness.

Part 2 spoilers My Part 2 neighbour counter was largely inspired by my summertime fascination with constraint-satisfaction problems such as the [N-Queens problem](https://stackoverflow.com/questions/29795516/solving-n-queens-using-python-constraint-resolver). Since I realized that "looking for a seat" in the 8 semi-orthogonal directions was effectively equivalent to a queen's move, I knew that what I was really looking for was a delta value – how far in some [Manhattan-distance](https://www.wikiwand.com/en/Taxicab_geometry) direction I had to travel to find a non-aisle cell. If such a number didn't exist, I knew not to bother looking in that direction.

My simulations, whether due to poor algorithmic design or just on account of it being Python, ran a tad slowly. On the full input, Part 1 runs in about 4 seconds, and Part 2 takes a whopping 17 seconds to run fully. I'll be sure to check the subreddit in the coming hours for the beautiful, linear-algebraic or something-or-other solution that runs in constant time. A programmer I have been for many years; a computer scientist I have yet to become.

Day 12: Not terribly much to say on this one. Only that, if you're going to solve problems, it may be beneficial to read the instructions, lest

spoilers You cause your ship to turn clockwise by 90º... 90 times.

The second part was a fresh take on a relatively tired instruction-sequence problem. The worst part was the feeling of dread I felt while solving, knowing that my roommate – who consistently solves the problems at midnight, whereas I solve them in the morning – was going to awaken another Eldritch beast of Numpy and linear algebra for at least Part 2. Eugh.

Day 13: This was not my problem. I'm going to wrap my entire discussion of the day in spoilers, since I heavily recommend you try to at least stare at this problem for a while before looking at solutions.

spoilers The first part was... fine. The only real trick was figuring out how to represent the concept of "the bus arrives at a certain time" (i.e., modulo), and just compare that to some offset relative to your input departure time. Simulation works perfectly fine as a lazy solution, since your smallest input value is likely to be something like 13 (and thus your simulation time is bounded). The second part? Not so much. I knew that I was cutting corners on the first solution, since this problem was just *screaming* to look more mathy than code-y. And, turns out I was right: the problem could be solved on pen-and-paper if you were so inclined. If you look around on the subreddit and other comparable programmer spaces, you'll see everyone and their mother crying for the [Chinese Remainder Theorem](https://www.dave4math.com/mathematics/chinese-remainder-theorem/) and, since I have to establish boundaries around my time and energy lest I nerd-snipe myself into academic probation, I had to "give up" relatively quickly and learn how to use the algorithm. My roommate was able to come up with a solution on his lonesome, which actually relies on a fact I was also able to come up with before giving in. If you use a simple for-loop search to find numbers which satisfy any **two** of the modulo requirements, you'll quickly realize that the gap between any two succesive numbers is always equal to the product of those two numbers. (Well, technically, their LCM, but the bus routes are prime for a reason.) So, you can pretty quickly conclude that by the end of it, you'll be searching over the naturals with a step of ∏(buses), and the only trick left is to figure out what starting point you need. I think my roommate was at a bit of an advantage, though, owing to his confidence. He's definitely a lot better at math that I am, so he could dive into hunches headlong with a confidence that I lack. I found myself unable to follow hunches due to worry that I was either a) completely missing the point, or b) would accidentally make some critical arithmetic mistake early on that throws off all of my findings. In hindsight, I absolutely *should* have figured out that final Giant Step (hue), and then worked it backwards from the given answer to see what starting points made reasonable sense. But, again, I balked a bit at the sheer enormity of how much I didn't know about this kind of algebra, so I ended up needing a little more Google than brainpower. I'm chalking this problem up as a learning experience, as I truly had never heard of the CRT. I'm sure "linear systems of residue classes" will pop up again in a similar problem, and it's certainly a hell of a lot faster to compute than using sieves or similar algorithms. Also, I learned that Python 3.8 programmers had a distinct advantage over lesser-versioned Pythonistas, owing to the new functionality that was recently added to the `pow` builtin. In short, `pow` can now solve modular inverses, which is a massive timesave over implementing it yourself. I didn't know about this builtin at all, so I've continued to accomplish my goal of better understanding the standard library.

Day 14: The last day of this week! I really enjoyed today's challenge: it was tough, yet accessible from multiple approaches if you weren't a well-learned expert on bitwise masking.

Part 1 was just getting you acquainted with the world of bitmasking and the general workflow of the problem: number in, pass through mask, number out, store in memory. As usual, the formatted text made my Regex Lobe go off, and for once I gave in: it actually made extracting those integers a little easier, as I realized the addresses were of very variable length.

Part 2 was a perfect level of challenge for a Monday morning, methinks. It served me a proper punishment for not reading the updated challenge text appropriately, and I had to think about some clever modifications to my code from Part 1 to make Part 2 work effectively. My final solution wasn't all too efficient, but both parts run in a little under two seconds.

Part 2 spoilers I'm quite proud of my usage of `'0'` to denote a "soft" zero (i.e., the mask does nothing to this bit) and `'Z'` to denote a "hard" zero (i.e., the mask sets this bit to zero). I suppose I could have also inverted the entire mask – setting all `0`s to `X`s and all `X`s to `0`s – to make the old parse function work normally, but this worked just as well and didn't require completely rejigging the masks to make them work a particular way.

[1]: I keep having to stop myself from using the acronym with which I'm familiar, lest I get in trouble with Tumblr's new puritan filters. I wonder if the similar acronym for dynamic programming would be of issue.

[2] If you're unfamiliar, this is a common competitive-programming idiom in Python for "the first element that satisfies..." JavaScript, unfortunately, takes the cake here, as it has a native Array#find method that works much better.

0 notes

oliverpdaniel · 3 years

Text

Advent of Code 2020: Reflection on Days 1-7

All in all, a pretty simple week. Tougher points, for sure – though I was often coding at the stroke of midnight, and often with a brain addled with melatonin and ~other things~ – but nothing so revolutionary it couldn't be done.

Day 1: I must admit, this pandemic season made me forget all about the Advent of Code until December 2nd, when it popped up on my feed. So, Day 1 I had to do out of sequence. No problem.

As usual, Day 1 is just to help those who are unfamiliar with competitive-style programming get their feet wet with the input-algorithm-output workflow. The dataset was nowhere near big enough to cause the naive O(n^2)[1] solution not to work, so I decided to focus on making my solution elegant, Pythonic, and making appropriate use of the standard library. itertools.product came well in handy here, and using an iterator kept memory complexity lower than a list-based product.

My roommate's solution, conversely, was a deeply cursed Frankenstein's Monster of linear algebra. I still don't want to talk about it.

Fun fact: According to Reddit, the first star (i.e., Day 1 Part 1) was earned just 36 seconds after midnight, probably by someone with at least two monitors and a light-up keyboard.

Day 2: Whenever my brain sees regularly-formatted strings of different pieces of data, my Regex Lobe immediately starts firing synapses. Though, of course, as it was famously said:

If you have a problem and solve it using regex, you now have two problems.

Just some good ol' split() tokenization was all that was needed here. Python's comparison-chaining (e.g., lower <= x <= upper) syntactic sugar really helped here. I could have made it even more terse if I really wanted to – competitive programmers are usually averse to lines of code like:

counter = 0 if condition: counter += 1

But it really, really wasn't worth the effort here. Save that for days that start with 2, not end with it.

Day 3: This one gave me more trouble than I care to admit, and I actually had to revisit it later in the day. Ultimately, although I had immediately realized that this was a modulo problem (cf. simulation), I was having difficulty visualizing just where all the numbers needed to go. A little bit of funkiness with the ordering of lines in my algorithm here, but once I figured out Part 1, Part 2 was a breeze. Got to use a pretty cool looking slice –N[dy::dy] which ended up doing exactly what I needed it to do to handle the various slopes. Cool puzzle, and great winter theming!

Day 4: Glory to Arstotzka! Even though I solved this problem in Python as well, my roommate agreed that my solution was pretty friggin' JS-y. I ultimately caved to my reptillian regex brain, using a whopping 7 different re.match calls (though some of them were just out of additional caution, such as making sure certain numerical values were exactly 4 digits). Call me a UI dev, because I don't trust my input to be well-formed at all. Ever.

I also used a neat little field->validator function lookup table, though the clunkiness of Python's lambda keyword really starts to show itself. It's a shame van Rossum so vehemently opposes (opposed?) making Python more amenable to function-style programming. I learned a lot about it from my JS days, and it's often a very reusable way to solve problems. CAUSE NO TROUBLE.

Day 5: I've been had. My roommate got got too. I followed the problem directions too closely, not realizing the obvious solution right under my nose. Ugh. Maybe checking others' solutions on the AoC subreddit – after I finish my own, of course - is detrimental to my mental health.

My solution for Part 2, considering, is quite clever – I just sorted the list of flights, lopped off the first and last values, and enumerated it starting the index at whatever the second flight value was. Then, whenever there was a mismatch, we had found the gap. I saw others using the famous XOR hack, which was probably slightly more efficient than my list sorting. Oh well. I was too tired to be doing that kind of math.

Day 6: Every first week of a programming challenge needs a sets problem. I don't use sets very much at all, so I did it in a more programmer-oriented approach; my roommate, conversely, is a data scientist who lives and breathes sets, both in Python and math. He absolutely crushed my time on this one. (Not that it's a competition or anything...)

Day 7: The first challenge to give pause to both my roommate and me. The hardest part, to be honest, was just parsing the friggin' data. I tried to use regex again, if for no other reason than to flex my skills on my roommate. But, it turns out that Python regex doesn't support non-greedily capturing lists of repeated groups, i.e., r'([ab])+' will only ever capture a single letter, usually the first to satisfy it. So, matching on aba will just yield a single group of a. Sigh.

After doing it properly with some list comprehension-fu, it was a pretty straight shot, using some good ol' DFS on both parts to calculate paths. I was almost disappointed that the input data, despite being so intimidatingly large, allowed my relatively naive solutions (i.e., just checking every bag for Part 1 to see which led to shiny gold, and simple, non-tail-recursive sums in Part 2. Considering I just had a whole test on recursion efficiency in Racket, I should probably have done something smarter. Lol.) to run almost immediately. I was hoping to have to be clever to tackle the larger dataset.

To make myself feel better, I renamed my graph – really just a lookup table, tbh – SAURON, because it sees all. Also, I was tipsy and couldn't think of a better name. We live in a pandemic; leave me alone.

Anyway, this was a fun first week, and I'm looking forward to problems becoming increasingly head-scratching. My living room has a gigantic whiteboard in it for a reason.

[1]: TODO: add MathJax support to my blog :)

0 notes

oliverpdaniel · 3 years

Text

Advent of Code 2020

Most years, my December schedule (and motivation) permitting, I try to complete the Advent of Code, a 25-day progression of Christmas-themed holiday challenges. In some years, you may gradually build up your own programming language compiler to help Santa rescue the elves; in others, you may be assisting the reindeer with their job scheduling. It's a lot of fun, and this year I've roped my roommates and a handful of friends to do it with me!

In the first half, this will likely have a more friendly-competitive feel, as we race to see who can solve both parts of the day's challenge first after they drop at midnight in our time zone. Just this morning, I came into my roommate's room and simply said, "It's 12:01"; nothing more was needed to get him to fetch his laptop and start reading the challenge. However, the real trick will come in in the second half of the challenge, which is famously difficult. I've never been able to solve all fifty challenges (25 days x 2 parts each) on my own, and this year I'm really hoping to top my ASCII-art Christmas tree with that glorious 50th on Christmas Day. So, by keeping a streak going, we can come together and combine our brainpower on tougher challenges.

Each of the four (well, 3.5) weeks of the Advent of Code, I'll try to write up a quick reflection on that week's challenges. In the beginning, these will be simple, as solving the challenge is usually no more difficult than the competitive programming I did almost every day in high school. But, as it takes more and more time to solve each challenge, hopefully I can share some cool insights. If I think the average reader (who can, uh, code) would be able to solve the problem on their lonesome, I'll try to be vague about what my actual solution looked like.

FTR: I primarily write my solutions in Python, if for no other reason than just to maintain the edge on my Python skills that may have been dulled at the grindstone of endless Django projects. I may occasionally write a day or two in another language, either if I perceive that language has a particular idiom that would be useful for the day's challenge, or if Python is just too darn slow on the large input dataset. I may or may not upload my code to a GitHub repo soon, but will obviously be keeping my own input private.

0 notes

oliverpdaniel · 3 years

Text

Let’s talk about casual homophobia.

I wanted to share a transcript of a TikTok video by a minor celebrity (I won't do them the honour of identifying them, but suffice it to say that this individual thrives mostly on controversy and poor publicity), to demonstrate what day-to-day homophobic language looks like. Many of these questions have been asked to me, or tell of real things that I've experienced, due to a generally callous view of queer folks. The quoted parts are the actual video, the unquoted responses mine.

Note in advance that some of these questions are clearly oriented towards gay men, but I am responding from the perspective of a bisexual man. Anyway...

"Okay, these are my questions for the gays – sorry, I was on Straight TikTok for a minute; what?"

Or, as you might like to call it, TikTok. For those unfamiliar, "Gay TikTok" is a small subset of the TikTok community that makes videos primarily revolving around in-jokes and shared experiences of the queer community. Thus, "Straight TikTok" is only extant in contrast, a joking reference to certain, overwhelmingly heteronormative parts of the TikTok community. While I'm not a big fan of the idea of 'ownership' or deciding who's allowed to say what, this (obnoxiously straight, in every sense of the word 'obnoxious') celebrity is trying somewhat unceremoniously to insert themselves into a narrative not their own here. Not off to a great start.

(1) "Would you care if your partner was bisexual?"

Whelp, this is one I can't really answer, can I? But, this still does lean into the old "gold-star" ideology of homosexuality, which makes it off-putting from the jump. For those unfamiliar, a "gold star" gay/lesbian is one who has never had sex with the opposite gender. This is a completely silly distinction, that fails to take into account personal circumstances, as well as – y'know – the fluid nature of human sexuality. TL;DR, even if you're exclusively into one gender, you shouldn't care about your partner's sexual orientation (other than, y'know, making sure it includes your gender) because, leaving aside the absolutely rad underworld of polyamory, they're only going to be into you while they're with you.

(2) "Have you ever been with someone of the opposite gender?"

Ah, more gold-starring! A great way to start. "You're trans? What's your deadname?"

(3) "Do you take offence when a girl calls you her Gay Best Friend?"

The Gay Best Friend is an expendable, non-threatening fount of femininity in masculine form, someone to go clothes-shopping with and who will give you sassy advice on boys. God forbid, however, that the Gay Best Friend try to be vulnerable with you about the difficulties of LGBTQIA+ life; they're only there for sashaying and making out with at parties, right? The Gay Best Friend is an incredibly harmful notion to men on both sides of the sexuality spectrum. Gay (and ESPECIALLY bi/pan/poly) men already know to fear the label, because of the dismissive treatment and expectation of performative homosexuality that comes along with it. Straight men should fight against it, too, because it's a symptom of the present hegemony of heterosexual relationships, which revolves around sexual transactionalism and a healthy dose of gender-role-fuelled intimidation[1]. (If you've never heard any of those words, you're probably the target audience here.)

(4) "Be honest – how many times has a straight person tried to hook you up with a gay person based solely on the fact that they're gay and no other compatibility requirements?" (with a devilish smile, into full blown "oh guuuuuurl" laughter)

This is a real thing that happens to people, myself included, all too frequently. It tells us that when you look at me, you don't think "Oliver", you think "Gay", and next time you meet another gay guy, that's the word ringing through your head. It's not funny. It's hurtful. If you're going to recommend a partner to me, make sure you actually have faith in a connection forming. As someone who ended up in an abusive relationship as a result of overzealous matchmaking, it's not something to be taken lightly; relationships, especially gay relationships and all the societal friction they inevitably entail, are not here for your endearment.

(5) "Are you down to hook up with someone who's 'just curious'?"

MORE gold-starring! God, could you imagine the uproar if a lesbian approached a straight person and said that they "missed dick" and/or wanted to experiment!? Oh, wait, that's already common in straight porn to the point of cliché. Gag; and not the good kind of gag.

(6) "Do you proudly wear the rainbow flag, or are you kinda against it because it kinda segregates?"

...what? When I first found this video, it was being duetted (TikTok's side-by-side video response) by a queer person, and at this point they took the opportunity to say, "I don't like you." I echo the sentiment.

(7) "Are you a 'yaaaaaas kweeeeen' gay or are you, like, 'fuck that shit what the fuck?'"

WE ARE NOT HERE TO PERFORM QUEERNESS FOR YOU. Leaving aside the sociolinguistic aspects of queer language and its intersection with (read: theft from) African-American Vernacular English, if people want to act flamboyantly gay, THAT'S NONE OF YOUR BUSINESS. If people want to act "normal" (read: heteronormatively!!!), that's NONE OF YOUR GOD DAMN BUSINESS. Queer people are fucking people, they act differently in different scenarios, and it's not for you to fetishize or to find "too much sometimes". When you accept a queer person into your life, you're accepting every facet of them into your life, for them to live and love unapologetically – not just the parts you find entertaining.

(8) "This might be a dealbreaker for me: do you like musical theatre?"

Yes. But even if I didn't – if I liked drinking beer and watching Nascar (sorry dad), but wish I had a boyfriend to do that with, guess what? That's my own fucking business. And, again, if your idea of a "dealbreaker" when engaging with a gay person is whether or not they like musical theatre – probably one of the most tired stereotypes about gay folks – and not, I dunno, if they're fun to be around and respect your boundaries and opinions, then maybe you're not looking for a gay friend for the right reason.

(9) "Be honest – do you still go through the Chick-Fil-A drivethrough and get that spicy chicken sandwich or those nuggies?" (big, face-scrunching smile.)

This is the one that REALLY got me. This displays just how tone-deaf this person is and how deeply they've objectified the concept of homosexuality for themselves. Chick-Fil-A is a massively homophobic organization from the top down, and they donate millions to organizations that want to bring into question my very right to exist, morally and legally.

As a straight person not affected by these issues, it's easy to say "well, I know I /shouldn't/ go to Chick-Fil-A because of the 'gay stuff', but oh IT'S SOOOOOO GOOOOOOOOD!". It's easy to momentarily forget one's morality because hey, it's not like you're directly hurting anyone, right? But, as a queer person who has to walk by the brand-new Chick-Fil-A at Yonge and Bloor every day on my walk to class, seeing the lines wrapping around the block lets me take direct measure of who, and how many, are willing to forget about me for just long enough to enjoy a fucking chicken sandwich. Go literally anywhere else. Eating at Chick-Fil-A is a choice, and it's a choice that informs me that you care less about my right to live than your own personal enjoyment.

(10) "Do you get upset when they have straight actors portray gay characters?"

This is a whole other debate, so I'm not going to get into the actual subject matter of this question. But hey – maybe, in an industry literally overrun with queer people, maybe we can stop converting a significant and pernicious problem in entertainment into a cutesy debate topic? Something really tells me that this person isn't going to start whipping out the intersectional feminist literature to explain their argument here. In all likelihood, it'll sound more along the lines of "but Eddie Redmayne looked so GOOD in that dress!"

(11) "And what's the GAYEST thing about you?'

Nope. Shut up and choke. I hate you.

Never tell me for a second that homophobia is "over" in Canada/the West/wherever. Never tell me that it's a distant issue, remaining only in far-off religious backwaters. This is what it can look like. Fetishization; dismissal; turning struggles for human dignity into pseudo-intellectual debates.

I'm not here to be your Gay Best Friend.

I'm not here to date your new gay acquaintance.

I'm not here to repeatedly explain to you my need to have rights.

I'm here for the same reasons you are.

I want to live and love, not to be treated like a toy.

Footnotes

[1] Okay, I'm obviously not saying that all straight relationships are built around sexual transactionalism and intimidation, nor am I saying that non-comphet relationships are not. But, in my experience as a reformed Gay Best Friend who has had to provide counsel to cishet friends over some INFURIATINGLY stupid relationship/courting issues, I would argue that a full ninety percent of them could be resolved if the experiencer simply viewed their partner/interlocutor/'tyng' as another human being, rather than being from the mysterious species that is The Opposite Gender.

2 notes · View notes