Arya’s Algorithms

  Getting Stuck: The Threads That Wouldn’t Behave Concurrency has always fascinated me. The idea that multiple tasks can run “simultaneously” — or at least give the illusion of simultaneity — feels like wizardry. But when I tried to actually implement something non-trivial, I got stuck in ways I never expected. The Task I wanted to simulate a bank with multiple accounts. Each account supports deposit and withdrawal. Multiple users (threads) perform transactions at the same time. Sounds simple. Attempt 1: Naive Multithreading I started with Python’s threading module: import threading class Account: def __init__(self, balance=0): self.balance = balance def deposit(self, amount): self.balance += amount def withdraw(self, amount): if self.balance >= amount: self.balance -= amount return True return False account = Account(100) def transaction(): for _ in range(1000): account.depo...

  Getting Stuck: When Dijkstra Meets Negative Edges One of the joys (and pains) of computer science is when you take a tool you know, confidently apply it, and then watch everything break down in surprising ways. This happened to me recently when I decided to revisit shortest path algorithms — specifically, Dijkstra’s algorithm — only to get stuck in a swamp of negative edges. Setting the Scene The problem was classic: Given a directed, weighted graph and a source vertex, find the shortest path to all other vertices. This is the kind of problem that every CS student learns early, usually with Dijkstra’s algorithm. I already knew Dijkstra like an old friend: Keep a priority queue of distances. Always expand the node with the current smallest distance. Relax its edges. Simple, elegant, efficient ( O((V + E) log V) with a binary heap). So when I started coding a graph utility for my project — a tool to analyze transportation networks — I confidently plugged in D...

Getting Stuck: The Stone Game That Wouldn’t Let Me Go One quiet evening, I found myself thinking about a very old type of problem in computer science and mathematics: two-player impartial games . The idea is simple — players take turns making moves until no move is possible, and the one who can’t move loses. I thought: Let me write some code to analyze one of these games. How hard could it be? The Setup I picked a variation of the Stone Game : There’s a pile of N stones. Two players alternate removing stones. On each turn, a player can remove 1, 3, or 4 stones. The player who takes the last stone wins. A classic "take-away" game. My goal was to write a program that, given N , tells me whether the first player has a winning strategy. Attempt 1: Brute Force Recursion I started with recursion. Define a function win(n) that returns True if the current player can force a win from a pile of size n . def win(n): if n == 0: return False f...

Getting Stuck — When Sorting Became a Trap  This is another entry in my Getting Stuck series. The title says it: I get stuck, I chase red herrings, I learn, and I climb out. This time the trap was a classical one: sort a file that’s larger than RAM . On paper, “just sort” sounds trivial. In practice, it became an odyssey through I/O, memory, representation, parallelism, and algorithm engineering. Problem statement (the kind that looks easy) You have a file with N integers, one per line. N is huge (tens or hundreds of millions). You cannot load all of them into memory. Produce a sorted file (same format). This is textbook external sorting territory, but I wanted to implement it myself for two reasons: (1) to understand performance pitfalls in practice, (2) because I enjoy learning the gritty details. Predictably, I got stuck several times. First attempts — tiny code, big assumptions I started with the naive in-memory approach (because why not check the obvious): # nai...

  Getting Stuck: When Hashing Isn’t Enough I was working on a side project where I needed to detect whether two strings were “similar” in some loose sense. The context was simple enough: given two strings, I wanted to know if they were almost the same, differing only by a few characters. Think of it like detecting typos in usernames or checking plagiarism in short text snippets. At first glance, this looked like a problem tailor-made for hashing. After all, hashing is the workhorse of so many fast algorithms — why not here? Attempt 1: Hashing to the Rescue (Or Not) I thought: If I hash each string, then identical strings will have identical hashes. Easy. But then the problem struck me: what about strings that are close but not identical? For example: "algorithm" "algorihtm" A transposition. Just two characters swapped. The hashes would be completely different. I wondered if I could get clever. Maybe I could generate multiple hashes per string by deleting...

  Getting Stuck: Writing a Turing Machine Simulator This entry in my Getting Stuck series started with what I thought was a fun challenge: write a Turing machine simulator from scratch. It sounded clean and manageable. After all, how hard could it be? A tape, a head, some states, some rules. By the end, I had written code that ran… and then refused to stop. I had also stumbled into undecidability theorems I’d only read about in textbooks. This is the story of how I got stuck — and what climbing out looked like. Step 1: The Innocent Beginning A Turing machine is described in almost childlike terms: An infinite tape with symbols on it. A head that can move left or right. A finite set of states. A transition function telling the machine what to do next. So I wrote down the core class in Python: class TuringMachine: def __init__(self, tape, transitions, start_state, accept_state, reject_state): self.tape = list(tape) self.head = 0 sel...

  Getting Stuck: The Case of the Elusive Cycle This is another chapter in my Getting Stuck series, where I document the messy, often frustrating process of solving computer science problems. This episode is about graph theory — and how I got trapped trying to detect cycles in a directed graph. Sounds easy, right? Well… let’s see. Step 1: The Obvious Attempt The problem: Given a directed graph with n nodes and m edges, detect if it contains a cycle. Immediately, I thought: Easy, just do a depth-first search (DFS) and track visited nodes. So I wrote: from collections import defaultdict class Graph: def __init__(self, n): self.n = n self.adj = defaultdict(list) def add_edge(self, u, v): self.adj[u].append(v) def has_cycle(graph): visited = [False] * graph.n def dfs(u): if visited[u]: return True visited[u] = True for v in graph.adj[u]: if dfs(v): return True ...

  Getting Stuck: When Cooperation Collapses — Repeated Prisoner’s Dilemma with Noise This was the one problem that looked like a polite conversation between two rational agents — and turned into a screaming match with foggy hearing. I wanted to understand how cooperation could be sustained between selfish agents when their interactions were repeated but noisy. Sounds textbook, right? Famous results (tit-for-tat, folk theorem, grim trigger) promise neat strategies. But once I actually started to play with imperfect observation — the small, realistic twist where you sometimes misread the other player’s move — everything that was tidy started to fray. This is the story of getting stuck: my naive assumptions, the routes that wasted time, the experiments that confused me, and finally the insight that pulled me out. The Game (short version) One-shot Prisoner’s Dilemma (payoffs in standard normalized form): Two players simultaneously choose C (cooperate) or D (defect). Payof...

  Getting Stuck: The Nim Variant That Played Me I like to believe that I’ve learned to recognize traps in mathematical problems. Especially in games. If something looks too neat, too regular, too easy, I get suspicious. But this time, the trap wasn’t in the setup — it was in my own head. The Game That Looked Harmless Here’s the problem: One pile of n stones. Two players alternate. On your turn, you may remove 1, 3, or 4 stones . Whoever takes the last stone wins. That’s it. Barebones, no hidden twists. Just arithmetic. I’ve seen countless problems like this. My instinct: there’s always a neat modular pattern in the losing positions. Like in ordinary Nim (remove 1 or 2 stones), where the losing positions are just multiples of 3. I was convinced I’d crack this in fifteen minutes. Spoiler: it took me an entire evening, and I ended up learning more about myself than the stones. My First Pass: Confidence at Full Blast I began the way every combinatorial game an...

  Getting Stuck: When Threads Betray You Welcome back to Getting Stuck . This time, instead of the abstract world of Turing machines, I wandered into something that should’ve been simple: writing a little multithreaded program to speed up a task. It was supposed to be clean, efficient, and elegant. Instead, I ended up chasing ghosts — bugs that showed up, disappeared, and then reappeared when I least expected. Step 1: The Simple Idea The task: count how many times a number appears in a giant list. I thought, Why not parallelize it? With Python’s threading module, I could split the list into chunks and count in parallel. import threading numbers = [i % 100 for i in range(10**6)] count = 0 def worker(chunk): global count local_count = chunk.count(42) count += local_count threads = [] chunk_size = len(numbers) // 4 for i in range(4): t = threading.Thread(target=worker, args=(numbers[i*chunk_size:(i+1)*chunk_size],)) threads.append(t) t.start() for...

  Getting Stuck: Hashing My Way Into Chaos Welcome back to Getting Stuck , the series where I share my CS problem-solving misadventures. Today’s episode: hash functions. On paper they look simple. In practice, they almost destroyed me. Step 1: The Problem I wanted to build a small key-value store. Nothing fancy, just strings as keys and integers as values. Obviously, I needed a hash function. Naively, I thought: Why not just sum the ASCII codes? def bad_hash(s): return sum(ord(c) for c in s) print(bad_hash("abc")) # 294 print(bad_hash("cab")) # also 294 (!) And immediately, disaster: "abc" and "cab" collided. My hash function didn’t care about order. But instead of abandoning it, I got stubborn. Step 2: First Red Herring — Random Hashing I thought, “What if I assign each character a random number and sum them up?” import random char_map = {chr(i): random.randint(1, 1000) for i in range(128)} def random_hash(s): return ...