|
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
|
