

Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.
Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.
I am not interested in leaderboards (based on resolution time since publication), first because for Europeans the only way to be competitive would be to wake up very early or stay up very late, but also because I only do this because it is somehow fun to me. Sometimes I may not have the time to play at all on a given day and catch up later in the week.
Anyway, I thought it might interest some people on this list.
[1] https://adventofcode.com[2] https://github.com/catwell/adventofcode/tree/master/2018
Pierre Chapuis


This is interesting. An interesting twist might be to use a different language each day. Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.I am not interested in leaderboards (based on resolution time since publication), first because for Europeans the only way to be competitive would be to wake up very early or stay up very late, but also because I only do this because it is somehow fun to me. Sometimes I may not have the time to play at all on a given day and catch up later in the week.Anyway, I thought it might interest some people on this list.[1] https://adventofcode.com[2] https://github.com/catwell/adventofcode/tree/master/2018 Pierre Chapuis


interesting. The first star on day one is elementary to solve just with a basic very Excel sheet, but the second star is much more difficult as it involves cyclic aruthmetic (you can solve it by brute force but it rapidly quite computing intensive as each test requires decomposing 1016 integers into primes in order to test which position to look at (otherwise the search loops are unbounded): you need some knowledge of cyclic arithmetic to solve it with an efficient algorithm which is ensured to find a solution in a bounded and in fact quite small time. Your current test code in Haskell uses the brute force approach to repeat searches in more and more repeated cycles, but even if you find a repeated frequency with N cycles of the list, you could still find a lower frequency located below in the input list. There's a more efficient solution by sorting the frequencies produced by the first cycle. But then you need to apply the algorithm to compute a lowest common multiplier and see if it's divisible by a position in the sorted list. Finally you have to aplky a second sort... Technically you can still do that within Excel by several operations involding copying computed values from one column to another (without their formula) and then apply a custom sort. over a group of columns. All this could as well be done in Lua of course (instead of Excel, you need Lua tables) This is interesting. An interesting twist might be to use a different language each day. Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.I am not interested in leaderboards (based on resolution time since publication), first because for Europeans the only way to be competitive would be to wake up very early or stay up very late, but also because I only do this because it is somehow fun to me. Sometimes I may not have the time to play at all on a given day and catch up later in the week.Anyway, I thought it might interest some people on this list.[1] https://adventofcode.com[2] https://github.com/catwell/adventofcode/tree/master/2018 Pierre Chapuis


Op So. 2 Des. 2018 om 13:53 het Pierre Chapuis < [hidden email]> geskryf:
>
> Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.
>
> Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.
Well, Lua seems to be suggested by the farewell greeting "Good lu" :)
Do they get tougher as Christmas draws near? The first two days'
problems have not exactly been of Project Euler standard.


It's really fun.
There is a related subreddit
It's really fascinating to see what some languages offer featurewise to solve the problems, some implementations in certain languages blew my mind for elegance, and prompted me to investigate the language.
Op So. 2 Des. 2018 om 13:53 het Pierre Chapuis <[hidden email]> geskryf:
>
> Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.
>
> Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.
Well, Lua seems to be suggested by the farewell greeting "Good lu" :)
Do they get tougher as Christmas draws near? The first two days'
problems have not exactly been of Project Euler standard.


No but the second star problem gives an idea of the algorithmic complexity of actual problems (notably security problems, here it gives an idea about how and why the RSA algorithm works, this probelm being equivalent to finding a decomposition of a ~10 bits as a product of prime numbers; actual RSA keys are now based on at least 128 bit keys but most secure apps now use 1024 bit keys, where not only brute basic force attacks are not possible but also smart attacks using arthmetic properties is also computingly intensive). I bet the other problems are the same kind: they allow people experiment with encryption/security algorithms that are based on combinatorially difficult problems that are not soluble easily given the current limits of today's computers in terms of memory space available, number of available computing units that can run in parallel, and energy needed to make all this run... unless these resources are stolen, but even in that case there's a limit as there's not an infinity of devices you can steal to do that work as this is currently caped to about 36 bits today, still very far of the current 1024 limits of RSA).
Op So. 2 Des. 2018 om 13:53 het Pierre Chapuis <[hidden email]> geskryf:
>
> Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.
>
> Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.
Well, Lua seems to be suggested by the farewell greeting "Good lu" :)
Do they get tougher as Christmas draws near? The first two days'
problems have not exactly been of Project Euler standard.


I think that this small competition is to use these siumple problems to know if there are better strategies to solve complex problems that would allow to perform attacks and crack existing programming and encryption standards. But I'm now more concerned by the fact that all these algorithms can be broken much more easily by sidechannels (that have now been discovered everywhere and that are exploitable remotely), and especially timebased attacks. Such small competition will only reveal that possibly a few additional bits would be collected, without even being able to break RSA. Behind this competition which looks "fun", I'm convinced that it's organized and monitored by companies developing security standards, and that they're ready to pay for that to improve their own products and engineering methods. Le dim. 2 déc. 2018 à 23:06, Philippe Verdy < [hidden email]> a écrit : No but the second star problem gives an idea of the algorithmic complexity of actual problems (notably security problems, here it gives an idea about how and why the RSA algorithm works, this probelm being equivalent to finding a decomposition of a ~10 bits as a product of prime numbers; actual RSA keys are now based on at least 128 bit keys but most secure apps now use 1024 bit keys, where not only brute basic force attacks are not possible but also smart attacks using arthmetic properties is also computingly intensive). I bet the other problems are the same kind: they allow people experiment with encryption/security algorithms that are based on combinatorially difficult problems that are not soluble easily given the current limits of today's computers in terms of memory space available, number of available computing units that can run in parallel, and energy needed to make all this run... unless these resources are stolen, but even in that case there's a limit as there's not an infinity of devices you can steal to do that work as this is currently caped to about 36 bits today, still very far of the current 1024 limits of RSA).
Op So. 2 Des. 2018 om 13:53 het Pierre Chapuis <[hidden email]> geskryf:
>
> Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.
>
> Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.
Well, Lua seems to be suggested by the farewell greeting "Good lu" :)
Do they get tougher as Christmas draws near? The first two days'
problems have not exactly been of Project Euler standard.


>>I bet the other problems are the same kind
You can view past year's problems if you're so inclined. I wouldn't be surprised if companies see if there's a gem in there, but none of last year's problems were particularly challenging  indeed, maybe they do try to find more elegant solutions but I'm not sure why that would be a bad thing. I think that this small competition is to use these siumple problems to know if there are better strategies to solve complex problems that would allow to perform attacks and crack existing programming and encryption standards. But I'm now more concerned by the fact that all these algorithms can be broken much more easily by sidechannels (that have now been discovered everywhere and that are exploitable remotely), and especially timebased attacks. Such small competition will only reveal that possibly a few additional bits would be collected, without even being able to break RSA. Behind this competition which looks "fun", I'm convinced that it's organized and monitored by companies developing security standards, and that they're ready to pay for that to improve their own products and engineering methods.
Le dim. 2 déc. 2018 à 23:06, Philippe Verdy < [hidden email]> a écrit : No but the second star problem gives an idea of the algorithmic complexity of actual problems (notably security problems, here it gives an idea about how and why the RSA algorithm works, this probelm being equivalent to finding a decomposition of a ~10 bits as a product of prime numbers; actual RSA keys are now based on at least 128 bit keys but most secure apps now use 1024 bit keys, where not only brute basic force attacks are not possible but also smart attacks using arthmetic properties is also computingly intensive). I bet the other problems are the same kind: they allow people experiment with encryption/security algorithms that are based on combinatorially difficult problems that are not soluble easily given the current limits of today's computers in terms of memory space available, number of available computing units that can run in parallel, and energy needed to make all this run... unless these resources are stolen, but even in that case there's a limit as there's not an infinity of devices you can steal to do that work as this is currently caped to about 36 bits today, still very far of the current 1024 limits of RSA).
Op So. 2 Des. 2018 om 13:53 het Pierre Chapuis <[hidden email]> geskryf:
>
> Advent of Code [1] is a coding problem advent calendar: every day from December 1 to December 25, they publish two code problems that can be solved in any language.
>
> Like last year, I am doing it in Lua (I may solve the problem in another language as well some days, but I intend to do all of them in Lua at least). I publish my solutions [2] on GitHub.
Well, Lua seems to be suggested by the farewell greeting "Good lu" :)
Do they get tougher as Christmas draws near? The first two days'
problems have not exactly been of Project Euler standard.


On Sun, Dec 2, 2018 at 10:24 PM Dirk Laurie < [hidden email]> wrote:
> Do they get tougher as Christmas draws near? The first two days'
> problems have not exactly been of Project Euler standard.
Yes, they become much harder. You can look at the [Events] link to
see the previous years problems, and check the [Stats] link to get an
idea of the difficulty of each one.
Cheers


Okay, maybe I'm missing something. Since Lua is new to me and I
started a day late, I used C for the day one problem, to get the
mechanics of the website worked out. Like Philippe, I used Excel
for the first star, but then I saw the issue with that approach
for the second star and switched to C. I used a trivial list to
store all "frequencies" as they occurred, and the addFrequency()
function returned an indication that the new value was already
there. My data stream was 959 items and the program required 38
seconds on a Macbook Pro. Since I don't even know what cyclic
arithmetic is, maybe I'm missing something really important, and
bonus points to anyone who'll enlighten me. For instance, are
performance issues like runtime and memory consumption counted?
Sadly, now I'm a) hooked and b) committed to the "different
language every day" idea. I'll try to do days 2 and 3 tomorrow.
On 12/2/18 1:11 PM, Philippe Verdy
wrote:
interesting. The first star on day one is
elementary to solve just with a basic very Excel sheet, but the
second star is much more difficult as it involves cyclic
aruthmetic (you can solve it by brute force but it rapidly quite
computing intensive as each test requires decomposing 1016
integers into primes in order to test which position to look at
(otherwise the search loops are unbounded): you need some
knowledge of cyclic arithmetic to solve it with an efficient
algorithm which is ensured to find a solution in a bounded and
in fact quite small time.
Your current test code in Haskell uses the brute force
approach to repeat searches in more and more repeated cycles,
but even if you find a repeated frequency with N cycles of the
list, you could still find a lower frequency located below in
the input list. There's a more efficient solution by sorting
the frequencies produced by the first cycle. But then you need
to apply the algorithm to compute a lowest common multiplier
and see if it's divisible by a position in the sorted list.
Finally you have to aplky a second sort... Technically you can
still do that within Excel by several operations involding
copying computed values from one column to another (without
their formula) and then apply a custom sort. over a group of
columns. All this could as well be done in Lua of course
(instead of Excel, you need Lua tables)
This is interesting. An interesting twist
might be to use a different language each day.
Advent of Code [1] is a coding
problem advent calendar: every day from December 1 to
December 25, they publish two code problems that can
be solved in any language.
Like last year, I am doing it in Lua (I may solve
the problem in another language as well some days, but
I intend to do all of them in Lua at least). I publish
my solutions [2] on GitHub.
I am not interested in leaderboards (based on
resolution time since publication), first because for
Europeans the only way to be competitive would be to
wake up very early or stay up very late, but also
because I only do this because it is somehow fun to
me. Sometimes I may not have the time to play at all
on a given day and catch up later in the week.
Anyway, I thought it might interest some people on
this list.
[1] https://adventofcode.com
[2] https://github.com/catwell/adventofcode/tree/master/2018

Pierre Chapuis

Daryl Lee
All our discontents about what we want appeared to
me to spring from the want of thankfulness for what we
have.  Daniel Defoe


"cyclic artithmetic" is synonym for "modular arithmetic" (arithmetic over Z/nZ fields, where n is a finite integer and the division is inversible, unlike arithmetic on Z, Q, R or C with infinite bounds). 38 seconds on a Mac Pro is still lot of processing, and I'm sure you can get a reply in a few milliseconds if you use the proper representation of the problem: you'll end up decomposing integers into products of primes, and this can dramatically reduce the number of tests to perform (on this problem with 1027 data input, using basic brute force approache you end up testing about 1 million possibilities and using lot of memory or two embedded loops exploring the 1027*1027 possibilities to get a definite response). This problem is very similar to breaking RSA with a 10bit public product key and looking for one of the two primes whose product gives the 10 bit public key (note that RSA does not really uses primes because they are too large to be tested, instead it uses two "most probably" primes using a primarily test which is quite time intensive). This problem exposes a part of the RSA difficulty (for breaking public keys), based on the difficulty of decomposing very large integers into a product of two integers. But within this problem the problem is more limited because the product is still limited to 1027^2, so a brute force attack still works (even if it's not efficient and can be made dramatically faster by caching the decompositions in order to reduce the number of tests to perform).
I've not programmed the way to do that, but some people may find an efficient implemenhtation and new ideas to make this small problem much faster, without requiring much memory (note that sorting in this problem is not dramatically complex because you only sort rather small lists of about one thousands item and we know we can do that quite efficiently in O(n log n) time where n is about 1000, i.e. roughtly 10bits only products; but for actual modern use of RSA, working on 1024bit products, this is not possible in reasonnable time and with enough memory resources : this would not even be possible if we could use use all existing computers on Earth, because these huge numbers are many orders of magnitude above the total number of atoms in our observable universe and could run them all at 10 Gigahertz.
This makes this problem very interesting in fact to explore in order to find how we can optimie its resolution to get dramatically faster responses (with less loops and modest memory usage to store and cache the intermediate results).
The day 2 also explores such known computationally costly algorithms (here it is a well known problem of regular expressions and the difficulty to locate arbitrary long subtrings in a very large string (could be a entire database), without having to reparse the whole with brute force exploring M*N possibilities where M and N and the length of the substring and the longer string to scan: as these problems will have their computation difficulty growing each time, you won't be able to use basic tools like Excel to sum a list, you'll need to program and think really about the algorithms you use and the best data representation.
These problems are wellknown classes of algorithms where there's intensive research, and most of them are based on arithmetic (and you need to know many theorems on them): arithmetics on integers (or rationals) is one of the most complex part of mathematics and whose results interest a lot the whole computing industry, becaues these problems could reveal exploits that could be harvested to break security or privacy, and can now have very large impact on public freedoms and politics when all our economy now depends so much on computers and automated decisions.
Okay, maybe I'm missing something. Since Lua is new to me and I
started a day late, I used C for the day one problem, to get the
mechanics of the website worked out. Like Philippe, I used Excel
for the first star, but then I saw the issue with that approach
for the second star and switched to C. I used a trivial list to
store all "frequencies" as they occurred, and the addFrequency()
function returned an indication that the new value was already
there. My data stream was 959 items and the program required 38
seconds on a Macbook Pro. Since I don't even know what cyclic
arithmetic is, maybe I'm missing something really important, and
bonus points to anyone who'll enlighten me. For instance, are
performance issues like runtime and memory consumption counted?
Sadly, now I'm a) hooked and b) committed to the "different
language every day" idea. I'll try to do days 2 and 3 tomorrow.
On 12/2/18 1:11 PM, Philippe Verdy
wrote:
interesting. The first star on day one is
elementary to solve just with a basic very Excel sheet, but the
second star is much more difficult as it involves cyclic
aruthmetic (you can solve it by brute force but it rapidly quite
computing intensive as each test requires decomposing 1016
integers into primes in order to test which position to look at
(otherwise the search loops are unbounded): you need some
knowledge of cyclic arithmetic to solve it with an efficient
algorithm which is ensured to find a solution in a bounded and
in fact quite small time.
Your current test code in Haskell uses the brute force
approach to repeat searches in more and more repeated cycles,
but even if you find a repeated frequency with N cycles of the
list, you could still find a lower frequency located below in
the input list. There's a more efficient solution by sorting
the frequencies produced by the first cycle. But then you need
to apply the algorithm to compute a lowest common multiplier
and see if it's divisible by a position in the sorted list.
Finally you have to aplky a second sort... Technically you can
still do that within Excel by several operations involding
copying computed values from one column to another (without
their formula) and then apply a custom sort. over a group of
columns. All this could as well be done in Lua of course
(instead of Excel, you need Lua tables)
This is interesting. An interesting twist
might be to use a different language each day.
Advent of Code [1] is a coding
problem advent calendar: every day from December 1 to
December 25, they publish two code problems that can
be solved in any language.
Like last year, I am doing it in Lua (I may solve
the problem in another language as well some days, but
I intend to do all of them in Lua at least). I publish
my solutions [2] on GitHub.
I am not interested in leaderboards (based on
resolution time since publication), first because for
Europeans the only way to be competitive would be to
wake up very early or stay up very late, but also
because I only do this because it is somehow fun to
me. Sometimes I may not have the time to play at all
on a given day and catch up later in the week.
Anyway, I thought it might interest some people on
this list.
[1] https://adventofcode.com
[2] https://github.com/catwell/adventofcode/tree/master/2018

Pierre Chapuis

Daryl Lee
All our discontents about what we want appeared to
me to spring from the want of thankfulness for what we
have.  Daniel Defoe


There is certainly a faster solution for day 2, but my Lua solution gives the answer in 40 ms with my input on my machine, and my Haskell solution does in 120 ms (it could certainly be much faster but I don't know Haskell well so I don't really aim for performance).


On Mon, Dec 3, 2018, at 12:00, Pierre Chapuis wrote:
There is certainly a faster solution for day 2, but my Lua solution gives the answer in 40 ms with my input on my machine, and my Haskell solution does in 120 ms (it could certainly be much faster but I don't know Haskell well so I don't really aim for performance).
... I meant day 1 star 2, obviously.


Thanks! That sounds like something to come back to later when I have more than a day to work on it. "cyclic artithmetic" is synonym for "modular arithmetic" (arithmetic over Z/nZ fields, where n is a finite integer and the division is inversible, unlike arithmetic on Z, Q, R or C with infinite bounds). 38 seconds on a Mac Pro is still lot of processing, and I'm sure you can get a reply in a few milliseconds if you use the proper representation of the problem: you'll end up decomposing integers into products of primes, and this can dramatically reduce the number of tests to perform (on this problem with 1027 data input, using basic brute force approache you end up testing about 1 million possibilities and using lot of memory or two embedded loops exploring the 1027*1027 possibilities to get a definite response). This problem is very similar to breaking RSA with a 10bit public product key and looking for one of the two primes whose product gives the 10 bit public key (note that RSA does not really uses primes because they are too large to be tested, instead it uses two "most probably" primes using a primarily test which is quite time intensive). This problem exposes a part of the RSA difficulty (for breaking public keys), based on the difficulty of decomposing very large integers into a product of two integers. But within this problem the problem is more limited because the product is still limited to 1027^2, so a brute force attack still works (even if it's not efficient and can be made dramatically faster by caching the decompositions in order to reduce the number of tests to perform).
I've not programmed the way to do that, but some people may find an efficient implemenhtation and new ideas to make this small problem much faster, without requiring much memory (note that sorting in this problem is not dramatically complex because you only sort rather small lists of about one thousands item and we know we can do that quite efficiently in O(n log n) time where n is about 1000, i.e. roughtly 10bits only products; but for actual modern use of RSA, working on 1024bit products, this is not possible in reasonnable time and with enough memory resources : this would not even be possible if we could use use all existing computers on Earth, because these huge numbers are many orders of magnitude above the total number of atoms in our observable universe and could run them all at 10 Gigahertz.
This makes this problem very interesting in fact to explore in order to find how we can optimie its resolution to get dramatically faster responses (with less loops and modest memory usage to store and cache the intermediate results).
The day 2 also explores such known computationally costly algorithms (here it is a well known problem of regular expressions and the difficulty to locate arbitrary long subtrings in a very large string (could be a entire database), without having to reparse the whole with brute force exploring M*N possibilities where M and N and the length of the substring and the longer string to scan: as these problems will have their computation difficulty growing each time, you won't be able to use basic tools like Excel to sum a list, you'll need to program and think really about the algorithms you use and the best data representation.
These problems are wellknown classes of algorithms where there's intensive research, and most of them are based on arithmetic (and you need to know many theorems on them): arithmetics on integers (or rationals) is one of the most complex part of mathematics and whose results interest a lot the whole computing industry, becaues these problems could reveal exploits that could be harvested to break security or privacy, and can now have very large impact on public freedoms and politics when all our economy now depends so much on computers and automated decisions.
Okay, maybe I'm missing something. Since Lua is new to me and I
started a day late, I used C for the day one problem, to get the
mechanics of the website worked out. Like Philippe, I used Excel
for the first star, but then I saw the issue with that approach
for the second star and switched to C. I used a trivial list to
store all "frequencies" as they occurred, and the addFrequency()
function returned an indication that the new value was already
there. My data stream was 959 items and the program required 38
seconds on a Macbook Pro. Since I don't even know what cyclic
arithmetic is, maybe I'm missing something really important, and
bonus points to anyone who'll enlighten me. For instance, are
performance issues like runtime and memory consumption counted?
Sadly, now I'm a) hooked and b) committed to the "different
language every day" idea. I'll try to do days 2 and 3 tomorrow.
On 12/2/18 1:11 PM, Philippe Verdy
wrote:
interesting. The first star on day one is
elementary to solve just with a basic very Excel sheet, but the
second star is much more difficult as it involves cyclic
aruthmetic (you can solve it by brute force but it rapidly quite
computing intensive as each test requires decomposing 1016
integers into primes in order to test which position to look at
(otherwise the search loops are unbounded): you need some
knowledge of cyclic arithmetic to solve it with an efficient
algorithm which is ensured to find a solution in a bounded and
in fact quite small time.
Your current test code in Haskell uses the brute force
approach to repeat searches in more and more repeated cycles,
but even if you find a repeated frequency with N cycles of the
list, you could still find a lower frequency located below in
the input list. There's a more efficient solution by sorting
the frequencies produced by the first cycle. But then you need
to apply the algorithm to compute a lowest common multiplier
and see if it's divisible by a position in the sorted list.
Finally you have to aplky a second sort... Technically you can
still do that within Excel by several operations involding
copying computed values from one column to another (without
their formula) and then apply a custom sort. over a group of
columns. All this could as well be done in Lua of course
(instead of Excel, you need Lua tables)
This is interesting. An interesting twist
might be to use a different language each day.
Advent of Code [1] is a coding
problem advent calendar: every day from December 1 to
December 25, they publish two code problems that can
be solved in any language.
Like last year, I am doing it in Lua (I may solve
the problem in another language as well some days, but
I intend to do all of them in Lua at least). I publish
my solutions [2] on GitHub.
I am not interested in leaderboards (based on
resolution time since publication), first because for
Europeans the only way to be competitive would be to
wake up very early or stay up very late, but also
because I only do this because it is somehow fun to
me. Sometimes I may not have the time to play at all
on a given day and catch up later in the week.
Anyway, I thought it might interest some people on
this list.
[1] https://adventofcode.com
[2] https://github.com/catwell/adventofcode/tree/master/2018

Pierre Chapuis

Daryl Lee
All our discontents about what we want appeared to
me to spring from the want of thankfulness for what we
have.  Daniel Defoe

