primordial-soup's recent activity

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

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

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

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

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

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

    Part 2, Python(-ish)
    template = ls[0]
    rules = ls[2:] > fe(X.split(" -> ") | (λ x: (tuple(x[0]), x[1]))) | 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[0], insert)), pairs.index(pair)] = 1
        M[pairs.index((insert, pair[1])), 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[0] 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[0]
    rules = ls[2:] > fe(X.split(' -> ') | (lambda x: (tuple(x[0]), x[1]))) | 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[0], insert)), pairs.index(pair)] = 1
        M[pairs.index((insert, pair[1])), 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.

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

    primordial-soup
    (edited )
    Link
    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 votes
  4. Comment on Is there an open-source version of the Garmin Connect app for Android? in ~tech

    primordial-soup
    Link
    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 )
    Link
    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...

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

    primordial-soup
    (edited )
    Link Parent
    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[0]=='f']+'+-'[r[0]>'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[0]=='f']+'+-'[r[0]>'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[0]=='f']+'+-'[r[0]>'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.

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

    primordial-soup
    (edited )
    Link Parent
    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!

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

    primordial-soup
    Link
    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
    Link
    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.

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

    primordial-soup
    Link Parent
    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.

    Some relevant links:

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

    primordial-soup
    (edited )
    Link Parent
    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.

    5 votes
  12. Comment on <deleted topic> in ~tech

    primordial-soup
    Link Parent
    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 :)

    3 votes
  13. Comment on <deleted topic> in ~tech

    primordial-soup
    Link Parent
    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 :)
    4 votes
  14. Comment on <deleted topic> in ~tech

    primordial-soup
    Link
    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.

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

    primordial-soup
    Link
    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

    5 votes
  16. Comment on Fear of depths in ~games

    primordial-soup
    (edited )
    Link Parent
    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

  18. Comment on Synthwave in ~music

    primordial-soup
    (edited )
    Link
    If you are looking for a Spotify playlist, I typically listen from this one (644 hrs). This one (17 hrs) is also good, featuring more obscure artists and updating more frequently. I've also been...

    If you are looking for a Spotify playlist, I typically listen from this one (644 hrs).

    This one (17 hrs) is also good, featuring more obscure artists and updating more frequently.

    I've also been enjoying Jam2go recently. I'm not sure his work is synthwave, but it's certainly a similar genre.

    2 votes