Incendium – Making fractal animations


Udklip

I’ve recently created a piece of software for creating fractal animations. The full source code and a description of its features can be found at the project’s GitHub page. On this page, however, I’ll explain the technical details behind the algorithm used by the core engine of Incendium to generate its fractals. If you want a non-technical overview, please check out the GitHub page. In essense, the program works by drawing a bunch of polygons unto an empty frame. There are two central problems here, how to choose which polygons to draw, and to figure out where to draw them.

We start with a regular n-gon (called depth d=0) drawn with its center at the origin (0,0), and from each of its vertices, we draw another regular n-gon (it does not need to be the same n for every depth). These new polygons have center at the vertices of the old polygon and have depth d=1, and in general a polygon at depth d=n will have children of depth d=n+1. We continue doing this process until we’ve reached the specified fractal depth, giving us images such as (shown from depth d=0 to d=2):

naming_regex_tri_noname

Note that this image uses triangles, rather than the more general n-gon. This is because the math is pretty much the same for any n, and triangles are easier to visualize. Note that we’ve drawn all triangles here – what is a good method to choose which of these triangles to choose?

Choosing which polygons to draw

First of all, let’s label the polygons accordingly in a systematic fashion. Let’s label the very first n-gon the empty string \epsilon. Its n children will be appended the characters \Sigma = \{0,1,2,...,n-1\}, meaning that the children of the root node are called 0,1,2,...,n-1. The children of the polygon represented by the string 0 will likewise be appended these characters, and thus be called 00, 01, 02, ..., 0n. Adding these labels to the above drawing yields:

naming_regex_tri

Note that the length of the string s is directly related to the depth of the polygon represented by that string, that is |s|=fd for some fractal depth fd. For a constant polygon degree throughout the fractal, we will have a polygon for every possible string s \in \Sigma^* : |s| \leq fd. Thus we’ve reduced the problem of determining which polygon to draw to choosing a language L \subset \Sigma^* and drawing all the polygons represented by the strings in L. Please note that since the polygon degree isn’t necessarily constant, we can’t be sure that all such strings s actually exist in the fractal, but there is a relatively simple workaround.

To do this, we employ the help of regular expressions. While this technically limits the class of possible languages, it is a very simple approach, so we’re sticking with it. So, given some regular expression R we draw all polygons represented by all the strings in L(R). Shown here is the regular expression .^*1.^* which only accepts all regular expressions that contain a 1:

naming_regex_tri_only1

Where do we draw them?

single-polygon

Still, it’s not enough to just know which polygons to draw, we also need to know where to draw them. The root polygon is by definition placed at (0,0), so its location is trivial. It’s children are drawn with their centers at the vertices of the root polygon, which seems to suggest we need the position of these. Assume we have some polygon with “radius” r and rotation \theta. We know that all the vertices of the polygon lie on the graph for the circumscribed circle of the polygon. Therefore, we can easily derive the following formulas for the position of the vertices using trigonometry:

P_0 = ( r \cdot \cos(\theta), r \cdot \sin(\theta) )

P_1 = \left ( r \cdot \cos( \theta + \frac{1}{n} \cdot 2 \pi), r \cdot \sin( \theta + \frac{1}{n} \cdot 2 \pi) \right )

P_2 = \left ( r \cdot \cos( \theta + \frac{2}{n} \cdot 2 \pi), r \cdot \sin( \theta + \frac{2}{n} \cdot 2 \pi) \right )

And in general,

P_k = \left ( r \cdot \cos( \theta + \frac{k}{n} \cdot 2 \pi), r \cdot \sin( \theta + \frac{k}{n} \cdot 2 \pi) \right )

Where P_k is the k-th vertex.

Now, assume we have some polygon at depth d represented by some regular expression R=a_0 a_1 a_2 ... a_k, and we want to know the position of its vertices. We know the origin of this polygon is given by the polygon at depth d-1. This other polygon is naturally represented by the regular expression R' = a_0 a_1 a_2 ... a_{k-1}, so its position is P_{R'}. We know the character a_n represents which vertex we have (0 being the first vertex, 1 being the next vertex etc.). Therefore, we can write the following recursive relation:

P_{a_0 a_1 a_2 ... a_k} = P_{a_0 a_1 a_2 ... a_{k-1}} +  \left ( r(R) \cdot \cos( \theta(R) + \frac{a_k}{n} \cdot 2 \pi), r(R) \cdot \sin( \theta(R) + \frac{a_k}{n} \cdot 2 \pi) \right )

 Where r(R) is the radius for the polygon represented by R, and \theta(R) is the angle – these will be investigated later. This recursive relation has the base-case P_\epsilon = (0,0) and implementing it is straight-forward (shown here in pseudo-code):

function positionFromRegex(R)
    if len(R) == 0: return (0,0)

    return positionFromRegex(R')
           + ( r(R) * cos(theta(R) + a_k/n * 2pi),
               r(R) * sin(theta(R) + a_k/n * 2pi) )

It’s the size that matters

In the previous section, we just used r(R) to denote the radius of the polygon represented by the regular expression R, we’ll now derive an expression for this function. First note that the size should only be dependent on the depth. Strings of the same depth should have the same size – we don’t want 0210 to be larger than 1203. Therefore, we can assume that the argument for r is a number, so we have r(d) : d \in \mathbb{N}. Obviously, we want r(0) to be the largest radius (for the root polygon), and we label this r_0, so r(0) = r_0. We also want this function to be strictly decreasing as n \rightarrow \infty, so r(d) > r(k) for every d > k. Finally, we want to structure we’re designing to be a fractal – it should converge towards the same points as n \rightarrow \infty.

Note that the maximum distance from the origin that the first polygon can get is r(0), and therefore the maximum distance any polygon at depth d=1 can get from the origin is r(1) and so on… Therefore the maximum distance any polygon at an arbitrary depth d can get is r(0) + r(1) + ... r(d). And since we want our fractal to be finite we require this sum to be finite, that is:

\displaystyle \sum_{d=0}^{\infty} r(d) = K

For some finite constant K \in \mathbb{R}. This looks an awful lot like infinite geometric series. While it’s not the exclusive solution for r, it is a possible one giving us the following expression for r(d):

r(d) = r_0 \cdot \rho^d

For some constant \rho \in [0,1]. We call this constant the size decay of the fractal.

You spin my head right round…

We’ve just derived the expression for the function r(R) and now we’ll do the same for \theta(R). Using a similar argument as in the previous section, we want the argument of \theta to be the length of the regular expression R. We also want the rotation to not be very chaotic, as the assumption is that this won’t create beautiful fractals. Therefore we want the fractals to rotate a constant amount at every subsequent depth. This means we can derive the following expression for \theta(n):

\theta(n) = \theta_0 \cdot n

Where \theta_0 \in [0, 2\pi] is a constant. We call this constant the rotation of the fractal.

Putting it all together

Now we’ve derived expressions for the two unknown functions and we get the following final recursive relation for the position P of a polygon represented by the regular expression R= a_0 a_1 a_2 ... a_k:

P_{a_0 a_1 a_2 ... a_k}[x] = P_{a_0 a_1 a_2 ... a_{k-1}}[x] + r_0 \cdot \rho^k \cdot \cos( \theta_0 \cdot k + \frac{a_k}{n} \cdot 2 \pi)

P_{a_0 a_1 a_2 ... a_k}[y] = P_{a_0 a_1 a_2 ... a_{k-1}}[y] + r_0 \cdot \rho^k \cdot \sin( \theta_0 \cdot k + \frac{a_k}{n} \cdot 2 \pi)

P_\epsilon = (0,0)

I’ve split it into two lines for and to make it more comprehensible. We can also write this in pseudo-code:

function positionFromRegex(R)
    k = len(R)
    if k == 0: return (0,0)

    return positionFromRegex(R')
           + ( r_0 * rho^k * cos(theta_0 * k + a_k/n * 2pi),
               r_0 * rho^k * sin(theta_0 * k + a_k/n * 2pi) )

This has been implemented in the source code in the function called getPositionFromString();.

Recursively Generating Gradient Images from Regular Expressions


I’ve decided to write yet another blog post on this blog post (first post, second post), because I’ve found another algorithm which is far superior to the other algorithms. I’ve almost completely rewritten the source code (which can be found at this project’s GitHub page). Using this approach I’ve been able to generate a 16.384px x 16.384px image (right click > save as, my browser crashes trying to render the image).

172088341

The Problem

The greatest problem with the old algorithm was that we had to enumerate all strings, check if they’re part of the regular language and then compute their Hamming distances using @nya’s O(n) algorithm, which works much better than the modified O(n^2) algorithm for Levenshtein distance previously used. But since there are 4^d strings for some depth d this whole procedure quickly becomes infeasible as especially testing for membership in the regular language is expensive. This makes rendering the images very slow.

Another fatal problem with the old algorithm was its memory usage. For instance, for d=13 (images of size 8192px x 8192px) we need to save 67 million strings and equally many pixels. To calculate how much memory that many strings will take up on the heap, we can refer to the article on Javamex (since I’ve written the program in Java, results may be different for C++, Pascal, etc.), which states that the minimum number bytes B a single string of length n takes up on the heap is:

B = 8 \cdot \left \lceil \dfrac{n \cdot 2 + 45}{8} \right \rceil

Which for d=13 gives 5.0 GB of heap usage. Similarily, a BufferedImage uses 4 bytes of information per pixel and has 4^{13} pixels in total, resulting in a heap usage of 256 MB. This is all very inefficient and is a huge, unnecessary drag on the system. It also sets a strict upper bound on the size of the images as all this memory allocation quickly becomes too much for the size of the RAM in the computer. For my computer (which has 8 GB of RAM) this strict upper bound is d=14, as it would require 21 GB of memory to store both the image and the strings.

Fortunately, there is a way around most of this, and that is what we’ll be discussing in this article. Essentially, what we do is enumerate the strings one by one and add them to the image immediately, rather than generate all of them. We also circumvent the problem of testing for membership using a clever construction.

The Algorithm

To fully understand how this algorithm works, it’s essential to have some preliminary knowledge of finite automata and regular languages. A regular expression defines a regular language L, and so do finite automata. We can therefore construct a finite automaton from a regular expression. To do so, we employ the help of the dk.brics.automaton package written by Anders Moeller from Aarhus University. The reason we use finite automata is that they have a lot of nice features – there are efficient algorithms to minimize automata and determine language membership of strings.

What we want, however, is not the language that is defined by the regular expression – we want to restrict the strings to have a length d given some depth. Therefore we can compute the intersection of the automaton that accepts strings of length d and the automaton which defines L. Next up, we’ll enumerate all strings in L \cap \Sigma^d and store them in an array M.

Other than having an automaton A_1 which recognizes strings of length d in L, we also want an automaton A_2 that recognizes all strings of length d which aren’t in L – this is just L^c \cap \Sigma^d. Because now that we have M, we want to assign the remaining strings recognized by A_2 distances and save the associated pixel information in our raster.

To do this, we perform a depth-first search of A_2, starting at some initial state S. This can be written in Java-like pseudo-code as:

process(State s, String currentString, int depth){
    //Stop at end nodes
    if(depth == max && s.isAccepted()){
        int dist = getHammingDistance(s);
        paintPixel(currentString, dist);
        return;
    }
    
    //Otherwise, get all transitions and process them as well
    for(Transition t : s.getTransitions()){
        process(t.getDestination(), currentString+t.getChar(), depth+1);
    }
}

The most obvious speed-up with this approach is that s.isAccepted(); is a cheap operation, whereas testing for membership of a string in a regular language has a worst-case time complexity of O(e^n). The other advantage is that there is no reason to save all the Strings in an array, making it possible to make much larger images. To view the algorithm in further detail I encourage you to go read the source code for this project (there is decent documentation, so the code shouldn’t be too difficult to read).

Gallery

While there are plenty of these images in the previous posts, I thought it’d be fun to share a few more of them.

489401655 239796234 610459308 737665762 806638930 831050543

Faster Gradient Images from Regular Expressions


1576837430

After releasing my last post, I got some amazing feedback. The user @nya had tried replicating my algorithm in c++ and got some amazing results! Not only did he get just as beautiful images as I did, he was able to do it *much faster*. The code I wrote was able to generate a 512px x 512px image in just about one hour – and @nya was able to generate a 1024px x 1024px image in roughly five seconds.

While I wasn’t able to replicate his results, I got some fantastic feedback from @j2kun who made me realize that my approach was wasteful. Generating all strings to find the edit distance between two strings generates a lot of overlap and wasted CPU cycles. Instead, inspired by his post on word metrics, I decided to rewrite my algorithm.

The New Algorithm

For some depth d (string length), first generate all 4^d strings and save them in some set \mathcal{S}. Then find all the strings that match the regular expression and save them in some set \mathcal{M}. Then compute the set difference between \mathcal{M} and \mathcal{S} to find the set of all strings that don’t match the regular expression \mathcal{D} = \mathcal{S} \backslash \mathcal{M}.

Then, for every string in \mathcal{D} compute the minimum edit distance to any string in \mathcal{M} (iterate through the array) and store this value in a table. Obviously, the minimum edit distance any string in \mathcal{D} can have is 1, so when we find a string with a distance of 1, we break and give the string a distance of 1. We can write this is Java-like pseudocode as:

for(String s : D){

    int dist = depth

    for(String t : M){
        if(levenshtein(s,t) < d)
            dist = levenshtein(s,t)

        if(dist == 1)
            break
    }

    table.put(s, dist)
}

To find the actual source code used to generate the images, check out this project’s GitHub page.

For some depth d, note that this algorithm has time-complexity O(e^d) as we have 4^d strings. This is extremely slow for large d – but fortunately, we don’t need very large d, as d=10 gives an image with a size of 1024px x 1024px.

Although the apparent time complexity is very slow, it has much, much better performance than the old algorithm. While the old algorithm took an hour to produce a 512px x 512px image, this new algorithm can generate a 1024px x 1024px in less than a minute (varies depending on the size of \mathcal{M} and the complexity of the regex). It still doesn’t match the performance of @nya’s algorithm, but it is still an impressive speed-up.

Just to show that the performance of this algorithm dwarfs that of the old one, here are some 1024px x 1024px images that took anywhere from 10 seconds to 5 minutes to produce:

1489907359 1232128026 1286708620 1171104158

Gradient Images from Regular Expressions


The source code for this project can be found at its GitHub-page: https://github.com/SSODelta/GradientRegexImages

Gradient Images from Regular Expressions

1499758127

In one of my posts from last year, I detailed an algorithm for creating pretty fractal images based on regular expressions. While this idea wasn’t novel, it was still very interesting, and it was a challenge for me to code it. However, the other day I got a great idea – I had figured out a way to generalize this concept to (I presumed) create even more pretty images.

The problem with the old method was that it was binary whether or not a given pixel belonged to the regular language. This makes excellent sense from a computer science theoretical perspective, but when making pretty images it’s nice to have some variation. So instead of the binary approach, I’m going to allow pixels to have a certain distance to being a member of the regular language. We define that d=0 means that a pixel belongs to the regular language, and d=1 means that it has an edit distance of 1 to belonging to the language. We only use substitution as a transformation in this example, however, because we want all strings to have the same length

As an example, let’s consider the regular language 3*, and consider of strings of length 2. Obviously, the only string of length 2 that belongs to this language (and thus has d=0) is “33”. The strings of distance d=1 are the strings that can result in “33” after only 1 substitution. An example of this is the string “32”, which after changing the 2 to a 3 suddenly belongs to the regular expression. Likewise, an example of a string with d=2 is “11”, where both characters need to be changed for it to belong to the language.

Determining the Distance of Every String

Like in the old post, we need to generate all strings of length n, check if they belong to the language, and then paint the image based on this information. In the old post, however, it was pretty straight forward checking if the strings belonged to the language or not. But in this approach, we’re faced with a far more complicated problem – how do we determine the edit distance of any one string?

To do so, we first generate all strings of length and then we check which of these strings belong to the language (we first find all d=0 strings) and remember them in a HashMap. Then we generate all variations of these strings. Obviously, any string which is a variation of a d=0 string must be at most a d=1 – so, using this set of variations we mark all the strings not previously marked with d=0 with d=1. We continue doing so until we’ve exhausted the list of strings (which must happen eventually, as any two strings of length are at most edits apart).

At each step, we remove all strings for which we’ve already determined its edit distance as keeping it would only generate copies. Also, we stop after d=n-1 and mark the remaining strings as d=n (again, because the maximum edit distance is n).

Coloring the Pixels

After finding the edit distance of every string, we have an integer d \in [0; n]. We map this unto the interval [0; 1] by dividing each edit distance with n. Next up, we associate some color 0xRRGGBB with 0, and another color 0xRRGGBB with 1 and give each pixel a color in this gradient.

Performance

This algorithm is very, very slow though. I’ve not been able to generate any larger than 512×512 images on my laptop (my patience lasts about 1 hour), and I fear a 1024×1024 is impossible due to the time complexity of the algorithm. I’m sure there are many ways to improve the algorithm’s performance (dynamic programming, probably), but I’ve yet to find them. But if you find an improvement (or a mistake), feel free to leave a comment.

Gallery

Here is a list of all images I’ve yet to render on my machine. It’s very difficult to generate massive amounts of images due to the complexity of the algorithm (as opposed to my post on Newton’s Fractals, where I have a gallery of 100+ images)

Large (512 x 512)

6586539001387479819

Small (256 x 256)

 

1522158750 1499758127 1432102946 1169534704 746826633 729585713 615065986 610652209 161923623

How to Model the Wheels of a Slot Machine


How to Model the Wheels of a Slot Machine

casino

Recently, in my IT class we had to create our own simple games as an exercise in programming. What I chose to make was a casino with a lot of slot machines in Unity. It was mainly an exercise in using Unity as I have little experience working with it. To demonstrate what I’m talking about, I made a small video showcasing the slow machines:

https://www.youtube.com/watch?v=TCuDuJK2zQQ

Now, what I want to talk about in this post is how to make the wheels of the slot machine stop at the right entries, so that we can easily program the slot machines to do what we want. Which means we can have a function:

rotateAndStopAtAngles(ANGLE_1, ANGLE_2, ANGLE_3);

Let’s assume that the wheels are already in motion and are travelling with an angle velocity of \omega. Let’s also assume that the wheels are affected by a constant acceleration when they’re stopping. This means that their time dependent angle velocity can be described as:

\omega(t) = \omega_0 - \alpha \cdot t

Where \omega_0 is the initial velocity of the wheel and \alpha is the deceleration. Obviously we want the wheels to stop spinning, so we want to find the time t_a which satisfies:

\omega(t_a) = 0

Which means we get the following expression for t_a:

t_a = \dfrac{\omega_0}{\alpha}

Now, what we want to find now is the angle \theta_{start} where we start the deceleration of the wheel. Let \theta_{goal} be the angle we want to wheel to stop on. Obviously, the total angle breadth travelled \Delta \theta when decelerating is:

\Delta \theta = \displaystyle \int_{0}^{t_a} \! \omega(t) ~ \mathrm{d}t

Now, obviously we want \theta_{start} to satisfy:

\theta_{start} + \Delta \theta = \theta_{goal}

Or written out in full:

\theta_{start} + \displaystyle \int_{0}^{\frac{\omega_0}{\alpha}} \! \omega_0 - \alpha \cdot t \mathrm{d}t = \theta_{goal}

Which allows us to get the following expression for \theta_{start}:

\theta_{start} = \dfrac{1}{2} \cdot \dfrac{2 \cdot \alpha \cdot \theta_{goal} + \omega_0^2}{\alpha}

And as you can see in the above video, it works! This is what I love about math – it’s such a powerful language for describing the world. Although, due to technical issues (*cough cough* floats) and due to the fact that computers work with discrete units rather than continuous units it doesn’t stop at exactly the right angle, but this is easily mitigated as you can see in the above video by sliding in at low speed to get it to stop just right.

Storing the Images of Surveillance Cameras in Constant Space Using Infinite Geometric Series


I was recently in London – it’s a fantastic city and I loved my time there. However, I was completely baffled by the large amount of surveillance cameras in the city. Almost everywhere you go the Queen’s watching you.

While I won’t go into a debate on whether or not surveillance is a good thing, I do want to discuss the sheer amount of data these cameras must pick up on a daily basis. I mean, several cameras on every street recording video non-stop – that must be super expensive in storage. Is there any way we can circumvent this?

The Naïve Solution

An often used solution to the storage problem is to delete all images older than X days. This keeps the storage space needed constant and ensures that the most recent (and most relevant) photo information is readily available to check if needed. The most obvious disadvantage here is that the old images get deleted completely, making forensics difficult if the crime was committedso early that the camera has deleted all the relevant images. In this post we’ll detail an algorithm which keeps track of all images the surveillance camera has saved, yet accomplishes it in constant space.

Storing the Images of Surveillance Cameras in Constant Space using Infinite Series

For the sake of this post, let’s assume the surveillance cameras take still photos every X minutes. The reason for this is that this algorithm probably doesn’t work well with existing video codecs (or at least, I wouldn’t know where to start). Now, obviously we can’t just store an indefinite amount of high-quality images on a drive with a limited storage space, so what we’re going to do is let the old images degrade over time. That is, the older the images is, the worse quality it has.

This makes sense – we assume that the most relevant images are the most recent images. After all, why would the police need to look at 3 year old surveillance photos of a random gas station? (There certainly could be incentive to look at old images, but we assume it’s the recent photos that we need to have in the best quality).

The algorithm

We’ll let the images degrade with a constant factor r \in [0, 1] for every constant amount of images. That is, the first n images are saved in quality Q = 1 where Q represents how large a percentage of the data we’re keeping for the image, so Q=0.5 means that we have reduced the space by 50%. The next n images are saved in quality Q = r, and the next n images after these are saved in quality Q=r^2.

We’ll call the first n images for the priority 1 images, the next n images for the priority 2 images etc. If we assume all images require a maximum disk space of S, then obviously the total disk space D for all priority 1 images is D_1 = n \cdot S. Likewise, the total disk space for all priority 2 images is D_2 = r \cdot n \cdot S. And in general for priority p images, we get:

D_p = r^{p-1} \cdot n \cdot S

And for the first k priorities we get the total disk space T:

T_k = D_1 + D_2 + D_3 + ... + D_k

Which can be written using sigma-notation:

T_k = \displaystyle \sum_{i=1}^{k} D_i

Expanding this, we get:

T_k = \displaystyle \sum_{i=1}^{k} r^{i-1} \cdot n \cdot S

Switching our terms, we get:

T_k = n \cdot S \cdot \displaystyle \sum_{i=0}^k r^i

To show that the total disk space is constant no matter how long we let our surveillance cameras run, we need to show that no matter how many priorities we sum up we’ll always remain bounded below some finite constant. That is, we look at the limit as we increase k:

T_\infty = n \cdot S \cdot \displaystyle \sum_{i=0}^\infty r^i

And since this is a geometric series, we get the following expression:

T_\infty = \dfrac{n \cdot S}{1 - r}

 Which is finite for n,S,r \in \mathbb{R} proving that the disk space required is constant with this approach.

An example

Let’s say each surveillance camera has a total disk space of T = 2 ~ \textrm{Gb} (2,147,483,648 bytes), and that each image is stored in the JPEG file format with size 480p (720 x 480). According to Wikipedia, a Q=1 image requires about 8.25 bits per color pixel, which means that each photo takes up S = 348 ~ \textrm{Kb}.

Assuming we take one image every minute from our surveillance cameras, and that we want the images to degrade on a daily basis (all images taken the same day are of the same quality), then n = 1440 images.

Finally, we can easily derive:

r = 1 - \dfrac{n \cdot S}{T}

Which means that  r = 0.768, which means that the images degrade roughly 23% in quality every day given this setup (obviously the parameters can vary, but this was just one example). Notice that this formula gives r \notin [0,1] if n \cdot S > T. This makes sense because it implies that the priority 1 images themselves take up more disk space than the surveillance cameras (which is of course impossible).

I’m not sure how practical this would be to implement, but I found the thought interesting at least.

LoGiX – An Overview


This project’s GitHub page: https://github.com/SSODelta/LoGiX

LoGiX is a program for determining if a certain boolean expression is a semantic consequence of some list of premises.

Posts about LoGiX

LoGiX – An Overview

For the past week or so, I’ve been working on a program I call LoGiX. In it’s essense, it can be used to verify the validity of logical arguments based on a list of accepted premises. This means for instance that we can solve logical puzzles, such as the ones on http://4chests.blogspot.dk/.

Syntax

As of now, we don’t need to introduce all the commands of LoGiX, but let’s look at two simple commands:

def [EXPRESSION]
[EXPRESSION]?

Writing def defines a premise – an expression assumed true. Writing an expression followed by a question mark will ask LoGiX to verify whether or not the expression in question is a semantic consequence of the premises.

To make a really simple example demonstrating LoGiX, let P, Q, and R be three propositions. Then define that P \vee Q \Rightarrow R. Then we can ask LoGiX if P \Rightarrow R is a semantic consequence based on our premises (as would be expected). Written in LoGiX, we get:

def P or Q implies R
P implies R?

For which the output is “true”.

A more complicated example

To really show the power of LoGiX, let’s quickly go over a more complicated example:

Determine who out of the following is guilty of doping. The suspects are: Sam, Michael, Bill, Richard, Matt. 1) Sam said: Michael or Bill took drugs, but not both. 2) Michael said: Richard or Sam took drugs, but not both. 3) Bill said: Matt or Michael took drugs, but not both. 4) Richard said: Bill or Matt took drugs, but not both. 5) Matt said: Bill or Richard took drugs, but not both. 6) Tom said: If Richard took drugs, then Bill took drugs. Statement 6 is guaranteed to be true, and 4 out of statements 1-5 are false.

We’re going to model this logical puzzle in LoGiX and determine which of the suspects are guilty of doping. Let’s ignore the last line as of now, and only focus on statements 1-6, which gives:

TrueSam biimplies MichaelDrug xor BillDrug
TrueMichael biimplies RichardDrug xor SamDrug
TrueBill biimplies MattDrug xor MichaelDrug
TrueRichard biimplies BillDrug xor MattDrug
TrueMatt biimplies BillDrug xor RichardDrug
RichardDrug implies BillDrug

Looking at the first line, we see that if Sam is speaking the truth (TrueSam) then Michael took drugs (MichaelDrug) or Bill took drugs (BillDrug), but no both (hence the XOR) – notice that this is a bi-implication. Likewise, the last line says that if Richard took drugs (RichardDrug) then Bill took drugs (BillDrug), which is not a bi-implication.

We also need to model the statement that says that 4 of statements 1-5 are false. Note that this is analogous to saying the exactly one of Sam, Michael, Bill, Richard and Matt are speaking the truth. We can model this in LoGiX as:

exactly 1 of TrueSam, TrueMichael, TrueBill, TrueRichard, TrueMatt

Since we’re trying to find the person taking drugs, we are, in fact, also implying that only one person took drugs. Therefore, we also need to write:

exactly 1 of SamDrug, MichaelDrug, BillDrug, RichardDrug, TrueMatt

Since we’ve now modelled the entire puzzle in LoGiX, we can ask:

MichaelDrug?
BillDrug?
SamDrug?
MattDrug?
RichardDrug?

Which returns true only for SamDrug implying that Sam is the perpetrator.

Additional features

In some puzzles, we’re being told that a minimum of some propositions are true. Therefore we can write:

minimum [NUMBER] of [EXPRESSION_LIST]

Which defines that at least [NUMBER] of the list of expressions are true. Likewise we can define:

maximum [NUMBER] of [EXPRESSION_LIST]

I’ve found that one of the hardest things to do is actually interpreting the puzzles, so when you’re not getting the results you want, it’s possible to find an example of some expression having some value to try to find a contradiction. I’ve done this often when trying to debug my LoGiX programs, so I made a command in LoGiX. Which means you can write:

example [FALSE/TRUE] [EXPRESSION]

To get an example of the values of the boolean variables, when [EXPRESSION] is [FALSE/TRUE].

Likewise, if we want to know in how many cases an expression is true, we can use the following function:

num [EXPRESSION]

Which returns two numbers (e.g. 7/8) which denotes in how many cases the expression is true.

Comments and Printing

Any line prepended with pound-sign # will be ignored by the LoGiX-compiler which makes it easy to make comments:

#This line will be ignored by LoGiX
This line will not (and gives an error)

Also, LoGiX will print the output of any line when reading a file. Which means that we’ll get the following output from this file (output is prepended by > in this example):

P or Q implies R
>def P or Q implies R

P implies R?
>true

This can get messy really quickly when writing more complicated LoGiX programs, so it’s possible to designate when you want LoGiX to print its output. Writing !! toggles the global printing, and prepending a line with toggles printing for that specific line. This means that the following program:

!!
P or Q implies R
!P implies R?

Will only print true as its output.

Custom messages

It may be of benefit sometimes to have LoGiX write other output when some statement turns out to be true. Therefore, any message appended after ? when testing the validity of an expression will be printed instead of true if that expression turns out to be a semantic consequence of our premises. This means that:

!!
P or Q implies R
!P implies R?Yup, P implies R!

Will print “Yup, P implies R!”. We can also specify custom messages for when an expression is false. Anything after | will be interpreted as the custom message for when the expression is not a semantic consequence of our premises. Therefore, the following program:

!!
P or Q implies R
!R implies P?|They're not equal.

Prints only “They’re not equal“.

Relations and Types

For more complex situations, you may need to specify relations between certain objects. First of all, let’s learn how to define a type.

obj TYPE_NAME OBJ_1, OBJ_2, ... OBJ_N

Which defines a type with the name TYPE_NAME, and states that this type contains the objects OBJ_1, OBJ_2 … OBJ_N. As an example, let’s define a type:

obj Person Mark, John, Richie

So, we’ve defined a type – a person – and its contents are Mark, John and Richie. It’s important to note that both the type name and the objects in it have to start with a capital letter, and that none of them can share a name.

To define a relation, we do the following:

rel RELATION_NAME(TYPE_1, TYPE_2, ... TYPE_N)

Which defines an n-ary relation between the types within the parentheses. As an example, let’s define a simple relation using the above type:

rel IsFriendWith(Person, Person)

Which enables us to say that any two people are friends. Therefore, we could define:

def IsFriendWith(Mark, John)

Which states that Mark is friends with John. Commen sense tells us that this should also imply that John is friends with Mark (one-sided friendships might exists, but not in this example). But as it gets tedious to write all the relations, we can define general procedures about relations. For instance, the friend relation is reflexive which means that we can write:

def IsFriendWith(x,y) implies IsFriendWith(y,x)

Which says that if some person is friends with some other person y, then is also friends with x. Note that x and y are placeholder variables here. In this concrete example, we wouldn’t have needed to specify the above line. We could have written a modifier when defining the relation in the first place:

rel REF IsFriendsWith(Person, Person)

Which tells LoGiX that the relation is reflexive. Likewise, we can use any of the following modifiers:

  • REF – Reflexive
  • STRICT – Irreflexive, Strict
  • SYM – Symmetric
  • ASYM – Asymmetric
  • TOTAL – Total
  • TRANS – Transitive
  • EUCLIDEAN – Euclidean
  • EQ – Equality (Reflexive + Symmetric + Transitive)

Note that these modifiers only work when we’re dealing with binary relations of the same type. For instance, this program does not make any sense:

obj House NiceHouse, DecentHouse, PoorHouse
obj Person Mark, John, Richie
rel REF LivesIn(Person, House)
def LivesIn(Mark, NiceHouse)

Because this implies that NiceHouse lives in Mark, which contextually doesn’t make any sense.

A really complicated example (Lewis Carroll)

Let’s take a look at the following riddle by author Lewis Carroll:

All the dated letters in this room are written on blue paper. None of them are in black ink, except those that are written in the third person. I have not filed any of those that I can read.  None of those that are written on one sheet are undated. All of those that are not crossed out are in black ink. All of those that are written by Brown begin with “Dear Sir.”.  All of those that are written on blue paper are filed. None of those that are written on more than one sheet are crossed out. None of those that begin with “Dear sir” are written in the third person. Therefore, I cannot read any of Brown’s letters.

I love this riddle because it elegantly shows how limited the human brain is – I can’t follow Lewis Carroll’s argument. It doesn’t make any sense to me that he cannot read any of Brown’s letter based on this argument, but LoGiX can tell you. Based on this argument, we can come up with the following LoGiX code:

!!
#All the dated letters in this room are written on blue paper.
if DatedLetter then BluePaper

#None of them are in black ink, except those that are written in the third person.
if not ThirdPerson then not BlackInk

#I have not filed any of those that I can read.
if CanRead then not Filed

#None of those that are written on one sheet are undated.
if OneSheet then DatedLetter

#All of those that are not crossed out are in black ink.
if not Crossed then BlackInk

#All of those that are written by Brown begin with "Dear Sir."
if Brown then DearSir

#All of those that are written on blue paper are filed.
if BluePaper then Filed

#None of those that are written on more than one sheet are crossed out.
if not OneSheet then not Crossed

#None of those that begin with "Dear sir" are written in the third person.
if DearSir then not ThirdPerson

#So, I can't read Brown's letters?
!Brown implies not CanRead

Which returns true, proving that Lewis Carroll is a genius.