Developing Tic-tac-toe in Swift

Normally I blog about a program I’ve already written. I decided this time to take a different approach, and blog about a Tic-tac-toe program that I’m writing instead. This will give people who are interested in watching a Swift program evolve over time the chance to follow along. As I add new features and refactor the code, I will post about it on this blog.

The repository is on GitHub:

My first committed class is GameBoard. It is the data model that stores the state of a game, namely which positions have been marked with X’s and O’s.

That class’s unit tests are here. The test method naming convention I use is:


You will need the latest Xcode to build this project.


Posted in Swift, Tic-tac-toe | Tagged , | Leave a comment

Compressing a Swift array

Suppose you have an array of values in your Swift app and you need to compress it to a smaller size, with the intention of making it occupy less memory. If the array contains many consecutive repeated values it could be compressed by only including a repeated value once, and tracking the number of consecutive occurrences for that value.

How might that code work? What about the code to decompress an array, how can that be implemented in Swift?

If you are interested in figuring this out yourself, I posted a gist that you can use as a starting point to test your code:

My solution is shown below. It uses some slick Swift goodness, such as a where clause, the flatMap method, and tuple decomposition.


The full source code is available, as a playground, here:

Happy Swifting!

Posted in Swift | Tagged | 1 Comment

I’m back

This blog’s half year of inactivity is over. I had joined Apple as a software engineer, to work on a low-level communications component that runs on all iOS and OS X devices. As an Apple employee I was prohibited from blogging, hence my radio silence. But I decided that working for Apple was not my cup of tea, so I’m back to being a hired gun; a freelance mobile app developer. According to the rules and bylaws of Josh Smith Digital blogging is not only allowed, but encouraged!

Posted in Uncategorized | 6 Comments

Creating ASCII art in functional Swift

This article explores an iOS app, written in a functional Swift style, that converts an image to ASCII art. For example, when given the famous Lenna photograph…

…it creates a string that, when printed, looks something like this…

Zooming into her lovely face reveals that the image is actually text!

The Xcode project is available at

The big picture

Each pixel in an image is mapped to an ASCII value, referred to here as a symbol.

An image’s pixels are first transformed to an intermediary value, as seen below:

Let’s take this step-by-step.

First a pixel’s color is converted to a grayscale color. The grayscale color’s intensity (i.e. brightness) is normalized to a value between 0 and 1, where black is 0 and white is 1.

The next step is, to me, the most interesting part of the algorithm. Each color intensity value is translated to an ASCII symbol. Later we will visit the AsciiPalette class, which supports that.

Lastly, rows of ASCII symbols are joined to form a giant, multi-line string: the ASCII art.

Algorithm implementation

AsciiArtist implements the three steps outlined above; as seen on lines 31 to 33.

An AsciiArtist object relies on Pixel and AsciiPalette, which we’ll look at next.

Transforming pixels to intensities

Pixel represents the color at a specific image coordinate. A color consists of four bytes; one byte per channel (red, green, blue, and alpha). AsciiArtist asks a Pixel to determine its color intensity, which, as previously mentioned, is calculated by normalizing the pixel’s grayscale value to a percentage. Let’s see how that works…

In case you’re wondering about those weight values on lines 47 to 49, they are industry-standard numbers used for grayscale conversion, as explained here.

Transforming intensities to symbols

The symbolFromIntensity function in AsciiArtist transforms a color intensity to an ASCII symbol, by converting a normalized intensity value to an array index. That array is provided by AsciiPalette. The first symbol in the array is used for very dark pixels and the last symbol is for very bright pixels. Here is that AsciiArtist function again, for easy reference:


The question is: which ASCII symbols should be in the array, and in what order?

A poorly designed symbol palette yields improperly shaded ASCII art:

A better symbol palette produces a vastly superior result:

My approach to designing a good symbol palette is to let the computer figure it out. The AsciiPalette class renders each symbol to a separate image, with black text on a white background. It then sorts the symbols by the number of white pixels in their images. The more white pixels in the image, the higher the symbol’s intensity. The blank space character (‘ ‘) has the highest intensity value since it contains only white pixels, and would therefore be the last symbol in the array.

The AsciiPalette designated initializer requires a UIFont argument because the choice of font affects how a character is rendered, impacting the number of white pixels around it.

The code in this article is available at

Posted in Swift | Tagged , | 5 Comments

Zipping two lists in Haskell

Studying a pure functional programming, such as Haskell, can be an eye-opening experience. The standard library in Haskell provides a zip function, which combines the elements of two lists into a single list of tuples. I decided to implement my own version, named zip prime (actually, zip’ since Haskell allows a function name to include the prime (symbol). The simplicity amazes me:

The first line is the function declaration.  It states that zip’ takes two lists of possibly different element types (types a and b) and returns a list of tuples of those element types.

The next line explains what should happen when the second list is empty; return an empty list. Similarly, the line after that explains that an empty list should be returned if the first list is empty.

The fourth and last line of that function covers the case when neither list is empty. It creates a tuple from the first element in each list. That tuple then becomes the list element which precedes the result of zipping together what’s left of the two lists (i.e. zipping their tails).

What could be simpler?! I wish that Swift had this kind of  powerful pattern matching at the function definition level.

Posted in Uncategorized | Tagged ,

Caesar cipher in Swift

I posted a Swift project to GitHub that implements the Caesar cipher, which was the encryption technique used to protect Julius Caesar’s personal correspondence. It’s a straightforward algorithm that maps each letter in the alphabet to another letter.

The code also shows how to break, or “crack”, an enciphered message using basic statistical analysis.



Here are a couple of the unit tests in the CaesarCipherTests class, showing the expected output based on the input string and shift-by argument:

Here is how the encipher method in CaesarCipher works:

The Letters type seen in that code example is a trivial utility struct that simplifies working with an individual letter as its numeric character code. Unfortunately working with individual characters like this in Swift is cumbersome, because of the way Swift supports Unicode text. To treat an individual letter as its character code requires using the UnicodeScalar type, whose value property returns 65 for A, 66 for B, etc.


The decipher method is more complicated than its encipher counterpart. It uses statistical analysis to search for the letter mapping that, when applied to the enciphered text, best matches the expected letter frequencies in a written language’s words (English words, in my case). The statistical tool used to calculate the degree of difference between the observed (O) and expected (E) distributions is known as Pearson’s chi-squared test.

The core idea in the decipher method is to try all 26 possible character mappings and find the one whose relative letter frequencies most closely match the expected letter frequencies. The expected frequencies are calculated on-the-fly, by analyzing a list of English words included in OS X. The LetterFrequency class is responsible for that.

These unit tests from CaesarCipherTests show what to expect from the decipher method, including the fact that it cannot decrypt all messages (especially very short ones).

Here’s how the decipher method in CaesarCipher works…

Happy coding!

Posted in Swift | Tagged , | 2 Comments

Functional parallel programming in Elixir

This article reviews a program that implements a parallelized algorithm, using a functional programming style made possible by a fantastic new language named Elixir. Along the way I very briefly introduce Elixir, review the relevance of functional programming in modern computing, and explain what parallel programming is all about. There’s a lot of ground to cover, so let’s get started!

The program

This programming exercise is based on finding what I refer to as a wordset. A wordset is a list of words that, when written on separate lines, read the same both horizontally and vertically. For example:


You can run the program from a command prompt, such as Terminal in OS X. Type in a word and it will find all wordsets starting with that word. The program uses a list of words included with OS X, though a different word list could easily be used instead.

The source code, along with instructions on how to run the program, is available on GitHub at

Why Elixir?

Over the past few months I studied various functional programming languages, as well as the concurrency and parallel programming models their practitioners espouse. While certainly seeing value in each language I studied, only Elixir jumped out at me as elegant and expressive yet simple. It is a so-called impure functional language, meaning that it is built to support a functional programming style but also allows for symbols that can change value (a.k.a. variables).

Elixir code runs on top of Erlang’s virtual machine, commonly known as BEAM, just like Erlang code has for decades. Elixir code is compiled down to BEAM bytecode, just like Erlang code. Elixir is a modern language that enables today’s mainstream developers to harness the highly concurrent, fault-tolerant, distributed, bulletproof Erlang virtual machine that undergirds much of the telecommunication infrastructure on which our society depends.

After a few days of writing Elixir code, I was impressed. Once I saw firsthand how Elixir and the Erlang VM simplify multi-core computing, I was sold. I don’t expect to write Elixir code for a living any time soon, if ever, but the lessons I learn from the language and platform can be adopted in my daily software development practices. I wrote this article to share those lessons with others.

To learn more about Elixir visit its homepage:

Watch José Valim, the creator of Elixir, discuss the history and future of the language:

Watch a thought-provoking talk by Dave Thomas about the mental shift Elixir enables:

For a more in-depth introduction to the Elixir way of programming, I highly recommend the ‘Programming Elixir’ book by Dave Thomas:

Functional programming

For many years mainstream software developers considered object-oriented programming an oddball curiosity that only the academic computer science crowd seemed to take seriously. Procedural programming was the mainstay of professional software development; where functions were functions, data were data, and real men wrote in assembler. ;-)

Once computing hardware became powerful and cheap enough to support the extra overhead object-oriented software requires, that approach to programming began influencing the design of languages used by mainstream developers, such as C++ and Java. This initiated a cultural shift and the Object-Oriented Era began. All hail the Great Superclass in the sky!


The story is essentially the same with functional programming. Granted, there have been functional programming languages used in production systems for a long time, such as Erlang and Haskell, just as there were languages that supported object-orientation before it became mainstream. But generally speaking, functional programming has been an uncomfortably weird way of thinking about software development, something most developers have probably heard of but never actually tried, like pole dancing.


Now that the free lunch is over and we must write programs that can effectively put multiple CPU cores to work at the same time in order to leverage hardware advancements, the functional programming style is moving from the incubator to the real world. Functional programming guides us toward writing code that can flourish in a multi-core world.

Instead of hiding variables in objects, functional programming avoids mutable state as much as possible. Rather than modeling software as a community of law abiding citizens who interact via socially acceptable protocols in public, but whose private lives are full of sins and secrets, functional programming is all about setting up pipelines that transform data from one shape to another. The focus shifts away from using objects to model a problem domain, and toward setting up data transformation pipelines. The developer’s time is not spent writing a detailed list of steps needed to make something happen; it’s spent describing at a high level how that thing should happen and letting the runtime worry about the nuts and bolts.

If you find this intriguing (I sure do!) be sure to watch the presentation I mentioned above by Dave Thomas.

Parallel programming

Now we’re getting into some really exotic and exciting territory. I first learned about parallel programming when studying General Purpose GPU programming, also known as GPGPU, while doing some CUDA programming. This article does not cover how to write code that runs on a graphics processing unit (GPU), though it’s a very interesting topic worth investigating.

Much of the parallel programming literature on the Web is either for computer scientists doing academic research, or it’s about using a GPU to crunch a ton of numbers at the same time for things like physics simulations and artificial intelligence. Very, very heady stuff. But don’t let the extreme nerd factor scare you off!


At it’s heart, parallel programming is just about doing a lot of stuff at the same time by running your code on multiple processor cores. The more work that can be done at the same time, the faster the overall task will complete (in theory). Not every task lends itself to being parallelized, so it’s not a silver bullet to solve all of your performance woes. Many people refer to problems that can and should be parallelized as “embarrassingly parallel.” I’m not sure what there is to be embarrassed about, but that’s the expression.

Functional and parallel programming are BFF’s

Functional programming and parallel programming go together like peanut butter and jelly. Mutable state is concurrent software’s kryptonite. If multiple instances of your code are running at the same time on several of a CPU’s cores, any changes made to shared memory must be done with extreme care and caution. Ideally you wouldn’t do it at all!

Many of today’s most popular languages and platforms equip developers with hardly more than threads and locks to cope with multi-core computing. That’s like giving someone a musket and bayonet before parachuting them into a modern battlefield. Functional languages encourage immutability and, in the case of Elixir, provide a battle-tested virtual machine whose concurrency model effortlessly scales across cores and machines.

The parallelized algorithm

I’m not going to walk through every line of code in the Elixir program that I wrote. If you want to see the whole thing, it’s on GitHub here. Instead, let’s focus on the most interesting part: the parallelized algorithm that finds all wordsets beginning with the same word. That code is in the Engine module, which you can see below or view in GitHub here.


The search function on line 8 is passed three parameters:

  • word – the word for which wordsets are found
  • find_words – a function that the engine calls to get all available words of a certain length that have a specified prefix
  • publish – a function that the engine calls when it finds a complete wordset that should be remembered for later

By Elixir convention, the search function has a helper function named do_search. It might look as if there are two do_search functions, on lines 11 and 15, but in Elixir one function can have multiple “heads” that specify different parameter states and conditions. The Erlang virtual machine evaluates these function heads at run-time to determine which one to invoke based on the parameters it will pass. In this example, the function on line 11 is called only if the number of strings in the words list is equal to the size parameter, which means the wordset is complete. The function on line 15 is called when the wordset is missing at least one word. And that’s where the magic happens.

Let’s review that function line by line. Here it is again, for quick reference:


Line 15: The parameters are the same as we saw for the search function above, but there is also a size parameter now. That represents the number of words in a complete wordset.

Line 16: This is called a guard clause. It contains conditions that must be true at run-time for this function to be called. In this case, it expresses that this function is called when a complete wordset is not yet available to publish.

Line 17: Call the make_prefix function to determine the sequence of letters with which the next word in the wordset must start.

Line 18: Call the find_words closure (i.e. function) to get a list of all available words that start with the prefix and are the right length for the wordset being built.

Line 19: Use the |> pipe operator to pass the word list retrieved on line 18 into a utility function I wrote in an EnumEx module called to_lists, which splits the list into N sub-lists of equal size. This enables me to break up the list of words into as many sub-lists as my computer has available processors. Note that the @sublist_count module attribute is used to determine how many sub-lists to create. I set that attribute to the number of “logical processors” available on the host computer, as reported by the Erlang runtime:


Line 20: This is where the magic happens! Pipe the list of sub-lists of words into the Parallel module’s each function, which is a simple utility function I wrote based on some code in the ‘Programming Elixir’ book by Dave Thomas. The standard Enum.each in Elixir executes a function for every item in a collection, one at a time. My Parallel.each executes a function for every item in a collection at the same time, by farming the calls out to the CPU’s available processors. The function call on line 20 does not complete until all of the parallel function calls it spawns off are complete.

Line 21: Get ready to pass the current sub-list of words through a pipeline…

Line 22: Filter out the words in the sub-list that cannot possibly be part of a valid wordset (refer to the “adaptive tail-sniffing optimization” area of Engine.ex to see how that works).

Line 23: Recurse into another do_search function call but this time put the current word from the sub-list into the words list. This is how the algorithm progresses through the available words. The &1 symbol refers to the current word, which is the first parameter of the function called by Enum.each. This is standard Elixir syntax.

Line 24: The end of the closure passed into Parallel.each on line 20.

Line 25: The end of the do_search function.

Parting thoughts

Regardless of whatever languages and platforms you might currently identify with, or are paid to write software for, it’s important to investigate and learn from what other technologies have to offer. The overall shape of software development’s future is the same for all of us, whether we write mobile apps or Web sites or desktop programs, etc. We must learn to embrace and utilize multi-core processors. Many of our beloved technologies, and the mindsets they engender, are simply insufficient for what’s coming next. I hope that this brief excursion into functional and parallel programming has helped sparked an interest in preparing yourself for the future of software development. Or, at least I hope you liked the Simpsons pictures!

Posted in Uncategorized