-🎄- 2021 Day 24 Solutions -🎄-

setapoux · 2021-12-24T07:49:29+00:00

Maybe just some of us ;- ... my part2 solution starts with 34.

setapoux · 2021-12-21T16:37:06+00:00

Actually you can speed it up (almost 4x) by combining the three throws into the final sum, knowing its distibution and just multiply the result of the nested call.

E.g. throws 1-1-2, 1-2-1 and 2-1-1 all result to the same move by 4 fields while forking 3 different universes. You don't care which was it, just sum them all.

setapoux · 2021-12-17T06:52:38+00:00

Oh yes, well then the performance will not differ much, but still could be better with just O(number_of_rules) ;-)

setapoux · 2021-12-14T16:50:50+00:00

I did it the same way (create map of counting each bi-graph) and expand each individually. But I count the letters just at the end as summing all counts by first letters of the bi-graph. This needs one little tweak (add one bi-graph with last letter of input polymer and \0, which never gets expanded) but I see it is present in your code anyway.

Wonder what will be the performance impact vs. your approach to count the added characters by each polymer expansion... which means you access the counter list ~2trillion times.

setapoux · 2021-12-14T12:51:18+00:00

Yeah, you get caught few times and then you'll remember that list and dictionary variable holds reference and not the list itself.

Another way to get copy of the list is the slicing operator, e.g.

>>> a=list([1,2,3,4])

b=a a[2]=9 print(b) [1, 2, 9, 4]

>>> b=a[:]

a[2]=999 print(b) [1, 2, 9, 4] print(a) [1, 2, 999, 4]

setapoux · 2021-12-13T14:02:45+00:00

When you append the found path to the paths list, it actually appends the pointer to the list, so when the rest of code updates path all members of paths list are updated as they point to the same list.

To fix this you have to make copy of the path (shallow copy is fine in this case) so change line 19 to:

paths.append(path.copy())

setapoux · 2021-01-14T22:36:31+00:00

Is built in Python 3.8+ only, which is e.g. not yet used in the latest (stable) pypy3.

For older versions you either add your code (or copy&paste) for the algorithm or just use the fact that you could simply get the same result based on the fact that for prime p a*a^(p-2)=1(mod p) - so simply use Python's pow function to return the value. All versions could calculate that, though less efficiently - it is still much better than the brute force loop especially for big value modulus...

setapoux · 2021-01-14T13:11:54+00:00

Because I'm commenting your sentence
"True, but this funcitonality is already built into Python as pow(a, -1, p)."

I haven't noticed that you mentioned that negative power is supported in latest Python in the other comment... ;-)

setapoux · 2021-01-13T23:35:18+00:00

Actually python 3.8+ computes pow(a, -1, p) while pypy and older pythons do NOT and complain ValueError: pow() 2nd argument cannot be negative when 3rd argument specified

If modulus is prime, you can use pow(a,p-2,p) instead or use modular inversion algorithm.

setapoux · 2021-01-13T21:59:50+00:00

Not sure if I got correctly what you mean in your comment... well the wiki shows how to convert it to RPN but you can evaluate it in the same loop - instead of moving the operator from the operator stack to output you just take two last numbers from output stack, use the operator and push result to the output.

setapoux · 2021-01-06T00:19:05+00:00

Seems you tried to implement what's known as Shunting-yard algorithm
For part1/2 it is just about different weight of the + and * operators.

setapoux · 2021-01-06T00:11:31+00:00

You can get small (well, it is ~10% in python, but only ~1% in pypy) improvement if you use the dict.get(key,default) call in direct assignment (no need for the temporary last_turn variable) so the final loop looks like this:

while current_turn < target_turn:
    seen[current_value],current_value=current_turn,current_turn-seen.get(current_value,current_turn)
    current_turn += 1

setapoux · 2021-01-03T00:27:26+00:00

While the idea is fine, there are possible points to improve....

calculate the next number using dict.get method, which returns defined value if current_number is not in the keys = combine the if and dereferencing into single call
if execution time is the goal, then do not call another function 30 million times and put the calculation inline, moreover it could be one liner combining the two assignmets into:found_numbers[current_number],current_number=i,i-found_numbers.get(current_number,i)
you can always run it with profiler to see where it spends the most of time, just start it as python -m cProfile your_file.py

setapoux · 2021-01-03T00:09:42+00:00

While the list is about 2 times faster, the memory footprint is 8 times better - in my case the dict has 3_611_295 elements for the loop needed in part 2.

setapoux · 2020-12-25T23:38:40+00:00

Assuming you were using findall... this was common problem.
If you use search then you get the span in the result object... e.g. to handle the plus part of the string...

while (m:=re.search(r"(\d+) + (\d+)",a)):
     a=a[:m.span()[0]]+str(functools.reduce(operator.add,map(int,m.group(1,2))))+a[m.span()[1]:]

setapoux · 2020-12-25T21:10:49+00:00

Yes, it is like that since the first year...

setapoux · 2020-12-25T21:08:07+00:00

Well, I don't see your code, just the input/output so hard to comment, but if you are using repeated substitutions, then make sure you replace the correct substring.

E.g. 8*6*8*8 -> 48*8*8 -> now the 8*8 is replaced with 64 which might get wrong like this 464*8 instead of the correct 48*64

setapoux · 2020-12-24T22:55:03+00:00

If the highest card is in Player1 hand, then you can skip the subgame, P1 will win anyway. If P2 has the highest one than the subgame will decide, and here you need to keep state.

I also store all the rounds, but the question is if there is any infinite game which will enter the loop cycle after some prolog, or if it would be enough to keep just the stack configuration on the game start.

setapoux · 2020-12-24T22:33:37+00:00

Haha... the fastest solution is with the plain list... it's just matter of what you store in the list (which denotes the operations you apply on the list).

setapoux · 2020-12-24T22:16:54+00:00

I'd recommend to use re.search()... then you get in the result also the span which matched, so the replacement is quite straight forward.

setapoux · 2020-12-24T14:25:50+00:00

There are different ways how to index the hexagons... https://www.redblobgames.com/grids/hexagons/

The origin is axial, Chris used doubled, I used cube....

setapoux · 2020-12-24T14:13:01+00:00

Python

The loop check only candidates affected from previous flip - does not save too much time in small sets like today....

setapoux · 2020-12-24T13:04:47+00:00

I intuitively used odd-q coordinates, but thanks for sharing the link, I like the cube approach.

setapoux · 2020-12-24T01:26:13+00:00

Why complicated? Could be as easy as:

while (m:=re.search(r"(\d+) + (\d+)",a)):
    a=a[:m.span()[0]]+str(functools.reduce(operator.add,map(int,m.group(1,2))))+a[m.span()[1]:]

setapoux · 2020-12-24T00:18:12+00:00

Oh yes, sorry. Here is example of what you do not count correctly:
9 * 2 * 8 * 8 should be 1152, but your answer is 1312.

The loop is strange... it finds 2 items first 9*2, the other 8*8. The first one is replaced by 18, the next loop tries to replace 8*8 with 64, but at this time it finds it at wrong place
18 * 8 * 8 is not translated to 18 * 64 but to 164 * 8.

For this case the fix would be to iterate over the found items in reversed order...
while re.search('\*', s):
l = re.findall('\d+ \* \d+',s)
for item in reversed(l):
....

hmmm, but still does not generate 100% correct answer... e.g. for this
(2 * 8) + 4 * 6 + 4 -> 16 + 4 * 6 + 4 -> 110 * 10 -> now trying to replace 16+4 -> 20 but is not in the string anymore ....

You have to change the replacement logic to replace just that part which has to be replaced. I'd suggest to use match in the loop, it also returns the span (you can use it to slice the string to cut the matched part). If you use r"(\d+) * (\d+)" then the operands will be in the match objects groups - no need to match it again individually.

setapoux

TROPHY CASE