DEV Community: RobinFiveWords

PlutoViz: Testing some real things

RobinFiveWords — Thu, 02 Jan 2025 06:39:19 +0000

This entire series contains major spoilers for Advent of Code 2019 day 20.

I reached the point in the Manim tutorials where I needed LaTeX installed. It took me a few minutes to realize that was the issue and it wasn't simply going to be something I could install via conda, so I moved on. Conveniently, the next example showed how to construct a line from multiple segments, and I created a test spiral of line segments around the origin.

I had the idea that I'd animate the drawing of these multi-segment lines, and although it took me a while to find it, Manim's Create function does this. However, for most of my visualization, I should expect to have the entire multi-segment line pop in and out all at once. My solution popped over 21k states from the priority queue, and even if each of those states gets just one frame, at 60 fps it would take six minutes to display them all. I may slowly display the first several states and last several states, but the 21k in the middle will be some kind of blur. Let's say I let the blur last 15 seconds, at 30 fps. Each frame would represent about 50 states. So I'd need to decide how to present 50 states with a single image. Perhaps the "active" / last state would have its entire path highlighted, and the rest would have their last [multi-segment line] step and endpoint highlighted with some low opacity.

PlutoViz: More prep

RobinFiveWords — Tue, 31 Dec 2024 06:07:12 +0000

This entire series contains major spoilers for Advent of Code 2019 day 20.

I'm leaning toward attempting to animate part 1 in 2D rather than jumping straight to part 2 in 3D. It seems like the wiser approach.

Tonight I cleaned up my solution script a bit. Instead of importing my 2D point class, I pasted it into the script and removed all the methods I don't use here. I also checked whether any names I used in the global namespace appear in locals().keys() after from manim import *, and Point does, so I changed mine to Point2D.

I'm also starting the Manim tutorials. I'm a tutorial junkie, and as I don't have a background in graphics, it again seems wiser to let the experts show me around first.

PlutoViz: Introduction

RobinFiveWords — Mon, 30 Dec 2024 07:19:52 +0000

"Part 2 seems hella cool. Would love to see this visualized."

That's what I wrote late at night on November 13, after finishing part 1 of Advent of Code 2019 day 20, and reading part 2.

This entire series contains major spoilers for Advent of Code 2019 day 20.

Part 1 is a two-dimensional rectangular maze with a hole in the middle, and several portals that each connect a point on the inside edge with a point on the outside edge. Part 2 reveals that this maze is recursive, and each portal on an inside edge connects with a point on the outside edge of the next level of the maze.

I formed a picture in my head of an inverted pyramid, with each inner level positioned below and a little bit smaller than the previous level. After solving the puzzle, I got some ideas about what a visualization of the search for the shortest path could look like. I've wished for a couple years that I could put together visualizations like the ones I've seen in the AoC subreddit, and I have a strong enough feeling about this puzzle that I think this is where I should start. A recent 3Blue1Brown video gave me the confidence that Manim would be the right tool, for me, for this first job.

Here's what I think I'll need to do to make it happen:

Install Manim. Conda wanted to downgrade NetworkX in my base environment, so I'm creating a separate environment for Manim. My solution for this puzzle didn't rely on anything beyond the Python standard library, although Manim's dependencies resulted in somewhere close to 200 packages being installed!
Enhance my solution to track the full path for each candidate. I'm pretty sure the number of branches to consider is small enough that I could assign each new branch a unique integer id and store the branch's full path at that index of a list.
Enhance my solution to store the line segments for each path between portals within a level. While I'm using breadth-first search to identify the distance to any reachable portal, I'll also need to track the full path. Then in each path I'll need to combine adjacent steps in the same direction into a single segment.
Create a static 3D image of my solution path for the larger example.
Animate a new branch — adding to an existing path.
Animate multiple branches. I imagine only the branch currently in focus will be fully illuminated. Perhaps the branch previously in focus will fade down to some minimum level.
Tweak the entire visualization to give a sense of the space, movement, search, etc.

Would it be silly to write my own defaultdict?

RobinFiveWords — Mon, 23 Sep 2024 06:22:03 +0000

TL;DR — Yes? Python's defaultdict is exactly the right tool for the job I call upon it to do.

Python

defaultdict is part of Python's standard library. Python is already a high-level language, so it seems arbitrary to say I'll allow myself to use some but not all parts of it as given to me.

I do, however, like when I know everything that something does, and I know it doesn't do anything else. If I'm not mistaken, defaultdict is 300 lines of C code (starting at line 2175 here), and I can't say I understand everything that it does. When I use defaultdict, almost always I am looping through data, aggregating values, and looking to avoid the KeyError the first time a key appears in the data (or having to check whether the key exists each time).

I'm sure millions of people have done this for homework or fun before, but I didn't search for their solutions; I searched for how to make an object "subscriptable", how to add a key to a dict without the subscript syntax (which I'm guessing would infinitely recurse), and how to call the parent class's __init__ method (it had been a while). The following seems to work fine:

class DefaultDict(dict):
    def __init__(self, value_type):
        self.value_type = value_type
        super().__init__()

    def __getitem__(self, key):
        if key not in self:
            self.update({key: self.value_type()})
        return self.get(key)

I probably will never use this, because defaultdict is already the right tool for the job. It throws an exception immediately when the default factory is not callable or None. Someone has already thought through what type the result should have when taking the union of a dict and a defaultdict. It has a nice repr.

Where I find writing my own tool to be most useful is if an existing tool is complex in a way that makes it unclear whether it is the right tool to use. Or if an existing tool solves a bigger problem than I am trying to solve.

Java

I must not have needed a "default HashMap" before, because I just now discovered computeIfAbsent. While I was thinking it through, though, this one-off code seemed straightforward enough:

ArrayList<Integer> list = d.get(key)
if (list == null) {
    list = new ArrayList<Integer>();
    d.put(key, list);
}

The more concise way:

d.computeIfAbsent(key, (x -> new ArrayList<Integer>())).add(value)

I think I'm looking for a way to extend HashMap so that I can write

d.myGet(key).add(value)

and it will run the previous code. This seems somewhat straightforward...

class DefaultMap extends HashMap<Integer, ArrayList<Integer>> {
    ArrayList<Integer> myGet(Integer key) {
        return this.computeIfAbsent(key, (z -> new ArrayList<Integer>()));
    }
}

...except I would need to create a separate class for each set of key-value types. There might be a way to do this with generics, but because (if I understand correctly) classes and functions aren't first-class objects in Java, I'm not sure how that would be done. Here's where I really need to search for an answer.

And of course the top Google result is a link I've visited before, because of course this isn't the first time I've wondered about it. The .class property effectively allows the class of the default value, such as ArrayList, to be passed as a parameter to the constructor. I'm going to have to let this simmer.

Choosing data structures for Advent of Code 2018 Day 24

RobinFiveWords — Thu, 19 Sep 2024 03:59:53 +0000

How should I store the fighters in a battle with complex interactions?

Mild spoilers for Advent of Code 2018 Day 24 follow.

I'm working my way through Advent of Code's back catalog. 2018 Day 24 looks fun. Well, part 1 looks fun. I'm dreading whatever search part 2 will likely require. Anyway, AoC problems tend to be written in a style that suggests a way to implement. For example:

Each fight consists of two phases: target selection and attacking.

From this I could immediately write:

def fight():
    select_targets()
    attack()

This code already captures at least two ideas: There will be many fights. Target selection is completed before attacking. Of course, at a minimum this is missing what is fighting, how they will be passed into the fight, and whether the fighters will have their stats updated or be replaced with the results of the fight.

Each side has an army, and each army contains several groups. I briefly considered representing a group as a tuple (ordered list), but as I would have to unpack it each time to write code I could read, it's more convenient to make it an object with named attributes. So I created a Group class. I should also create an Army class, right? Well, that immediately caused me problems. The order in which the groups act does not depend on which army a group is in. If I explicitly created two armies, I would need to maintain a separate list of the initiative order to identify the group up next. Then that group would need to know which army it was in, and its army would need to know the opposing army, and that army would need to know its groups.

I decided it would be enough for each group to know what army it was in. Any time a group needs to act (on groups of the opposing army), I would consider the full list of groups, and filter out the groups from the same army.

for group2 in groups:
    if group1.army == group2.army:
        continue

This has the added benefit of preventing a group from targeting itself.

So I was going to store the groups in a single collection, but what kind of collection? During target selection, I wouldn't know whether a target would be selected at the time I computed its potential damage received. And I needed way to exclude a selected target from later target selection in that fight. I decided I wanted some way to access the right group.

Each group's initiative value looked to be a useful identifier. I could have just assigned a unique ID to each group, and hopefully I won't have to rework this in part 2, but the initiative values in the test input and my real input appear to be distinct positive integers starting from 1 with no gaps. I thought about just using a list with access by index (position in the list), but aside from having to handle index 0 — or get back into a language with 1-based indexing — relying on a list index to remain unchanged would prevent me from deleting groups that have no units remaining. And I wanted to delete groups with no units so I wouldn't have to check for that in many places.

I settled on a dictionary, with the initiative as the key and the group itself as the value. This way, any time I wanted to track which groups had already been targeted, or anything else, I could just track the initiative values. This would spare me from having to write code to determine whether two groups were the same. Then when I wanted to retrieve the group itself, I'd get it from the dictionary. Deleting a group, deleting the key-value pair, would have no effect on accessing remaining groups.

I was still a bit hung up on sorting. Python dicts preserve order starting in 3.6, and at first I thought I wanted to store the groups in initiative order. This isn't always the order in which groups act, though. Effective power is sometimes used, and this changes throughout the battle. What eventually seemed best to me was just sorting the groups as needed, when needed.

for group in sorted(groups,
                    key=lambda g: g.initiative,
                    reverse=True):

Turns out part 2 was also fun! A search, of course, but with a neat twist.

Getting packages to work when writing Java programs from scratch

RobinFiveWords — Tue, 17 Sep 2024 05:36:10 +0000

In early 2023, to get better at reading and understanding Java code, I worked through Crafting Interpreters as intended, by typing every line of code. Well, almost every line. In the Java section of the book, each class file starts with this package statement:

package com.craftinginterpreters.lox;

When I omitted that line and put all the Java source files in a single directory, everything compiled and ran as it should. When I tried to build a folder tree to match the package, it didn't work.

I'll be getting into Groovy soon, and I feel like I should solve this basic Java problem before I have to start learning about Gradle, Maven, Graven, and all other kinds of avens.

And...I've got it working now. I created a folder tree:

src
+-- com
    +-- craftinginterpreters
        +-- lox
            +-- *.java files

Then I navigated to the src directory and compiled:

$ javac com/craftinginterpreters/lox/Lox.java

And executed:

$ java j.lox.Lox

What took quite a bit of time to troubleshoot tonight is that I initially copied some but not all of the source files. 😬

I'm still not sure why I couldn't get it working a year and a half ago. In any case, problem solved!