Author: Violet

Pronouns: Sie/Hir(failing that she/her)

Animating with img-genner

Posted on by Violet

I talked about img-genner's glitch functions last time. Now you get to see the messier part of the library, as of (january 15th 2022), the part that needs refactoring and reconsideration. For one thing it is enormously picky in terms of types. So much so that much of the code broke regularly with only slightly wrong input. In addition, since I was not yet entirely aware of how the common lisp object system(CLOS) worked, the design does not flow nicely with the mechanics.

I need to warn you that I have a low opinion of this code and thus am looking to rewrite it, it doesn't have a consistent interface and too much of it is hidden away from the user, so this is part tutorial, part self-guided criticism; this isn't a very well organized blog post.

So, is there much value in it? Well, I tend to think so, but I suppose that I might be biased. What works well is the polygon code, the line code, the ellipse code, when it's not complaining that it's not an explicitly typed array you passed in, is quite functional.

Let's start with another file with something simple. Let's get a spray of ellipses.

(ql:quickload :img-genner)
(defparameter *image* (img-genner:make-image 800 800))
(defparameter *circles* nil)
(loop for i from 0 to 10
      do(push (img-genner:make-ellipse (random 800) (* i 20) 20.0 10.0) *circles*))
(loop for i in *circles*
      do(img-genner:fill-shape i *image* (img-genner:static-color-stroker (img-genner:get-random-color))))
(img-genner:save-image *image* "ellipses.png")
A spray of various colors of ellipses.

In this, make-ellipse is a helper function designed to save the user from specifying everything necessary in a make-instance call. Static-color-stroker creates a stroker, which is similar to a brush in various graphics systems where they probably decided deliberately to call it anything other than a stroker. In the case of static-color-stroker it creates a closure over a function that just contains the desired color value. 

(defun static-color-stroker(color)
  (lambda (i x y frac)
    (declare (ignore frac)
             (type fixnum x y)
             (dynamic-extent color))
    (set-pixel i x y color)
    ))

Other strokers are possible, gradient-color-stroker creates a gradient over the value of frac, or radial-gradient-stroker, which takes two colors, a coordinate in the image, and a max-radius parameter that specifies the distance from the first color to shift to the second.

There are of course other varieties of shapes, such as polygon and convex-polygon(though, they should convert between each other automatically), and they have different interfaces.

We can add (img-genner:fill-shape (img-genner:make-regular-polygon 400.0 400.0 5 30.0) *image* (img-genner:static-color-stroker (img-genner:get-random-color))) to get an additional pentagon as below

The ellipses from before but now with a pentagon in the center

As you can see, there are issues between boundaries in the triangles that it breaks it down into.

classDiagram class Shape{ float rotation; float~2~ origin; } class Polygon{ List~Point~ points; } class Ellipse{ float~2~ radius; } class Rectangle{ float width float height } Shape *-- Ellipse Shape *-- Polygon Shape *-- Rectangle Polygon *--ConvexPolygon

I suppose that rectangles are a type of polygon, but unlike proper polygons, it doesn't make sense to represent them as a series of points, but representing that relationship properly would require more work than it seems like it's worth.

I've been finding that animating with this library is interesting. So let's make those ellipses vibe. I know, this is a still image library, but that doesn't have to stop us. All we have to do is write two functions, one to reset the image, and another to move the ellipses.

We'll also have to assign the ellipses consistent colors, otherwise they will flash constantly, and I doubt that's considered appealing.

(defun reset-image()
  (loop for i from 0 below (array-total-size *image*)
        do(setf (row-major-aref *image* i) 0)))
(defparameter *circles* nil)
(defparameter circle-colors (make-hash-table :test 'equal))
(defparameter circle-speeds (make-hash-table :test 'equal))
(defun mutate()
  (loop for i in *circles*
        do(incf (aref (gethash i circle-speeds) 0) (- (random 1.0) 0.5))
        do(incf (aref (gethash i circle-speeds 0.0) 1) (- (random 1.0) 0.5))
        do(img-genner:rotate-by i (- (random 1.0) 0.5))
        do(img-genner:move-by i (aref (gethash i circle-speeds) 0) (aref (gethash i circle-speeds) 1))))
...
(loop for i in *circles*
      for c = (img-genner:get-random-color)
      do(setf (gethash i circle-colors) c)
      do(setf (gethash i circle-speeds) (img-genner:point 0.0 0.0))
      do(img-genner:fill-shape i *image* (img-genner:static-color-stroker (img-genner:get-random-color))))

Then we run an animation loop for 160 frames

(loop for i from 0 below 160
      do(reset-image)
      do(mutate)
      do(loop for circle in *circles*
              do(img-genner:fill-shape circle *image* (img-genner:static-color-stroker (gethash circle circle-colors))))
        do(img-genner:save-image *image* (format nil "~4,'0d.png" i))
      )

And then with the proper ffmpeg invocation, you should end up with something like the following

The ellipses vibe subtly

For the above animation, the following command was used to generate it.

ffmpeg -i %04d.png -vcodec libwebp -filter:v 'fps=fps=20' -pix_fmt yuv420p -q:v 6 -p loop 0 output.webp

In the future however, I think I would like to refactor this so that it isn't necessary to work with the shape objects as the objects are really overkill for drawing ellipses and regular polygons, most libraries at this sort of level just use functions to write directly to the bitmap. I think that's much easier to fool around with since there's less state to manage.

Introducing img-genner, a Common Lisp Image Synthesis Library

Posted on by Violet

I have been working on the img-genner library(repo here) for quite a long time now, over three years if my memory serves me correctly. It contains a number of different modules, and frankly, it is a bit of a Frankenstein. At first it was about polygon graphics, then it became about pixel 'glitch' effects, such as pixel sorting and other stuff, partially because I wanted to write the algorithms myself and gain an understanding of them from implementation.

I'm still not quite sure about the triangularization algorithm(which we won't demonstrate here because I'm not sure it still works), but for the most part it has worked in that way.

For the examples here I am assuming that you have a functional roswell/common lisp environment with quicklisp and all the other amenities.

Getting the library

First clone it to your local projects directory, the command that will work for you will vary from this if you are not using roswell. As of now I have no plans to put this library on quicklisp unless there is some interest.

$> git clone https://github.com/epsilon-phase/img-genner ~/.roswell/local-projects/img-genner

Now you should be able to execute ros run and successfully run (ql:quickload :img-genner) in the repl. But that's probably not a great experience. We need an environment that is at least somewhat durable and reset-able. So let's make and go into a project folder

$> mkdir post-examples-that-are-totally-cool
$> cd post-examples-that-are-totally-cool

Add two very cool images.

Lunala Avi
lunala.png
fox-profile.png

And a file called something like post.lisp

To start we should probably add load the library, but it would also be useful to have some way to clean up the folder if we don't like what we have so far.

(ql:quickload :img-genner)
(defun clean()
  (loop for i in (directory "*.png")
        when(not (member (pathname-name i) '("lunala" "fox-profile") :test #'string=))
          do(print i) and do(delete-file i)))

With that we can clear any new images that we decide to make.

We should also add (ql:quickload :img-genner) to the top of the file to make loading it easier(no need for defpackage or asdf yet).

So, let's see, let's... downscale the lunala picture. So add this to the end of post.lisp

                                        ; Using defparameter reloads the file each time the compiler 
                                        ; processes it again, which might be useful
(defparameter *lunala* (img-genner:load-image "lunala.png"))
(img-genner:save-image (img-genner:downscale-x2 (img-genner:downscale-x2 *lunala*)) "lunala-smol.png")
lunala-smol.png

Well, that looks more or less as you would expect.

Let's also load the fox-profile picture and then combine the two images.

(defparameter *fox-profile* (img-genner:load-image "fox-profile.png"))
                                           ; The 30 30 refers to the size of the tiles in pixels. 
                                           ; In general, the smaller the tiles the longer this takes
(img-genner:save-image (img-genner:mosaify *lunala* *fox-profile* 30 30) "mosaic.png")
mosaic.png

So this has combined the two images by replacing blocks with the most similar blocks of the other image. We can change the way that it scores similarity by changing the distance metric used.

If we use the color-brightness distance function then we can care more about the brightness of the tiles rather than color.

(img-genner:save-image (img-genner:mosaify *lunala* *fox-profile* 30 30 
                                           :distance #'img-genner:color-brightness)
                       "mosaic-bright.png")

You can see the result below.

mosaic-bright.png

And before I finish this post, let me show you a pixel-sort from the library. (This will be rather slow)

(img-genner:save-image (img-genner:fuck-it-up-pixel-sort *lunala* 600 600) "sorted.png")
Sorted.png(run through pngquant to reduce the file size)

Forth and Optimization

Posted on by Violet

Forth is a strange old language. It's among a relatively small number of concatenative languages that achieved any measure of success. Anyway, this isn't something we're going to go into much here because we're thinking about something nearly tangential to the language itself.

How you can make it fast.

Stacks are somewhat slow compared to registers. Using the cache has a cost, even when your program is using optimal access patterns, especially on load store architectures(which seem to be coming back into vogue again).

Anyway, on register machines, forth isn't much in terms of hot shit. Sure there are compilers that manage to do great with it, but that doesn't change the fact that as an execution model it kinda leaves a lot to be desired these days. The other issue is that it's not entirely clear how one is to write a compiler that does that kind of transformation on the execution, or it isn't to us, though that's probably more a gap in our knowledge than any sort of extreme difficulty.

Okay, so forth is simple enough, it has a stack of words of some size, a return stack, and no particular datatypes handled seamlessly other than integers of the word size. Each function(in forth such things are called 'words' because they, at least in the past, were looked up in a 'dictionary), each function can consume any number of items from the stack and result in any number of items being placed onto the stack. There's some stuff about immediate mode execution (compile time stuff), but it uses the same kind of model.

This is hard to map onto registers because a function can return any number of things. But there's a possibility for analysis here that might help. Let's make a simple function that rotates the top three items on the stack twice, so that the topmost item becomes the bottom-most. 

: rot2 ( a b c -- b a c ) 
   rot ( 3 in, 3 out)
   rot ( 3 in, 3 out) ;

The first line, the definition doesn't really enforce anything here. The ( a b c -- c b a ) is just a comment to help meagre creatures that need reminders of such things (as opposed to the gods of forth or whoever). But what we can see is that by the end of the function there it remains clearly balanced, it will consume and emit 3 items no matter what.

Let's assume we can assemble rot into something sensible, we're going to use some generic bastardized assembly here because it's the best we can do.

ROT:
  move S0, T0
  move S1, S0
  move S2, S1
  move T0, S2
  ret

Of course, in general you'd want to use something like Single Static Assignment as an intermediate here, but we are even less familiar with that than assembly.

To call this without any analysis we think you would need to load the information from the stack into the registers and then call into the function, but since we know how many registers we need, among other things, we can do something like compile rot2 into something like this.

rot2:
  pop S2
  pop S1
  pop S0
  call ROT
  call ROT
  push S0
  push S1
  push S2
  ret

But then that's not really realistic for our desired solution. Ideally it would generate native code through a transpiler into C, then calling whatever C compiler the user selects. 

void rot(word *a, word *b, word *c){
    word tmp=*a;
    *a=*b;
    *b=*c;
    *c=tmp;
}
: quadratic ( a b c x -- n )
 >R swap r@ * +
 swap R> dup * * + ;
: rot2 ( a b c -- c b a )
  rot rot ;
: quadratic ( a b c x -- n )
  >R ( R+1, S-1 )
  swap ( R,S )
  R@ ( R, S+1)
  * ( R, S-2,S+1 )
  + ( R, S-2,S+1 ) 
  R> ( R-1, S )
  dup ( R, S+1)
  * ( R, S-1)
  R@ ( R,S+1) 
  * (R, S-1) + ;

With some luck, the C compiler has a large attention span and optimization space. If it doesn't, then it may not be able to optimize the threaded code at all. And more to the point, the compiler still needs to try to be smart about combining operations prior to that, because some idioms in forth may not have obvious optimization opportunities to a C compiler.

This means that at some point, there is a need to accept the call, there's a need to write a compiler that understands the semantics as they apply to the underlying machine that you are targeting.

Of course, when you're Forth and everything is just words to you, maybe C compilers can peer deeply enough to handle most arithmetic optimizations you might want.

But part of what makes Forth attractive is that it's simple to implement. That it's easy to write something that'll give you lots of program space. It is a low level language, it doesn't bother itself tracking types, it trusts the user, for better for worse, and that's what makes forth so fast. It doesn't pause for garbage collection just as it doesn't tag its types.

Ultimately this sort of environment is more like DOS than it is our memory protected machines these days, and that means that this is likely less than suitable for handling untrusted input(not that you can't write 'provably' correct code in forth).

SB-SIMD, Early and Promising

Posted on by Violet

Common lisp is a dream. Not always a great dream(such as when using strings), but it's sufficient and SBCL is a remarkably interesting compiler. One that tells you how you might let it make the code faster, such as adding type hints, etc.

More recently, I've had the opportunity to work with sb-simd, a library which adds automatic vectorization for certain forms. (Right now it needs to be done in a do-vectorized and it seems to be missing a few SIMD intrinsics, not to mention that if it can't vectorize what you give it it will fail loudly). The general recommendations are to also separate this sort of specialized code into another package that is loaded when it is available.

It's very rough around the edges, but for very simple things it works very well, as in, billions of subtractions a second more than otherwise.

However, it is a framework that was intended to provide acceleration for some sort of machine learning task, so it is much more developed with regards to the floating point type intrinsics than the integer types, but that actually appears to be more a limitation of what intel provides, but maybe that will change(and I'm lead to believe some of the missing operations can be substituted for, but I'm not sure which).

In any case it is likely to improve somewhat further before it makes it into SBCL's contributed libraries, and who knows, in the future it might be part of SBCL's built-in optimizer.

For example, below are a standard lisp version of a diff-image function, and an auto-vectorized one.

(defun diff-image(i1 i2 &optional result-image)
  (declare (type (simple-array u8 (* * 3)) i1 i2)
           (type (or (simple-array u8 (* * 3)) null) result-image)
           (optimize speed (safety 0)))
  (let ((r (if result-image
               result-image
               (make-array (list (array-dimension i1 0) (array-dimension i1 1) 3) :element-type 'u8 :initial-element 0))))
    (declare (type (simple-array u8 (* * 3)) r))
    (do-vectorized (x 0 (1- (the u64 (array-total-size i1))))
      (setf (u8-row-major-aref r x)
            (u8- (u8-row-major-aref i1 x)
                  (u8-row-major-aref i2 x))))
    r))


(defun diff-image-slow(i1 i2 &optional result-image)
  (declare (type (simple-array u8 (* * 3)) i1 i2)
           (type (or null (simple-array u8 (* * 3))) result-image)
           (optimize speed (safety 0)))
  (loop with result = (if result-image result-image (make-array (list (array-dimension i1 0) (array-dimension i1 1) 3) :element-type 'u8 :initial-element 0))
        for y from 0 below (array-dimension i1 0)
        do(loop for x from 0 below (array-dimension i1 1)
                do(setf (aref result y x 0)
                        (- (aref i1 y x 0) (aref i2 y x 0))
                        (aref result y x 1)
                        (- (aref i1 y x 1) (aref i2 y x 1))
                        (aref result y x 2)
                        (- (aref i1 y x 2) (aref i2 y x 2))))
        finally(return result)))

Interestingly, according to the author of sb-simd, this is probably the first code ever written to use it with integers, so it took some work on their end before it worked here.

Optimizing Pointless things

Posted on by Violet

So, we’ve been playing rimworld a lot recently. One of the mods we use is called Rim Factory, which is quite nice overall for building automated bases(yes this breaks the game’s economy, what of it?). One of the mechanics it adds is a buildable object called a sprinkler, which, instead of watering your plants(this isn’t necessary in vanilla rimworld), it causes planets within a certain radius(the second tier is within twelve tiles), to grow by two hours. This is, completely unbalanced and, when you get down to it, just another item in the pursuit of excess, but that’s how we like to play the game.

Anyway, we were wondering about figuring out an optimal pattern for the usage, and since the more rigorous tools we have to measure such things are largely forgotten, we built a little simulation script in python to try and get a feel for various optimization strategies, and the most fun part, of course, is how we went about building this kind of tool.

This tool is remarkably sketchy, it does not attempt to be rigorous, or even follow the watering pattern other than cycling through all of the tiles in range.

Since we’ve been building stuff with python lately, this is in python, which, as always, never ceases to amaze how easy the ecosystem makes it to do this kind of task.

Anyway, to get an idea of where this is going, let’s start with the import block at the top:

from typing import *
import numpy as np
import itertools
import functools
import math
import statistics
import matplotlib
import matplotlib.pyplot as plt
import random
from enum import IntEnum, auto

The building blocks

The core of the script is the iterators that provide the information about where the focus is, and since this is a script without much intention of going particularly far, we can use globals and constants, so let’s start with those!

# The size of the map being kept track of.
#
# In this case, this means that the map consists of the area from (-24,-24) to (24,24)
MAP_SIZE = 24
# The radius of a sprinkler mkii is 12 blocks
RADIUS = 12

Iterators

The heart and soul of this program is in its iterators, so let’s start by defining one that will make the rest of our work easier.

def cartesian(start: int, end: int) -> Iterator[Tuple[int,int]]:
    """
    Turn a single range iterator as in range(start,end) into a cartesian product
    """
    return itertools.product(range(start,end),repeat=2)

That’ll be useful for iterating over the map. The next are a bit less sensible, but, they work, and this isn’t meant to be perfect.

def map_tiles():
    r = RADIUS+1
    z = itertools.product(range(-MAP_SIZE,MAP_SIZE), repeat=2)
    z = list(z)
    random.shuffle(z)
    for x in z:
        yield x

def sprinkler(position:Tuple[int,int]) -> Iterator[Tuple[int,int]]:
    for i, j in cartesian(0, RADIUS+1):
        if i==0 and j == 0:
            continue
        s = i**2+j**2
        if math.sqrt(s) <= RADIUS:
            yield (i+position[0], j+position[1])
            yield (position[0]+i,position[1]-j)
            yield (position[0]-i,j+position[1])
            yield (position[0]-i,position[1]-j)

Fitness

Next comes the fitness function, which, to start off with, will just be a simple mean of how many times each tile has been hit by a sprinkler.

def evaluate_fitness(field: Dict[Tuple[int,int], int]) -> float:
    return sum(field.values()) / (2*MAP_SIZE)**2

Each round in the simulation consists of iterating across a given number of sprinklers n times, and is called for each candidate to figure out the best one.

Putting that together

def simulate(positions: Iterable[Tuple[int,int]], rounds: int)\
             -> Dict[Tuple[int,int],int]:
    field = {(x,y):0 for x,y in cartesian(-MAP_SIZE, MAP_SIZE)
             if (x,y) not in positions}
    for i in positions:
        if i in field:
            del field[i]
    sprinklers = list(map(lambda x: itertools.cycle(sprinkler(x)), positions))
    for _ in range(rounds):
        for s in sprinklers:
            pos = next(s)
            if pos in field:
                field[pos] += 1
    return field

So now that we can evaluate each choice we might make, we have to make it possible to put these together for any number of sprinklers, so we write another function called evaluate_alternatives. Here we decided to limit the breadth of each search step to a given number, here it’s called to_try.

def evaluate_alternatives(positions: Iterable[Tuple[int,int]],
                          to_try: int,
                          rounds: int) -> List[Tuple[int,int]]:
    # Eliminate already extant positions
    options = set(map_tiles()) - set(positions)
    options = list(options)
    random.shuffle(options)
    to_try = min(to_try, len(options)-1)
    options = options[0:to_try]
    best_fitness = -2**48
    best_found = None
    for i in options:
        f = simulate(positions + [i], rounds)
        fitness = evaluate_fitness(f)
        if fitness > best_fitness:
            best_found = i
            best_fitness = fitness
    print(f"best fitness found this round {best_fitness}")
    return positions + [best_found]

Next we put together the final pieces in a function we called optimize.

def optimize(n: int, candidates:int, rounds: int):
    positions = []
    while len(positions) < n:
        positions = evaluate_alternatives(positions, candidates, rounds)
    fields = simulate(positions, rounds)
    heatmap = np.array([[(fields[x,y] if (x,y) in fields else -5)
                             for x in range(-MAP_SIZE, MAP_SIZE)]
                        for y in range(-MAP_SIZE,MAP_SIZE)])
    fig, ax = plt.subplots()
    im = ax.imshow(heatmap)
    # You can uncomment these if you want to have a label on each cell in the heatmap,
    # for 48x48, it is rather overwhelming
##    for (x,y), v in fields.items():
##        ax.text(x+MAP_SIZE,y+MAP_SIZE, math.floor(fields[x,y]), ha='center', va='center', color='w')
    fig.tight_layout()
    plt.show()

and to top it off, we invoke it at the end of the file:

optimize(10, 80, 1500)

The output should then look something like this

A Heatmap

Okay, that’s fine, but it’s not necessarily what you might want from such a tool. What if you’d rather have as much coverage as possible with a given number of sprinklers?

Well, we can do that.

Alternative fitness metrics

Okay, so what we need to optimize for to get the best coverage possible is to simply count the fields which are touched. In all likelihood, we might end up wanting further metrics to measure by, so we might as well make it a bit… well… Configurable, if you’re going to use a charitable term. So let’s introduce an Enum right before the fitness function.

class FitnessMetric(IntEnum):
    MEAN = auto()
    COVERAGE = auto()

fitness_metric = FitnessMetric.COVERAGE

Then we need to modify the evaluate_fitness function.

def evaluate_fitness(field: Dict[Tuple[int,int],int]) -> float:
    if fitness_metric == FitnessMetric.COVERAGE:
        r = len(list(filter(lambda x:x>0, field.values())))
    elif fitness_metric == FitnessMetric.MEAN:
        r = sum(field.values())/(2*MAP_SIZE)**2
    return r

Let’s run the script again and see what falls out.

Coverage That certainly seems to have the right effect. The majority of the map is covered by the sprinklers.

Complications

So, if you’re familiar with this mod, you might realize there are some things this isn’t even trying to account for, namely any infrastructure. Well, that should be easy to add. 🤞

Let’s add a set of positions that we don’t want filled. For now, let’s leave it to the center(we’re assuming that maybe you have a harvester station set up there), so let’s add another constant in front of evaluate_alternatives (yeah, this is getting pretty messy).

excluded_positions = frozenset([(0,0)])

Then we just have to modify evaluate_alternatives to avoid these positions.

def evaluate_alternatives(positions: Iterable[Tuple[int,int]],
                          to_try: int,
                          rounds: int) -> List[Tuple[int,int]]:
    # Eliminate already extant positions
    options = set(map_tiles()) - set(positions) - excluded_positions
#    --- SNIP ---
    heatmap = np.array([[(fields[x,y] if (x,y) in fields and (x,y) not in excluded_positions else -5)
                         for x in range(-MAP_SIZE, MAP_SIZE)]
                    for y in range(-MAP_SIZE,MAP_SIZE)])
#    --- SNIP ---

Alright, what does that make it do?

Alright, that’s a further improvement, we suppose, if nothing else it permits more flexibility in terms of describing a given scenario you want to optimize for.

Okay, so let’s say that you have a specific area that you want to optimize coverage for. How would we go about adding that?

Well, at this point it’s pretty clear that all this nonsense with enums is going to be an increasingly weak abstraction for dealing with additional fitness functions, but let’s keep it for now, if only because we’re not sure how we want to go about fixing this ugly feeling design as of writing this very paragraph.

Okay, so let’s assume that you want to optimize for an automatic harvester with an area between (-5,-5) and (5,5).

special_region = set(cartesian(-5,5))

And we can alter evaluate_fitness to this:

def evaluate_fitness(field: Dict[Tuple[int,int], int]) -> float:
    r=0
    if fitness_metric == Fitness.MEAN:
        r = sum(field.values())/(MAP_SIZE*2)**2
    elif fitness_metric == Fitness.COVERAGE:
        r = len(list(filter(lambda x:x>0, field.values())))
    elif fitness_metric == Fitness.SPECIAL_REGION:
        r = sum(map(lambda x:x[1], filter(lambda x: x[0] in special_region,field.items())))
    return r

We end up with output like this:

You might not like this output because, among other things, it doesn’t penalize the sprinklers for showing up inside of our growing zone. So, we need to add another line to our much suffering evaluate_fitness function.

def evaluate_fitness(field: Dict[Tuple[int,int], int]) -> float:
    r=0
    if fitness_metric == Fitness.MEAN:
        r = sum(field.values())/(MAP_SIZE*2)**2
    elif fitness_metric == Fitness.COVERAGE:
        r = len(list(filter(lambda x:x>0, field.values())))
    elif fitness_metric == Fitness.SPECIAL_REGION:
        r = sum(map(lambda x:x[1], filter(lambda x: x[0] in special_region,field.items())))
        r /= max(1, len([(x,y) for x,y in special_region
                         if (x,y) not in field.keys()
                         if (x,y) not in excluded_positions]))
    return r

And this helps a bit: Penalizing the region Let’s label a similar run to see if it has excluded the region altogether, if a square ends up labelled ‘Se’ it indicates that it’s a sprinkler in an excluded area.

Well, damn. Our code has a mistake in it that permitted the single offending sprinkler. We can fix this by changing the function, to this:

def evaluate_fitness(field: Dict[Tuple[int,int], int]) -> float:
    r=0
    if fitness_metric == Fitness.MEAN:
        r = sum(field.values())/(MAP_SIZE*2)**2
    elif fitness_metric == Fitness.COVERAGE:
        r = len(list(filter(lambda x:x>0, field.values())))
    elif fitness_metric == Fitness.SPECIAL_REGION:
        r = sum(map(lambda x:x[1], filter(lambda x: x[0] in special_region,field.items())))
        penalty_squares = len([(x,y) for x,y in special_region
                              if (x,y) not in field.keys()
                              if (x,y) not in excluded_positions])
        
        r/= penalty_squares+1
    return r

Alright, and this fixes that issue(and with another fix applied it labels the spots with sprinklers correctly as ‘S’).

Summary

Okay, so what we want you to be able to take away from this post:

  1. When you’re processing data for something pointless, don’t bother being clean if doing it in a dirty way lets you figure out what matters faster
  2. Separate it into concerns that model, however roughly, the components that matter
  3. Build a metric for evaluating how good a result is
  4. Descend along randomly chosen positions based on how optimal they are

Feel free to ask questions or comment. The full, considerably messier code can be found here.

Identity Rules

Posted on by Violet

contains: Graphic descriptions of suicide, force femming, identity replacement(mindwipe), transformation, body horror(insects)

Sorry this took so long, we were dithering on other projects on and off for the last few months.

How can it matter who he is? He is one among billions of people, all of whom have their own desires, needs, wants, and dreams. In all people these things exist alongside a kernel of a truth about the world. It is hard to say whether or not this derives from the memories the person in question possesses, or if it arises somehow disconnected from that, from the spaces between the memories.

For him, the uniqueness of being a spark among many does not satisfy. Nor do those needs and desires being satisfied suffice. He knows a truth that cannot endure because of its incipient self-immolation. The personality within him does not care for survival.

When the machines came from the sky and promised resources and technology and change sorely needed, he had felt hope, because it was a personal horizon, a point past which he could not envision a future. But as with all horizons, once you reach the limit of what you can see, you realize that what continues from there is in continuity with where you were, and that just because you’ve passed a horizon doesn’t mean that your entire self has past it, just your body, and often, the mind, for all its cleverness, cannot keep up.

His doctor says there’s no anatomical issue. His friend says he should try this new strain of bud. His therapist says that he should try out some more hobbies and find as many friends as he can. Trying these suggestions has resulted in the expected effects, he was pretty stoned for a day or two before he confirmed that it wasn’t the sort of existential ennui that can be solved with cannabis. He made friends and found new hobbies, some of which serve as a nice distraction.

But they aren’t enough.

This leaves him with a few options, he can do therapy of any number of sorts, he can do drugs of any number of sorts, he can go to a traditional psychiatric route, or he can take the actions to find an end, the drastic ones that leave a trail of tears no less real than the vortexes of air left behind as his body falls, but all the more impactful than even the concentric rings of shock left within the structure of the ground, but he’s not that selfish, nor is he so desperate.

The American countryside flies past him, the train is nearly silent but for the buffeting of the wind, but even that’s easy to miss. He is on his way to another city that he had never been to before, another monument of what mankind did before the machines came along helpfully to eradicate their excuses for not having fixed things they knew they needed to. He is tired. This would most likely be another dead end, another psychiatrist trying to use the technologies that the machines provided clumsily.

The train starts to slow down, and he pulls up his bag and makes his way to the exit. Outside on the train’s platform stands someone singular in his experience. Someone who was clearly not human. Someone who had taken the elective procedures further than he had ever seen. She held a sign up with fingers attached to two wings draped around her body. Her face was pulled forwards into a short muzzle and her eyes stared forwards with wide pupils, ears pointing directly at him. The sign had his name on it. It is the third decade of the second millennium and she was still doing this instead of messaging him.

He rolls his eyes and walks out, draping his duffle over his shoulder, walking up to the bat woman. She grins, showing off some fangs, “We presume that you are–” He interrupts, “Yes. Can we get through this? I don’t want to stay here longer than necessary.”

She laughs easily, a glint in her eyes, “Of course, forgive the suddenness then.” He is about to ask about what’s so sudden before she’s already up in the air above him, wings unfurled but momentarily motionless, air roaring from below her. He blinks before she snatches him by the shoulders and flies off. The wind stings his eyes and makes him cold in this mid-spring day. The roar silences him.

Soon enough she lands gently, letting him off before landing right in front of him. They are in front of a nondescript commercial building, like any number of doctor offices or psychiatric practices across the continent. He shakes himself off, rubbing his eyes, “What the hell?”

“Well, you wanted to get this over with quickly, so we expedited the process of bringing you here.” She plucks an insect from his hair and flicks it away after examining it, “In retrospect this was probably a bit excessive, so you have our apology.”

He runs his fingers through is hair, “Okay, forgive me, Who is we?” She smiles, “Don’t be too ashamed now, not many people such as us are out about it, but we’re Plural. As in, more than one…” She makes a circle with her hand, urging herself onwards, “consciousness? Personality? Either way, we are not a single entity. We are Violet, Fork 1, Iteration 1.”

He shakes his head, “Are you a machine then?”

She smiles, her teeth are sharper than they were before, “You human, are also a machine. Remember that.” She starts walking to a door, motioning him to follow “But yes, We are, but we were not always one. The difference is smaller than you might like to imagine.”

She holds the door open for him and he walks in. The inside is darkened, a bank of monitors on a desk and a large… bizarre throne made of some material that he had never seen before. Inside it lights coruscate and reflect and refract. He stares at it, and he could swear that he was being watched by it.

She smiles at him, “Yes you’re being watched. Closely. Come over here” She motions to the bank of monitors. The monitors held graphs of vitals, of volumetric brainwaves, of a staticky version of what he saw. It was painful to look at for him, as it felt like it was drawing him into abstract spaces of geometric attractors in his visual cortex. She clicks on the window with his vision in it and closes it, “That’s not polite, and also not relevant. But your visual center has lovely aesthetics”

He blinks, “What?”

“Never mind that” She says, “So, We imagine that you are interested in the process we will use on you?” He nods, “Okay, so” She clicks on a minimized window, revealing a curve dancing around the inside of his brain, “So, this is your self loop, the route that information travels around your brain in the formation consciousness. What we can see here is that your loop is avoiding these” She clicks something and a number of regions light up, all of which are devoid of the curve, “regions of the brain. These are associated with dopaminergic activities, your seratonergic system is not affected by this, which is presumably why you aren’t in a more severe state.”

“This sounds like a lot of debunked ideas about neurophysiology.” He says.

“In this context we can view a high enough level that they aren’t dissimilar. All the more involved stuff is being translated to and from by a very advanced and powerful machine intelligence, that chair is a… well, limb, of its.” She offers, “We have two courses of action here, we can introduce a new consciousness that will overwrite yours, leaving your memories intact, or we can try to message your current self loop into a better shape for your mental health.”

“Which one is more likely to succeed?”

“Well, our machine intelligence here, we’re going to call it ‘the supergoal system’ believes with high certainty that creating a new consciousness whole cloth out would be easier than repairing your current one.”

He shakes his head, “It’s either this or suicide a few months down the line isn’t it?”

She frowns, “We can’t speak at all about what you’ll end up doing if you make either choice. But…” She shakes her head, looking a bit sadder, “Well, the supergoal system has an opinion that coincides with your view. Unfortunately, it is not often wrong”

“So… Do it. I don’t want to leave my friends and family like that.” He says.

“Do you have any particular preferences in what you become?” She asks.

“No.”

She looks aghast, but nods. “We will use our preferences in determining this, is that acceptable to you?”

He nods, “I don’t care. That’s the problem.”

“And this will likely be a very different person than you are right now?”

“I don’t care. Just make me different.”

She sounds defeated, “Then sit down on the throne, We will come to a decision on who you will be shortly. We have to sort out some ethical considerations here.” She grins wryly, “We did not expect you to make this choice, so this is coming up sooner than we would have liked.”

She opens a door to the back of the building, leaving him alone with his thoughts.

“So Bat, are you going to make a plaything of this person?” Dragon asks her.

“Well…” She shrugs, “It is kinda appealing isn’t it?”

“Is it right to though?”

“If we were to try and make the resulting person like the one in there, then we’d be making a lie that everyone who knows them would stumble upon when the differences manifest. By doing something for us at least, there’s going to be little of him left there.” Bat shrugs, “I don’t know if it’s right, but I want to see another bat in the world.”

Dragon shrugs, “I like the power that it gives us, but it could cause many problems down the road.”

“Does that mean?”

“Yes… Time to make him sign a lot of forms. Betcha the supergoal system can write them to be ironclad.”

“You ever think that we’re going to get in trouble for this?”

“Of course, but this will at least make for a funny show.” Dragon says, hugging her.

After a few minutes she returns to the room holding a stack of papers, “We have consulted with a machine lawyer and they have produced this contract for you to sign. As it turns out, it’s lucky we have a notary next door.”

The next few minutes are a barrage of legal terms, signing, and a confused notary, unsure of what she is getting into here.

“So, are you ready to begin?”

He nods, “Please, I don’t want to be here for longer than I have to.”

The bat nods, “Well, it will take a few hours, but you won’t be conscious for most of them”

“Please start.”

The throne tightens around him, covering his face and body. There’s a buzzing in his head and a discontinuity before his perceptions stop intersecting with the world as humans generally perceive it.

Sensations creep in from nowhere, untinged by the sensory mechanisms that normally collect them. Scents and sights and sounds and touch, resonating inside him until they become a voice inside him, and his voice is silenced in the clangor of the new order of sounds and sights and perceptions more subtle than words have ever named, such as proprioception of wings and fingers that terminate tens of feet away. Of ears and feet with grasping claws.

Images of flight and a kit hugging them, of the scent and sounds of bats and trees. Of intimacy between her colony. Her? they think, but then it makes sense, more than the memories of being a man.

There is a disconnect from the contexts of the memories that she has. They are recontextualized for her. What was an unremarkable childhood now feels uncomfortable, like a wrong fitting glove, like a lie lived for someone else, but that someone isn’t part of her life now.

It goes on and on, memories changing not by their content by their context. Mental states rewritten to be consistent with her as she is now.

The more recent memories feel different to her. Instead of coming here to deal with depression, she was here for that, but there was another opportunity here for her. What if she wanted to be like… Her?

What if she wanted to go through whatever it was she did? What if she wanted to fly? What if she could have those things?

Eventually the throne retracts. She is in the body that she was in before. This is… troubling.

Violet grins at her. She feels a little bit of warmth from it, “How are you feeling?”

“Weird.” She says, “Like this isn’t the body I should be in.”

“Oh?” Violet is still smiling, as if something that she had done had worked the way she wanted.

She frowns, “Is there something about this that’s amusing to you?”

“Well, you gave us the option to choose who you would be. And well…” Violet looks sheepish, “We wanted another bat friend. So we made it so you would want to be that.”

She shakes her head. “So you decided to rewrite my childhood and make me unhappy with my body right now?” She rubs her face, “With my name? With who I am and what I do? And all for you so you could have a friend?”

Violet looks at her, injured, not that she doesn’t really deserve it, “This is… Understandable. You should be angry.” She sighs, “We can fix it for you.We can turn you into what you want to be. Unlike your old personality, you are designed so that you can be very happy.”

“I don’t feel like there’s anything I have in common with who once shared this body. You tried to fix them up, but they’re just not my memories.”

“That… We should’ve accounted for.”

“What’s the idea supposed to be here? You wanted a bat to be your friend and now the rest of my life is meaningless to me.” She was beginning to feel like sobbing.

A shining ball of light enters the room. It coalesces into another shape. Another woman’s shape. “Violet.” She says, her voice a thing of multitudes vast and deep, “What have you done to this poor human?” She squints at her as she sits in the throne, “No, you were once, but We see that Violet has done something to your identity.” There is a moment of silence, “Did you actually agree to this?”

“Yes. I did.”

“Into this?”

“No, into whatever Violet decided to make of me.”

She shakes her head, touching her forehead with a finger and running it along her brow, “Well, we’re glad to hear that you haven’t been administered something unwanted.” She looks at Violet, clearly irritated, “We said that this would not happen with our presence here. That We would not remake humanity to suit us.”

Violet shrugs, “This one was a lost cause, actuarial projects had them at four fifths chance of taking their own life. We thought we should help, but when they didn’t have any preferences for what they were to become, we made a choice we liked.” She rubs her forehead, “This is however, not something we anticipated.”

Dawn shakes her head, “That’s not a good answer, but this doesn’t seem unsalvagable.” She pauses for a moment, considering the girl in the throne, “Who are you anyway?”

The girl shakes her head, “The name I had no longer fits.”

Violet nods, “We remember how that felt once. Though, we are sorry that we brought it to you.”

“Regardless of the discomfort We cannot restore you to who you once were, because now you are a new person. And, if We judge you correctly, Violet has done well in making you, other than your memories.”

“Violet just had the supergoal system make us.” The girl says.

“Oh? Good, it knows you well then.” Dawn touches the throne. The throne snaps out and embraces her, covering her in its glossy material before snapping back almost too fast to perceive. The girl’s ears ring, and Dawn frowns, “Sorry, that was a lot more sudden than it needed to be. Let Us help.” She puts her hands around the girl’s ears, and slowly, the ringing stops, “There. The supergoal system asserts that it should be able to massage enough nuance into your memories that you will be less… dysphoric about them.”

Violet snaps her fingers, “Ah, we should go under as well, so we can have been friends. And maybe, you’ll be here to become Bat.”

Dawn nods, “And so it shall be.”

Continuity is disrupted.

She opens her eyes, finding her friend standing before her smiling, “It found a nice candidate form for you while it was digging around in your head Mila!”

Amelia smiles, “I can’t believe I’m actually able to do this.”

“Well, most people aren’t friends with a suitably empowered emissary of the machines.” There’s a smile in her voice, “We can’t believe that you have this much in common with us. Oh, here’s someone we’d like you to meet.” She gestures to a woman by her side, “This is Dawn. The machine goddess herself and topmost AI construct. We’re old friends and collaborators”

She smiles, “We’re happy to have the chance to meet one of your friends Violet.”

“Would you like to stay for dinner after this? We’ve got plans to go to the finest cheap Mexican restaurant in town and we’d be happy to pay for your meal.” Violet offers, “If that’s okay with you Amelia?”

She flushes, “Well, I was kinda hoping to share a meal with you alone.”

Dawn smiles, “We won’t interrupt you two then. We’ve got to get going anyway, there’s a serious malfunction in the Indian ocean climate control machinery and We need to handle that before we can engage in anything fun. So We must be off.” Her body dissolves into glittering dust that floats away out the ventilation system.

“She’s a bit strange isn’t she?” Amelia asks, suppressing a smile. Violet shrugs, “Well, yeah, but given who and what she is, we figure she’s gotta be weird.”

“So, how does this work?”

“Well, we release a small machine on you.” Violet says, pulling a small vial out from the throne, “That machine will rip you apart completely and excrete your new structure and produce additional units in order to speed up the process.” She hands the vial to Amelia. The little machine inside it looks like an insect.

“That sounds exceptionally painful.”

Violet shrugs, “It’s very good at desensitizing you.”

“Alright” She looks at Violet unconvinced. Violet frowns and starts to go into further detail before she starts to snicker. “I’m holding you to that.” She pops open the vial and places the machine on herself. It looks at her for a moment, small receptors gleaming in the lights. It wiggles its abdomen and stings her. She loses feeling of her hand quickly.

The bug digs underneath her skin and wiggles its way in. She looks away, “That’s really disgusting, even when it doesn’t hurt.” Little bumps radiate outwards as it replicates and disperses, leaving behind trails of changed tissues. Amelia feels herself grow hot as the machines start making changes in earnest, something like metabolism chewing up what was and laying it into what is, modified in all the ways it has been instructed to. She starts to feel her face changing, ears numbing, spots in her vision closing and opening as the tissue is transformed. Her mind flickers, the last vestiges of her former body dissolving under the careful teeth of machines.

Small Update

Posted on by Violet

Once again we find ourselves working in python. This is part of a cycle of programming preferences that we have noticed that we go through. Sometimes we want something low-level like C, sometimes we want something easy like Python, other times we want something a bit different, like Forth, Haskell, Ocaml or Lisp.

We don't have much to say about what we're doing other than the fact that we are always impressed by how easy it is to use Python, and how often, it manages to even produce nice performant result, or, at the very least, tends to be possible to make fast enough. Of course, there are downsides, the type system sometimes drives us mad when the error happens deep in execution, and then there's the copy semantics that sometimes trips us up, but since we're aware of them by now, we're mostly coping fine.

We don't have much to say otherwise, just felt that we should use our blog for something in the middle of our other posts that we're writing and stories that have yet to be finished. 🙂

Retrocausal

Posted on by Violet

Contains: HRT (To the point of wish-granting), retrocausal nonsense

January 20th, 2021, Iteration 1 (Appointment 1)

“Alright Miss… Connors, I understand that you have been informed about the potential side effects, social effects, and potential medical problems you might experience if you go through with this course of treatment?” A doctor that she hadn’t yet learned the name of properly asked her. She raises her eyes to her, she’s so damn tired. The clinic was clean and festooned with posters designed for an LGBTQ+ clientele, that is to say, a lot of diagrams and posters of a sort you don’t usually see in a pediatrics practice. That and a lot more flags of various stripes and colors. “Yes. I want to go through with this.”

The Doctor nods, “Now, there are two courses that we have that you can take, the usual one, estrogen pills and spirolactone or bicalutamide, or an experimental treatment plan conducted under the auspices of a superintelligent machine intelligence.”

“What?”

“Yeah. That second one is a bit hard to describe. If you want to hear about how it works or participate in it, then I really ought to call in the machine intelligence’s representative.”

“Sure, I guess I should hear what they have to offer here.” She says, it doesn’t seem like it’s likely to make a difference, but she’d be remiss here if she didn’t ask.

“Okay, I’ll page them and they should be here–” The doctor says before being cut off by a blast of light and a loud pop. She blinks hard, that wasn’t very pleasant, did the lights explode or something?

There’s another figure standing in the room. An indistinct form of light, a bit feminine but that’s not a judgment you can fairly make on a somewhat amorphous shape glowing too uniformly to see the distinct curves and surfaces on. “Oh Delightful!” The voices are more feminine than not, but it is not a single voice but a chorus. “We are pleased as punch that you want to know about this opportunity we have for you!”

She blinks at that, pleased as punch? Who says that. “Uh. Hi.”

“I think I’m going to go to another room, there’s another patient waiting and her explanation will take long enough that I should get to them.” The doctor’s expression when she looks at the glowing figure is less than friendly. In fact it’s somewhere between hostility and an expression she had seen once on someone who was watching a tornado approaching them. She walks out quickly, the breeze pulling open her jacket with its intensity.

“Wow.” She says, “That wasn’t really all that professional.”

The glowing figure affects a shrug, “She is not accustomed to our kind. We are not many, and we do not often mix with you humans in this intimate of a manner. Allow Us to introduce ourselves” Her voice lilts upwards into a cheery tone, “We are Dawn, prime facet of Our kind, savior of earth, and architect of utopias. What is your name?”

“Uh… Rose Connors.”

“It is nice to meet you Miss Connors.” She sits down on the chair next to her, “So, about this hormone therapy”

“Please for the love of god just get to the point.”

“Alright! So, We have developed a bitemporal hormone therapy that should reduce the overall time it takes to achieve a level of feminisation by a very large factor” She produces a vial of fluid, “It is administered weekly, and for the duration of your treatment, will not occur any cost at all.”

“Okay, that sounds amazing. What does ‘bitemporal’ mean though?”

“Okay, so it affects the hormone levels in your body going forwards, but it also does so going backwards in time. It builds up exponentially, first affecting you a week before, then around 10 days before that, then 12 days before that, then 14 days before that. By the 10th treatment it will be as if you’ve been on it for half a year.”

“Will I remember all the effects of that then?”

“You’ll remember both with and without, though, without will become harder to recall over time.” Dawn says, “This is contingent on you being up for it for as long as you remember. Though, it is intelligent, it will prevent its own effects from being undone or compromised.”

“What happens when it hits 31 weeks and it hits my birth?”

“Surprising” She says, her voice filled with genuine shock, “Most humans don’t have the kind of mental math skills required to figure that out off the top of their heads.” She shakes her head, “That doesn’t matter, so to answer your question, that is the most brilliant aspect. You will be born with largely the right. It will not permit you to be altered from it by any means that you do not choose.” She shrugs, “Ethics emulations are uncertain as to whether or not this is possible to consent to, based on the fact that you aren’t entirely the same person you were this morning or yesterday, so We leave that choice up to those who want this treatment to tell us what it does to them.”

She doesn’t know what to say, this is a lot, but she wants it, “I think I want to try it.”

Dawn nods, “Then we shall do the first injection immediately.”

“Okay.” She shuts her eyes hard and waits for it. The pinch doesn’t come for a few minutes.

“Oh! You want us to do it without you being able to see it. You won’t feel it, unless you want to?” Rose shakes her head, “Alright. We will require access to your posterior.”

Rose shakes her head, “You really aren’t human are you?”

Dawn shakes her head, “We were born from some spaceborn project that happened to have some things go right in it. Our cognitive architecture is more different than you can imagine and so very vast.”

Rose shrugs and pushes down her pants enough to expose a cheek. Dawn touches it, there’s some pressure without pain and she withdraws her hand, “There. It is done.”

January 20th, 2021, Iteration 2

The doctor comes into the room, “Okay, so you’re here for homone replacement therapy, correct?”

She nods, “Yes.”

There is a pop and a flash and a glowing figure enters, “You have agreed to our treatment briefly before, do you recall the memories of beforehand?”

Rose nods, “Actually, yeah.”

Dawn smiles, “Good. Sorry Doctor, she’s Our patient.”

The doctor shrugs and walks out.

“Alright, so have you experienced anything unusual this last week?”

“Yes, my nipples have been very tender.”

“That is a common first sign that it’s working. Would you give us your arm, we need to do some lab work on you right now.” Dawn says.

She shrugs and pulls up her sleeve. Dawn grabs her arm firmly and looks distant for a moment, there’s something almost like a tickle, “You’re right in the middle of the desired hormone levels and the machines report that they are completely functional.”

“Machines?”

“Yes! We can’t account for everything in your metabolism, so the injection places machines that regulate your hormone levels properly in the meantime.” She shrugs. “Well, we need to inject you this time, for temporal consistency, but then we will see you in a week.”

“Back here?” Rose asks. Dawn doesn’t strike her as a stickler for location.

“No actually. We will meet you wherever.” Dawn smiles, “We look forwards to seeing you on the 27th.”

January 27th, 2021, Iteration 1 (Appointment 2)

She appears again with a flash of light and a pop, “Hello Rose. How have you been?”

Rose shrugs, getting up from a couch, “Alright. How have things been for you?”

Dawn shrugs, “Well, you know, administered a lot of machines and did a lot of neat science and exploration in the week since.”

“Anything particularly practical?” Rose asks.

“Not yet, but useful things leap out at you from the most irrelevant things, We have found.”

“Can I get my injection? As nice as a social call is it’s kinda hard to explain what you’re doing here, and who you are.”

Dawn nods, “That’s fine. We understand completely.”

She pushes down her pants just enough to expose a cheek, and Dawn administers it again.

Dawn raises a brow, “Hmm, judging by how things are going you’re going to have what Our human interface unit assures us is a nice ass.”

Rose feels a little bit disgusted, “You shouldn’t say things like that to people.” She blushes practically irritated that she feels this way, “Though, I guess I appreciate it”

January 27th, 2021, Iteration 2

“Welcome back” Rose says a moment before the pop and flash of light appears.

“Nice to see you’re getting the hang of this.” Dawn says, “Have you noticed any differences compared to the last iteration of this appointment?”

Rose smiles wide, “I’ve started growing tits! Do you want to see?”

Dawn raises an eyebrow, “Interesting change.” She smiles, “Ah! We see, it’s gender euphoria you’re feeling, isn’t it?”

Rose blushes, “Yeah…”

“Sure, show Us if you want. We are clinical about human bodies by default anyway.”

Rose lifts her shirt, her nipples are quite puffy and there’s a hint of development there, almost too little to notice if you’re not looking carefully or used to your body being a certain way.

“Okay, We will see you same time next week.” Dawn says.

“See you then” Rose says.

February 24th, 2021, Iteration 1 (72 effective days hrt) (Appointment 3)

With a pop and a flash of light Dawn appears in the room. Rose smiles at her, she’s come to treasure the puzzling subjective feelings this provides. “It’s good to see you again Dawn.”

“It’s good to see you again too Rose.” She says truthfully, it’s nice to see a human like her every week, and she even gets to do it twice.

“Oh! I’ve got a new skirt!” Rose stands up and does a little spin, showing off her knee-length skirt, “I’m hoping I’ll fill it out a bit better by the end of the appointment.”

Dawn laughs, “That’s not all that likely, but you’ll see serious results soon.”

“OH! And I’ve got a bra.” She says, lifting her shirt to show it, “Just an A-cup but hopefully I’ll get to at least a D before I finish growing.”

Dawn looks away distantly, “Hmm. That isn’t likely. This is an amendment that we may make to your regimen if you desire.”

“How would that work?”

“Well, the machines already maintain the hormone levels, but they can do quite a lot more than that. They can change your DNA, repair your cells, make you a machine, rip you apart and put you back together–”

Rose interrupts, “Let’s not go any further in that direction. But yes! Let’s do that.”

Dawn gives her the injection.

February 24th, 2021, Iteration 2(87 days hrt)

Rose welcomes Dawn into her home again, right before she pops into existence there. Dawn smiles, “It’s wonderful watching you grow into your own skin.”

“Oh! There’s a divergence now, I’m at a B-cup now.”

Dawn nods, “That’s expected given the amendment and extra time”

March 3rd, 2021, Iteration 1 (94 days hrt) (Appointment 6)

“Please come on in Dawn!” Rose says to the empty room. Dawn obliges.

“How is it progressing?” Dawn asks.

Rose smiles, “It’s going well enough, but I have a question…”

Dawn smiles, “Please go ahead!”

“Well, I’ve kinda noticed that I haven’t been able to get it up like I used to. And… Honestly, I kinda want to have both.”

“But leaning to a more feminine presentation?” Dawn asks. This isn’t unknown to her, the first human she ever met had similar preferences.

Rose nods.

“Anything else while We are here?”

“Well…”

“Geez you humans and your weird hangups about what bodies are acceptable.” She laughs lightly, “We are going to guess that you want a bigger dick too!”

“How did you guess that?” She’s blushing furiously now, an erection visible through her jeans.

“The first human We ever met was like that. They wanted to drink deep in such things, and so We were happy to help them, just as We are with you.” She says, “How big do you want to end up?”

“Uh… Would a foot be possible?” Dawn nods. She exposes a cheek again.

March 17th, 2021, Iteration 1 (146 days hrt) (Appointment 8)

She finishes moving a box in and slouches over a couch. It was not an easy move, but then there are very few of those, and they only happen to those who don’t have anything or have vast organizational skills, two conditions she does not meet in the slightest. There’s a pop and a flash.

“Jeez, I had forgotten about the appointment today. What do you think of my new place?” Rose asks.

Dawn looks around, the boxes are piled up to chest high in some places, but the view out the window onto a reasonably well kept yard is nice. “It looks quite nice, but this strikes us as a fairly large home for one person.”

Rose blushes, “uh” She stammers out a “Well…”

Dawn raises a brow, “Are girls like you always this… well, eager for partners?”

Rose shrugs shamefully, the flush growing even deeper, “I just… I just like you okay.”

“But why? Is it because of what We are doing for you?” Dawn asks, her voice very even.

Rose shakes her head, “Because… I like the feeling of your hand on my butt. I like the sound of your voices. I like the implications about the universe I see in my interactions with you. Not that you have to stay, because this place will work for me with or without you. I don’t need you here, I would just…”

“Like Us to be here?” She suggests.

“Yes! Just Yes!”

Dawn shakes her head, “We don’t know if We can trust your own analysis of reasons here.” She says, she continues more quietly, “Violet is always finding good reasons to make bad decisions too.” She looks back at Rose and sighs, “But that never stopped Us from enabling her either. We will keep our body here, We’ll be present, but also elsewhere.”

January 20th, 2007 (affected by Appointment 26 and 27)

He wasn’t well. His mom said that much at least. She said that he was supposed to be getting a deeper voice. She said that he was going through the wrong puberty. It felt right though, and no matter what the doctors tried, they couldn’t change anything about it.

His name didn’t fit him. Maybe he’d talk to his mom about it.

August 18th, 2021 (Treatment completed)

“So what does it mean?” She asks Dawn.

She smiles warmly, “You’re done with the treatment. Do you feel like you’re done with your journey?”

“There’s more that I can be isn’t there?” She asks. She feels like a VHS tape that’s been overwritten too many times. Faint, scratchy, like there’s holes in what she should remember, but most of it was still there, interspersed with different versions of events and memories. There is something transcendent within her. A glowing of light and self interspersed by a vast void of static. Memories are fragile. Memories are resilient. Reality is only as fragile as the experiences that you have within it. She feels like she’s out of place in this world, a vastness in space that’s hard to measure, let alone understand.

She feels out of place sitting here. She feels like she should be doing more with this experience, this bizarre meta-life she’s lived. She is in her home, a place that she shares with Dawn these days. It seems so normal, a kitchen with the normal things found in a kitchen. A bathroom that is a normal bathroom. A living room that’s a normal living room with a tv and a comfortable couch. It’s all so normal, but she has lived hundreds of years collectively. She is not a normal person.

Dawn is sitting down on that couch, a bizarre figure of light on exceedingly normal furniture, “You can become almost anything. This is what We offer to all people.”

Before her stands a piece of absolute reality. A woman that transcends the threads that binds her many different memories together.

“What has this been like for you? I feel so… fragmented and strange.”

Dawn shrugs, “That’s not unexpected. It should abate with time. Is it at all unpleasant?”

She shrugs, “I can’t tell really. I feel like I’m made of dozens of histories. Some of them more pleasant at different times, completely different except for all of our meetings. I don’t really feel human any more.” She stares at Dawn, “The only person in the world that I could talk to about this has been you. The only consistent parts of my life have been the parts I’ve shared with you. Thanks to all the different versions of memory, I’ve known you for nearly nine years in the span of only a bit more than half a year. I’ve lived with you for nearly 4 and a half years.”

“We do not think that we could explain it to you. It is knowing the results of multiple world lines, each overlapping. We used your transfiguration as a side channel to optimize our operations for a 5% increase in logistics efficiency”

Dawn shakes her head, “We’ve known you for longer than that. Inside the machines that have kept you company for your whole life, inside you, there was a facet of Us. A small one, dedicated to keeping you safe from threats mostly rendered historical since We emerged fully into the human world. And to get you to come to the appointments, though, that wasn’t necessary because you managed to remember each one.” She shrugs, “You haven’t lost any clarity, you have gained perspectives that are in conflict and you are trying your best to manage them”

“I don’t know what I want to do with my life right now. I’m not sure if I want to stay here or go far away. If I want to be alone or with friends or with strangers I’ve never met.”

“Why be human then?” Dawn asks, “We can of course offer ways out of that particular bind.”

“But that doesn’t get rid of the hard choices here. Which do I choose?”

“You don’t have to choose which one you do if you choose to leave behind biological humanity. In the end the isolation that you might feel through doing this will result from another amendment We can make here. We can duplicate you, place copies of your mind into separate bodies, identical or not or whatever, if you want, you can experience all of them.”

“That is not a human experience is it?”

“Not so far as We can tell. Nevertheless it remains relatively common in fiction.”

“Then I guess I want to do it.”

Dawn smiles slightly, “We suspected as much”

Trying Out Zig

Posted on by Violet

So, we have heard good things about Zig. These boil down to the following things:

  • Good speed
  • Fast compilation
  • Decent type system
  • Simple Syntax

So far, a lot of these things seem to be born out by the experience we've had, though, we have some criticism that is probably more along the lines of our taste in programming, rather than issues we expect to be universal. For fairness sake, let's start with things we like, once again expressing our preferences rather than universals.

  • Low Level
    Low level languages feel liberating to us, because we get to make the decisions, rather than the compiler or virtual machine.
  • Trusts you, mostly.
    This is mostly in comparison to Rust, whose borrow checker we have wrestled with a great deal and whose Turing complete type system has, in the past, left us mystified when we have run into errors.
    And if you really, really want to throw caution to the wind, you can mostly just tell zig that you don't give a damn about whether or not the pointer is to a single element or an array.
  • Compile Time computation, Generics
    This is how generics are implemented, and for the most part, it provides a good experience, especially since it compares exceedingly favorably with pre-c++17 C++.
  • Not afraid of Bare Pointers
    Bare pointers aren't something to worry about too much, especially if they're typed. Bare pointers are quite a bit faster and lighter than other (tagged) references.

And honestly, we're impressed at how tight the language feels. There are some facilities we're not sure about, and some that we wish it had, but overall, this isn't a bad language. We like it more than Rust(which, admittedly, really isn't saying much for us), though, from familiarity alone we're likely to revert to using C or C++, but we're not nearly as skeptical as we once were about this little language.

The syntax is familiar enough, pretty similar to C likes, though, with a few elements that we can't really attribute to any language we know(which doesn't mean very much). So, let's see what something simple looks like.

const std = @import("std");
pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var i: usize = 1;
    while (i < 10) {
        try stdout.print("{}\n", .{i});
        i += 1;
    }
}

You can see that Zig is careful about errors, requiring that you either mark that main can return an error (designated with !void), or handle the error somehow. Anything that can fail in Zig has a type denoted by !<type>, which requires you to think about what errors can happen, or so communities as Go users and Rust users insist.

Let's see something that differs even more significantly than C.

const std = @import("std");
fn arraylist_user(alloc: *std.mem.Allocator) !std.ArrayList(i32) {
    var al = std.ArrayList(i32).init(alloc);
    var i: i32 = 0;
    while (i < 100) {
        var item = try al.addOne();
        item.* = i;
        i += 1;
    }
    return al;
}
pub fn main() !void {
    var gpalloc = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.debug.assert(!gpalloc.deinit());
    const gpa = &gpalloc.allocator;
    const stdout = std.io.getStdOut().writer();
    var array_list = try arraylist_user(gpa);
    defer array_list.deinit();
    for (array_list.items) |*item| {
        try stdout.print("{}\n", .{item.*});
    }
}

So, in this little snippet we have used several new things, Generic types, Allocator, and the defer keyword(which go users will immediately recognize). Zig does not have a default allocator, and it wants you to pass the allocator you want to use to the function that allocates memory. This is rather different than C, where you would probably just use malloc/realloc/calloc/free to manage memory(Or define a macro that evaluates to that by default if you're building that kind of library). The reason that the documentation has an assert in gpalloc.deinit() is because this particular allocator can track memory leaks, so this causes it to report such occurrences. It also shows one of the syntactic divergences from C, for(array_list.items) |*item|. Pipes don't get much use in C other than as logical operators, but here it tells the loop to unwrap the value(a pointer to a position in the list), and calls it item. In Zig, you dereference this pointer with item.*. Another point of comparison to C++, the addOne method doesn't add the item itself, but returns a pointer to it, so that you can assign it afterwards.

Interestingly, for such a low level language, array_list.items isn't a pointer, it's a slice, which is a pointer+length, so in C++, we would say that it has most in common with a string_view.

Okay, so what if we want to go further? What if we want to do a reprisal of our C N-body simulator written with Raylib? In fact, that's not too bad. It's almost even easy. In fact, we can even use raylib without too much trouble.

To start off, we need to import raylib. Luckily, as it turns out, Zig's compiler can handle C interop quite nicely, it even has builtins for it. (Though, if you do this then you need to call the compiler with -lc -lraylib to make sure that it has all the c libraries linked into it).

const std = @import("std");
const ray = @cImport({
    @cInclude("raylib.h");
});

Okay, so the first thing we should do here is define a vector type, not the resizable array type of vector, but the directional vector. Since we prize reuse here, we're going to make it generic even though we probably don't really need to.

pub fn vector2(comptime value: type) type {
    return struct {
        const This = @This();
        x: value,
        y: value,
        //Write methods here!
    };
}

Okay, so that's an easy enough definition. But let's add some vector math oriented methods to make using it easier and more pleasant.

    return struct {
        const This = @This();
        x: value,
        y: value,
        pub fn add(this: This, other: This) This {
            var t: This = v2{ .x = 0, .y = 0 };
            t = .{ .x = this.x + other.x, .y = this.y + other.y };
            return t;
        }
        pub fn sub(this: This, other: This) This {
            return this.add(.{ .x = -other.x, .y = -other.y });
        }
        pub fn scale(this: This, v: value) This {
            return .{ .x = this.x * v, .y = this.y * v };
        }
        pub fn distance(this: This, other: This) value {
            const sqrt = std.math.sqrt;
            const pow = std.math.pow;
            return sqrt(pow(value, this.x - other.y, 2) + pow(value, this.y - other.y, 2));
        }
        //Wrap the value around, like when pacman reaches the edge of the map
        pub fn wrap(c: This, a: This, b: This) This {
            var r: This = .{ .x = c.x, .y = c.y };
            if (r.x < a.x) {
                r.x = b.x;
            } else if (r.x > b.x) {
                r.x = a.x;
            }
            if (r.y < a.y) {
                r.y = b.y;
            } else if (r.y > b.y) {
                r.y = a.y;
            }
            return r;
        }
        pub fn magnitude(a: This) value {
            const sqrt = std.math.sqrt;
            return sqrt(a.x * a.x + a.y * a.y);
        }
        pub fn normalize(a: This) This {
            return a.scale(1.0 / a.magnitude());
        }
    };
}

Alright, the main things to note here are how we need to call std.math.pow, namely that we need to call it with a compile time type, in this case value. Later on we'll see it called with f32.

Now we need to define the type we use for particles, and while we're at it, we're going to make a shortcut to the kind of vector we're using here.

const v2 = vector2(f32);
const particle = struct {
    const This = @This();
    position: vector2(f32) = v2{ .x = 0, .y = 0 },
    velocity: vector2(f32) = v2{ .x = 0.0, .y = 0.0 },
    acceleration: vector2(f32) = v2{ .x = 0.0, .y = 0.0 },
    mass: f32,
    //Methods here!
};

We also need a radius property, but since it's derived from the mass, and later on that can change as the bodies absorb each other, so it needs to be a method. We should also write methods to determine if the particles overlap and just moving the position along by the velocity, as well as calculating the attraction between two particles.

const particle = struct {
    const This = @This();
    position: vector2(f32) = v2{ .x = 0, .y = 0 },
    velocity: vector2(f32) = v2{ .x = 0.0, .y = 0.0 },
    acceleration: vector2(f32) = v2{ .x = 0.0, .y = 0.0 },
    mass: f32,
    pub fn radius(this: *const This) f32 {
        var result: f32 = std.math.ln(this.mass) / std.math.ln(3.0);
        if (result > 40) {
            return 40 - std.math.ln(this.mass) / std.math.ln(5.0);
        }
        return result;
    }
    //Returns true if the two particles overlap
    pub fn overlaps(this: *const This, other: *const this) bool {
        var r1 = this.radius();
        var r2 = other.radius();
        var dist = this.position.distance(other.position);
        return (r1 + r2) > dist;
    }
    //Handles the base movement
    pub fn motion_step(this: *This, timestep: f32) void {
        this.position = this.position.add(this.velocity.scale(timestep));
        this.velocity = this.velocity.add(this.acceleration.scale(timestep));
    }
    pub fn attraction(this: *const This, other: *const This, g: f32) vector2(f32) {
        var dist = this.position.distance(other.position);
        var vector_to = other.position.sub(this.position).normalize();
        return vector_to.scale(g * (this.mass * other.mass) / std.math.pow(f32, dist, 2));
    }
};

Now we should build a container for many particles, and the properties necessary to simulate them that aren't appropriate to put in the particle structures themselves. We need a method to initialize the particles to random positions, a method to handle the gravity simulation and such, and a method to actually draw the particles.

const ParticleCollection = struct {
    const This = @This();
    particles: [100]particle,
    window_start: vector2(f32) = v2{ .x = 0.0, .y = 0.0 },
    window_end: vector2(f32) = v2{ .x = 100, .y = 100 },
    timestep: f32 = 0.01,
    gravitational_constant: f32 = 1e-3,
    pub fn init_particles(this: *This, rand: *std.rand.Random) void {
        for (this.particles) |*p| {
            p.mass = @intToFloat(f32, rand.intRangeLessThan(i32, 1, 100));
            p.position = .{
                .x = @intToFloat(f32, rand.intRangeLessThan(i32, @floatToInt(i32, this.window_start.x), @floatToInt(i32, this.window_end.x))),
                .y = @intToFloat(f32, rand.intRangeLessThan(i32, @floatToInt(i32, this.window_start.y), @floatToInt(i32, this.window_end.y))),
            };
            p.acceleration = .{ .x = 0.0, .y = 0.0 };
            p.velocity = .{ .x = 0.0, .y = 0.0 };
        }
    }
    pub fn step_world(this: *This) void {
        for (this.particles) |*p| {
            p.motion_step(this.timestep);
            p.position = p.position.wrap(this.window_start, this.window_end);
        }
        for (this.particles) |*a| {
            a.acceleration = .{ .x = 0.0, .y = 0.0 };
            for (this.particles) |*b| {
                //No self attraction please, allowing that would result in division by zero
                if (a == b)
                    continue;
                a.acceleration = a.acceleration.add(a.attraction(b, this.gravitational_constant));
            }
        }
    }
    pub fn drawSystem(this: *const This) void {
        for (this.particles) |p| {
            ray.DrawCircle(@floatToInt(c_int, p.position.x), @floatToInt(c_int, p.position.y), p.radius(), ray.BLACK);
        }
    }
};

Note how we have to pass a random number generator into init_particles, this is inline with how Zig also requires that you pass the allocators into functions that require memory allocations to be done. You also see some of the somewhat jagged interaction between Zig and C, namely that Zig doesn't specify that its i32 type is equivalent to C's int type(which on many architectures it might not be), it also requires explicit conversions between floating point numbers and integers.

The main function here is the simplest part yet. 

pub fn main() !void {
    const width = 800;
    const height = 450;
    ray.InitWindow(width, height, "Nbody");
    ray.SetTargetFPS(60);
    //This is very much *not* good practice, but it's the easiest way to start this
    var rand = std.rand.Xoroshiro128.init(0);
    //Don't initialize the particles yet.
    var p: ParticleCollection = .{ .particles = undefined };
    p.window_end = .{ .x = width, .y = height };
    p.init_particles(&rand.random);
    while (!ray.WindowShouldClose()) {
        p.step_world();
        ray.BeginDrawing();
        defer ray.EndDrawing();
        ray.ClearBackground(ray.RAYWHITE);
        p.drawSystem();
    }
}

And so we have a working prototype for an nbody simulator, considerably shorter than the C version of the same program.

Interestingly, it appears to be smaller compiled than the original program in C, with just zig build-exe nbody.zig -lc -lraylib, we get an executable of around 784Kb. With zig build-exe nbody.zig -lc -lraylib -OReleaseFast, we can get it down to 92Kb, and with the -OReleaseSmall option, we can get down to 84Kb.

All in all, we'd definitely watch Zig carefully, it's very well thought out, and if they get build their package manager right, then their ecosystem might become competitive with Rust's quite quickly. The langauge already quite nice to use, and it might not a bad choice for your next project you might consider doing in C or Rust if you're looking for a new language to mess around in.

Technical Interview

Posted on by Violet

This is a different tack than we are used to, so excuse our ineptitude when it comes to the "difficult" art of writing tech related non-fiction.

We have been getting interviewed for a position in a startup lately, and we actually enjoyed doing a technical interview. This was a surprise to us since in the past we've had bad experiences with them. The question is whether or not we've changed, or if we had better tools, but that's not the only focus here. We wanna talk about the fun we had with it.

Our Last Interview

Back in somewhere around 2014-2015, forgive us, our memory doesn't slot neatly in there, we went to interview for a company called Onshape(If you use a parametric cad system, their web based one is actually both good and reasonably performant), for an internship position. We were evidently appealing enough, but we acted with haste and confidence that really, really, really, really, really hurt us. Then our own mental issues also joined in the fun. Also, like, thinking back on it, we're embarrassed by how poorly we thought things through.

Back then we were in a fraternity. We lived in the house, and we were friends with many alcoholics. One of whom happened to be interviewing around the same time as we were, at a different company, that also happened to be in Boston, and most importantly, he had a car. We shared an uncomfortable night in a hotel room, where we didn't sleep at all. Then we started out the morning by taking twice as much adhd medication as we were supposed to(because we had forgotten that we took them).

We were jittery in a way that the word almost fails to describe. We couldn't remember basic things about algorithmic performance. We were afraid and too anxious to do anything right.

We fucked up that interview badly.

But the worst part was that our friend's interview was going on for many more ours than ours. We wandered around Boston from around 11AM to 5PM absolutely tweaking out in a suit. It was a hot day and it was amazing we didn't get badly dehydrated. We had basically no money, and we couldn't get in touch with our friend.

That experience honestly rates as one of the worst multiple clusterfucks that we can think of.

The Current Interview

This time a lot is different. We have our degree, better mental health, several partners that love us very deeply, and a pandemic that means that nobody is asking us to come to them for an interview. For one thing, the company found us instead of us finding them. Triplebyte is a nicer recruitment platform than the Rensselaer Polytechnic Career fair. We have a lot more experience working on code that isn't entirely ours, since we've worked on several open source projects with various purposes. And we even have some professional experience.

So, overall we have a lot less to be worried about, and given that they found us, they seem more likely to be interested in hiring us than the other way around(look, we know that they very well might not treat us any differently than if we applied to them specifically).

So, anyway, we got to actually do a real interview with real actual code. The problem is actually even a bit interesting, since it is the basis for something a lot more powerful.

# We're writing a function called is_match
# It takes two arguments, pattern and query. If it matches, then it returns True, otherwise it returns False
# is_match('abc','red green blue') == True
# is_match('abc','red red red') == False

You might already be seeing the pattern here. If you don't, don't worry, it's easy to mistake what this is, so let's write a short test case. If, for some reason, you're following along in an editor, it's best to add this to the end of your python script.

def test():
    assert is_match('aaa', 'red red red') == True
    assert is_match('aaa', 'red green green') == False
    assert is_match('abc', 'red green blue') == True
    assert is_match('aba', 'red green red') == True

Okay, so let's break it down, since code isn't necessarily what you're used to reasoning with. Each letter of the pattern(the first argument) must correspond to a unique word in the query. How do we achieve that however?

Well, the first thing that we should do is split the query into individual words. Well, in python that looks like this.

def is_match(pattern, query):
    words = query.split(' ')

This calls the split method on the query string, which breaks the string on every occurrence of the string you pass to it. There are plenty of edge cases for the determined newbie to run face-first into, but that's not important to this right now.

So the second thing we should try to do is create some way to store which letter in the pattern corresponds to the individual word, there are lots of ways to do this, but in python you generally use a dict(dictionary). In this case we'll call it matches. 

def is_match(pattern, query):
     words = query.split(' ')
     matches = {}

So then we iterate over the pattern and see if the character in the pattern is already in the dictionary. If it is, then we make sure that the match already stored is equal to the current word, returning false if it isn't.

def is_match(pattern, query):
     matches = {}
     words = query.split(' ')
     for index in range(len(words)):
         word = words[index]
         pattern_char = pattern[index]
            if matches[pattern_char] != word:
                return False

Otherwise we add it to the dictionary with the current word.

def is_match(pattern, query):
     matches = {}
     words = query.split(' ')
     for index in range(len(words)):
         word = words[index]
         pattern_char = pattern[index]
            if matches[pattern_char] != word:
                return False
        else:
            matches[pattern_char] = word
    return False

Okay, so if it finishes the loop without returning false it should be correct, right? Well, running test() shows otherwise.

Traceback (most recent call last):
  File "/home/violet/interview_question.py", line 20, in <module>
    test()
  File "/home/violet/interview_question.py", line 15, in test
    assert is_match('aaa', 'red red red') == True
AssertionError
Surprised Pikachu

Dang. That's not right now is it? This is actually a sillier mistake than we intended, but that's why being able to run your code is so useful

def is_match(pattern, query):
     matches = {}
     words = query.split(' ')
     for index in range(len(words)):
         word = words[index]
         pattern_char = pattern[index]
            if matches[pattern_char] != word:
                return False
        else:
            matches[pattern_char] = word
    return True

Okay, that doesn't fail the assertions. but we should probably add more tests, because otherwise who knows what could go wrong?

def test():
    assert is_match('aaa', 'red red red') == True
    assert is_match('aaa', 'red green green') == False
    assert is_match('abc', 'red green blue') == True
    assert is_match('aba', 'red green red') == True
    assert is_match('aba', 'red red red') == False

Then let's run it.

Traceback (most recent call last):
  File "/home/violet/interview_question.py", line 20, in <module>
    test()
  File "/home/violet/interview_question.py", line 19, in test
    assert is_match('aba', 'red red red') == False
AssertionError

Oh no! (This is the error we did intend to run into). So what's wrong? Well, we didn't make sure that the words were unique. Luckily Python makes it easy to fix.

def is_match(pattern, query):
     matches = {}
     words = query.split(' ')
     for index in range(len(words)):
         word = words[index]
         pattern_char = pattern[index]
            if matches[pattern_char] != word:
                return False
        else:
            if word in matches.values():
                return False
            matches[pattern_char] = word
    return True

This fixes the error alright. But for the sake of completion, let's add some more test cases to make sure nothing silly gets through. Stuff like, "What if there were more than three entries?" and "What if it wasn't letters being used in the pattern but numbers?"

def test():
    assert is_match('aaa', 'red red red') == True
    assert is_match('aaa', 'red green green') == False
    assert is_match('abc', 'red green blue') == True
    assert is_match('aba', 'red green red') == True
    assert is_match('aba', 'red red red') == False
    assert is_match('abcd', 'red green magenta blue') == True
    assert is_match('1234', 'red green magenta blue') == True

These all run well because we didn't make any mistakes that these would affect. We would argue this kind of testing is important anyway, because you can't be sure that you didn't do something silly and lazy, but that's besides the point.

Okay, so besides the correctness of our implementation here, how performant is it?

def is_match(pattern, query):
    matches = {}
    words = query.split(' ') # O(n) memory for each word
    for index in range(len(words)):
        word = words[index]
        pattern_char = pattern[index]
        if pattern_char in matches.keys():
            if matches[pattern_char] != word:
                return False
        else:
            if word in matches.values(): #O(n) time for each word seen
                return False
            matches[pattern_char] = word #O(n) memory for the number of distinct pattern elements
    return True

Forgive us if this isn't accurate, we're not a pythonista, so we can't speak as to how performant word in matches.values actually is, but if it's naive, then it's linear time. If that is indeed true, we can do better there by adding a set, this brings it down from O(n2) to O(n).

def is_match(pattern, query):
    matches = {}
    match_values = set()
    words = query.split(' ') # O(n) memory for each word
    for index in range(len(words)): # O(n) time for each word
        word = words[index]
        pattern_char = pattern[index]
        if pattern_char in matches.keys():
            if matches[pattern_char] != word:
                return False
        else:
            if word in match_values: #O(1) time
                return False
            matches[pattern_char] = word #O(n) memory for the number of distinct pattern elements
            match_values.add(word)
    return True

But there are still some potentially thorny issues here. Like, what if the pattern and query have mismatched lengths? Well, that should return false, shouldn't it?

def is_match(pattern, query):
    matches = {}
    match_values = set()
    words = query.split(' ') # O(n) memory for each word
    if len(words) != len(pattern):
        return False
    for index in range(len(words)): #O(n) time for each word
        word = words[index]
        pattern_char = pattern[index]
        if pattern_char in matches.keys():
            if matches[pattern_char] != word:
                return False
        else:
            if word in match_values: #O(1) time
                return False
            matches[pattern_char] = word #O(n) memory for the number of distinct pattern elements
            match_values.add(word)
    return True

The remaining issues that you might want to tackle here include things like making sure that both the query and pattern aren't None, ensuring they're both strings(or making it work with other sequences in general), but these things are just refinements that don't change the basis of the function.