Electronics > Microcontrollers

(1/7) > >>

paulca:
I figured this would be right up the street for some of you.. and send others running a mile :)

This years "Advent" of code Calendar.

If you have not seen these daily puzzle style coding exercises, here is how it works.

Each day they give you a puzzle to solve and a short set of example data for discussion purposes and a worked example.  Small enough data to do it in your head.  Then they provide you to a link to a much larger data set which... you are not doing in your head.

The answer is usually a single number.  If you get the answer correct, it will open a second part to the question.

The second part of the question sorts the cruft out of the runnings.  It is usually taking the complexity up another level, while forcing your to reapproach the problem in a new way entirely.

Obviously, day by day it gets progressively harder.
Day 1 I think I had both parts done in 10 minutes.  Instant answers, even in python.
By Day 4 however, it took me over an hour and it took nearly 2 minutes to run, involving (In my solution) linearised bounded recursion. (instead of using actual recursion).  With a seed of 198 items it peeked on the bell curve at over 2 million items.  I figured if you wrote it in C and an Arduino with enough memory for linearised recursion, it would probably run faster than my big iron running python!

Give it a crack.

I believe it is okay to post solutions for calendar items older than 7 days.  If you wish to disclose anything about a solution below before that time has expired, please enclose it in a "Spoiler" tag.

Have fun.

mariush:
For the last couple years, I did them for fun in php up to around day 25.

I skipped some because I didn't want to do them, as the solutions relied on obscure algorithms or knowing some mathematical tricks.

imho the problems should be brute force-able in a realistic amount of time (ex a couple of days of running on a modern computer), not require an average programmer to be aware of some odd rarely used algorithm, or some methods that favor specific languages.  (ex you can only take one of the first places if you can read and parse a file using regular expression and basically know regular expressions so well that you can write complex regular expression on the fly and get it right first try)

abeyer:

--- Quote from: paulca on December 06, 2023, 04:14:36 pm ---Obviously, day by day it gets progressively harder.

--- End quote ---

My experience in the past has not been that kind of steady progression... there are easier and harder days, but not a steady increase imho.

--- Quote from: paulca on December 06, 2023, 04:14:36 pm ---By Day 4 however, it took me over an hour and it took nearly 2 minutes to run

--- End quote ---

For day 4? Or do you mean 5? 4 has a fairly simple linear time and space solution.  ;)

--- Quote from: paulca on December 06, 2023, 04:14:36 pm ---I believe it is okay to post solutions for calendar items older than 7 days.  If you wish to disclose anything about a solution below before that time has expired, please enclose it in a "Spoiler" tag.

--- End quote ---

I'd suggest/request just putting any answers/hints in a spoiler or linking off-site, regardless of day.

abeyer:

--- Quote from: mariush on December 06, 2023, 04:33:51 pm ---imho the problems should be brute force-able in a realistic amount of time (ex a couple of days of running on a modern computer)

--- End quote ---

In my experience they generally are with a bit of thought. (though I certainly don't have the patience to actually let one run for a couple days without rewriting it to be faster first  ;D)

--- Quote from: mariush on December 06, 2023, 04:33:51 pm ---ex you can only take one of the first places if you can read and parse a file using regular expression

--- End quote ---

If you aren't down to learn and know regex, algorithms, math tricks, and a whole lot more (not to mention investing time in tools and practice) you shouldn't even be thinking about the first places. They're often solved within seconds by people who train for doing these competitions. That's great if you want it, but most people just do them for fun.

jgrossman:

--- Quote from: abeyer on December 06, 2023, 07:38:20 pm ---My experience in the past has not been that kind of steady progression... there are easier and harder days, but not a steady increase imho.

--- End quote ---

Yeah, same here. I guess it really depends on if you know the answer they are trying to elicit. I find as well it's generally equal-or-harder each day, but sometimes you just know the trick and it takes minutes per part for a solution even in the later days.