nathan's recent activity

  1. Comment on Day 14: Restroom Redoubt in ~comp.advent_of_code

    nathan
    Link
    Wasn't sure how to approach part two, I first started looking for pixels that were symmetric across the y axis, but then I realized the image probably didn't need to be centered. Then I had the...

    Wasn't sure how to approach part two, I first started looking for pixels that were symmetric across the y axis, but then I realized the image probably didn't need to be centered. Then I had the idea to try and measure the entropy of each pixel, once they were in the arrangement of a christmas tree that probably had low entropy. Super fun puzzle :)

    Part 2 
    import os
import re
import math
from collections import defaultdict
from copy import deepcopy
file = 'test.txt' if os.environ.get('DEBUG') == 'y' else 'input.txt'


if file == 'test.txt':
    rows, cols = 7, 11
else: 
    rows, cols = 103, 101

def grid(bots):
    g = [[0 for _ in range(cols)] for _ in range(rows)]
    for bot in bots:
        bx, by, _, _ = bot
        g[by][bx] += 1
    return g

bots = []
with open(file, 'r') as f:
    for line in f:
        px, py, vx, vy = map(int, re.findall('-?\d+', line))
        bots.append([px, py, vx, vy])


def print_grid(g):
    for y in range(rows):
        for x in range(cols):
            v = g[y][x]
            out = v if v else '.'
            print(out, end='')
        print()


def step(bots, g):
    for bot in bots:
        bx, by, vx, vy = bot
        nx, ny = bx + vx, by + vy 
        if nx < 0: nx += cols 
        elif nx >= cols: nx -= cols
        if ny < 0: ny += rows
        elif ny >= rows: ny -= rows
        bot[0], bot[1] = nx, ny
        g[by][bx] -= 1
        g[ny][nx] += 1

nbrs = [
    (-1, -1),
    (-1, 0),
    (-1, 1),
    (0, -1),
    (0, 0),
    (0, 1),
    (1, -1),
    (1, 0),
    (1, 1),
]

def _in(x, y):
    return 0 <= x < cols and 0 <= y < rows

def prob(x, y, g):
    val = 0
    for dx, dy in nbrs:
        nx, ny = x + dx, y + dy
        if _in(nx, ny) and g[ny][nx]:
            val += 1
    return 1 - val / 9, val / 9
            
def entropy(bots, g):
    total = 0
    for x, y, _, _ in bots:
        p0, p1 = prob(x, y, g)     
        if p0 != 0.0 and p1 != 0.0:
            total -= p0 * math.log(p0)
            total -= p1 * math.log(p1)
    return total



min_entropy = float('inf')
min_grid = None
min_frame = 0
g = grid(bots)
for i in range(10000):
    step(bots,g)
    e = entropy(bots, g)
    if e <= min_entropy:
        min_frame = i + 1
        min_entropy = e

print(min_frame)

  2. Comment on Day 12: Garden Groups in ~comp.advent_of_code

    nathan
    Link
    Used a trick I didn't see elsewhere that simplified things. When trying to decide to increment the wall count, check if a neighbor in a direction parallel to the wall also has a wall in that...

    Used a trick I didn't see elsewhere that simplified things. When trying to decide to increment the wall count, check if a neighbor in a direction parallel to the wall also has a wall in that direction. So for walls running left and right, check that the cell to the left of the current cell does not have a wall. Only one cell per left to right wall segment will be leftmost.

    Part 1 and 2 
    from collections import deque
import os

file = 'test.txt' if os.environ.get('DEBUG') == 'y' else 'input.txt'

grid = []

with open(file, 'r') as f:
    for line in f:
        grid.append(list(line.strip()))

dirs = [
    (-1, 0),
    (0, 1),
    (1, 0),
    (0, -1)
]

same_side_dirs = {
    (-1, 0): (0, -1),
    (0, 1): (-1, 0),
    (1, 0): (0, -1),
    (0, -1): (-1, 0),
}

rows = len(grid)
cols = len(grid[0])

def _in(row, col):
    return 0 <= row < rows and 0 <= col < cols

def bfs(row, col, enqueued):
    if (row, col) in enqueued:
        return 0, 0, 0

    enqueued.add((row, col))
    q = deque([(row, col)])
    perimeter = 0
    area = 0
    walls = 0
    area_id = grid[row][col]
    
    while q:
        x, y = q.pop()
        area += 1
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if not _in(nx, ny) or grid[nx][ny] != area_id:
                perimeter += 1
                sx, sy = same_side_dirs[(dx, dy)]
                if not is_same_wall(x + sx, y + sy, dx, dy, area_id):
                    walls += 1
            elif (nx, ny) not in enqueued:
                enqueued.add((nx, ny))
                q.appendleft((nx, ny))
    return area, perimeter, walls

def is_same_wall(row, col, dx, dy, area_id):
    nx, ny = row + dx, col + dy 
    same_region = _in(row, col) and grid[row][col] == area_id
    is_wall_in_dir = not _in(nx, ny) or grid[nx][ny] != area_id
    return same_region and is_wall_in_dir

enqueued = set()
total = 0
total_new = 0
for row in range(rows):
    for col in range(cols):
        area, perimeter, walls = bfs(row, col, enqueued)
        if area * perimeter: print(f"{area=}, {perimeter=}, {walls=}")
        total += area * perimeter
        total_new += area * walls
print(total)
print(total_new)
    1 vote

  3. Comment on Any good Youtube channels on learning Data Structures and Algorithms, especially the math part? in ~comp

    nathan
    Link
    For improving your reasoning I would recommend focusing on proofs. Proofs were the only thing that helped make things “real” for me, and helped me think about problems holistically. However for...

    For improving your reasoning I would recommend focusing on proofs. Proofs were the only thing that helped make things “real” for me, and helped me think about problems holistically.

    However for your specific question about the divide and conquer squaring algorithm, I gotta say I don’t know what your professors are smoking asking for that. I have a masters in CS and that algorithm is not a homework problem, especially for what seems to be an undergraduate level course. If you’re willing to take a look you can find mathoverflow posts which describe the algorithm in detail. You can also search Toom Cook multiplication, of which your squaring problem is a special case.

    3 votes

  4. Comment on What programming/technical projects have you been working on? in ~comp

    nathan
    Link Parent
    The system design primer is mostly a resource for interviewing but is a good resource to discover some of the basics. I would also give designing data intensive applications a read if you do any...

    The system design primer is mostly a resource for interviewing but is a good resource to discover some of the basics. I would also give designing data intensive applications a read if you do any kind of work with large scale datastores.

    4 votes

  5. Comment on Someone dead ruined my life ... again. (Tiffany follow-up) in ~humanities.history

    nathan
    Link
    This was well worth the 20 minutes IMO, made me laugh out loud and also gave me a glimpse into a frustrating nightmare that I’ve thankfully never had to experience. One of my favorite videos of...

    This was well worth the 20 minutes IMO, made me laugh out loud and also gave me a glimpse into a frustrating nightmare that I’ve thankfully never had to experience. One of my favorite videos of his for sure

    12 votes

  6. Comment on Reddit is raising up to $700M in Series F funding, at a valuation of over $10 billion in ~tech

    nathan
    Link Parent
    Fidelity doesn’t get to use the funds in retirement accounts to invest in whatever it wants does it? It’s invested in whatever you set your investments to Unless it somehow gets to work like a...

    Fidelity doesn’t get to use the funds in retirement accounts to invest in whatever it wants does it? It’s invested in whatever you set your investments to

    Unless it somehow gets to work like a bank, lending out multiples of its customers assets and I’m just not aware

    1 vote

  7. Comment on Primality test using regex in ~comp

    nathan
    Link
    In case anyone else is confused, the numbers in this article are represented in unary. I.e. 0: 1: 1 2: 11 3: 111

    In case anyone else is confused, the numbers in this article are represented in unary. I.e.

    0:
    1: 1
    2: 11
    3: 111

    5 votes

  8. Comment on <deleted topic> in ~science

    nathan
    Link
    Just throwing out community college courses as an option. Most colleges will have a placement exam that will put you at the right level as well. Math is something you learn only by doing, and it...

    Just throwing out community college courses as an option. Most colleges will have a placement exam that will put you at the right level as well. Math is something you learn only by doing, and it can be hard to identify exercises that help you really nail a concept and ones that are just rote calculation.

    4 votes

  9. Comment on Lockdown effectiveness: Much more than you wanted to know in ~health

    nathan
    Link
    This persons articles always follow the same pattern for me, I get invested in the first 2/3rds or so when the author presents a coherent summary of current research, and then the last 1/3rd the...

    This persons articles always follow the same pattern for me, I get invested in the first 2/3rds or so when the author presents a coherent summary of current research, and then the last 1/3rd the author starts bullshitting and multiplying numbers together to do unit cancellation and uses this to come to whatever conclusion they preferred in the first place. Like I don’t disagree with the conclusion here but just saying “oh there’s high error bars here” when you say that more strict lockdowns accounted for .6% of GDP loss some states is just ineffective communication.

    6 votes

  10. Comment on Attempting to use a software engineering approach to win at chess against my brother—and only my brother in ~comp

    nathan
    Link
    This post is great, person spends a lot of time to get an edge in a chess game and hangs a back rank mate in 1. Mirrors my experience trying to play chess, it’s never too late to hang mate,...

    This post is great, person spends a lot of time to get an edge in a chess game and hangs a back rank mate in 1. Mirrors my experience trying to play chess, it’s never too late to hang mate, especially if you’re not very good like me.

    4 votes

  11. Comment on Tab viewer/organizer? in ~tech

    nathan
    Link
    Tree Style Tabs? I see a lot of people recommend it, I never found myself remembering to use it enough for it to be useful, but if you’re an organized kind of person it may work better

    Tree Style Tabs? I see a lot of people recommend it, I never found myself remembering to use it enough for it to be useful, but if you’re an organized kind of person it may work better

    8 votes

  12. Comment on Turns out, Spock is kinda bad at logic in ~tv

    nathan
    Link
    The chess scene from one of the early episodes always bothered me. Spock is playing Kirk and Kirk checkmates him, and then Spock complains, “The logical move was the Rook!”. What kind of logic...

    The chess scene from one of the early episodes always bothered me. Spock is playing Kirk and Kirk checkmates him, and then Spock complains, “The logical move was the Rook!”. What kind of logic system has the winning move not be the logical move?

    19 votes

  13. Comment on What have you been eating, drinking, and cooking? in ~food

    nathan
    Link Parent
    It could maybe generously be described as light brown? It gets some color from the sausage fat and can pick up some color when you cook the roux

    It could maybe generously be described as light brown? It gets some color from the sausage fat and can pick up some color when you cook the roux

  14. Comment on What game(s) have you tried to repeatedly get into but ultimately could not? in ~games

    nathan
    Link Parent
    Yeah Terraria is definitely an “alt-Tab” to the wiki every two minutes kind of game. At least until you’ve played it a couple times. The devs did release a journey mode which I haven’t tried but...

    Yeah Terraria is definitely an “alt-Tab” to the wiki every two minutes kind of game. At least until you’ve played it a couple times. The devs did release a journey mode which I haven’t tried but was supposed to take some of the frustration away as I understand it

    6 votes

  15. Comment on What have you been eating, drinking, and cooking? in ~food

  16. Comment on <deleted topic> in ~life

    nathan
    Link Parent
    Regarding updating addresses, make sure to actually delete your old addresses from whatever app (Amazon Grubhub etc). I sent packages and food to my old apartment a couple of times before I wised up

    Regarding updating addresses, make sure to actually delete your old addresses from whatever app (Amazon Grubhub etc). I sent packages and food to my old apartment a couple of times before I wised up

    1 vote

  17. Comment on Quitting Reddit follow up thread in ~talk

    nathan
    Link
    I missed the original thread, but I wanted to share my experience here in case it helps someone who was struggling quite a bit with internet addiction. I quit reddit 100% back in August, I was...
    • Exemplary

    I missed the original thread, but I wanted to share my experience here in case it helps someone who was struggling quite a bit with internet addiction. I quit reddit 100% back in August, I was really unhappy with how much of my time was spent just aimlessly looking at memes online and consuming digital carbs. I wrote down my schedule of when I would get up and get to work and how often I would take a break and it was just sad to see how much of my time was staring at my screen trying to get a hit of dopamine.

    I took the plunge of quitting reddit and hackernews, and for about 4 months I didn't look at either. As I don't have any other social media this basically meant that I had very little reason to use the internet (I wasn't active on Tildes at this time either). I eventually started dipping my toe in particular reddits of interest to me (/r/financialindependence), but I still limit it heavily. I would strongly recommend at least trying a few weeks of this detox, it did wonders for my ability to sit down and focus on something and quite a bit of time that I previously would have spent on reddit I was able to better spend elsewhere.

    I think the biggest lesson I would share from my experience is to set yourself up for success. On my work laptop, my personal laptop, my phone and my tablet I blocked reddit and hackernews at the domain level. On a laptop it's easy just edit the /etc/hosts file (or OS specific equivalent). For months after quitting I would hit ctrl+t and start typing in 'reddit.com/r/all', it took so long to break this habit I was starting to get concerned it would never go away. The other thing I did that made this attempt successful was to find something that scratched that free dopamine itch in the first few days, without it coming from the internet. In my case this was reading a fantasy series that was enjoyable but didn't take any mental effort to enjoy, similar to just scrolling reddit. I read the first three books in a week just because so much of my time that was previously internet went into this series. (Series is Cradle by Will Wight, recommend it if you're into progression fantasy, probably not otherwise). I also started reading magazines, The Economist, National Geographic, Scientific American.

    I don't think the specifics of the magazines were important I think for me they just filled two critical gaps. One they gave me something to do with my time that was as easy as reading reddit. Previously when I quit reddit I tried to use the time to do something hard, learn a new skill, deep clean my house, exercise rigorously. When those things got hard I gave up on both doing the hard thing and quitting the internet. Two is that they fulfilled a similar desire of reddit which is just to consume information, I like that about the internet of always being exposed to new information. This was something that was missing in my previous attempts and I think ended up being key in making this one stick longer term.

    The other thing I did was limit my screentime overall. I can't limit work, but I can track my phone's screentime and avoid my personal laptop if I so choose. I set a goal of having less than an hour of screen on time for my phone for a month. It ended up sticking for a long time, it's just now that I've slowly been ramping up on the screen time again, this time consuming various online news sources (and Tildes). It's something I'm keeping an eye on for now, but now I know the skills and challenges associated with quitting I don't think it will be quite so troublesome.

    In short, if you want to quit I would make sure you set yourself up for success by making it difficult to access reddit, and finding something similarly easy to replace the time. Identify what you miss about reading the internet and find something better to replace it.

    24 votes

  18. Comment on Organizing life in checklists in ~life

    nathan
    Link
    I’ve been experimenting with organization for the past month or so, after reading Getting things done. Since GTD is so analog in its design I feel like it’s not the right approach for me to use...

    I’ve been experimenting with organization for the past month or so, after reading Getting things done. Since GTD is so analog in its design I feel like it’s not the right approach for me to use software to do tracking. Shell and Vim feel a lot more like pen and paper do, they occupy the same place in my head. So I use a directory structure where I have an in tray text file, subdirectories for projects (each project is a file) contexts (each context is a file) a someday directory (each someday project is a file, if I pick it up I move it into the projects directory) and a reference directory. Each project gets its own reference file.

    I’ve been using this at $DAYJOB and it’s been making things a lot easier to track.

    I also structure the information in the text files so that I can grep recursively and get a list of all open loops, all “waiting for”s etc

    1 vote

  19. Comment on TV Tuesdays Free Talk in ~tv

    nathan
    Link
    Has anyone watched the second season of Sex Education on Netflix? I found the first season to be moderately enjoyable, but didn’t want to waste my time if the second wasn’t any good

    Has anyone watched the second season of Sex Education on Netflix? I found the first season to be moderately enjoyable, but didn’t want to waste my time if the second wasn’t any good

    1 vote

  20. Comment on Remove Richard Stallman in ~tech

    nathan
    Link Parent
    Agreed, I just felt that in discussions online people either misread or mischaracterized what he was saying. What he was saying was shitty enough on its own, people didn’t need to change it to...

    Agreed, I just felt that in discussions online people either misread or mischaracterized what he was saying. What he was saying was shitty enough on its own, people didn’t need to change it to something even shittier, that just leaves wiggle room for intolerant people to yell “he didn’t say that” and ignore what was actually said.

    2 votes