"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 10-bit

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 10-bits only products; but for

actual modern use of RSA, working on 1024-bit 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.

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)

*Post by Personal*This is interesting. An interesting twist might be to use a different language each day.

--

Daryl Lee

Sent from my iPhone

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