primordialsoup's recent activity

Comment on Day 11: Monkey in the Middle in ~comp

Comment on Day 10: CathodeRay Tube in ~comp
primordialsoup ah! i assumed it was done automatically. thanks for doing this :)ah! i assumed it was done automatically. thanks for doing this :)

Comment on Day 10: CathodeRay Tube in ~comp
primordialsoup the problem title appears to be missing from the tildes title today.the problem title appears to be missing from the tildes title today.

Comment on Day 10: CathodeRay Tube in ~comp
primordialsoup (edited )LinkPart 1, in Pythonish c, x = 0, 1 scores = [] def cycle(): global c c += 1 scores.append(c * x) for l in ls: cycle() if l != "noop": cycle() x += int(l.split()[1]) sum(scores[c] for c in (20 + 40...Part 1, in Pythonish
c, x = 0, 1 scores = [] def cycle(): global c c += 1 scores.append(c * x) for l in ls: cycle() if l != "noop": cycle() x += int(l.split()[1]) sum(scores[c] for c in (20 + 40 * i  1 for i in range(6)))
Python code generated from the above
import sys from pyp import pypprint lines = [x.rstrip('\n') for x in sys.stdin] ls = lines (c, x) = (0, 1) scores = [] def cycle(): global c c += 1 scores.append(c * x) for l in ls: cycle() if l != 'noop': cycle() x += int(l.split()[1]) output = sum((scores[c] for c in (20 + 40 * i  1 for i in range(6)))) if output is not None: pypprint(output)
Part 2, in Pythonish
c, x = 0, 1 screen = np.full((6, 40), False) def cycle(): global c c += 1 i, j = np.unravel_index(c  1, screen.shape) screen[i, j] = x  1 <= j <= x + 1 for l in ls: cycle() if l != "noop": cycle() x += int(l.split()[1]) for i in range(screen.shape[0]): for j in range(screen.shape[1]): print(" #"[screen[i, j]], end="") print()
Python code generated from the above
import sys import numpy as np lines = [x.rstrip('\n') for x in sys.stdin] ls = lines (c, x) = (0, 1) screen = np.full((6, 40), False) def cycle(): global c c += 1 (i, j) = np.unravel_index(c  1, screen.shape) screen[i, j] = x  1 <= j <= x + 1 for l in ls: cycle() if l != 'noop': cycle() x += int(l.split()[1]) for i in range(screen.shape[0]): for j in range(screen.shape[1]): print(' #'[screen[i, j]], end='') print()

Comment on Day 6: Tuning Trouble in ~comp
primordialsoup thanks for linking to this! @Gyrfalcon—you won't find it searching "Pythonish" online, that's just a name i made up for the purpose of posting AoC solutions to Tildes :)thanks for linking to this!
@Gyrfalcon—you won't find it searching "Pythonish" online, that's just a name i made up for the purpose of posting AoC solutions to Tildes :)

Comment on Day 9: Rope Bridge in ~comp
primordialsoup (edited )LinkPart 1, in Pythonish step = {"R": (1, 0), "L": (1, 0), "D": (0, 1), "U": (0, 1)} head = np.full(2, 0, dtype=object) tail = np.full(2, 0, dtype=object) visited = {tuple(tail)} for l in ls: inst,...Part 1, in Pythonish
step = {"R": (1, 0), "L": (1, 0), "D": (0, 1), "U": (0, 1)} head = np.full(2, 0, dtype=object) tail = np.full(2, 0, dtype=object) visited = {tuple(tail)} for l in ls: inst, n_str = l.split() for _ in range(int(n_str)): head += step[inst] if any(abs(diff := head  tail) > 1): tail += np.sign(diff) visited.add(tuple(tail)) len(visited)
Python code generated from the above
import sys from pyp import pypprint import numpy as np lines = [x.rstrip('\n') for x in sys.stdin] ls = lines step = {'R': (1, 0), 'L': (1, 0), 'D': (0, 1), 'U': (0, 1)} head = np.full(2, 0, dtype=object) tail = np.full(2, 0, dtype=object) visited = {tuple(tail)} for l in ls: (inst, n_str) = l.split() for _ in range(int(n_str)): head += step[inst] if any(abs((diff := (head  tail))) > 1): tail += np.sign(diff) visited.add(tuple(tail)) output = len(visited) if output is not None: pypprint(output)
Part 2, in Pythonish
step = {"R": (1, 0), "L": (1, 0), "D": (0, 1), "U": (0, 1)} knots = np.full((10, 2), 0, dtype=object) visited = {tuple(knots[1])} for l in ls: inst, n_str = l.split() for _ in range(int(n_str)): knots[0] += step[inst] for i in range(1, len(knots)): if any(abs(diff := knots[i  1]  knots[i]) > 1): knots[i] += np.sign(diff) visited.add(tuple(knots[1])) len(visited)
Python code generated from the above
import sys from pyp import pypprint import numpy as np lines = [x.rstrip('\n') for x in sys.stdin] ls = lines step = {'R': (1, 0), 'L': (1, 0), 'D': (0, 1), 'U': (0, 1)} knots = np.full((10, 2), 0, dtype=object) visited = {tuple(knots[1])} for l in ls: (inst, n_str) = l.split() for _ in range(int(n_str)): knots[0] += step[inst] for i in range(1, len(knots)): if any(abs((diff := (knots[i  1]  knots[i]))) > 1): knots[i] += np.sign(diff) visited.add(tuple(knots[1])) output = len(visited) if output is not None: pypprint(output)

Comment on Day 6: Tuning Trouble in ~comp
primordialsoup (edited )LinkPart 1, in Pythonish (l > p  (windowed, X, 4)  (locate, X, all_unique)  first) + 4 Python code generated from the above from more_itertools import all_unique from more_itertools import first...Part 1, in Pythonish
(l > p  (windowed, X, 4)  (locate, X, all_unique)  first) + 4
Python code generated from the above
from more_itertools import all_unique from more_itertools import first from more_itertools import locate from more_itertools import windowed from pipetools import X from pipetools import pipe import sys p = pipe for l in sys.stdin: l = l.rstrip('\n') output = (l > p  (windowed, X, 4)  (locate, X, all_unique)  first) + 4 if output is not None: print(output)
sed 's/4/14/'
for Part 2. 
Comment on Day 5: Supply Stacks in ~comp
primordialsoup day 13 last year had a string answerday 13 last year had a string answer

Comment on Day 5: Supply Stacks in ~comp
primordialsoup (edited )LinkPart 1, in Pythonish (*ls_top, ls_top_last), ls_btm = ls > p  (split_at, X, ~(X == "")) stacks = (ls_top > fe(X.ljust(len(ls_top_last) + 1))  fe(p  (chunked, X, 4)  fe("".join)) ...Part 1, in Pythonish
(*ls_top, ls_top_last), ls_btm = ls > p  (split_at, X, ~(X == "")) stacks = (ls_top > fe(X.ljust(len(ls_top_last) + 1))  fe(p  (chunked, X, 4)  fe("".join))  as_args(zip)  fe(fe(X[1])  where(X != " ")  always_reversible  list)  tuple) for n, i, f in (ls_btm > fe((re.search, r"move (\d+) from (\d+) to (\d+)")  X.groups()  fe(int))): for _ in range(n): stacks[f  1].append(stacks[i  1].pop()) stacks > fe(X[1])  "".join
Python code generated from the above
from more_itertools import always_reversible from more_itertools import chunked from more_itertools import split_at from pipetools import X from pipetools import as_args from pipetools import foreach from pipetools import pipe from pipetools import where import re import sys from pyp import pypprint p = pipe fe = foreach lines = [x.rstrip('\n') for x in sys.stdin] ls = lines ((*ls_top, ls_top_last), ls_btm) = ls > p  (split_at, X, ~(X == '')) stacks = ls_top > fe(X.ljust(len(ls_top_last) + 1))  fe(p  (chunked, X, 4)  fe(''.join))  as_args(zip)  fe(fe(X[1])  where(X != ' ')  always_reversible  list)  tuple for (n, i, f) in ls_btm > fe((re.search, 'move (\\d+) from (\\d+) to (\\d+)')  X.groups()  fe(int)): for _ in range(n): stacks[f  1].append(stacks[i  1].pop()) output = stacks > fe(X[1])  ''.join if output is not None: pypprint(output)
Part 2, in Pythonish
(*ls_top, ls_top_last), ls_btm = ls > p  (split_at, X, ~(X == "")) stacks = (ls_top > fe(X.ljust(len(ls_top_last) + 1))  fe(p  (chunked, X, 4)  fe("".join))  as_args(zip)  fe(fe(X[1])  where(X != " ")  always_reversible  list)  list) for n, i, f in (ls_btm > fe((re.search, r"move (\d+) from (\d+) to (\d+)")  X.groups()  fe(int))): stacks[f  1] += stacks[i  1][n:] stacks[i  1] = stacks[i  1][:n] stacks > fe(X[1])  "".join
Python code generated from the above
from more_itertools import always_reversible from more_itertools import chunked from more_itertools import split_at from pipetools import X from pipetools import as_args from pipetools import foreach from pipetools import pipe from pipetools import where import re import sys from pyp import pypprint p = pipe fe = foreach lines = [x.rstrip('\n') for x in sys.stdin] ls = lines ((*ls_top, ls_top_last), ls_btm) = ls > p  (split_at, X, ~(X == '')) stacks = ls_top > fe(X.ljust(len(ls_top_last) + 1))  fe(p  (chunked, X, 4)  fe(''.join))  as_args(zip)  fe(fe(X[1])  where(X != ' ')  always_reversible  list)  list for (n, i, f) in ls_btm > fe((re.search, 'move (\\d+) from (\\d+) to (\\d+)')  X.groups()  fe(int)): stacks[f  1] += stacks[i  1][n:] stacks[i  1] = stacks[i  1][:n] output = stacks > fe(X[1])  ''.join if output is not None: pypprint(output)
i have also been challenging myself to solve each puzzle in a single expression. here are my singleexpression solutions for today:
Part 1, in Pythonish
(ls > p  (split_at, X, ~(X == ""))  as_args(λ t, b: (t > p  always_reversible  (λ ls: (λ top_width: ls > fe(X.ljust(top_width))) (len(first(ls)) + 1))  fe(p  (chunked, X, 4)  fe("".join))  as_args(zip)  fe(fe(X[1])  where(X != " ")  list)  list, b > fe((re.search, r"move (\d+) from (\d+) to (\d+)")  X.groups()  fe(int))))  as_args(λ sl, ii: (ii > fe(as_args(λ n, i, f: range(n) > fe_do(λ _: sl[f  1].append(sl[i  1].pop()))))  tuple, sl > fe(X[1])  "".join )[1]))
Python code generated from the above
from more_itertools import always_reversible from more_itertools import chunked from more_itertools import first from more_itertools import split_at from pipetools import X from pipetools import as_args from pipetools import foreach from pipetools import foreach_do from pipetools import pipe from pipetools import where import re import sys from pyp import pypprint p = pipe fe = foreach fe_do = foreach_do lines = [x.rstrip('\n') for x in sys.stdin] ls = lines output = ls > p  (split_at, X, ~(X == ''))  as_args(lambda t, b: (t > p  always_reversible  (lambda ls: (lambda top_width: ls > fe(X.ljust(top_width)))(len(first(ls)) + 1))  fe(p  (chunked, X, 4)  fe(''.join))  as_args(zip)  fe(fe(X[1])  where(X != ' ')  list)  list, b > fe((re.search, 'move (\\d+) from (\\d+) to (\\d+)')  X.groups()  fe(int))))  as_args(lambda sl, ii: (ii > fe(as_args(lambda n, i, f: range(n) > fe_do(lambda _: sl[f  1].append(sl[i  1].pop()))))  tuple, sl > fe(X[1])  ''.join)[1]) if output is not None: pypprint(output)
Part 2, in Pythonish
(ls > p  (split_at, X, ~(X == ""))  as_args(λ t, b: (t > p  always_reversible  (λ ls: (λ top_width: ls > fe(X.ljust(top_width))) (len(first(ls)) + 1))  fe(p  (chunked, X, 4)  fe("".join))  as_args(zip)  fe(fe(X[1])  where(X != " ")  list)  list, b > fe((re.search, r"move (\d+) from (\d+) to (\d+)")  X.groups()  fe(int))))  as_args(λ sl, ii: (ii > fe(as_args(λ n, i, f: range(n) > fe_do(λ j: sl[f  1].append(sl[i  1].pop(n + j)))))  tuple, sl > fe(X[1])  "".join )[1]))
Python code generated from the above
from more_itertools import always_reversible from more_itertools import chunked from more_itertools import first from more_itertools import split_at from pipetools import X from pipetools import as_args from pipetools import foreach from pipetools import foreach_do from pipetools import pipe from pipetools import where import re import sys from pyp import pypprint p = pipe fe = foreach fe_do = foreach_do lines = [x.rstrip('\n') for x in sys.stdin] ls = lines output = ls > p  (split_at, X, ~(X == ''))  as_args(lambda t, b: (t > p  always_reversible  (lambda ls: (lambda top_width: ls > fe(X.ljust(top_width)))(len(first(ls)) + 1))  fe(p  (chunked, X, 4)  fe(''.join))  as_args(zip)  fe(fe(X[1])  where(X != ' ')  list)  list, b > fe((re.search, 'move (\\d+) from (\\d+) to (\\d+)')  X.groups()  fe(int))))  as_args(lambda sl, ii: (ii > fe(as_args(lambda n, i, f: range(n) > fe_do(lambda j: sl[f  1].append(sl[i  1].pop(n + j)))))  tuple, sl > fe(X[1])  ''.join)[1]) if output is not None: pypprint(output)

Comment on Day 4: Camp Cleanup in ~comp
primordialsoup (edited )Link Parentit is a little preprocessor i cobbled together. it has two stages: sed 's/λ/lambda/g'. (in the future i'd like to actually extend the grammar of an existing Python implementation instead of using...it is a little preprocessor i cobbled together. it has two stages:

sed 's/λ/lambda/g'
. (in the future i'd like to actually extend the grammar of an existing Python implementation instead of using this hack to mimic an extended grammar.) 
pyp
with apyprc.py
that is (for the most part)`pyprc.py`
import plumbum.cmd as cmd from plumbum import TF from functools import * from itertools import * from operator import * from pipetools import * stdout = sys.stdout p = pipe fe = foreach fe_do = foreach_do Xp = xpartial from more_itertools import * import numpy as np ls = lines # string input parsing n = int(l) ns = lines > foreach(int)  list y = float(l) ys = lines > foreach(float)  list f = l.split() fs = lines > foreach(X.split())  list
much of the cool stuff happening is actually not done by preprocessing—it's
pipetools
's purePython tricks with heavy usage of(more_)?itertools
on top. 

Comment on Day 4: Camp Cleanup in ~comp
primordialsoup advent of code is the only time that i write dynamically typed code these days. and lo and behold! 2/3rds of the time i took for part 1 was spent because i forgot to convert strings to ints and...advent of code is the only time that i write dynamically typed code these days. and lo and behold! 2/3rds of the time i took for part 1 was spent because i forgot to convert strings to ints and didn't realize what was going wrong :')
Part 1, in Pythonish
(ls > fe(X.split(",")  fe(X.split("")  fe(int)  tuple)  permutations  fe(as_args(λ a, b: a[0] <= b[0] <= b[1] <= a[1]))  any)  sum )
Python code generated from the above
from itertools import permutations from pipetools import X from pipetools import as_args from pipetools import foreach import sys from pyp import pypprint fe = foreach lines = [x.rstrip('\n') for x in sys.stdin] ls = lines output = ls > fe(X.split(',')  fe(X.split('')  fe(int)  tuple)  permutations  fe(as_args(lambda a, b: a[0] <= b[0] <= b[1] <= a[1]))  any)  sum if output is not None: pypprint(output)
Part 2, in Pythonish
(ls > fe(X.split(",")  fe(X.split("")  fe(int)  tuple)  permutations  fe(as_args(λ a, b: a[0] <= b[0] <= a[1]))  any)  sum )
Python code generated from the above
from itertools import permutations from pipetools import X from pipetools import as_args from pipetools import foreach import sys from pyp import pypprint fe = foreach lines = [x.rstrip('\n') for x in sys.stdin] ls = lines output = ls > fe(X.split(',')  fe(X.split('')  fe(int)  tuple)  permutations  fe(as_args(lambda a, b: a[0] <= b[0] <= a[1]))  any)  sum if output is not None: pypprint(output)

Comment on Day 3: Rucksack Reorganization in ~comp
primordialsoup ooh, string.ascii_letters is nice here, i'm going to steal that :)ooh,
string.ascii_letters
is nice here, i'm going to steal that :) 
Comment on Day 3: Rucksack Reorganization in ~comp
primordialsoup (edited )LinkPart 1, in Pythonish (ls > fe((divide, 2)  fe(set)  (reduce, and_)  one  string.ascii_letters.index  X + 1)  sum) Python code generated from the above from functools import reduce from...Part 1, in Pythonish
(ls > fe((divide, 2)  fe(set)  (reduce, and_)  one  string.ascii_letters.index  X + 1)  sum)
Python code generated from the above
from functools import reduce from more_itertools import divide from more_itertools import one from operator import and_ from pipetools import X from pipetools import foreach import string import sys from pyp import pypprint fe = foreach lines = [x.rstrip('\n') for x in sys.stdin] ls = lines output = ls > fe((divide, 2)  fe(set)  (reduce, and_)  one  string.ascii_letters.index  X + 1)  sum if output is not None: pypprint(output)
Part 2, in Pythonish
(ls > p  (chunked, X, 3)  fe(fe(set)  (reduce, and_)  one  string.ascii_letters.index  X + 1)  sum)
Python code generated from the above
from functools import reduce from more_itertools import chunked from more_itertools import one from operator import and_ from pipetools import X from pipetools import foreach from pipetools import pipe import string import sys from pyp import pypprint p = pipe fe = foreach lines = [x.rstrip('\n') for x in sys.stdin] ls = lines output = ls > p  (chunked, X, 3)  fe(fe(set)  (reduce, and_)  one  string.ascii_letters.index  X + 1)  sum if output is not None: pypprint(output)
edit: replaced
λ c: ord(c)  (ord("a") if c.islower() else ord("A")  26) + 1
withstring.ascii_letters.index  X + 1
. 
Comment on Tildes Video Thread in ~misc
primordialsoup (edited )LinkVivian Strange—Bo Burnham and Content Cinema (18:12) (youtube). if Bo Burnham's "Inside" touched you this probably will too. i'll definitely be rewatching "Inside" soon because of this essay :)...
Vivian Strange—Bo Burnham and Content Cinema (18:12) (youtube).
^{if Bo Burnham's "Inside" touched you this probably will too. i'll definitely be rewatching "Inside" soon because of this essay :)}

Lily Alexandre—Cinema's First Kiss Was Between Two Women (38:52) (nebula/youtube).
^{could you imagine if repressive patriarchs today were fine with a lesbian kiss being filmed in a context where they thought that filming a straight kiss would be taboo? well, upper class academia in the late 1800s united states thought so! (but only because women were repressed even more!)}
^{also, i do not have the words to state how lovely and touching the outro to this video is, especially when seen in the context of the essay.}

Quality Culture—Lilo & Stitch is a Weird Movie (17:28) (youtube).
^{lilo is a weird protagonist by disney's standards, but we love that for her}


Comment on Tildes Game Giveaway Thread: Holiday 2021 in ~games
primordialsoup I'd like Absolute Drift please. Thanks for putting this together!I'd like Absolute Drift please. Thanks for putting this together!

Comment on Day 14: Extended Polymerization in ~comp
primordialsoup 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 doublecounting # ceil to correct for template[0] and template[1] offbyone'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.

Comment on Day 12: Passage Pathing in ~comp
primordialsoup (edited )LinkPart 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).

Comment on Is there an opensource version of the Garmin Connect app for Android? in ~tech
primordialsoup 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.

Comment on Day 6: Lanternfish in ~comp
primordialsoup (edited )LinkI 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)
By my tests this is slower than my lineartime version for
n = 256
, but it starts beating my lineartime version aroundn = 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 forn = 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... 
Comment on Day 2: Dive! in ~comp
primordialsoup (edited )Link ParentI 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.
Part 1, in Pythonish
Python code generated from the above
Part 2, in Pythonish
Python code generated from the above