Swift Fun with ArraySlice

There is a lovely article by Luna An describing ArraySlice objects in more detail than I do here. It covers Swift 3 at the moment, and you should note that Swift 4 includes support for single-ended ranges, so you can create slices ala [..<count].

I found a good use for an ArraySlice while trying to find quartiles in a set of data.

The problem of finding each quartile is essentially the same problem of finding the median from three different data sets, one being the original input set, the other two being the upper and lower half of the set after removing the original median element, if it exists.

Here, I use findMedian to perform all three tasks. I found that I had to do a bit of extra work because the array slice is not indexed starting at zero. I wonder why they chose to implement slices in this way?


Command Design Pattern in Swift

It is the summer of Swift.

I was perusing some wonderful design patterns from Oktawian Chojnacki, and I decided to play around with the Command pattern. The Command pattern represents commands as objects to go between a Caller, which references the commands, and a Receiver, which is referenced by the commands.

I’m reminded of a game :


Here, each command object operates on a Robo, telling it to make a single move. The commands are collected into a program.

The first draft of this code had the Commands store their target Robo in a property. I realized a problem with this in that my program would accept commands for any Robo, when only one Robo belongs to the program. My solution for this was to give control of the command target to the program itself.

Of course, now the commands are little more than glorified functions, which can be stored in arrays in Swift anyway.

Swift Dictionary Reduce

Why is it so hard to find examples of Swift dictionary reduce operations? Examples for arrays abound :

See this if you’re looking for a detailed HowTo.

But dictionary is the more advanced problem. How do I reduce when I have keys and values?

The key here is to note that a dictionary yields the contents of its sequence in tuples containing pairs of values. We still have our familiar $0, $1 arguments from reduce as above, where $0 is the partial sum and $1 is the individual element value. But now $0 and $1 are both tuples, and you get to their contents through $0.0, $0.1, $1.0, and $1.1.

This example concatenates the strings and adds the integers, and the two separate data types just happen to use the same symbol for the two operations.


React and Angular are popping up a lot in job interviews these days. I decided to try React, since it is rumored to be the simpler of the two. So I created the old Chinese stone game Go in a Codepen. Normally I post code and talk about it in this case, but I think I will just let the Codepen speak for itself. Here, I report my experiences.

There is a lot of learning material out there, but the best resources start out right away with productive examples that get you working quickly. This tutorial video from Traversy Video does a very good job. I used this React demo from Facebook to model my architecture after.

The least trivial part of the game was the capture algorithm. The game engine must figure out if a newly placed stone results in another stone being surrounded. To figure this out, I implemented a recursive breadcrumb algorithm. The method searches recursively in four directions, resulting in a wide descending tree, but marks visited spots on the matrix to prevent infinite recursion. If at any point an empty space (liberty, in game terms) is found, the call stack starts bubbling up with that information. The recursive call will say whether or not a liberty was ever found. If it was, I run a second method to erase all visited points on the matrix, otherwise I run a different method to restore the marked spots back to original.

Here is my reaction (?) to React :

  • JavaScript is fun for web programming in limited amounts, but Object-Oriented frameworks like ES2015, Babel, etc. inevitably make it worse. this.method.bind(this)? Yucko.

  • Hidden inherited methods are traps waiting to happen. My IDE (Codepen) did not alert me to inherited methods, so this may be my own fault for not using a JetBrains tool or some such. Pick unique method names just in case.

  • I don’t really see the payoff. I understand the principle of data flow and limiting state on classes, but a real class-driven language does this in a more flexible way without need of a framework.

I know a little bit of CSS and HTML, so I was able to decorate it a bit, so that it kind of looks like an old wood board.

Big O and friends

All software developers know about Big O. For instance, contemporary sorting algorithms usually have \mathcal{O}(n\log{}n) complexity. Something like \mathcal{O}(n\log{}n) looks like a function of a function, but it’s really a classification system.

We start by defining the complexity of an algorithm to be an estimate of the number of steps required to solve a problem. This count is going to vary by the size of the problem, and so the complexity must be a function of the problem size.

Sometimes this can result in a nasty looking functions like f(x)=3x^2+2x+7 or f(x)=5x^2-999. We say that both of these functions are in the category \mathcal{O}(x^2) because they have similar growth properties. This is called Bachmann-Landau notation.

In mathematics, this notation describes the asymptotic behavior of a function. if f(n) = \mathcal{O}(g(n)), then we have a guarantee that after a certain point, the graph of f(n) will fall below the graph of g(n), if you’re willing to rotate g(n) a bit. In computer science, we use this to understand how the performance of an algorithm will change as the size of the problem or input grows. There are actually several Bachmann-Landau notations, each of which gives us some kind of indication on the limits of the growth of a function.

Name Notation Analogy
Big O f(n) is \mathcal{O}(g(n)) f(n) \le g(n)
Little o f(n) is o(g(n)) f(n) < g(n)
Big Omega f(n) is \Omega(g(n)) f(n) \ge g(n)
Little omega f(n) is \omega(g(n)) f(n) > g(n)
Theta f(n) is \Theta(g(n)) f(n) = g(n)

Credit goes to MIT for the excellent table and analogies. The definitions of each can be found in the referenced material.

Additionally, some of these definitions can be expressed using calculus. We start with the definition of o in the material says that f(n) is o(g(n)) if :

\displaystyle  \forall C > 0 , \exists k \,|\, ( x > k \rightarrow |f(n)| \le C|g(n)| )

That’s a symbolic mouthful. It means, “For all positive values of C, there exists some k such that, if x>k, the absolute value of f(n) is less than or equal to the absolute value of g(n) multiplied by C.

Separately, any calculus text will give this definition for a limit at infinity. I like Paul’s Online Calculus Notes. It says that \lim_{x\to\infty} f(x) = L if

\displaystyle  \forall \epsilon > 0, \exists N \forall x>N : |f(x)-L| < \epsilon

Again in plain English, “For any positive value of \epsilon, there must exist some value for N such that for any value of x that is greater than N, this inequality holds.”

Let’s make some substitutions of variable names in the above equation. If we change out f(x) for f(x)/g(x), 0 for L, C for \epsilon, n for x, and k for N :

\displaystyle  \forall C > 0, \exists k  \forall n>k : |f(n)/g(n)| < C


\displaystyle  \forall C > 0, \exists k  \forall n>k : |f(n)| < C |g(n)|

This boils down to an alternative definition of o. f(n) is o(g(n)) if :

\displaystyle  \lim_{x\to\infty} f(x)/g(x) = 0

This allows us to use other mathematical tricks, like L’Hopitals Rule, to figure out if two given functions follow this relationship.


Ah, it’s nice to be free from exams and assignments. Grading is over!

A lot of small but indispensable tools belong in the software developer’s toolkit. Take Markdown, for example. I am actually writing this post using WordPress Jetpack’s new Markdown composition features. So far, so good! I use Markdown extensively for creating documents. There is only a little bit to learn, but you can create nice documents very quickly. I use Typora for MD docs on my Mac, and I highly recommend it.

Mustache is a template system embedded in several front-end web frameworks. It is very simple to use, and the whole thing can be described in one unix-style man page.

I find it is most instructive to play with frameworks interactively using playgrounds or other REPL environments, so one npm install -g mustache later I am on the way to learning it.

Mustache works by embedding tags into any type of text data, such as plain text, HTML, or Markdown. Tags are encapsulated using mustache symbols (the curly brace) like this : {{tag}}. Take this example :

These tags will be replaced by variable values found in another file to follow. Some variables mark sections that can be repeated or left out all together based on their values. There values are found in a separate file.

In Mustache lingo, the above data comprises a template file. It will be formatted using variables contained in the following JSON file, called a view or hash :

The result is the following

You can see how this might be more useful if the JSON object was produced by loops in JavaScript and the template data was marked-up HTML instead of simple plain text. But that’s the general idea.

Misnomers in Computer Science

One thing you notice if you work in our field for very long is that the terms change as quickly as the practices and the technology. Once upon a time, memory was a premium product. Now it is cheap. Small-memory-footprint algorithms were once valuable. Now not so much. Open-source software was once for academics and scientists. Now the all top companies use it.

Terminology is changing as fast as the technology, but sometimes not fast enough. Take RISC and CISC : According to a questionable definition of RISC, Reduced Instruction Set Computing is called so because of the reduced number of computer instructions supported by the CPU. A better definition, in my opinion, comes from pointing out that the removal of complex memory-fetching instructions reduces the complexity of CPU design. After all, RISC CPUs add instructions at every generation, and we still called them RISC.

CISC (where C stands for Complex) computing predates RISC, and includes high-level instructions that compute complex software functions to fulfill common developer needs, such as moving sprites around on the screen or computing a high-level math function. But, starting with the 486, CISC CPUs have deprecated the clumsier older instructions, implementing them on top of a RISC core using microcode to support the older instruction set. That’s right! CISC has been RISC all along, or at least since 1989.

These days the term CISC means Intel x86 or x64, while RISC just means anything else. The terms no longer have technical value to chip developers. The same thing happened with the terms System V and Berkeley Unix : The terms just don’t mean anything outside of historical context. To test whether I’m right, try to name one difference between the two supposed flavors of operating systems. The unix family of operating systems has diverged so much that no single standard for all file placement, application behavior, and kernel functionality describes any real operating system in any way.

Another example is the seemingly innocuous term driver. Historically, the term driver was chosen for software that interfaced with a peripheral. The software drove the peripheral to come to life and start doing something. This is the same sense of driver that is used in the term test driver, which drives software to wake up and do something, so that the correct behavior of that software can be validated.

But today, a device driver is integrated into the operating system, providing applications with a standard API to request some task be performed in the hardware. The device driver has taken on a passive role. It no longer drives anything.

While reading about DDS and distributed simulation, I am struck by how easy it would be to utilize this kind of framework for a distributed control system. It turns out that DDS is being used for exactly that purpose. And not just DDS: Other software platforms, like HLA, are bridging the gap from simulation to realization. We now live in a world where you can mix and match your real and simulated components as you please.

So is the line between simulation and control system going away? Time will tell.

Heap’s Algorithm

Any sophomore computer science student knows that there are O(n!) permutations of any given array. But do you know how to produce those permutations? I didn’t , so I Googled it.

One simple strategy is to pick an element, then pick from those remaining, and so on until a single permutation is achieved. Then just backtrack one step and change your selection, finish the permutation again, and so on. For example, if you want to permute ABCD :

  1. Select A
  2. Select B, yielding AB
  3. Select C, then D, yielding ABCD, your first permutation
  4. Back up two positions and select D, then C, yielding ABDC
  5. Back up three positions and select C, then B, then D, yeilding ACBD
  6. And so on…

This might be a pretty straightforward implementation using recursion and a running collection of element lists (several copies). This is memory and CPU intensive, so an in-place solution would be nice.

Heap’s algorithm provides an in-place swapping method to find each permutation in about one step each, so it is very efficient. It is named after B. R. Heap, not after your favorite semi-sorted tree.

The core idea is very intuitive: Hold the last element of your list while recursively permuting the other n-1 elements (one must understand recursion). Then swap that last element with one of the others, and permute n-1 elements again. This way you get every possible permutation of n-1 elements for every possible fixed element value at position n. This should get us all permutations.

The tricky part is swapping out the nth element for one of the others. You might be tempted to write a loop that picks a new element from the n-1 to swap with, but remember that we permute the n-1 elements at every step, effectively scrambling them. Take AB C as an example. The n-1 permute leaves us at BA C. Say we swap with B, giving us CA B. The n-1 permute then takes us to AC B. We know that we should swap with A, because that is the only choice left to sit at the fixed position. And it is at position 0, just like the previous swaps!

The six permutations produced look like this :

ABC -> BAC -> CAB -> ACB -> BCA -> CBA

Let’s apply the same swap-with-zero strategy to four elements, abbreviating the three-element permutations for clarity :

ABCD -..-> CBAD -> DBAC -..-> ABDC -> CBDA -..> DBCA -> ABCD --X..OOOPS

We started repeating permutations before finding all of them. It turns out that AB is a different kind of permutation than ABC because of the length.

To see why, start by assuming that our permutation method will, if run twice, return the same permutation it started with. (This can be proven through induction once we understand the whole algorithm, but I will leave out the proof.) When ABC is being permuted, the first two elements are permuted three times while the elements take turns at the right position. This odd number of permutations makes the first two elements unstable in the sense that, every time we swap in the nth element, they are in a different order.

But when ABCD is being permuted, the ABC scramble is being performed an even number of times (four times), so it is stable except for the swap of the nth element. It is easier to see if we look at the algorithm output right before it swaps the nth element:

BA -> AC -> CB

CBA -> CBD -> CAD -> BAD



Notice that the odd-length scrambles are stable except for the one-character substitution, while the even-length ones are not. This is a hand-waving explanation at best, but it works to give us an intuitive understanding of the algorithm.

So, for even-length permutations, the n-1 swap is always done with the first element, while for odd-length permutations, the n-1 swap is done with the kth element, where k is a counter from position 0 to n-2 that increments every time we do this.

The recursion is still there, but with very little extra state, very few loops and conditionals. And it takes barely more than O(n!) swaps, which is close to ideal. You can find the code in all its glory on Github, but here it is for your edification. Uncomment the console.log’s to see each operation in action.