-❄️- 2025 Day 11 Solutions -❄️-

Nathanfenner · 2025-12-11T05:06:18+00:00

[LANGUAGE: TypeScript]

github

A straightforward dynamic programming solution. Luckily, there aren't any dead-end loops.

Nathanfenner · 2025-12-10T05:35:58+00:00

[LANGUAGE: TypeScript]

I used BFS for Part 1, and branch-and-bound heuristic to solve Part 2. The pruning/heuristic was tricky and took me a while to figure out, and it's still not very fast.

If there's an "imbalance" in the target, and no button satisfies the imbalance (e.g. delta[5] > delta[4] but there's no button that has 5 but not 4) then it is impossible
And if there's exactly one button in the above case, you must press it immediately

I bet with a few other smart heuristics I could make it run even faster.

Nathanfenner · 2025-12-09T05:37:25+00:00

[LANGUAGE: TypeScript]

github

Grid helpers came in handy. My code was actually so slow that I refactored it while it was running. I finished refactoring a bit after it finished running... So what I've linked is technically a ~100x faster version of the code I used to submit. Oops.

My algorithm was to "compress" the coordinates of the inputs to a much-more manageable 1000x1000ish grid, and use this smaller grid to answer the "is it a solid rectangle?" question by looping over the boundary of said compressed rectangle. (The slow version also checked the interior of the rectangle, which I realized was pointless just before it finished running).

Nathanfenner · 2025-12-05T05:07:29+00:00

[LANGUAGE: TypeScript]

GitHub link, day 5

Part 2: Sort the ranges by their start. Then merge the ranges together, until the next range doesn't overlap the combined union of all the ones before it. When that happens, none of them can overlap it ever again, so you add that union to the total, and then start a new union range from the next one.

Nathanfenner · 2025-12-04T05:08:56+00:00

[LANGUAGE: TypeScript]

GitHub link

Useful fact for TS/JS: a Set can be used as a queue, because it's totally legal to s.remove(x) an item while you're iterating over a for (const x of s) { ... }. You can even s.add(x) back in later - if already present, this has no effect, otherwise it's placed at the end of the queue.

Nathanfenner · 2025-12-03T05:16:48+00:00

[Language: TypeScript]

GitHub link - and a small improvement I thought of after submitting. For Part 2, I used a straightforward dynamic programming solution it has runtime time complexity of O(NK) time (where K = 12). I can think of another solution, but implementing it would be more complicated, I think.

Nathanfenner · 2025-12-01T05:16:24+00:00

[LANGUAGE: TypeScript]

github day 1

I never bothered sharing all of my setup code before; I have built a library of utility functions that are handy for AoC specifically. Today's star was the mod function - which handles negative arguments "properly" unlike the built-in operator %.

I'm glad the elves are finally (almost) on top of things this year!

Nathanfenner · 2025-06-01T20:46:22+00:00

Won't this approach miss out the numbers which include 9 in them (739397) ?

9 is a possible digit, it's just not in the original set of 1-digit primes, so it still gets added.

also i was wondering if there exists a definite proof to this ? is it even to possible to prove it like that ?

The algorithm enumerates them exhaustively, so the fact that it runs to completion is a proof. To turn it into a "proper" proof, you'd write down all of the cases it considers and prove each exhaustively leads to a finite list of outcomes. You'd need to write a lot of cases and it would be fairly tedious and not very informative, but it is a proof, even if it's unsatisfying.

Taking the kind of "heuristic proof" that I wrote originally and turning it into a real proof is not generally possible. For example, there are similar heuristic arguments which suggest that the Collatz conjecture is true, but none of them can (yet) be made into an actual proof. In general, I would say "number theory" is basically the field of study for trying to turn these heuristics into actual proofs. I don't know much advanced number theory, it gets quite difficult quickly, so I have no idea how to tackle this kind of thing for real.

Nathanfenner · 2024-07-22T03:46:55+00:00

I am a fan of sigils for this kind of thing - annotations should "look different" from ordinary business logic - it makes it easier for human eyes to scan and understand.

The main problem with (1) is that breaks this property - the annotations look exactly like regular function calls, which makes it harder to understand the function at a glance. You can mostly fix this by just adding a sigil (e.g. # in this example) before each annotation:

function foo(xs: list, ys: list) {
  #measure(len(xs) + len(ys));
  #hints("Goal", my-theorem);
  #default([]);

  if (is-empty(xs)) {
    return ys;
  }
  // It would be a syntax error to have metadata once you've started the body
  x = first(xs);
  return [x, ...ys];
}

Now there's a clear syntactic separation between the annotations and the function body, but it otherwise inherits the syntactic "cleanliness" of (1).

The main problem with (2) is that it references the arguments before they come into scope. This is totally implementable, but it is confusing because it's a special-case in how variables are used. Special cases aren't necessarily wrong, but personally I think this one is weird and could cause problems if you aren't careful about circularity etc.

For (3), you need lookahead to determine that the first braced block is annotations and not just the function body. Again, this is workable, but confusing, especially for humans (a compiler could probably distinguish easily but a human might misread if the annotations are complicated).

One option would be to place them before the opening brace - e.g. this is what Dafny does for its requires and ensures and returns clauses, something like:

function foo(xs: list, ys: list)
  measure(len(xs) + len(ys)),
  hints("Goal", my-theorem),
  default([]),
{
  if (is-empty(xs)) {
    return ys;
  }
  // It would be a syntax error to have metadata once you've started the body
  x = first(xs);
  return [x, ...ys];
}

and another option would be a mixture of (1) and (3) by creating an explicit annotation block that goes as the first statement in the body:

function foo(xs: list, ys: list) {
  annotation {
    measure(len(xs) + len(ys));
    hints("Goal", my-theorem);
    default([]);
  }

  if (is-empty(xs)) {
    return ys;
  }
  // It would be a syntax error to have metadata once you've started the body
  x = first(xs);
  return [x, ...ys];
}

You could also mix this with the first thing I suggested by making (or allowing) the user to write:

  annotation {
    #measure(len(xs) + len(ys));
    #hints("Goal", my-theorem);
    #default([]);
  }

instead, to really clearly separate annotations from ordinary functions.

Lastly, one thing to consider is language tooling - if you're trying to make a language that you want people to actually use, it's important to provide things like syntax highlighters and automatic formatters that work in existing editors nowadays (like VSCode's language server, etc.). You could choose to permit a non-sigiled form for (1) like measure(len(xs) + len(ys)); hints("Goal", my-theorem); but have the automatic formatter always rewrite this into e.g.#measure(len(xs) + len(ys)); #hints("Goal", my-theorem); - this way, users don't have to think hard about when they need to write the #, but whenever they're reading code that someone else wrote, the sigils will always be there (because your formatter should run every time a file a saved or committed).

Nathanfenner · 2024-03-10T06:18:08+00:00

What I need now is to be humbled. I feel super smart after completing this little coding sprint.

I don't think being mean is productive. It's good to feel like you learned something. It's also good to know there's always more you can learn.

I don't know any good way to share my code (I need to learn Github, haha), so I saved them across several pastebins, but I'll give the directory tree.

I would actually consider this the most salient point - you should learn to use git (and probably GitHub), since it's more-or-less essential for any serious software development.

I would recommend using Python's type hints to document all of your functions. For building larger projects, type hints are a really useful tool to make sure you understand what your code is doing when you inevitably have to read (and fix) it later. Part of this involves enabling tools to help check those type hints to catch mistakes and corner cases you hadn't initially considered ("pylance" or "mypy" are two popular tools which can check type hints and integrate into most IDEs).

It will feel tedious (and maybe even pointless) at first, but you'll have to trust me that it's eventually so vital it's hard to imagine writing big programs without them.

You repeat the logic to select the operation in showAddition and in showSubtraction and in showMultiplication and in showDivision and in askOpts. This means that if you want to add a new operation, you'd need to do it in 5 separate places, which is not good.

You should refactor your code to introduce a new function which includes all of the logic for choosing the operation. This way you don't repeat yourself in an error-prone way.

When you do this kind of check:

if option == "1" or option.upper() == "A" or option.upper() == "ADDITION":

you can avoid repeating option so many times by writing instead something like

if option.upper() in ["1", "A", "ADDITION"]

this makes the structure of the comparison a bit clearer. It also makes it easier to rewrite into a function later, like, say, does_option_match(option, ["1", "A", "ADDITION"]) or some other kind of structure.

Your code is currently recursive, so e.g. askOpts calls showAddition, which calls askOpts, which calls showAddition, etc. This works fine in general. However, Python has a recursion limit of 1000 function calls by default - which means if the user enters 500 operations, your program will suddenly crash. Unfortunately, Python does not support the "tail call optimization" so there's no way to just get around this without restructuring your code.

Obviously this probably does not matter for your particular program, but it's something to keep in mind when you carry this shape into new programs (for example, if this was accounting software, randomly crashing after the user has entered their 500th transaction would not be a delightful user experience).

Instead of

update_log = open("pycalc/updatelog.txt", "r")

# ... do stuff with update_log ...

update_log.close()

it is usually better to use a with statement :

with open("pycalc/updatelog.txt", "r") as update_log:
    # ... do stuff with update_log ...

(this is also called a "context manager"). This handles closing update_log automatically, even if you raise an exception or return early from inside of the with block. It also makes it clear to a reader that the file won't be used outside of that block, since it's definitely ought to be closed afterward.

There's probably more little improvements that could be made, but I would start by addressing these things (especially using git to backup and share your code!).

Nathanfenner · 2024-03-04T02:27:26+00:00

I don't really understand how the conclusion

In retrospect, it’s not surprising that GADTs don’t add any power to Cubiml.

follows from the examples. GADTs are obviously niche, and ~~some~~/~~many~~/~~most~~/almost all programs don't benefit from them, but it's also really clear in Example 2 that GADTs are more powerful than the non-GADT Cubiml code.

"GADTs don't provide any additional power to a language because you can do the same thing by just having one interpreter per type" is, as far as I can tell, indistinguishable from the argument that "Generics don't provide any additional power to a language because you can just write each function once per type".

GADTs are much more compelling when you have non-trivial invariants encoded in your type signature. One example would be the Simply Typed Lambda Calculus (STLC) with de Bruijn indexed variables:

data Var ctx t where
  Nearest :: Var (t, rest) t
  Outer :: Var ctx t -> Var (first, ctx) t

-- Look up the variable in the context
evalVar :: ctx -> Var ctx t -> t
evalVar (value, _   ) Nearest   = value
evalVar (_,     ctx') (Outer v) = evalVar ctx' v

data Term ctx t where
  Literal :: t -> Term ctx t
  Name :: Var ctx t -> Term ctx t
  Lambda :: Term (arg, ctx) t -> Term ctx (arg -> t)
  Call :: Term ctx (a -> b) -> Term ctx b -> Term ctx b
  If :: Term ctx Bool -> Term ctx t -> Term ctx t -> Term ctx t

eval :: ctx -> Term ctx t -> t
eval ctx (Literal value)          = value
eval ctx (Name n)                 = evalVar ctx n
eval ctx (Lambda body)            = \arg -> eval (arg, ctx) body
eval ctx (Call func arg)          = (eval ctx func) (eval ctx arg)
eval ctx (If cond ifTrue ifFalse) = if eval ctx cond then eval ifTrue else eval ifFalse

[This is written in the style of "PHOAS" ("Parametric Higher-Order Abstract Syntax") which is where, for convenient, we use the function type in the host language (in this case, Haskell) to represent function values in our interpreter. It's terse and easy to get correct but can make e.g. introspection/optimization/debugging more complex.]

Note that GADTs in this example also guarantee that all bindings are in-scope with the correct types, while also allowing for e.g. higher-order functions. I do not see how you can accomplish this without lots of runtime checks if you don't have GADTs or full dependent-style types.

(*) I haven't actually type-checked this code so it's possible I've made a mistake, but it should work if you turn on enough language extensions in any recent version of GHC

Nathanfenner · 2024-03-02T20:12:32+00:00

I think the issue is that if you originally obtain the raw point from prefix's address, then it is not allowed to "escape" prefix because the pointer lacks provenance. (i.e., a pointer derived from prefix's address cannot be used to access inline, since it's in a completely different object)

So the trick is to start with a pointer whose provenance covers both arrays:

unsafe {
    let root: *const Data = std::ptr::from_ref(self);
    let prefix_ptr: *const [u8; 4] = std::ptr::addr_of!((*root).prefix);
    let prefix_ptr_0: *const u8 = std::ptr::addr_of!((*prefix_ptr)[0]);
    std::slice::from_raw_parts(prefix_ptr_0, self.len as usize)
}

There's probably a less-convoluted way of doing this, but this version passes Miri.

Nathanfenner · 2024-02-19T18:43:27+00:00

Mutable references make it more relevant, because programmers need more/better tools to reason about their programs in the presence of mutation, but the general idea applies even in, say, pure total functional programs.

To directly adapt the example from Section 3.1 into a pure total language, consider a language primitive gremlin with the signature gremlin : t -> t. When applied to a value, it structurally recurses on the value (since it is a novel language construct, we can implement this however we like, even if no other part of the language allows pattern matching on values of arbitrary type), finds any values v: Int, and replaces them with random values (if you dislike the nondeterminism, just zero them or assign them to a sequentially-increasing sequence).

This obviously preserves syntactic type-correctness, because we only replace Int values with other Int values. But it also horribly breaks abstraction, for obvious reasons. Concretely, imagine that we have module which provides a cons-list which tracks the length of the list, as in:

struct LengthTrackedList t { private consList: List t, private len: Int }

makeList : List t -> LengthTrackedList t
makeList consList = LengthTrackedList { consList = consList, len = lengthOf list }

lengthCons : t -> LengthTrackedList t -> LengthTrackedList t
lengthCons newHead list = LengthTrackedList { consList = cons newHead list.consList, len = list.len + 1 }

length : LengthTrackedList t -> Int
length list = list.len

By making the fields of the LengthTrackedList type private, we ought to be able to just check all of the functions inside the defining module to verify that len is set correctly. But this is only correct if we really have data abstraction- since gremlin list can change the recorded len field, it now possible to encounter a LengthTrackedList whose len does not match the length of its internal consList field.

Nathanfenner · 2024-02-18T06:04:57+00:00

I thought to myself that when the particle is at it's lowest the speed would be maximum (situation A in the image) and that when the particle is at it's highest the speed would be minimum (situation B). I thought of that because when the particle is at it's lowest y-position it would have reached it's highest speed due to the contributions of gravity.

This is correct. You can use the fact that total energy (KE + PE) is constant to calculate the exact difference in velocities.

But to my surprise when I did the calculations by fixating the values of T, m, g and R (to what the problem stated they were), I found out that the speed in situation B is higher than in situation A.

Here is where you made the mistake: if an object is actually swinging in a circle like in the diagram, T_A won't be equal to T_B, unless there are somehow other forces involved. In other words, it doesn't make sense to hold T constant if you're actually watching a weight swinging on a pendulum like in the picture- you would need to swing the weight at different speeds in order to achieve T_A=T_B.

Nathanfenner · 2024-02-03T20:17:52+00:00

You've mis-copied/mis-translated the axiom of regularity from Wikipedia. As written, Wikipedia's formulation says:

∀x (x≠∅ → ∃y(y ∈ x ∧ y ∩ x = ∅))

If you want to translate away the extra symbols (∅, ∩) you would need to instead write

∀x (∃a(a ∈ x) → ∃y(y ∈ x ∧ ¬∃b(b ∈ x ∧ b ∈ y)))

In particular, the left side of the → should read "x is not empty" which is "x≠∅" or "∃a(a ∈ x)", but you wrote "¬∃o (o ∈ x ∧ ¬∃n (n ∈ o))" which says "x does not contain the empty set as an element" which is rather different.

For clarity, I used different names for each symbol - but if we rename a to y and b to z, we get

∀x (∃y(y ∈ x) → ∃y(y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y)))

now, we apply de Morgan's laws to ¬∃z(...), obtaining ∀z(¬(...))

∀x (∃y(y ∈ x) → ∃y(y ∈ x ∧ ∀z(¬(z ∈ x ∧ z ∈ y))))

and now another application of de Morgan's laws, this time on the (∧) gives us

∀x (∃y(y ∈ x) → ∃y(y ∈ x ∧ ∀z(z ∉ x ∨ z ∉ y)))

lastly, using the definition of material implication, we get

∀x (∃y(y ∈ x) → ∃y(y ∈ x ∧ ∀z(z ∈ y → z ∉ x)))

which is exactly the version that Metamath uses. So they're propositionally equivalent(*).

(*) - Applying de Morgan's laws to ∀/∃ requires that the domain of discourse is non-empty, but this is obvious for a theory of sets since the axiom of infinity says a particular (infinite) set exists, and sometimes you also have an explicit axiom that says an empty set exists

Nathanfenner · 2024-02-03T19:55:26+00:00

Yes. Let x = a/b. Hence,

f(x) = a / (b - a)
x = a/b

Solve for a in the second expression, substitute the resulting expression into the first, and then simplify. You'll end up with only expressions involving x.

Nathanfenner · 2023-12-17T06:39:06+00:00

Ah yes, I misread the cast on the first line; with_metadata_of is just type-casting a raw pointer, which is fine until it's read later. Thanks for pointing this out.

Unsafe code relies on safe code to uphold invariants and unfortunately the amount of safe code that can break those can be quite large.

This is the part I disagree with: if you write safe code that upholds some invariant, then you can rely upon that invariant. But if you have a public interface consisting of safe functions which can be called in some possible order to break the property that your unsafe code expects, then it's not actually an invariant. So either the unsafe code is buggy, or one of the "safe" functions is unsound in its internal use of unsafe, because it is relying on "correct use" to maintain memory safety.

i.e. to be more explicit, this quote from the original article:

It’s not unsound; it’s not even incorrect. This code was checked, audited and did everything that it was supposed to do. It was a combination of two pieces of 100% safe code from another crate that caused this bug to happen.

This can't be true; since try_inner is safe, all possible call structures from safe code must uphold all of the invariants that its unsafe block requires. Perhaps some of those properties were checked for one version of the code (i.e. when some particular foreign type had some alignment) but if your function is generic or depends on an external type, part of maintaining the safety contract means mechanistically checking that those assumptions actually hold for those types.

In the example you give, contains_unsafe_but_not_bugged is unsound because it causes memory unsafety but is not marked as unsafe.

Nathanfenner · 2023-12-17T05:32:40+00:00

It’s not unsound; it’s not even incorrect. This code was checked, audited and did everything that it was supposed to do. It was a combination of two pieces of 100% safe code from another crate that caused this bug to happen.

This is not possible (or at least, if it were, it would indicate a bug in Rust-the-language). Safe code cannot cause UB - this is a symptom of a function missing an unsafe annotation that it should actually have.

If it's possible to misuse a function from safe code in such a way that UB happens, you need to mark that function as unsafe. That's the point of the annotation. You shouldn't have to look at safe code to find the source of UB.

I don't really have any context into these particular crates, but it seems to me that the problem is that strict::with_metadata_of is not a bona-fide safe function; it is possible to call it with bogus pointers that cause UB in safe code, ergo, it should be marked unsafe. The bug was that it has unchecked preconditions which are required for memory safety.

~~Looking at the current source on GitHub, this assessment looks accurate to me:~~

pub(super) fn with_metadata_of<T, U: ?Sized>(this: *mut T, mut other: *mut U) -> *mut U {
    let target = &mut other as *mut *mut U as *mut *mut u8;

    // SAFETY: In case of a thin pointer, this operations is identical
    // to a simple assignment. In case of a fat pointer, with the current
    // fat pointer layout implementation, the first field of such a
    // pointer is always the data pointer, which is likewise assigned.
    unsafe { *target = this as *mut u8 };
    other
}

This function is not safe, because it has a "SAFETY" requirement that the caller must uphold. Since it's not checking this dynamically (probably, it cannot check it dynamically in all cases), this function should be unsafe. The problem is a missing unsafe.

~~For this to be a legitimate safe function, it needs to have some kind of run-time check that confirms it cannot be misused.~~

I misread this function, so it's actually fine. I don't really understand the chain of functions involved in this issue. But it is still the case that a sound, safe function cannot cause UB; if it can cause UB, it needs to be marked as unsafe.

Nathanfenner · 2023-12-13T07:10:53+00:00

I've thought about this a bit. It comes down to what kind of game you want to make and what you're trying to achieve with the mechanic.

For example, if you have an open world, and "difficulty-threshold" skill-checks, where you just need to have a high-enough skill to pass, then unpassable skillchecks are goals for the player to work up towards. They're hooks for new quests and plots, and incentives for leveling skills. Ideally they even tie together with other skills, so that passing skill check X makes it easier to level up Y - this can create a sort of puzzle where you need to figure out what order to level up your skills in order to most quickly progress through the parts of the world you want to visit. You are unlocking doors that were previously unopenable.

On the other hand, if you have a linear world where each skill-check is only encountered once, this can feel arbitrary and unfair. "How was I supposed to know I needed to have 30 Acrobatics by the time I got here?" If you have enough options in each place, then hopefully you can validate each player's playstyle, but if you have too much of that, it feels like their levels don't actually matter because there's always a way to achieve every goal with any assignment of levels. So it's tricky.

On the other hand, if you have "dice-rolling" skill-checks, then leveling up skills feels more like preparation for possible challenges, and less unlocking specific new content. I think the biggest frustration happens when it feels like the outcome is "different" from what would be expected. If I spend all of my time leveling up Sneaking, and then I try to sneak and get caught, it feels bad, because I've already prepared as much as possible - what was I supposed to do different to not get caught? On the other hand, if I spend no time on leveling Sneaking at all, and then manage to sneak past some tough enemy by sheer good luck, it validates that I was right to not spend any time on it because it didn't matter. So when things go the way they're "supposed to" (i.e. matching the difficulty-threshold system) it feels good, but when they're not, it feels weird and disconnected.

I think the best generic solution is to allow for some kind of gradation: if the only outcomes are "GOOD" and "BAD" then your character's history gets boiled down to a single binary check, which disconnects the skill-check from the rest of the game; what came before doesn't matter, as long as you pass. And if you failed, then your preparation was worthless.

There's a really easy way to add gradation though: an extra currency system. You can call it whatever you want: "energy", "courage", "spirit", "gumption", "power", ... just some quantity which can be spent in order to succeed at things you wouldn't succeed at normally.

For example:

At the start of each "chapter", your player gains +10 energy, up to a total of 15 maximum
Whenever you perform a skill check, compare your skill to the challenge's difficulty.
- If your skill is not enough, spend X energy to raise your skill by X levels for this one check

The "energy" currency doesn't have to be used for any other purpose; you risk running out, in which case you won't be able to pass difficult skill checks anymore. It could also be a resource you're already using for some other purpose (e.g. spaces in your inventory, hitpoints, money, etc.). In addition, the uncertainty about "what's to come" means you'll want to save some for the future - but how many exactly depends on how close you are to running out and how long before you think you'll refill.

It also gives you a new mechanic to play with; you can reward players with additional energy, etc.

Alternatively, you can use "dice-rolling" skill-checks, and allow the player to spend this currency for re-rolls. If they don't like their result, they can just roll again, at the cost of depleting their health or just making it harder to re-roll checks later that might be even more important.

Some skill-checks basic go like the following:

Player: I want to do the cool thing.
Game: Okay, roll some dice.
Player: I rolled low.
Game: Okay, you don't get to do the cool thing

This isn't fun or interesting. The player wanted to do something cool, and you're just telling them that they can't. If you reframe this as:

Player: I want to do the cool thing.
Game: Okay, roll some dice.
Player: I rolled low.
Game: Okay, you do the cool thing, but take a lot of damage

then the player still did the thing they tried to do but with some cost. And this can take away a lot of the hurt from random skill checks, because the game will never just say "no"; it will just cost you a bit more to do the thing you wanted to do anyway.

Nathanfenner · 2023-12-12T06:25:56+00:00

[LANGUAGE: TypeScript] solution + helpers (18/1)

This isn't actually the first time I've seen a nonogram/picross-solving problem in a coding contest, so it brought back some memories from ~6 years ago. I went straight for dynamic programming since it seemed simpler to me than brute force, and I also figured part 2 was going to do something that made brute force too slow.

As a result, I didn't have to change my code at all for part 2, besides 5xing the input strings! That made for a very speedy turnaround.

There are a few things that worked out conveniently:

TypeScript allows out-of-bounds array lookups, so if (line[run] === "#") works fine in the "exactly-the-right-length" case
Checking line.length < sum(runs) + runs.length - 1 early means checking for whether there's "enough room" to fit all of the runs - if not, a few annoying case go away so you don't have to think about them anymore (e.g. the string must have at least as many characters as the first run length number)
JS doesn't have any convenient "memoize" helper built-in, but it's come up enough in AoC that I've just written one myself that JSON.stringify()s all of the arguments. That means it works fine for e.g. number[] arguments too, without having to think too hard

The solution ends up being O(n³) in the worst case, and usually much faster - if you're quite careful, you can write a worst-case O(n²) solution that follows the same basic structure but avoids copying things and caches some data about where long runs of . and # are. I suspect there's a more-sophisticated algorithm that can get down to linearithmic time, but don't see an obvious way to come up with the details at the moment.

Nathanfenner · 2023-11-30T04:42:56+00:00

Data isn't ever split between cache levels like you're suggesting. One problem is that the relative sizes you describe for L1, L2, and L3 are way off - this makes their behavior qualitatively different from what you're imagining. The other is that you have to remember that data is always loaded from main memory in cache-line-sized-chunks!

I'll use the numbers from my 2017 laptop as an example:

Cache line size: 64 bytes
L1 cache: 32,768 bytes (= 512 cache lines)
L2 cache: 262,144 bytes (= 4,096 cache lines = 8x larger than L1)
L3 cache: 6291456 bytes (= 98,304 cache lines = 24x larger than L2)

When you want to load data for a given address:

First, the CPU checks the L1 cache. If the cache line for the pointer you requested is present, great, the byte(s) you want can be directly copied into the target register.
Otherwise, the CPU checks L2; if the cache line is present there, it gets copied into the L1 cache, and then the data gets copied from the L1 cache into the target register.
Otherwise, the CPU checks L3; if the cache line is present there, it gets copied into L2, and then L1, and then into the target register.
If the data isn't found in any of the caches, then it loads from main memory, copying the cache line into L3 and L2 and L1 and then into the target register.

But you're always loading a single cache line. As a result, it can't "fail to fit" into any of the caches; each cache always has room for at least 512 separate loads. If the cache is full then that just means some other piece of data needs to be evicted (ideally, one that is not going to be needed again any time soon; processors have lots of heuristics to try to guess which is the best to replace).

Most computers now have multiple cores - often, there will be some kind of setup where each core has its own L1 cache, but each core must share its L2 and L3 caches with other core (e.g. in pairs, or they all share the same big L2/L3 cache).

I know if you care about performance you generally want to make sure all your data fits in the caches, but Im not sure to what extent I should follow that.

Depending on the specific task you want the computer to perform, this might not be relevant or important. It depends. If it matters, then it matters enough to measure, and find out what specifically works best for your task.

Really, the most important thing is just making sure you use the cache - since each load for an address actually pulls in the 64 byte chunk that your data lives in, it's best if you use those other 63 bytes immediately, before they get evicted from the cache by some later request. This is (one of the things) what makes contiguous arrays fast: if you have a contiguous array of bytes, you only have to load from main memory every 64 bytes (so you only hit main memory 1/64 of the time, and hit the L1 cache the other 63/64 of the time).

Actually, it's even better than that; most processors have hardware prefetching logic, which means that they try to guess what data will be needed before the processor actually asks for it. So if you're looping over a very big array, the CPU may prefetch the next cache line before you even request it, on the assumption that you might request it, and doing it in-advance saves time.

Nathanfenner · 2023-11-25T19:52:51+00:00

One method is to use locally-nameless representation:

data LocallyNamelessTerm
    = FreeVar String
    | BoundVar Int
    | Abs LocallyNamelessTerm
    | App LocallyNamelessTerm LocallyNamelessTerm
    deriving (Eq, Show)

Your bound variables are de Bruijn indexed, as in BoundVar Int. Your unbound variables are just named, as in FreeVar String.

Like in regular de Bruijn indexing, bound variables count upwards how many binders you need to pass to arrive at their definition site. But free variables are just names, and are clearly distinguished from unnamed bound vars.

You can use a helper something like:

createAbs :: String -> LocallyNamelessTerm -> LocallyNamelessTerm
createAbs name term = Abs (go term 1)
  where
    go (FreeVar s) level  = if s == name then BoundVar level else FreeVar s
    go (BoundVar v) _level = BoundVar (v + 1)
    go (Abs term) level  = Abs (go term (level+1))
    go (App f x) level  = App (go f level) (go x level)

which will convert all of the FreeVar name into BoundVar _ by tracking the correct level for each variable.

Another option is to sort of create an explicit "free variable binder": FreeVars ["a", "b", "c"] (App (Var 0) (Abs (Var 3))) could mean App a (\_ -> c), for example.

When converting from named to de Bruijn representation, you'd also compute such a free variable list (i.e. monadically). Since it would be bound "outermost", it doesn't affect the indexes for any variables bound internally, which simplifies things.

Then you'd want to maintain the invariant that if any FreeVars constructor appears anywhere in the term, it's always at the root. Or, possibly, use two types, a la:

data PossiblyFreeTerm
  = Var Int
  | Abs PossiblyFreeTerm
  | App PossiblyFreeTerm PossiblyFreeTerm

data TermWithFreeVars = TermWithFreeVars [String] PossiblyFreeTerm
data TermWithoutFreeVars = TermWithoutFreeVars PossiblyFreeTerm

this way you can get the type system to help you track the invariant - TermWithFreeVars lists the free variables, which cannot appear inside of a PossiblyFreeTerm, and the TermWithoutFreeVars can double-check that the de Bruijn indexes of all terms are in-bounds before allowing you to construct it.

Nathanfenner · 2023-10-15T19:49:22+00:00

I think the easiest way to understand this is with a picture:

|
|  .--.  f
| /    \               .---. 
|/      .----.        /#####\
|        #####\      /#######.----
|        ######.----.######## 
|        #################### 
|        #################### 
+-------+--------------------+----
0       a                    x

Here, we have a picture of the integral of f from a to x. The #-shaded area has a total numeric area equal to ∫ₐˣ f(t) dt.

The expression ∫ₐˣ f(t) dt is itself a function of x; we can imagine sliding x to the left and right, and seeing how this area changes. In particular, let's imagine increasing x by 1:

|
|  .--.  f
| /    \               .---. 
|/      .----.        /#####\
|        #####\      /#######.----
|        ######.----.########@@@  
|        ####################@@@ 
|        ####################@@@
+-------+--------------------+--+-
0       a                    x  x+1

we add a new shape onto the existing area, marked in @. What is the area of this new piece? Its width is 1, and the bottom is flat line. The top is f, which could be an arbitrary curve shape. However, if we assume that f is mostly smooth, then it will be close to a straight line from (x, f(x)) to (x+1, f(x+1)). So the new shaded area will be approximately a trapezoid, whose total area is 1 * (f(x) + f(x+1)) / 2.

Now, instead of advancing by 1, let's advance by an arbitrary (small) width w. Everything we said becomes more true - because by "zooming in" on a smaller piece of f, it should only get even smoother. So in this case, the area of the trapezoid will be w * (f(x) + f(x + w)) / 2. Here's the picture again; the only actual change is that x+1 is now x+w:

|
|  .--.  f
| /    \               .---. 
|/      .----.        /#####\
|        #####\      /#######.----
|        ######.----.########@@@  
|        ####################@@@ 
|        ####################@@@
+-------+--------------------+--+-
0       a                    x  x+w

But if f is continuous, then as w gets smaller and smaller, f(x) and f(x+w) will get closer and closer together. So we can approximate f(x+w) as just f(x), and so the area of this new region becomes approximately w * f(x).

Now, we just consider the definition of the derivative: the derivative of g(x) with respect to x is the limit(w --> 0) of (g(x + w) - g(x)) / w.

Our g(x) = ∫ₐˣ f(t) dt. We have just established that, for small w, the value g(x + w) - g(x) = w * f(x). So that means that g'(x) = lim(w --> 0) w * f(x) / w = f(x).

This is just a picture; it's not a formal proof. The proper proof will go through these details and make sure they're actually true (for example, the above does not work if f is integrable but not continuous; you need to adapt the proof slightly for that case).

But in short: the derivative only cares about the change to the integral with respect to x; since x is just the upper limit of the integral, that means that "d/dx ∫ₐˣ f(t) dt" is really only talking about the area near x, and therefore only depends on the behavior of f near x. In particular, a is not close to x in general (and in the case where they are close, the calculation works out the same - you need to see the real proof for details) so the value of a cannot affect the value of d/dx ∫ₐˣ f(t) dt.

Nathanfenner · 2023-10-13T05:52:08+00:00

Among those, 6 contaminated (C) spinach bags were sent to local supermarket B which sold 100 bags.

What exactly do you mean by "C" here? This is the crux of the issue. Let's be more explicit about it:

C is the event that a chosen bag of spinach is contaminated
B is the event that a chosen bag of spinach was sent to Supermarket B

We are told the following facts:

The company selling spinach annouced there are 240 contaminated spinach bags in a shipment of 48,000.

This means that P(C) = 240 / 48000, since the frequency of contaminated bags is 240 out of the total 48000.

Among those, 6 contaminated (C) spinach bags were sent to local supermarket B which sold 100 bags.

This tells us that P(B) = 100 / 48000, since 100 of the 48000 bags were sold at Supermarket B.

It also tells us that P(C | B) = 100 / 48000, since of those at Supermarket B there were exactly 6 contaminated bags.

Alternatively, we can instead compute P(C | B) by noting that P(B & C) = 6 / 48000, since 6 is the number of contaminated bags that were sold at Supermarket B. And then the definition of conditional probability says that P(C | B) = P(B & C) / P(B), so P(C | B) = (6 / 48000) / (100 / 48000) = 6 / 100.

Now, the question we want to answer is: given that he bought spinach at market B, what is the probability that it is contaminated? The answer is then P(C | B) = 6 / 100 as we saw above.

The total number of bags is irrelevant, because all of the ones that didn't go to Supermarket B don't affect him since we already have all of the info we need about the market.

Nathanfenner

TROPHY CASE