[HN Gopher] Advent of Code 2021
___________________________________________________________________
Advent of Code 2021
Author : ducharmdev
Score : 512 points
Date : 2021-12-01 13:41 UTC (9 hours ago)
(HTM) web link (adventofcode.com)
(TXT) w3m dump (adventofcode.com)
| surfer7837 wrote:
| Am doing it in Haskell. Every year I do it in Haskell, and then
| promptly forget half the language until I start it in December
| again
| sireat wrote:
| Decided to try Golang this year.
|
| Compared to Python and Scala it is way more verbose for simple
| challenges as this.
|
| I almost feel like I am back in the early 1990s of writing C.
|
| I miss zip, sum, map and list comprehensions...
| zora_goron wrote:
| Related thread from last week:
| https://news.ycombinator.com/item?id=29292818
| Toutouxc wrote:
| I'd like to remind everyone that it's totally okay to do the
| first 10-15 days and leave the really hard stuff to people who
| are smarter or maybe have more free time. The first few days will
| still be fun.
|
| I'm checking out Elixir this year, because I write 95 % Ruby at
| work and I'm getting really intrigued by the functional stuff
| seeping into it.
| SketchySeaBeast wrote:
| Also, you can be strategic, the weekend ones are built to be
| longer than the weekday ones, so there's still some fun to be
| had later on even if you get stuck.
| pablodavila wrote:
| Jose Valim (creator of Elixir) will be streaming his solutions
| on Twitch. Thought that might be interesting for you.
| whalesalad wrote:
| I started doing mine in Elixir last year but it was a very
| steep gradient combined with everything else going on in
| life. So excited to hear this! I will be watching every
| episode for sure.
| Toutouxc wrote:
| Beautiful, thanks!
| qsort wrote:
| It's also okay to just do the problems without the competitive
| aspect. I love competitions and all, but sure as hell I'm not
| waking up at 5AM for an entire month in the pursuit of internet
| points.
| mumblemumble wrote:
| My main use case for AoC is practice with new languages. So I
| tend to prefer to do the same one from several years ago over
| and over, because then I can focus on grokking the language
| and not the problem, and I can compare my solutions across
| languages to get a better feel for how they affect how I
| solve problems.
|
| The leaderboard is occasionally interesting to me for the
| first week of December, but, realistically, I can't see
| getting invested in it without also moving far, far to the
| west of where I live now.
| andreineculau wrote:
| Thought about that last year. You wouldn't have your
| solutions public but any chance?
| TrueDuality wrote:
| I do love using these advents to try out new things. New
| patterns, new languages, new algorithms.
| thanksfortherem wrote:
| Thanks for the reminder, guy who knows Ruby and is learning
| Elixir and makes authoritative comments.
| dimgl wrote:
| I did Elixir one year for advent of code! It was pretty fun and
| helped me learn the language a bit more actually. Hope you
| enjoy.
| regulation_d wrote:
| I really enjoy doing these problems in Elixir, but the fact
| that the default collection type is a linked list makes certain
| problems difficult. However, Erlang does have a fifo queue (a
| doubly linked list), which can be helpful and let's you
| practice some Erlang interop while you're at it.
| https://www.erlang.org/doc/man/queue.html
| [deleted]
| Xavdidtheshadow wrote:
| AoC is one of my favorite events of the year. I find the puzzles
| to be much more approachable than things like Project Euler. I
| regularly credit my yearly participation for making me a better
| programmer.
|
| I also do a daily writeup of my solution, which helps make sure I
| understand the problem and help others who are learning. I found
| it super rewarding last year, so I'm doing it again this year.
| They're in my GH repo. Here's today's:
| https://github.com/xavdid/advent-of-code/tree/main/solutions...
|
| My big tip is that you probably don't need to worry about
| competing for the leaderboard (unless you really want to). Go at
| your own pace, don't stay up weird hours, and take a break.
| Cyphase wrote:
| Anyone who's interested is welcome to join the group in
| #adventofcode on Libera.Chat. We hang out there and in the
| spoilers channel, especially around and for some hours after the
| release time each day. Lots of interesting discussion goes on. A
| lot of people aim for the leaderboard (which is certainly not
| required), then afterwards discuss solutions, optimizations,
| rewrites, edge cases, and more. We also have an IRC leaderboard
| (the AoC site has a private leaderboard feature). It's all good
| fun!
|
| Disclosure, just in case: I'm one of the ops in the channel.
| LandR wrote:
| Like every year, I feel I'm being lured in by an overly easy day
| 1.
|
| Then somewhere between day 10 and 15, there will be a steep
| increase in difficulty and I'll tap out for the year. Then come
| back to the puzzles over the course of the year and maybe knock
| out another one or two.
| time_to_smile wrote:
| And for anyone celebrating the holidays day 10-15 tends to be
| where I find real life holiday planning/activities start to
| rapidly take over my free time. I'm certainly not going to miss
| out on eggnog with friends and family so I can solve a few
| extra AoC problems.
|
| I personally don't mind, if I spend 10 days learning a new
| language and solving some problems I'm satisfied. I'm still
| very excited when AoC comes up every year!
| SketchySeaBeast wrote:
| Yup, the first couple of days are always simple, but then
| you're on Saturday of week 2 and wondering why it's already 4
| AM.
| codingdave wrote:
| Agreed - I did Day One by copy/pasting the input into a
| spreadsheet and calculating the answers in additional columns.
| I suspect I'll need to actually write code soon, though. And
| give up soon after that.
| jaywalk wrote:
| I did the same thing. I was about to start writing some code,
| and then figured it would be much quicker to just drop it in
| Excel and write a couple formulas.
| bhrgunatha wrote:
| There are some plots [1] of the time taken for the first 100
| solutions to part 1 (silver dot) and part 2 (gold dot). They're
| a good visual indication of the relative difficulty of each
| question and how the difficulty of the second part increases.
|
| [1] http://www.maurits.vdschee.nl/scatterplot/
| djaychela wrote:
| Those plots are really comforting for me, as on the days
| where a part was difficult (such as day 20 part 2 last year)
| I didn't find a solution. Thanks, I'll be keeping an eye on
| them this year as things progress (or not!)
| speedgoose wrote:
| And that's for the top 100. I would assume that the
| differences would be even larger for the average developers.
| artursapek wrote:
| ...is the y axis showing DD:HH:MM or HH:MM:SS?
| Jtsummers wrote:
| HH:MM:SS, the first 100 solvers are usually done within
| minutes, hours at most, and never days. None of the
| problems are _that_ hard.
| artursapek wrote:
| wow 0:
| wpietri wrote:
| Ooh, that's really interesting. And given how many folks here
| talk about dropping out as it gets harder, that suggests the
| later problems look easier than they are.
| Jtsummers wrote:
| The weekday problems tend to be easier so you get a ramp
| up, but with drops in difficulty. A lot of people give up
| after one or two of the hard days and don't continue, but
| there's no actual requirement to do them in order. If
| they'd skip the hard ones they'd probably find several more
| solvable (for them) problems remaining in the year.
| pedrosorio wrote:
| These plots only include the first 100 people. Those
| dropping out as it gets harder were unlikely to be be
| represented in the top 100 for later problems either way.
| Strilanc wrote:
| I like that the data clearly shows the server issues on day
| 1.
| Volundr wrote:
| Is this really saying for 2021, the first solution to the
| first problem came in 30 seconds after being posted? That's
| insane!
| notafraudster wrote:
| I'm in a really bad time zone for AoC right now, but here
| was my solution in R for day 1 problem 1.
| library(tidyverse) # pre-typed lines =
| readLines("data/day1.txt") %>% as.numeric() # Read data
| diff(lines) %>% .[. > 0] %>% length() # Part 1
|
| This didn't involve me being a sophisticated or good
| programmer, and if I was in a time zone to be competitive I
| also would have written a function to submit my answer from
| within my IDE (which can also be pre-written). I could
| absolutely buy people wanting to be competitive and being
| able to do this in 30 seconds. I actually could have pre-
| written the second line of three, in point of fact.
| Rietty wrote:
| People are incredibly quick at both skimming/parsing the
| problem, coupled with a language like python where you can
| generally express stuff incredibly concisely and not have
| to worry too much about types, it makes it very quick.
| exdsq wrote:
| Rust this year! We should have a daily HN post to share our
| solutions for open code reviews :)
| Jtsummers wrote:
| They have a daily mega thread for solutions over on Reddit:
|
| https://www.reddit.com/r/adventofcode/
|
| https://www.reddit.com/r/adventofcode/comments/r66vow/2021_d...
|
| It's interesting to see the various solutions, especially when
| you realize, "Oh, duh, I did more work than necessary." and can
| go back and improve your own with the new knowledge.
| patrickdavey wrote:
| I love adventofcode. I have a rule I follow now which makes it a
| lot more enjoyable: if I can't make headway on a problem after
| trying for a day or so, I'll use the subreddit to find a hint,
| and then usually that's enough to help me to the answer. Very
| occasionally I just completely cheat (often the pure math based
| questions).
|
| I don't like missing out on the stars.... I mean it's the only
| way you get to see the awesome ascii art when you collect all 50
| for the year.
|
| Many thanks to Eric and team for what must be a huge effort to
| run such a fun programme.
|
| Oh, the other thing I do: I don't even start until sometime in
| January :) far less stress and keeps the whole family much
| happier ;)
| floitsch wrote:
| Perfect time to explore Toit (http://github.com/toitlang/toit) :)
| WesleyJohnson wrote:
| This is the first year I'm going to participate. Not really
| interested in competing with anyone else, just against my own
| imposter syndrome. Based on the responses regarding the obscure
| algorithms you may need, I'm no longer confident I'll win against
| him either.
| Toutouxc wrote:
| Look at this this way: other solid, good, honest programmers
| (just like you) on HN and reddit agree that some AoC puzzles
| require obscure algorithms, and they also get stuck on those.
| sdevonoes wrote:
| Only reason I don't do Advent of Code is because you have to wake
| up at 5-6am in Europe. I barely can make me a coffee at that
| time.
| jstx1 wrote:
| The global leaderboard really isn't the point for most of the
| people who do AoC. You can always do the puzzles later in the
| day.
| Jtsummers wrote:
| You don't _have_ to wake up early, only if you want to be part
| of the 100 first solvers. I gave up on that after my first
| year, if I can 't solve it at night (10pm my time now, used to
| be midnight) in less than an hour, I punt to the next
| afternoon.
| w-m wrote:
| Anybody interested in getting a just-for-fun HN user leaderboard
| going? Here's my code: 194284-90c48b41
|
| In the last couple years I usually stopped up after a few days
| when I didn't find the time to do one of the puzzles or got stuck
| with the Rust borow checker. Maybe having a leaderboard helps
| with the motivation to keep on going! :)
| Cyphase wrote:
| Having a fun group to do it with does. Come join us in
| #adventofcode on Libera.Chat! We also have an IRC leaderboard.
| [deleted]
| MYEUHD wrote:
| Is it considered cheating if I use another program (such as wc)
| to know the number of lines in the input file?
| Mountain_Skies wrote:
| That's for you to decide but the point of the exercise, besides
| having fun, is finding a solution. If wc is something you'd use
| to solve a similar problem, seems reasonable to use it here too
| and within the spirit of the challenge.
| Cyphase wrote:
| People have solved puzzles by hand in the past. No tool is off
| limit, including your brain, pen, and paper.
|
| I would say the only thing that's "cheating" would be looking
| up solutions to "solve" the problem faster than other people,
| whether they be the rest of the world on the global leaderboard
| (which is unlikely since the people who make the leaderboard
| are good about not posting solutions until it's full) or some
| friends you're competing with on a private leaderboard.
|
| Otherwise, let your conscience be your guide. As the saying
| goes, when you cheat, you're only cheating yourself.
| ninju wrote:
| Any software tools are acceptable. I used Excel to solve 2021
| day 1
| throwawaygal7 wrote:
| I really like this event but wish the name would be changed to
| something more sensitive.
|
| Would this have been named 'Kwanzaa of code' or 'Diwali of code'
| or 'lesser eid of code'? Of course not
| matsemann wrote:
| How is it insensitive? In my country (Norway) there's advent
| calendars for everything and has been since I was a child. Home
| made advent calendars with a small gift each day, or store
| bought with a chocolate, beer, liquorice, or similar per day.
| There are special advent calendar TV shows, where an episode is
| released each day in December.
| throwawaygal7 wrote:
| Here you go:
|
| Advent is a season of the liturgical year observed in most
| Christian denominations as a time of expectant waiting and
| preparation for both the celebration of the Nativity of
| Christ at Christmas and the return of Christ at the Second
| Coming. Advent is the beginning of the liturgical year in
| Western Christianity, and is part of the wider Christmas and
| holiday season.
| matsemann wrote:
| I know what advent is, as I said I and my fellow countrymen
| do loads of advent stuff.
|
| Why does that make this offensive?
| silicon2401 wrote:
| There's nothing insensitive about the word 'advent'.
| Additionally, you are free to start a Kwanzaa of Code or Diwali
| of Code or both and people are free to join.
| petercooper wrote:
| I had to look up the etymology and it basically comes from
| Latin ad-venire or "to come".. so symbolizes merely the
| eventual arrival of something or prelude to something.
| silicon2401 wrote:
| Exactly. That comment was a great example of outrage
| culture. Instead of stopping to think of what advent means
| or put in the effort to start a Kwanzaa of code, the other
| commenter instead chose to just complain and get upset over
| nothing
| throwawaygal7 wrote:
| You're the one that has no idea what Advent means in
| western European culture
| throwawaygal7 wrote:
| Advent is a season of the liturgical year observed in most
| Christian denominations as a time of expectant waiting and
| preparation for both the celebration of the Nativity of
| Christ at Christmas and the return of Christ at the Second
| Coming. Advent is the beginning of the liturgical year in
| Western Christianity, and is part of the wider Christmas and
| holiday season.
| the-smug-one wrote:
| And that is bad?
| Mountain_Skies wrote:
| Unfortunately to some their idea of being inclusive means
| hating anything and everything about whatever culture is
| dominate. The destruction and elimination of that culture
| is their only acceptable path to diversity and inclusion.
| shever73 wrote:
| It's great to have AoC back again. Last year was my best yet,
| where I managed to get up to day 23. This year, I'm focusing on
| keeping the solution to as few lines of code as possible.
| Mountain_Skies wrote:
| If you enjoy Advent of Code, be sure to check out their sponsors.
| Not only because their support helps make AoC possible but also
| because they often have their own coding challenges that can be a
| fun compliment to AoC itself.
| Barrin92 wrote:
| Eric Wastl who makes Advent of Code also made the Synacor
| Challenge (https://challenge.synacor.com/) a bunch of years ago
| which is similar to the Intcode AOC problems and a lot of fun.
| Mountain_Skies wrote:
| Nice, now I'll have something to do in January while going
| through AoC withdraw.
| paxys wrote:
| Advent of Code has become an annual tradition for me. I do wish
| that they would update their scoring in some way to prioritize
| something other than how quickly you can write up the solution
| every day at midnight when the question is released.
| volfied wrote:
| I wish private leaderboards allowed for people to "start"
| solving when they send the first request to the problem page. I
| know it can be abused, but if it's just for private
| leaderboards, it will level the time zone problems.
| jugg1es wrote:
| This is a great idea. Maybe submit it as a suggestion.
| Jtsummers wrote:
| It's been brought up in the subreddit over the past few
| years and always rejected.
| makapuf wrote:
| Problem is, you can have two accounts, get you algorithm on
| the first and flash through the second.
| estomagordo wrote:
| Any ideas? The only thing I can think of is time after you saw
| the problem, which would work with an honor system on a
| social/friendly leaderboard.
| OwlsParlay wrote:
| The only thing I can think of is if they teamed up with
| LeetCode to allow people to use the built-in compiler to
| solve the problems.
|
| Obviously for the folks who use <ObscureLanguageX> this
| wouldn't work but it would be a nice collaboration otherwise.
| paxys wrote:
| I don't know the technical solution for this, but there can
| be some judgement on the quality of the solution (like how
| efficient it is in terms of time and space).
|
| Here's an example - in part 2 of day 1 of this year (2021),
| there's no need to actually add up the 3 measurement range,
| since the middle 2 values will always cancel out. You simply
| need to loop through the array compare index i with i+3.
| Maybe there should be an extra point for people who figured
| this out?
|
| Another problem is that the input set is always small enough
| to make a brute force solution the most favorable one. So
| what they are really judging is the speed at which someone
| can read/parse the input file and write some loops.
| matsemann wrote:
| Sounds like https://open.kattis.com/ would be right up your
| alley.
| the-smug-one wrote:
| Fun fact: Kattis is how a lot of homework is distributed
| at KTH, seeing it being mentioned always brings up some
| nice memories :).
| Jtsummers wrote:
| > Another problem is that the input set is always small
| enough to make a brute force solution the most favorable
| one. So what they are really judging is the speed at which
| someone can read/parse the input file and write some loops.
|
| That's only true for, well, ok maybe 1/2-2/3rds of the
| days. The rest require something more complicated, either
| with more complicated algorithms or more clever algorithms
| to get performance to a reasonable level. See the other
| discussion here about 2020 Day 13. The naive solution
| worked on the samples, but would not have worked on the
| actual input.
| Strilanc wrote:
| One of the genius things about advent of code is that the
| server never needs to touch unknown, potentially malicious,
| code. The server just compares the claimed answer to the
| stored answer.
|
| Maybe one way it could do the performance testing is: 24
| hours after the puzzle is announced, a "speed test input"
| becomes available. The speed test input would be
| substantially larger than normal inputs. Because people
| have had time to write the code, all they have to do is
| dump the input into the code and put the output into the
| box the fastest. A notable bottleneck is that every problem
| does have to be solved by the server ahead of time, and if
| it starts taking ten minutes to solve each instance then
| that's expensive unless you use very small pools of inputs.
| boutell wrote:
| Tackling it in TypeScript this year, which is interesting because
| I haven't used TypeScript before (I'm experienced with
| JavaScript). This is a good way to really drill it into my
| fingertips.
|
| If you care to follow along:
|
| https://github.com/boutell/advent-of-code-2021
| kryptiskt wrote:
| I'm also doing it in Typescript this year, but I'm doing it in
| the browser to get a little modern web experience (I'm a C++
| developer by day). I have a pretty nifty setup with Snowpack
| that will rebuild it and refresh the browser automatically when
| I save, and a little scaffolding for making a widget for a
| problem, I don't use a framework:
| https://github.com/melted/aoc2021.
| volfied wrote:
| I recommend using a runner like
| https://github.com/caderek/aocrunner, so you can focus on
| coding, rather than project set up.
| penjelly wrote:
| tsc file.ts && node file.js
|
| is pretty simple but yeah.. i guess as the scope increases it
| may require a dist folder or scripts
|
| edit: wow nevermind im seeing a sibling comment here is using
| the browser and it looks like a major headache..
| orange_puff wrote:
| This is my first year participating. I've solved about 20-30
| questions from previous years and really loved them. I tried to
| compete last night for top 100 and was 7 seconds off (rank 123).
| I shouldn't have tested my code for the first problem because it
| was too trivial!!
|
| But, that gets the competitive aspect of this challenge out of
| the way immediately so I can simply have fun with these problems
| :)
|
| I am excited for them to become a bit more challenging because my
| friend and I are going to work on them together.
| uyt wrote:
| If you're doing AoC you should join the subreddit
| /r/AdventOfCode: https://www.reddit.com/r/adventofcode
|
| There's usually a lot of different solutions (including many in
| esoteric languages or code golfed) along with screencasts and
| visualizations to explain how they got there. I find that even
| when the puzzles are easy I still learn a lot from the community
| by seeing all the different ways to skin a cat!
| vidro3 wrote:
| this always sounds appealing but i really don't find these types
| of problems fun to do, mostly frustrating.
| penjelly wrote:
| dont those statements contradict eachother? it sounds appealing
| how? cause its a challenge exercise? But challenges are
| frustrating?
| anandoza wrote:
| You don't understand how something can sound appealing at
| first, but then in practice isn't enjoyable?
| penjelly wrote:
| "always sounds appealing" implies the same thing happens
| every year to parent comment. either you dont enjoy it or
| you do? its not like the type of exercises change year to
| year. theyre coding challenges everytime.
| vidro3 wrote:
| yes, i get tricked every year. at first it's 'ooh some
| neat challenges to help me improve or learn new skills'
| then it's like, 'ugh this is annoying and i don't like
| it.'
| whalesalad wrote:
| I wish I could take a month off from my client obligations to jam
| on stuff like this. I always get started - make it a few rounds -
| and then get crushed by the pressure of everything else. These
| sorts of games are so fun with TDD. Red. Red. Red. Red. ....
| Green!
|
| Anyone here currently on any kind of sabbatical to just
| decompress and learn new stuff?
| joshgrib wrote:
| Seconding this as a great time to use/try TDD! Every problem
| comes with a small sample input and output, so you get a test
| case for free
| reikonomusha wrote:
| AoC is often used to learn a new programming language, but it can
| also be used to improve them--especially less established ones.
|
| Theres a small community [0] of people who decided to try out
| Coalton [1], which is a Common Lisp DSL that has a strict,
| Haskell-like type system, and has strict evaluation (not lazy)
| semantics. Pattern matching, algebraic data types, all that jazz
| are supported directly in a Common Lisp environment.
|
| For example, here is a function to read in the first problem's
| data, which makes use of the usual high order functions (map and
| filter), as well as currying (only one argument provided to /=,
| making it curried): (declare read-aoc-data
| (Unit -> (List Integer))) (define (read-aoc-data _)
| "Read the data for problem 1." (let ((data (fromSome
| "Couldn't read AOC1 data." (read-
| file-into-string aoc1-input-file)))) (map parse-int-
| or-fail (filter (/= "") (split-string #\Newline
| data)))))
|
| Type annotations, as in any good ML, are optional (except when
| there are polymorphism bugs, like one found during AoC!). Unlike
| Haskell, purity isn't demanded.
|
| There's a small contest [2] with all sorts of prizes for doing
| AoC in Coalton and contributing back to the project through
| tutorials, PRs, and bug reports.
|
| [0] They hang out on Discord https://discord.gg/cPb6Bc4xAH
|
| [1] https://github.com/coalton-lang/coalton
|
| [2] https://coalton-lang.github.io/20211129-aoc-contest/
| dunefox wrote:
| Oh man, I'm using CL for aoc this year and just figured out how
| to install Coalton. Maybe I'll do couple of days in it as well!
| kemiller wrote:
| I love these puzzles, and I'm grateful they only let you do two
| per day or I'd never get any work done.
| jstx1 wrote:
| One of the fascinating things is reading other people's
| solutions. You get wild extremes - from easy clean solutions that
| I would never think of to some very weird choices. Especially in
| the first few days when the puzzles are easier it's more of the
| latter - there are some extreme abuses of Python in today's
| solutions thread on reddit. I get that it works but I also hope
| that nobody I work with ever writes code that way. I assume it
| happens more with Python because beginners are more likely to use
| it and because it gives you so much flexibility.
|
| On the flip side, it's a bit humbling to see people solving the
| difficult days extremely quickly or having very concise and
| elegant solutions.
| timvisee wrote:
| Last year I solved all puzzles in less than 1 second. This year,
| for lack of a better goal, I'll be trying to do the same:
| https://github.com/timvisee/advent-of-code-2021
| ta988 wrote:
| Try 500ms and divide by two every year
| taftster wrote:
| Moore's law and all that.
| Toutouxc wrote:
| I thought you were trolling at first. :)
| gray_-_wolf wrote:
| To be honest I'm amazed by the times. Mine (reasonably written
| C) is 4ms, so 0.025ms is quite amazing. Any idea what magic
| does rust do inside to achieve this speed?
| estomagordo wrote:
| Man, it takes me longer to even read a problem statement!
| auxym wrote:
| I think they mean 1 second of program execution time :)
| YoungWeb wrote:
| This is my first time encountering this and I like it. I am
| looking forward to completing these this month.
| nineplay wrote:
| I love Advent of Code. As I sit here trying to prepare for my
| next set of 'leet' interviews, I wish employers could switch over
| to this style of tech questions. Advent of Code requires good
| coding and problem solving skills. Leet coding requires you to
| memorize every operation for dozens of data structures like how
| to insert elements in a min heap.
|
| ( Insert elements at the end and swap with the parent until the
| tree is correctly ordered again. Good luck figuring this out in
| 20 minutes if you don't know it ahead of time. )
|
| ( Now prepare yourself to remember how to insert/delete/search
| for elements in every other data structure with any number of
| different qualifiers when it's not going to be obvious at the
| outset of the question what kind of data structure to use )
|
| ( Oh and make sure you've memorized the time and space complexity
| )
|
| ( Not that I'm bitter or anything )
| jhenkens wrote:
| I'm there with you 100%. I just took a break after 6 years of
| consecutive employment. Apparently I did well at my job -
| remained an IC, but was given more recognition via titles and
| more and more cross-org design meetings. But now after 6 years
| of solving hard big scale problems, I've got to come back to
| how to interview for companies again. Incredible waste of time
| spending days studying leetcode, interviewing for companies I'd
| likely not work for just to practice skills I haven't needed in
| 6 years.
| pedrosorio wrote:
| > Leet coding requires you to memorize every operation for
| dozens of data structures like how to insert elements in a min
| heap.
|
| I've done dozens of leetcode contests (4 problems every
| Saturday) and never had to use knowledge of the implementation
| of a min-heap (though I did "import heapq" a few times) to
| solve any of the problems.
|
| Are you using "leet coding" to refer to technical interviews
| that simply ask you to implement textbook data structures
| (somewhat boring imo), as opposed to solving leetcode problems?
| kristaps wrote:
| My current company actually did just that - I got to solve two
| AoC2020 puzzles for my code sample.
| nouveaux wrote:
| Do you mind sharing what company did this? Seems like a great
| place to work?
| flaie wrote:
| I have been solving these since years, I find it a nice way of
| assessing a language and deep dive since it will cover lot of
| parts of what makes a language.
|
| I have been porting my old solutions in other languages into
| Kotlin over the time, and will be again doing them in Kotlin. I
| find it a nice language for AOC since custom extensions and DSL
| possibilities, it has a good builtin libraries and you can always
| fallback on Java, even if it has some shortcomings.
|
| Regarding the AOC per se, I take it as a fun daily challenge, I
| know I won't be able to be part of the top 100, at least I would
| with some luck during the first 3 days, and then.. nope, that's
| life, try not to be too competitive. Last year it took me 8 hours
| to solve day 20, but it's a game, you should have fun doing it (I
| had), if not people should stop.
|
| However, I strive in trying to write pretty, compact, idiomatic
| and as functional as possible code, which means that sometimes I
| will write an ugly solution in 5 minutes, and will take an hour
| to make it beautiful.
|
| Besides I like to read the story, I know plenty of friends who
| don't even read the adventures of Santa, they just solve the
| puzzle and that's it, they don't even know they saved Christmas
| :-D !
| matsemann wrote:
| Yeah, kotlins stdlib for collections is great. Has all kinds of
| variants of reducing, grouping, filtering, mapping, taking,
| dropping etc one can think of. Today's solution was to just
| call the window function.
| 101011 wrote:
| Spoilers dude! I haven't started yet.
| Jtsummers wrote:
| > which means that sometimes I will write an ugly solution in 5
| minutes, and will take an hour to make it beautiful.
|
| I think I spent 2 hours last night just playing around with
| different methods of solving it after my initial version. Other
| libraries, slightly altered algorithms. I think that's one of
| the parts I enjoy the most, solving the puzzles is fun. Trying
| a dozen different variations is, for me, more fun (and more
| edifying).
| ducharmdev wrote:
| Haha, your last line really made me smile.
| raldenx wrote:
| I can vouch for wasting hours of coding due to not reading the
| problem thoroughly.
| patrickdavey wrote:
| Or not trimming your input. I worked and reworked and
| reworked a problem once, the answer was some number in the
| billions. Eventually I gave up because I just couldn't work
| out where I went wrong. I then took someone's working
| solution and plugged my input in, and I was out by one,
| because it counted chars and I had a stray newline.
|
| I'd like to say it only happened once, but, it happened again
| later that year... And then never again (because I pulled out
| code to always strip newlines after reading it in ;)
| Waterluvian wrote:
| I respect that AoC gets very difficult and is for an audience
| that isn't me.
|
| But I love the format and what I'd enjoy is a similar project
| where the difficulty doesn't really increase, but each day is a
| different problem domain. Breadth not depth.
|
| For example, perhaps we start with some data processing from a
| file. Then answer some basic statistics question about the data.
| Then maybe some basic signal processing. We form an image. We
| transform the image. We play the image as audio. We break it into
| packets of some sort then share it on a "network." We reassemble
| it. We build a state machine and pass it the reassembled data in
| some way. We discover some new output.
|
| Etc. etc. culminating with some fun discovery that inside that
| original data was a secret code or whatever.
|
| And instead of an intense challenge, we've just had a fun walk
| through an intro to two dozen subdomains of CS/sweng. You may not
| have immediately known the answer to each puzzle but you never
| felt lost.
| djhworld wrote:
| Enjoy doing these when I can, although probably takes me 6 months
| to complete the puzzles, doing them here and there.
|
| Not really into the competitive aspect, although I guess it
| doesn't matter that much anyway.
|
| There was on AoC a few years ago that got you to build a toy
| computer, to the point where you were running simple games on it.
| That was mind blowingly fun!
| clircle wrote:
| I'm using Advent of Code this year to learn Common Lisp. I
| started doing the 2015 exercises a few days ago, and I'm having
| the _most_ fun you can have with a computer.
| tester34 wrote:
| I wonder how popularity of "exotic" languages increases when
| AoC's around
|
| F#, Lisp and so on
| mikewarot wrote:
| I'll balance that out for you, I do my programming in Pascal.
| I'm going through the old ones as well, hoping to back-fill in
| answers to all of them.
|
| https://github.com/mikewarot/Advent_of_Code_in_Pascal
| mcjiggerlog wrote:
| It seems like 80% of people I've heard talking about AoC are
| planning on doing it in Rust (including me!). It's definitely a
| great way to get up to speed with a language you're interested
| in learning.
| jstx1 wrote:
| In last year's survey Rust was around 10%. It's definitely
| overrepresented but not quite that much.
| aunderscored wrote:
| I definitely enjoyed doing rust. I'm planning on doing go,
| rust, and python. We'll see how well that holds up
| ducharmdev wrote:
| Yup, I'm doing Rust this year as well. I've worked through
| rustlings a couple times in the past, but haven't had many
| excuses to use Rust.
|
| I was proud last year when I got to day 18 with Python, but
| I'm setting the bar much lower this year. I don't have any
| experience with C/C++ (just C# and a bit of Go), so thinking
| more carefully about memory mgmt is new to me. But the
| functional aspects of Rust are pretty exciting.
| asicsp wrote:
| Some create a language just for AoC, for example:
| https://github.com/healeycodes/adventlang
| mnw21cam wrote:
| That'd be interesting given that 2019 was already _about_ a
| created language.
| riffraff wrote:
| One of the solutions I saw today was in Intcode (the
| language from 2019), it was pretty incredible.
| jstx1 wrote:
| There's definitely a selection effect - the type of person that
| will spend time on Advent of Code is also likely to be the type
| of person that learns and uses more exotic languages, or at
| least languages that aren't used that much commercially.
|
| Some stats to confirm -
| https://preview.redd.it/jrhlcxrzy0761.png?width=2275&format=...
| - taken from from last years' unofficial survey -
| https://www.reddit.com/r/adventofcode/comments/kj53l1/unoffi...
| jarpschop wrote:
| Why would Alexandria Ocasio-Cortez' presence increase the
| popularity of some programming language?
| speg wrote:
| Advent of Code.
| BiteCode_dev wrote:
| That sounded like a joke :)
| Toutouxc wrote:
| It's important to understand that for every person
| familiar with the name and the abbreviation there are
| roughly 22 people who have no idea who she is.
| gerikson wrote:
| The price of humor on HN is eternal downvotes.
| Nicksil wrote:
| >The price of humor on HN is eternal downvotes.
|
| Not if its funny.
| petercooper wrote:
| APL is the language I only _ever_ see around AoC. But it 's so
| impressive too. Like the first part of today's solution is
| "+/-1|x<1[?]x" (stolen from someone on Reddit) and I'm like..
| ok, I need to learn this language one day.
|
| (Since their solution is now being discussed, it's from here: h
| ttps://www.reddit.com/r/adventofcode/comments/r66vow/2021_d...)
| ollran wrote:
| APL is quite common in the code golf scene.
| Jtsummers wrote:
| Interesting solution. 1[?]x
|
| Rotates the sequence so the first becomes the last.
| x < 1[?]x
|
| Element-wise compare each, resulting in a list of 1s and 0s
| -1 | x<1[?]x
|
| Drop the last element because it's actually not part of the
| solution (thanks to the earlier rotation). +/
| -1|x<1[?]x
|
| Sum all of them, since it's just 1s and 0s this gives a
| correct count. Part 2 is solvable (unless I missed something,
| works on the sample data) by just changing two characters
| from that solution. Neat.
| petercooper wrote:
| Thanks for the explanation! I just found someone with a
| different approach who has similarly broken it down on
| Twitter:
| https://twitter.com/janiczek/status/1465969017089363969
| Jtsummers wrote:
| https://tryapl.org
|
| That's an online APL REPL with all the symbols listed at
| the top, hover to get a tooltip that tells you both how
| to type it into the REPL and what its name is. I'd
| forgotten what rotate was because my APL deep-dive was 2
| or 3 years ago now. It's handy for discovering the
| symbols and breaking down the harder-to-understand one-
| liners (for novices or those unfamiliar with it).
| overkalix wrote:
| Not particularly exotic, but the last two years I pushed myself
| to do them in elixir (although my solutions become
| progressively shoddy until I quit, usually around day 10-12).
| Then I promptly forget everything I've learnt because I can't
| introduce the language in my work.
| phillipcarter wrote:
| I'm using it as an opportunity to try out Crystal. I have zero
| Ruby experience, so it's a fun experience coming in from a "no,
| actually, none of this is familiar to me" perspective. Nice
| language.
| riffraff wrote:
| There's always some cool stuff done with Raku, I'm giving it a
| chance this year as my "second language", we'll see how it
| goes.
| runevault wrote:
| I've been getting back into f# lately and going to use it for
| AoC to give me real challenges to work on instead of arbitrary
| ideas, so it is certainly helping one of the mentioned for me.
| Jenz wrote:
| Lisp is exotic?
| Scarbutt wrote:
| Esoteric is the word I would use.
| carnitine wrote:
| Seriously? Lisp of all languages? Also esoteric is already
| applied to languages like Brainfuck which are designed to
| be as abstruse as possible.
| Scarbutt wrote:
| Yes, Lisp and F# are esoteric programming languages in
| the industry.
| mrtranscendence wrote:
| I've only seen "esoteric" refer to programming languages
| that are deliberately constructed to be obscure or
| unusual, usually in ways that make them unusable in some
| practical sense. Your Brainfucks or Malbolges, say. I've
| never heard of anyone applying that term to Lisp or
| especially F#. They might be unpopular, but they're
| usable, practical languages with good implementations.
| aarchi wrote:
| I'm solving Advent of Code in Whitespace, a
| quintessential esolang.
|
| https://github.com/andrewarchi/ws-challenges
| ByteJockey wrote:
| A lot of people consider anything not in the tiobe top 10
| to be esoteric (especially for the purposes of enterprise
| work).
|
| Maybe obscure is a better word here?
| mrtranscendence wrote:
| Obscure is a good choice. I'd probably use niche.
| Honestly, esoteric _could_ be a good word to describe
| lisp, except for the fact that it seems to already exist
| as a term for a category that wouldn't include lisp.
| ByteJockey wrote:
| Niche is fair. Basically, I'm trying to describe "not
| mainstream".
| bcrosby95 wrote:
| By this metric, Ruby, Swift, Go, Rust, Kotlin, and
| Typescript are all obscure. Some of these are even more
| obscure than Lisp.
| [deleted]
| the_only_law wrote:
| I was going to do something fun, but gimmicky and try to
| implement them all in like SPL/2100 on an emulator running RTE,
| but quickly found I'd end up spending the month learning the
| latter. I've been trying to think I've something, else fun to do
| or maybe use a language I've been itching to try, like Ada, but
| I'm not sure any of the questions will be of a nature to let me
| utilize the strengths of that language and I fear it will all end
| up being really boring procedural algorithms. I can think of a
| ton of other gimmicky solutions, but none that are very fun.
| briffle wrote:
| Looks like the Sysadvent has started again today, after taking
| last year off.
|
| Its great for those of us on the more OPS side of DEVOPS:
|
| https://sysadvent.blogspot.com/
| bussierem wrote:
| I really enjoyed the early part of this last year, but I got to
| Day 19 and suddenly it became
|
| "if you memorized some mathematical concepts and an obscure
| algorithm and also recognize that this exact algorithm is the
| only efficient solution to the problem then you can solve this in
| 5 seconds, otherwise it will never finish running with any other
| algorithm".
|
| I immediately quit. I'm not doing these to prove I'm smarter than
| other people or memorized random math concepts, I'm doing this to
| practice writing code or to learn a new language.
|
| Not sure if this is indicative of other years (This is the
| farthest I've persisted in the 3 I've tried) but it was EXTREMELY
| demotivating, and killed every desire to continue or to even try
| it again next year.
|
| *EDIT*: Apologies, I was incorrect on the Day where this
| happened. It was actually Day 13, with the Chinese Remainder
| Theorem being the solution. I must have copy/pasted a solution in
| frustration and continued past that point. My mistake.
| petercooper wrote:
| At the time, I had the same thought process as you. I did
| eventually come back and do the rest of the days though which
| were surprisingly trivial in comparison! I seem to recall some
| people _did_ manage to solve that day using brute force with a
| non modular approach though.
| bussierem wrote:
| I'm quite surprised, I spent hours on multiple different
| solution and every single one was brutally slow.
| petercooper wrote:
| My memory is hazy, but I seem to recall it involved a lot
| of parallelization and running it for a couple of days on
| high end gear along with luck. So definitely not the
| intended approach! :)
| smcl wrote:
| I was the same as you for a few minutes - I was demotivated and
| when I found out what was behind it I thought "huh I never
| learned this and I'm not sure how I _would have_ ever learned
| this " and felt a little bit defeated. But then I read a little
| bit on the subreddit, read the wiki on CRT, put together a
| solution and moved on. It's meant to be a bit of fun, if you
| have to skip one challenge (or cut a couple corners) it's no
| big deal - you can always come back to it later :)
|
| It can be demotivating if you check the number of people who
| solved it quicker you, but just pretend they all cheated off
| one really really smart person and you'll feel much better :D
| lostdog wrote:
| Last year I figured it out from first principles, like some of
| the other commenters, but that problem was one of the hardest
| for me (like the tile rotating problem, which was excellent).
|
| This year, my rule is that if it looks like the Chinese
| remainder theorem, then I can just look it up. There's no need
| to stay stuck on something that's supposed to be fun.
| Strilanc wrote:
| It actually was on day 19, it's just that puzzle #13 was the
| 19th puzzle given out [1]. I'm not sure why the numbers didn't
| come in order last year.
|
| [1]: https://adventofcode.com/2020 shows the number order
| mercurywells wrote:
| If you look at the 'map' on the left side and also follow the
| plot in the puzzle descriptions, you can see that you were
| island hopping, so top to bottom is not the order the puzzles
| came out in.
| Strilanc wrote:
| Oh yeah, that's right.
| jstx1 wrote:
| I see it as on opportunity to expose yourself to a bunch of
| things in mathematics and computer science. Also, I'm pretty
| sure that you could get to the solution you're referring to
| without knowing any number theory at all.
| tyingq wrote:
| Link to last year's Day 19:
| https://adventofcode.com/2020/day/19
|
| I didn't read it in depth, but it feels like you could build
| regexes on the fly to solve it. Perhaps I missed something
| crucial.
|
| Edit: Ahh, day 13: https://adventofcode.com/2020/day/13
| Jtsummers wrote:
| Part 2 complicated it, but yes. I just built regexes on the
| fly for Part 1. I wonder if they mean Day 13. The underlying
| math is based on the Chinese Remainder Theorem, but it is
| solvable without knowing it (or, in my case, "knowing" it,
| once I saw others mention it it came back but my math degree
| was a long time ago). A solution could be discovered
| incrementally without knowing the math by trying to optimize
| the naive version.
| bussierem wrote:
| I did mean Day 13, thank you -- I updated my post
| accordingly. Sorry about the confusion!
| bussierem wrote:
| Apologies, I updated my post. It was Day 13 where this
| happened. Not sure why I stopped at Day 19, tbh.
| ZiiS wrote:
| Day 13 you really needed to know of Chinese remainder
| theorem; I would say this was probably the only day in the
| last couple of years so dependent on non-trivial maths. I
| would still recommend AoC though.
| justinsaccount wrote:
| yep, that's what I did. simply converted the input into a
| regex and matched it. part 2 had to add a little special
| casing but ultimately not that difficult.
| CastFX wrote:
| I loved day 19 because I managed to use some Automata theory
| I studied at uni. Something like, I cannot simply use a regex
| because it's a context-free grammar. Then I learned about
| recursive regexes and how they could be used to parse a cfg.
| Aaah fascinating, really.
| TYMorningCoffee wrote:
| For Day 13, I played around with the numbers and eventually
| noticed that you could increment by the product of the numbers
| you consumed so far.
| karmanyaahm wrote:
| fwiw the Chinese Remainder Theorem is taught in basic
| cryptography courses. ig it could be obscure for someone
| outside the field though
| justinsaccount wrote:
| > if you memorized some mathematical concepts and an obscure
| algorithm and also recognize that this exact algorithm is the
| only efficient solution to the problem then you can solve this
| in 5 seconds, otherwise it will never finish running with any
| other algorithm
|
| well that's just not true at all.
|
| I had no idea WTF the Chinese Remainder Theorem was and just
| worked out the issue iteratively. All you had to know was that
| if you are trying to find some large number that is divisible
| by other prime numbers, the deltas between the candidates will
| be the product of the numbers.
|
| as in, if you are trying to find a number that is divisible by
| both 37 and 41, you really just need to find numbers divisible
| by 1517.
|
| I forget what the name for this mathematical concept is, but
| it's far less obscure than the CRT.
| boutell wrote:
| Yes, I worked it out similarly and I saw comments on the
| twitters recently from others who did. Also usually the tough
| stuff is in the second part of each day, which I feel is
| pretty fair and provides a way to feel reasonably good about
| your result if you're not completely successful.
| justinsaccount wrote:
| Yeah, I always liked how I could generally solve something
| a "dumb" way for part 1, but would likely need to refactor
| it to be a bit smarter to solve part 2.
| gknoy wrote:
| > All you had to know was that if you are trying to find some
| large number that is divisible by other prime numbers, the
| deltas between the candidates will be the product of the
| numbers.
|
| "All you have to know is .. {this magic}" -- that really
| reminds me of my freshman year math classes where the TAs
| would just say, "well if you do it THIS WAY..." (when my main
| question was how the heck you stumble upon looking at the
| problem that way, vs all the failed ways)
| justinsaccount wrote:
| It's not really magic though. Here's a simpler variation of
| the problem:
|
| Two buses make different circular routes from the same
| depot. One bus takes 3 hours to do a loop, the other takes
| 5. At what times from the start of the day will both buses
| be at the depot at the same time?
|
| you could write a loop like this: for t
| in range(0, 10000): if t % 3 == 0 and t % 5 ==
| 0: print("same at", t)
|
| which if you run, you'd see: same at 0
| same at 15 same at 30 same at 45
| same at 60 same at 75 same at 90
|
| and even if you knew nothing about math, you could see that
| and think, oh, so they just meet every 15, which happens to
| be 3 times 5... You don't need to count up one at a time
| and check remainders, you can just increment by 15 and get
| the exact same result.. for t in range(0,
| 10000, 15): print("same at", t)
|
| That's more or less what I did when I solved it.. saw how
| the problem simplified to finding the common multiples of
| numbers, which when they are prime is just the product.
| apply this process iteratively and you have the solution.
| solveit wrote:
| > when my main question was how the heck you stumble upon
| looking at the problem that way, vs all the failed ways
|
| Well you stumble through half a dozen failed ways first, is
| the usual method. Eventually you gain "intuition" that lets
| you jump straight to the way that works and you can't
| explain exactly how you thought up the correct method, but
| it just feels so natural and anyway, you can explain in
| great detail why nothing else would work.
|
| I'm teaching calculus this year so I sympathise with both
| sides. The problem is that the answer to "how did you know
| to do it that way?" is experience, as in all fields. But
| students rarely have the time to accumulate experience and
| intuition before finals, so there's frustration all around.
|
| What I'm saying is I'm not looking forward to grading six
| hundred finals where many students will inevitably spend
| too much time on approaches that were obviously (to me)
| doomed from the start because they haven't stumbled enough
| to know it yet.
| shever73 wrote:
| Yep, that's pretty much how I solved it too. I had (and still
| have) no idea how to apply the Chinese Remainder Theorem.
| Looking back at my solution, I just iterated through the
| input, which I'd mapped to a Python list.
| Someone wrote:
| Nitpick: there's no way to _apply_ the Chinese Remainder
| Theorem. It merely states that _"if one knows the
| remainders of the Euclidean division of an integer n by
| several integers, then_ one can* determine uniquely the
| remainder of the division of n by the product of these
| integers, under the condition that the divisors are
| pairwise coprime."*
| (https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
| It doesn't say _how_ to determine that number.
|
| https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Com
| p... describes a few algorithms for doing that.
| anandoza wrote:
| Well, you can apply the theorem to the problem. Or apply
| its principles to the problem.
| dunham wrote:
| least common multiple. It's also what popped into my head
| when I first saw the fizzbuzz problem.
|
| I've only done 2019 and 2020, but found 2020 to be a lot
| easier. I got stuck for a day or two on one of the 2019 ones.
| The one point I was briefly stuck in 2020 was when I was
| using the wrong data structure. (I don't want to spoil
| anything.)
| smcl wrote:
| Yeah 2019 had a couple of mind-benders involving mazes -
| there are two Part 2s that I need to motivate myself to
| come back to because my fumbling that got me the respective
| Part 1 solution was useless for Part 2 (Day 18 and Day 20).
| Looking back at them they shouldn't be _too_ hard, I just
| think that at that moment I didn 't have the time to spare
| and never felt like coming back to them. Maybe if I'm bored
| between Xmas and New Year :)
| matsemann wrote:
| I often find that part1 can be solved by most, but part2
| sometimes needs a clever trick, experience or some knowledge.
| Doing only part1 or skipping some day is perfectly fine,
| though. So I don't really get your anger.
|
| I actually like when it teaches me something new. If you get
| stuck you could always google for the concepts you need and
| learn of them, or go to the subreddit and get hints but still
| solve the programming part yourself.
| Strilanc wrote:
| Interesting. I think one of the main benefits of AoC is it
| tends to teach you things. So I would have gotten stuck, read
| peoples answers on the subreddit the next day, and the problem
| would have stuck in my memory as one that taught me something
| new.
|
| I also wouldn't consider knowing properties of the GCD to be a
| "random math concept". It shows up in a reasonably large number
| of contexts. For example, in public key cryptography. A
| specific case is that at one point someone realized they could
| just collect hundreds of millions of RSA public keys and crack
| low entropy ones by checking for common divisors. Doing this
| naively by checking each pair would have been very costly, but
| they used properties of the GCD to massively reduce the cost by
| pooling keys [1].
|
| [1]: Page 7 of https://www.quintessencelabs.com/wp-
| content/uploads/2020/03/...
| estomagordo wrote:
| I'm sorry you were coerced into thinking :(
| _pmf_ wrote:
| > Not sure if this is indicative of other years
|
| It is.
| [deleted]
| hu3 wrote:
| I had the same feeling about https://projecteuler.net/ but PE
| is very clear about being math focused so that's on me.
|
| I wish Advent of Code puzzles were strictly algorithm focused
| without relying on specifics of mathematics. Skipping puzzles
| is demotivating for the completionist in me that lacks time to
| re-read math books.
| Buttons840 wrote:
| We should avoid certain questions because they're
| demotivating to some people?
|
| Perhaps a compromise would be to start with an easy input
| that any pile of if statements can handle, then give a longer
| input that will break all but the best algorithms as a bonus.
| bussierem wrote:
| I think it's more that the puzzles should avoid having a
| "correct solution" in the form of a known algorithm. If the
| puzzle can basically only be solved by remembering a
| specific algorithm, and any other algorithm (or attempt)
| will grind for hours, then the puzzle isn't about
| algorithms, or about coding, it's about whether or not you
| memorized a part of a math textbook and can recognize that
| it applies to the problem.
|
| Granted, I don't know the process of AoC in terms of
| vetting and building their puzzles, but it seems that the
| person/people involved all share very similar levels and
| domain of knowledge. Having more people reviewing or
| involved in the process that have a wider range of
| skillsets might avoid these situations.
|
| Example from what I was talking about before: Day 13 of
| AoC2020 was basically "the answer is the Chinese Remainder
| Theorem". If you remembered that...great you could solve
| this in 10 seconds (hell some languages have a _function_
| for that theorem!). If not....well good luck finding a
| solution that runs in under 6h. That has nothing to do with
| _programming_. Its just math, there wasn't even programming
| involved (literally some solutions were just "parse the
| input and pass it to mathlib.chinese_remainder()"). That's
| not satisfying to solve for the majority of people, I feel
| (opinion, I know).
| Joker_vD wrote:
| Is this CRT? Not exactly sure, but it does not run for
| six hours: result = 0 addend =
| 1 for divisor, desired_offset in [(7, 0),
| (13, 1), (59, 4), (31, 6), (19, 7)]: # keep
| trying numbers until we find the one that, with
| # the desired offset added to it, would divide without
| # remainder while (result + desired_offset) %
| divisor != 0: result += addend
| # adding another addend should not break previous results
| # so make it divisible by all previous divisors
| addend *= divisor result %= 7*13*59*31*19 #
| Is it really needed? Eh. print(result)
| bussierem wrote:
| This is exactly my thoughts on it. Granted I was never strong
| in math, and that's partly on me, but the early days (and
| even most mid days) of AoC are usually all about algorithms
| design and efficiency, but then sometimes you get these
| random "pick the right math formula" ones and just like you
| said, I have to "skip" them and it's so demotivating.
| LandR wrote:
| I solved day 13, both parts, and I'm pretty far from an
| algorithm wiz, I also never used Chinese Remainder Theorem.
|
| Part 1 runs in ~0.5 msecs Part 2 runs in ~2 msecs
| Buttons840 wrote:
| Does every problem need to be solvable by everyone?
|
| Project Euler used to say something along the lines of "not
| everyone can solve every problem, and that's OK". Looks like
| they've removed that statement though. I remember encountering
| it early in my career and realizing some problems I cannot
| solve, even though others can.
| nouveaux wrote:
| Project Euler was one of the first programming puzzle sites.
| I give credit to them for my interest in programming puzzles.
| However, I quickly abandoned them once I found other sites
| that was less math focused.
|
| For my personal goals, I want to get better at programming
| and not at math. When I find myself spending more time on the
| math rather than programming, I just skip the problem. I
| suspect many people abandon Project Euler for the same
| reasons I encountered.
|
| With all that said, I agree that not everyone can solve every
| problem and that is ok.
| jweather wrote:
| What other sites do you recommend with less math-focused
| problems?
| Jtsummers wrote:
| https://www.spoj.com
|
| When I was in college we used this (or an earlier
| version, that's a different URL than what I recall) in
| preparation for ACM programming competitions.
| vbezhenar wrote:
| It's pretty daunting when you're invested into something,
| spent a plenty hours only to realize that you're not in those
| 5% who's going to complete this challenge.
|
| IMO AoC should strife to be completable by 80% of programmers
| (number is out of thin air, but you got the idea).
|
| Project Euler is a different beast.
|
| Of course that's just my opinion.
| overboard2 wrote:
| I for one want that 5% to have interesting challenges, even
| if I can't be a part of that 5%. Unique achievements should
| be meaningful and celebrated, not removed for fear of
| upsetting the majority who cannot achieve them.
| NikolaeVarius wrote:
| Why is there a lack of "git gud" in some of these
| programming circles.
|
| Its meant to be hard and meant to force you to learn.
| progbits wrote:
| While I agree with the sentiment of creating accessible
| content I think if you make the problems so easy 80% can
| solve them, what fraction will have fun doing so? Wouldn't
| say 50% find them trivial and boring/unsatisfying?
|
| I think AoC goes for slowly growing difficulty which helps
| keep more skilled people engaged.
| Epitom3 wrote:
| > IMO AoC should strife to be completable by 80% of
| programmers
|
| What would be the point then, it will be just another
| leetcode
| auxym wrote:
| For what it's worth, I'm not a (professionnal) programmer,
| and I can usually solve 80% of the AoC problems
| intuitively. That's OK for me.
|
| For the other 20% where I don't even know where to start, I
| look up a solution on reddit, try to understand it and re-
| implement it myself, and learn something new. The 2020 day
| 13 problem mentioned by GP was indeed one of those for me
| last year.
| ollien wrote:
| Honestly, I didn't even understand how the CRT applied
| even after knowing it was required. This visualization[1]
| is what eventually helped me solve it.
|
| [1]: https://www.reddit.com/r/adventofcode/comments/kcl7d
| 2/2020_d...
| sdevonoes wrote:
| What's the main difference (besides submitting an answer
| faster than anyone else) between Project Euler and AoC? I
| find both rather similar (and I can do Project Euler any time
| of the year)
| Jtsummers wrote:
| Project Euler problems seem to be all math based, at least
| as far as I've seen. Advent of Code problems have numbers
| as results (most of the time), but aren't always based on
| some mathematical formulation(s).
|
| See 2019's IntCode puzzles for instance for something very
| far from Project Euler. They also had the side-effect of
| benefiting anyone who spent time refactoring their initial
| versions to create a better interface, a later day (23?)
| has you run 50 IntCode computers concurrently and
| communicating with each other. This became very hard to
| actually implement for many people because of the structure
| of their simulator and how they'd handled concurrent
| simulations earlier.
| Joker_vD wrote:
| Excuse me, what? You don't need to know CRT or indeed anything
| about the number theory except that you can divide numbers, the
| solution is simply: for each ID in list:
| next_departure = round_up_to_next_integer(earliest_time / ID) *
| ID delay[ID] = next_departure - earliest_time
| nearest_bus = ID with lowest delay return nearest_bus *
| delay[nearest_bus]
|
| That's it. I can think of only two other algorithms: the one
| that replaces division on the second line by repeated
| subtraction, and the one that uses repeated increments and
| checking whether the result is divided by the ID without a
| remainder.
|
| How do you even use CRT to solve this?
| Jtsummers wrote:
| Are you looking at part 1 or part 2? GP is talking about part
| 2.
| Joker_vD wrote:
| Can't find part 2 on the site, had to google...
| result = 0 addend = 1 for divisor,
| desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19,
| 7)]: # keep trying numbers until we find the
| one that, with # the desired offset added to
| it, would divide without # remainder
| while (result + desired_offset) % divisor != 0:
| result += addend # adding another addend
| should not break previous results # so make it
| divisible by all previous divisors addend *=
| divisor print(result % (7*13*59*31*19))
|
| This algorithm self-evidently works and is indeed "fast
| enough" if done by the computer.
| Jtsummers wrote:
| The key insight that many people, particularly those
| without the stronger math background, miss is that you
| can increase the addend like you (and I, in my solution)
| have done. So they either leave it at 1 (and the solution
| is around 1-2 trillion, IIRC, so that's not happening
| quickly) or they do _one_ optimization which is to set it
| to the first divisor (7 in your example, which still
| leaves you with hundreds of billions of loop executions),
| but don 't adjust it with each newly matched bus line.
|
| And instead of talking down to people, it can be more
| productive if you walk through a solution instead of
| stating "This algorithm self-evidently works" like a
| jerk.
|
| Also, the last modulo isn't needed.
| Joker_vD wrote:
| > walk through a solution instead of stating "This
| algorithm self-evidently works" like a jerk.
|
| After every iteration, "result" gives correct remainders
| for all divisors considered so far, so if the loop ends,
| the "result" will give correct remainders for all
| divisors. The only problem is whether it will end or not,
| and that I just tried experimentally: it stopped, so ok.
| Not really sure how to explain it further.
|
| > Also, the last modulo isn't needed.
|
| Good to know, I was not sure if I wouldn't step past it
| due to constantly increasing addend. I knew about this
| modular reduction from that one time when I needed to
| align/move/scroll things on a 80x25 grid.
___________________________________________________________________
(page generated 2021-12-01 23:00 UTC)