Advent of code.

[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.
https://adventofcode.com/2023

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]

Obviously, day by day it gets progressively harder.

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.

By Day 4 however, it took me over an hour and it took nearly 2 minutes to run

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

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.

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

[abeyer]

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)

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  )

ex you can only take one of the first places if you can read and parse a file using regular expression

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]

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.

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.

[abeyer]

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.

I think it's more than that. Sure, there are some questions that particular people will have more background in or just "click with" and will introduce individual variations in perceived difficulty. But there are also some pretty big differences in what I'd call the inherent difficulty, too.

Take the last two days for example: A direct approach to day 5 without any thought about the problem and data could still take some effort to implement and easily run for more than a day just to solve part 2. But for day 6, even the most naive implementation that's just a direct literal translation of the problem description to code is going to be quick and easy to write and still solve the "big" problem within seconds.

Of course they both also have much better solutions, if you "know the answer/trick." (Though I kinda disagree with that framing. One of the things I like about AoC is that their problems tend to not be focused on eliciting one specific solution where you know it or you don't. They've always seemed to me much more about having a solid grasp of fundamentals and when/how to use them together to effect a solution. When there is a bit of "trivia" needed it tends to be optional and/or fairly basic and accessible. (eg the closed form high school algebra answer to day 6.) There have been exceptions to this... but they were exceptions, not the norm.

[SiliconWizard]

The web site kind of sucks.

[paulca]

A problem I had, until day 4 when I finally slapped myself and stopped...  I started writing "professional, clean, code".  I had error handling, I had logging FFS, I had entire sequences designed to workaround and accomodate "holes in requirements".

I was literally about to write a dynamic parser in day 4, but instead i just opened the input data file and learned it was a fixed sized grid.  On day 1-3 I would have already launched into handling arbitrary numbers of columns etc.  On day 2 or 3 I think I did write code which would accept any size of grid, with any number of corner cases covered and even up to 5 digit numbers.  I could have scanned the input file and checked if those corner cases existed or not and the exact, fixed dimensions of the static data.

[Andy Watson]

Couldn't access the problems - requires Github, google, or redit login - which I don't have.

If this type of programing problem-solving appeals, checkout:
https://projecteuler.net/about

The first few problems are trivial but most require some maths trickery. Most of the problems can be brute-forced if you get desparate

[paulca]

So, day 5.  The first part doesn't look hard.

What they will ask for in part 2 or it I am dreading.  I know whats coming.

EDIT:  Not as bad as I thought.

[SiliconWizard]

Couldn't access the problems - requires Github, google, or redit login - which I don't have.

Yes, I don't particularly liked that they don't give any option for registering directly on the web site. I have github and google accounts, but I never, never use them as a login means on any other site. It's a big no-no to me.

[ledtester]

Yes, I don't particularly liked that they don't give any option for registering directly on the web site. I have github and google accounts, but I never, never use them as a login means on any other site. It's a big no-no to me.

You can just create a throw-away Google/Github account.

[paulca]

Couldn't access the problems - requires Github, google, or redit login - which I don't have.

Yes, I don't particularly liked that they don't give any option for registering directly on the web site. I have github and google accounts, but I never, never use them as a login means on any other site. It's a big no-no to me.

Half of the internet works on 3rd party OAuth authentication these days.

Look at it on a more positive note.  You give your sensitive login details, etc.  to a single company.  Other companies you want to do stuff with online who accept that auth provider will just get your userId and the token.  This is actually has advantagous information boundaries and protections, rather than the opposite.

If your primary GitHub accounts are work related, create a new one just for auth.  I have about 3 GitHub accounts and about 3 GitLab accounts.  Work, public, scrap, customer, etc.  It would, for example, be a bit unprofressional to attach my personal hubby account GitHub up to a crypto-exchanges internal auth, so I created a github account specifically for that customer.

The other major advantage is...  the company do not own or control the account.  YOU do.  You can kick the other company out of your auth with a single click.  You can change the email, name, add remove things and delete the account when you stop working for that org or stop dealing with that company.  They have no control over it to stop you.

[PA0PBZ]

This is both fun and a time sink, I did day one in Excel 

[mariush]

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!

I had a bit of time and did the first 4 days in PHP, and posted the results here : https://github.com/mariush-github/adventofcode2023/tree/main

Surprisingly day 1 took me the longest, but mostly because of the way the part2 is described ... took me some time to realize that when you have sequences like oneight you're supposed to decode as 18, not "1ight"...

Day 4 I basically did it in around 15 minutes and it solves more or less instantly.

Going back to what I was saying about over complicated code, compare my solution to day 1 (see link above) with the solution below https://syltaen.com/advent-of-code/?year=2023&day=1

Code: [Select]

function solve($lines) {
    return $lines->map(function ($l) {
        $nums = $l->chars()->keep(range(0, 9));
        return (int) ($nums->first() . $nums->last());
    })->sum();
}

$solution_1 = solve($input->lines);


$digits = [    "zero"  => 0,    "one"   => 1,    "two"   => 2,    "three" => 3,    "four"  => 4,    "five"  => 5,    "six"   => 6,    "seven" => 7,    "eight" => 8,    "nine"  => 9,];

$solution_2 = solve($input->lines->map(fn ($l) =>
    scalar(preg_replace_callback("/(".implode("|", array_keys($digits)).")/", fn ($r) =>
        $digits[$r[1]]
    , (string) $l))
));
(ignoring the fact he added zero even though the problem doesn't say anything about zero being replaced with 0, in fact there's no 0's in the whole input file.)

what's more readable, what version's more easy to be understood by a junior developer a year from now, which version can be more easily adapted to support tweaks, changes to the problem... etc etc

[paulca]

Honestly.  I wish functional programming would ___ away off back to data science and information theory and get out of normal coding.

It's garbage.  It reads like an equation in an information theory textbook.  It's illegible.  It's written in abstract mathematical constructs which humans do not speak in.  Only trained acdemics understand the reason behind half of the keywords even.

That section you posted, I can wrap my head around it, I have used functional orientated frameworks for data processing, but it is just a blob of grammar-less, syntactic sugar that is apparently designed to obfuscate the code AWAY from being useful for the programmer.  Really all they did was take those pesky pubic static methods that NOBODY liked or encouraged and gave them a fancy academic title and it became the latest buzz craze.

Bunch of w*** if you ask me.

I write my code so it can be read by a human.  That's the whole fing point of it.  As "US English" is the international code standard language...

It should read like english.

If this then that, otherwise this

Is plain English.

that.apply(this$$).yeild().map( x, x=x+x ).collect(asList())

I made that up, but it's about as legible as the vast majority of information theory code... sorry functional and lambda w@nk.

[paulca]

https://pastebin.com/1Ud2Uphd

[zilp]

https://pastebin.com/1Ud2Uphd

That code fails when the last line doesn't have a line terminator.

Which maybe gives a hint as to why functional-style code has a tendency to have fewer bugs: If you avoid dealing manually with indices, you can't have off-by-one indexing errors.

[paulca]

https://pastebin.com/1Ud2Uphd

That code fails when the last line doesn't have a line terminator.

You know what makes all code fail.

People making up requirements.

Note the code works if the last line has no newline.  It fails when it DOES have a newline as it produces an enumeration of a blank line.

The input file provided is static.  I can read it.  It does not have a newline on the end of the last line.  Therefore the code is bug free and obtains the correct answer.

Which maybe gives a hint as to why functional-style code has a tendency to have fewer bugs: If you avoid dealing manually with indices, you can't have off-by-one indexing errors.

Functional-style code does not have a tendency to have fewer bugs.  It's just the sheer amount of code that is put behind the functional-style APIs has been well unit tested.  You know what those APIs use under the covers?  Indices, arrays and iterators (aka pointer arithmetic).  However, as computers, nor humans work in a functionally orientated way it tends towards massively inefficient code, code that is hard to read and repeatedly has to be re-written, results in dozens of different ways to do the same thing.  All of which are bad for code quality.  IMHO.

There is a video on YouTube where a dev sends his python project in for "opimisation".  In functionally orientated higher, than high level Python it was written in it ran in something like 15 minutes.

Simply removing all the functional crap, list comprehension and all the high level "convenience methods" and just using plain old lists/arrays and iteration dropped the run time below 2 minutes.

Rewriting it in Rust and it ran in 15 seconds.  In pure C and then ASM small gains only where made.

The only people really behind this style of coding are the large enterprises.  It is cheaper on aggregate for them to buy 10 servers and 3 cheap developers, than it is to buy 1 server and 3 expensive developers.  Servers do not cost $2500 a DAY!)

What functional languages like Scala and Haskel et. al yield does not come from the syntax.  It comes from the strict management of state and it's mutability.   The same principles can be applied in Java, C, Python and ASM, without fancy gibberish producing closures (lambda).  Though they are exceptionally easy to copy and paste off GPT or Stack Overflow.

[zilp]

https://pastebin.com/1Ud2Uphd

That code fails when the last line doesn't have a line terminator.

You know what makes all code fail.

People making up requirements.

Note the code works if the last line has no newline.  It fails when it DOES have a newline as it produces an enumeration of a blank line.

The input file provided is static.  I can read it.  It does not have a newline on the end of the last line.  Therefore the code is bug free and obtains the correct answer.

You are obviously wrong, but ... I guess you don't care?

Which maybe gives a hint as to why functional-style code has a tendency to have fewer bugs: If you avoid dealing manually with indices, you can't have off-by-one indexing errors.

Functional-style code does not have a tendency to have fewer bugs.  It's just the sheer amount of code that is put behind the functional-style APIs has been well unit tested.  You know what those APIs use under the covers?  Indices, arrays and iterators (aka pointer arithmetic).

So, your argument is that because an abstraction is based on something that is prone to bugs, therefore, the abstraction can not abstract away that risk by using one well-tested implementation? Are you sure that that makes sense?

However, as computers, nor humans work in a functionally orientated way it tends towards massively inefficient code, code that is hard to read and repeatedly has to be re-written, results in dozens of different ways to do the same thing.  All of which are bad for code quality.  IMHO.

You do realize that you are assuming that your personal subjective experience is universal, right? You are, maybe, not thinking in functional terms. Which is fine. That doesn't mean that that is universal among humans.

Now, I have no idea why you think that functional-style code needs to constantly be rewritten, or why you think that there being dozens of ways to do the same thing is somehow unique to functional-style code.

What I do notice, though, is that you found a way to write imperative-style code that's incorrect, and that you didn't even manage to see the bug after I pointed out to you what the bug was.

There is a video on YouTube where a dev sends his python project in for "opimisation".  In functionally orientated higher, than high level Python it was written in it ran in something like 15 minutes.

Simply removing all the functional crap, list comprehension and all the high level "convenience methods" and just using plain old lists/arrays and iteration dropped the run time below 2 minutes.

Rewriting it in Rust and it ran in 15 seconds.  In pure C and then ASM small gains only where made.

None of which addresses correctness. I didn't claim that functional-style code is the solution to all problems.

But also, isolated execution times of some piece of code is just completely irrelevant. If that code is run once a year in yome batch job, it would be nonsensical to spend any time on optimizing it. If you start buying more servers because that thing is being called all the time and dominates your CPU consumption, then you are just bad at selecting the right tool for the job.

The only people really behind this style of coding are the large enterprises.  It is cheaper on aggregate for them to buy 10 servers and 3 cheap developers, than it is to buy 1 server and 3 expensive developers.  Servers do not cost $2500 a DAY!)

That's a nonsensical comparison?

What functional languages like Scala and Haskel et. al yield does not come from the syntax.  It comes from the strict management of state and it's mutability.   The same principles can be applied in Java, C, Python and ASM, without fancy gibberish producing closures (lambda).  Though they are exceptionally easy to copy and paste off GPT or Stack Overflow.

I guess it is true that it doesn't come from the syntax, as you don't really need much syntax to have HOF or lambdas!? I mean, the C standard lib has higher-order functions (see qsort()), and GCC even has sort-of closures in C (aka nested functions), and I think clang even supports function literals in C!? It is unfortunate, of course, that it took C some 50 years or so to catch up with Lisp.

Though I guess I am really curious what it is about lambdas that seems to confuse you so much!? Do loop bodies also confuse you? Or is it the concept of functions with lexical scope? Or ... what?

[rtv]

You might find this guy's blog interesting. Using Commodore 64 to solve problems.
SPOILERS http://clb.confined.space/aoc2023/ SPOILERS

[paulca]

https://pastebin.com/1Ud2Uphd

That code fails when the last line doesn't have a line terminator.

You know what makes all code fail.

People making up requirements.

Note the code works if the last line has no newline.  It fails when it DOES have a newline as it produces an enumeration of a blank line.

The input file provided is static.  I can read it.  It does not have a newline on the end of the last line.  Therefore the code is bug free and obtains the correct answer.

You are obviously wrong, but ... I guess you don't care?

Have you run it?

This is not subjective it's emperical.  There is one right answer.  Any code which delivers it is correct.  It will be deleted.  It will not be reused, it was a one off to solve a one off problem.  It gave the right answer therefore it is correct.

"Obviously".

Explain yourself.

You see this is the issue I see most with this new era of extremely highlevel APIs.  The people who come out of Uni with 0 years experience and all they know at these high-level APIs, except in most cases when you ask them about the corner cases and exact specifications for each of their streaming functions... they haven't a clue and have never read the manuals. 

I don't think you are capable of understanding the code I wrote or even running it.  Or you would have found it works perfectly well.  So the "obvious" bit is that you must be wrong?

Make it fail.  Then come back and explain why it failed.

[zilp]

I don't think you are capable of understanding the code I wrote or even running it.  Or you would have found it works perfectly well.  So the "obvious" bit is that you must be wrong?

Make it fail.  Then come back and explain why it failed.

Code: [Select]

$ printf onetwo > test-data.txt ; python x.py
Found one
Line Value: 11
Total: 11

I mean ... how hard can it be?

[paulca]

If you were a software engineer on my team.... I'd be requesting your retraining or reassignment right now.

Can you run it properly with proper test data and less of an attitude and then prove it has a problem.

Seriously if it has a problem I'm curious to see a reproduction of it.

Prove to me it fails the requirements and produces an in correct answer?

Also, if you want a quick test don't use "onetwo", use "oneighten" and expect the answer 19.

[paulca]

Anyway, since it's well old now.  Day 5 part 2. 

The obvious solution is to just wrap your tree walker in a loop across each range.  I am pretty sure most people choose this approach and then realise it will take hours or days depending on your hardware and choice of language.  If engineers actually opened the test file they would discover the number are 6-10 digits, including the range lengths.  So the total nodes in that tree are astronomical.

Having seen the input file, I went "Hell no!".  I set about treating "ranges" as the atomic datum.  Instead of iterating over the elements within the ranges, I just used the range dimensions instead and iterate through them.

The bottom end "datum" comparison is comparing two ranges to produce an output of 1..3 ranges.

Ranges can overlap and not overlap in an exhaustive and repetitively short number of permutations.

* No overlap - return the original range
* Left partial - return the range which is overlapped with it's offset applied.  Also return the non-matching portion without offset as a range.
* Right partial - Same as above
* Centre partial - Return the left unmatching range, the matching range with offset and the right hand unmatching range.
* All inclusive - Return the full input range with offset applied.

Where I came to a complete halt, most likely getting hung up on a choice I'd made and chasing my tail....  is in the iteration.

I have no problems iterating a tree.  I have no problems iterating a dynamic tree like those ranges.  Where I hit the "Uh oh, ummm... errrr... ahhh... shit... em..."  was

How do you iterate down the "fixed tree" of mappings, while also iterating a dynamic tree of ranges, ie...  putting the stepping stone out in front of you, iterating to it, generating a bunch more ranges for that "tier" of the tree before moving to that step.

The "choice" I made which hung me up and needs fixing is the choice of using a recursive function with a linear iterator for the "mapping tree".  Obviously once the "ranges" tree expands it over consumes from that.  I was about to "consider" using cloned iterators as I descent the trees, but that just make things every more complex and messy.

So I would need to start again with a fresh mind.  The range compare and split function is sound.  I just need to figure out the best way to track down two trees in parallel, if that makes sense.  I probably need to draw some diagrams to explain it.

I'm not beaten by it.  If this was a work Jira and I didn't have choice I have "other levels" of concentration to go to... It's just hit that... hmm... sounds like too much work for a simple quiz barrier.