# primordial-soup's recent activity

1. ## Comment on Tildes Game Giveaway Thread: Holiday 2021 in ~games

primordial-soup
I'd like Absolute Drift please. Thanks for putting this together!

I'd like Absolute Drift please. Thanks for putting this together!

2. ## Comment on Day 14: Extended Polymerization in ~comp.advent_of_code

primordial-soup
Like day 6, this can be done in O(log(n)) via exponentiation by squaring: Part 2, Python(-ish) template = ls rules = ls[2:] > fe(X.split(" -> ") | (λ x: (tuple(x), x))) | set chars =...

Like day 6, this can be done in O(log(n)) via exponentiation by squaring:

Part 2, Python(-ish)
``````template = ls
rules = ls[2:] > fe(X.split(" -> ") | (λ x: (tuple(x), x))) | set
chars = set(template) | set(collapse(rules))
pairs = list(product(chars, repeat=2))
state = np.zeros((len(pairs), 1), dtype=object)
for pair in pairwise(template):
state[pairs.index(pair)] += 1
M = np.zeros((len(pairs), len(pairs)), dtype=object)
for pair, insert in rules:
M[pairs.index((pair, insert)), pairs.index(pair)] = 1
M[pairs.index((insert, pair)), pairs.index(pair)] = 1
# use (matrix) exponentiation by squaring to get O(log(n))
state = np.linalg.matrix_power(M, 40) @ state
# factor of 2 to avoid double-counting
# ceil to correct for template and template[-1] off-by-one's
counts = [ceil(sum(count * pair.count(c)
for pair, count in zip(pairs, state[:, 0]))
/ 2)
for c in chars]
max(counts) - min(counts)
``````
Python (which the above is transpiled to)
``````#!/usr/bin/env python3
from itertools import pairwise
from itertools import product
from math import ceil
from more_itertools import collapse
from pipetools import X
from pipetools import foreach
import sys
from pyp import pypprint
fe = foreach
import numpy as np
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
template = ls
rules = ls[2:] > fe(X.split(' -> ') | (lambda x: (tuple(x), x))) | set
chars = set(template) | set(collapse(rules))
pairs = list(product(chars, repeat=2))
state = np.zeros((len(pairs), 1), dtype=object)
for pair in pairwise(template):
state[pairs.index(pair)] += 1
M = np.zeros((len(pairs), len(pairs)), dtype=object)
for (pair, insert) in rules:
M[pairs.index((pair, insert)), pairs.index(pair)] = 1
M[pairs.index((insert, pair)), pairs.index(pair)] = 1
state = np.linalg.matrix_power(M, 40) @ state
counts = [ceil(sum((count * pair.count(c) for (pair, count) in zip(pairs, state[:, 0]))) / 2) for c in chars]
output = max(counts) - min(counts)
if output is not None:
pypprint(output)
``````

In practice though, with n = 40 this is slower than the O(n) algorithm.

3. ## Comment on Day 12: Passage Pathing in ~comp.advent_of_code

primordial-soup
(edited )
Part 1, Python(-ish) edges = ls > fe(X.split("-") | frozenset) | set # define a recursive λ via variables rather than via Y, which seems to be necessary in # order to get speedup from @cache...
Part 1, Python(-ish)
``````edges = ls > fe(X.split("-") | frozenset) | set
# define a recursive λ via variables rather than via Y, which seems to be necessary in
# order to get speedup from @cache
count_paths = None
count_paths = cache(λ start, used_smalls=frozenset():
1 if start == "end" else
sum(count_paths(choice,
used_smalls | {start} if start.islower() else used_smalls)
for edge in edges if start in edge and
(choice := one(edge - {start})) not in used_smalls))
count_paths("start")
``````
Part 2, Python(-ish)
``````edges = ls > fe(X.split("-") | frozenset) | set
# define a recursive λ via variables rather than via Y, which seems to be necessary in
# order to get speedup from @cache
count_paths = None
count_paths = cache(λ start, used_smalls=frozenset(), double_used=None:
1 if start == "end" else
sum(count_paths(choice,
used_smalls | {start} if start.islower() else used_smalls,
choice if choice in used_smalls else double_used)
for edge in edges if start in edge and
((choice := one(edge - {start})) not in used_smalls or
(double_used is None and choice != "start"))))
count_paths("start")
``````

Caching gives a big speedup if you do a recursive graph search like I did. With caching, part 2 only takes ~ 105 ms on my laptop (or 210 ms if you include interpreter startup time).

4. ## Comment on Is there an open-source version of the Garmin Connect app for Android? in ~tech

primordial-soup
https://www.goldencheetah.org/ (though not a mobile app) might do this. It's aimed for cycling, but perhaps it can pull GPX from a Garmin watch too.

https://www.goldencheetah.org/ (though not a mobile app) might do this. It's aimed for cycling, but perhaps it can pull GPX from a Garmin watch too.

1 vote
5. ## Comment on Day 6: Lanternfish in ~comp.advent_of_code

primordial-soup
(edited )
I managed to find the trick to get linear runtime, but this morning my housemate realized it can be done in O(log(n)): Python(-ish) f = ls > p | one | X.split(",") | fe(int) | list # there are...

I managed to find the trick to get linear runtime, but this morning my housemate realized it can be done in O(log(n)):

Python(-ish)
``````f = ls > p | one | X.split(",") | fe(int) | list
# there are only 9 possible states that a fish can be in
s = np.c_[[f.count(n) for n in range(9)]]
# use (matrix) exponentiation by squaring to get O(log(n))
M = np.roll(np.diag(np.ones(9, dtype=object)), -1, axis=0)
M[6, 0] = 1
np.sum(np.linalg.matrix_power(M, 256) @ s)
``````

(Ignore the first line; it's just reading input from stdin. My code above actually gets transpiled to

Python
``````from more_itertools import one
from pipetools import X
from pipetools import foreach
from pipetools import pipe
import sys
from pyp import pypprint
p = pipe
fe = foreach
import numpy as np
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
f = (ls > ((((p | one) | X.split(',')) | fe(int)) | list))
s = np.c_[[f.count(n) for n in range(9)]]
M = np.roll(np.diag(np.ones(9, dtype=object)), (- 1), axis=0)
M[(6, 0)] = 1
output = np.sum((np.linalg.matrix_power(M, 256) @ s))
if (output is not None):
pypprint(output)
``````
before Python sees it.)

By my tests this is slower than my linear-time version for `n = 256`, but it starts beating my linear-time version around `n = 2_000_000` (~ 5 s runtime).

There is then also a speedup that can be had by diagonalizing the transition matrix when taking the power of it, but I'm not sure how to do this (fast) without introducing numerical error:

Python(-ish)
``````f = ls > p | one | X.split(",") | fe(int) | list
# there are only 9 possible states that a fish can be in
s = np.c_[[f.count(n) for n in range(9)]]
# use (matrix) exponentiation by squaring to get O(log(n))
M = np.roll(np.diag(np.ones(9, dtype=object)), -1, axis=0)
M[6, 0] = 1
Ma = M.astype("float64")
d = 0
while True:
d += 1
t0 = time.perf_counter()
exact = np.sum(np.linalg.matrix_power(M, d) @ s)
t1 = time.perf_counter()
D, P = np.linalg.eig(Ma)
approx = np.sum(np.real(P @ np.diag(D ** d) @ np.linalg.inv(P) @ s))
t2 = time.perf_counter()
if round(approx) != exact:
print(f"{d=}", f"diff={exact - approx}")
print(f"speedup={(t1 - t0) / (t2 - t1):.2f}x")
break
``````

For my input and laptop this approximation works up to `n = 260`, but rounds the wrong way at 261. The speedup for `n = 261` is about 2.3x.

I tried using sympy do this exactly but it was much slower than not diagonalizing and just using Python's `int`. Let me know if any of you know of a way to get the speedup without losing precision...

6. ## Comment on Day 2: Dive! in ~comp.advent_of_code

primordial-soup
(edited )
I managed to golf your code down a bit more: Part 1 (chars -= 31) x=y=0 for l in open(0): r,M=l.split();m=int(M);exec('yx'[r=='f']+'+-'[r>'f']+'=m') print(x*y) Part 2 (chars -= 26) x=y=a=0...

I managed to golf your code down a bit more:

Part 1 (`chars -= 31`)
``````x=y=0
for l in open(0):
r,M=l.split();m=int(M);exec('yx'[r=='f']+'+-'[r>'f']+'=m')
print(x*y)
``````
Part 2 (`chars -= 26`)
``````x=y=a=0
for l in open(0):
r,M=l.split();m=int(M);exec(('a','y+=a*m;x')[r=='f']+'+-'[r>'f']+"=m")
print(x*y)
``````

Using booleans as indices to replace conditionals, `exec`, and seeing if `==` can be changed to `>`/`<` seem like they'd be pretty widely applicable tricks for one's Python golfing tool belt.

7. ## Comment on Day 2: Dive! in ~comp.advent_of_code

primordial-soup
(edited )
Welcome to Tildes! For golfing, you could prune a few characters by placing the input in a file with a short name and hardcoding it: open("i") in place of sys.stdin. Edit: Even better, I just...

Welcome to Tildes!

For golfing, you could prune a few characters by placing the input in a file with a short name and hardcoding it: `open("i")` in place of `sys.stdin`.

Edit: Even better, I just learned you can use `open(0)` to read stdin!

8. ## Comment on I need help with a story that involves math in ~science

primordial-soup
All of these ideas are great. Another one, which has the advantage of being pretty easy to explain, might be something like: Excel incorrectly assumes that the year 1900 is a leap year.

All of these ideas are great. Another one, which has the advantage of being pretty easy to explain, might be something like: Excel incorrectly assumes that the year 1900 is a leap year.

1 vote
9. ## Comment on What do I need to know switching phones from Blackberry 10 to Android? in ~tech

primordial-soup
As other folks have mentioned already, F-Droid is really excellent. Depending on how much you want to de-Google, you might consider installing a version of Android that isn't the one from your...

As other folks have mentioned already, F-Droid is really excellent.

Depending on how much you want to de-Google, you might consider installing a version of Android that isn't the one from your phone's manufacturer. Personally I've found a good balance between FLOSS and usability using the microG Project's LineageOS builds. I was using LineageOS with Open GApps1 for a few years, but I made the switch to LineageOS with microG last year and it's been smooth sailing. For what it's worth, you might also want to look into GrapheneOS and CalyxOS (if they support your device).

If it supports your device, Magisk is a popular method for rooting. See if there's a guide for your device on XDA-Developers.

And some app recommendations:

• AdAway for system-level adblocking. Requires root. uBlock Origin in Firefox is great, but having no ads in every app is even better.
• Aurora for installing Google Play apps without a Google acct.
• OsmAnd+ for maps and navigation. To be honest, there isn't a FOSS navigation app with UI that parallels the Google Maps app, but this is the best I know of.
• FairEmail
• DAVx5 for syncing calendars/contacts
• QKSMS

1: Misleading name. Open GApps is just a way to install the closed-source Google Apps on LineageOS/other distros.

10. ## Comment on The great Wikipedia titty scandal in ~tech

primordial-soup
I think you are right. From what I can tell, he also contributed some good redirects, so nuking them all would have taken out both good and bad ones. I'm not sure where to find the ratio of good...

I think you are right. From what I can tell, he also contributed some good redirects, so nuking them all would have taken out both good and bad ones. I'm not sure where to find the ratio of good to bad though.

11. ## Comment on Email: How about doing it right? in ~tech

primordial-soup
(edited )
I have the same problem with connected addresses. If a breach links my identity to one of my @randomword.com addresses, all the others get linked to my identity as well. I don't think that there...

I have the same problem with connected addresses. If a breach links my identity to one of my `@randomword.com` addresses, all the others get linked to my identity as well. I don't think that there is a way to avoid this without switching to a domain that is shared with others. (SimpleLogin and AnonAddy are both FLOSS solutions for this, with paid hosting available—a business model that I'm particularly fond of.) However, switching to a shared domain would make me dependent on a particular host, and I quite like that I am able to change mail hosts just by changing some DNS records.

Perhaps a decent solution is to just make the `@randomword.com` addresses less conspicuous, e.g. by using a username generator for them.

12. ## Comment on <deleted topic> in ~tech

primordial-soup
Yep! However if your database is in an old format then XC will upgrade it [src]. But the upgrade is to the same format that KeePass uses (KBDX 3.1/KBDX 4), so it will still be compatible with...

Yep! However if your database is in an old format then XC will upgrade it [src]. But the upgrade is to the same format that KeePass uses (KBDX 3.1/KBDX 4), so it will still be compatible with KeePass.

And you can always make a backup to be extra safe :)

13. ## Comment on <deleted topic> in ~tech

primordial-soup
Yeah, I switched from KeePass to KeePassXC when I switched from Windows to Linux for just that reason. However XC does have some other features that might be worth switching for: browser extension...

Yeah, I switched from KeePass to KeePassXC when I switched from Windows to Linux for just that reason. However XC does have some other features that might be worth switching for:

• browser extension for autofill (more convenient than auto-type, IMO)
• TOTP (i.e. 2 factor authentication equivalent to Google Authenticator, etc.) from a password database that you can back up
• easily check for duplicate passwords and passwords compromised by data breaches
• easily download site icons to make your DB prettier :)
14. ## Comment on <deleted topic> in ~tech

primordial-soup
While I don't know the answer to your question, I would highly recommend using KeePassXC for it's browser integration if nothing else. It's a super easy switch to make since KeePassXC uses the...

While I don't know the answer to your question, I would highly recommend using KeePassXC for it's browser integration if nothing else. It's a super easy switch to make since KeePassXC uses the same database format as KeePass.

15. ## Comment on You want to see my data? I thought we were friends in ~science

primordial-soup
Hah, I just came to ~science with the intent of posting this. When I first clicked on this link on HN I was expecting an article about data privacy, but instead I was pleasantly surprised. While...

Hah, I just came to ~science with the intent of posting this.

When I first clicked on this link on HN I was expecting an article about data privacy, but instead I was pleasantly surprised. While the title is enticing I do think that it can be misleading. Perhaps a title like "Where academia works against science" would be clearer?

Discussion on HN

16. ## Comment on Fear of depths in ~games

primordial-soup
(edited )
I'm a big fan of Jacob Geller's content as well. You might enjoy a couple other channels: Leadhead - Video essays analyzing video games. I highly recommend their content if you like Jacob Geller....

I'm a big fan of Jacob Geller's content as well. You might enjoy a couple other channels:

You might also check out this post. I haven't had the chance to check out all of its mentioned channels myself, but I suspect that the post is a treasure trove.

1 vote
17. ## Comment on To make an atom-sized machine, you need a quantum mechanic in ~science

primordial-soup
The pun reminds me of the covers of two textbooks: https://www.uscibooks.com/taylor_errorcov.jpg https://d.gr-assets.com/books/1386912834l/245483.jpg

The pun reminds me of the covers of two textbooks:

1 vote
18. ## Comment on Synthwave in ~music

primordial-soup
(edited )