[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Advent of Code
- From: Philippe Verdy <verdy_p@...>
- Date: Sun, 2 Dec 2018 21:11:32 +0100
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  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  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. https://adventofcode.com https://github.com/catwell/adventofcode/tree/master/2018-- Pierre Chapuis