Sorry About The Lack of Updates

I’ve been otherwise distracted. I haven’t even downloaded Xcode 7 β2 yet. I have replaced my 17 year old Impreza with a new Impreza. Here’s a picture. It’s kind of nice. I didn’t know cars had come so far in those 17 years. My previous Impreza was a five speed manual. The new one has the CVT. A bit of adaptation is required. I think it’s a bit larger too.

Interfacing with the iPhone is not perfect. That may be user error on my part. Or it could be something else. Playing music and receiving phone calls hands free works. Sending text messages, having texts read to me, and originating phone calls does not. The rear view camera is next to useless. The iPhone won’t use the LCD display as a secondary display device.

2015 Impreza Sport CVT
2015 Impreza Sport CVT

An Eight Queens Puzzle Solution in Swift 2

As WWDC 15 week comes to a close, I thought I would try my hand at writing a Swift 2 solver for the Eight Queens Puzzle. My inspiration is actually due to the fact that I am watching the MIT SICP Lecture Series. Eight Queens was mentioned by Hal Abelson during one of the lectures after assignment was introduced. The solution I am presenting is not a good one. But it does the job. It does a brute force search through 16,777,216  (that is, 88) combinations and produces the 92 distinct solutions.

The code is in this Gist followed by the output as produced from running in the Xcode 7 beta (7A120f) debugger. Then I will proceed to discuss the code.
[gist user=”DavidSteuber” id=”f85e6a6487e3d40bb01e”]

Solution 1: [3, 1, 6, 2, 5, 7, 4, 0] in 1299851 steps
Solution 2: [4, 1, 3, 6, 2, 7, 5, 0] in 1551564 steps
Solution 3: [2, 4, 1, 7, 5, 3, 6, 0] in 1695330 steps
Solution 4: [2, 5, 3, 1, 7, 4, 6, 0] in 1733354 steps
Solution 5: [4, 6, 0, 2, 7, 5, 3, 1] in 3077172 steps
Solution 6: [3, 5, 7, 2, 0, 6, 4, 1] in 3343851 steps
Solution 7: [2, 5, 7, 0, 3, 6, 4, 1] in 3355114 steps
Solution 8: [4, 2, 7, 3, 6, 0, 5, 1] in 3434452 steps
Solution 9: [4, 6, 3, 0, 2, 7, 5, 1] in 3645684 steps
Solution 10: [3, 0, 4, 7, 5, 2, 6, 1] in 3759875 steps
Solution 11: [2, 5, 3, 0, 7, 4, 6, 1] in 3829994 steps
Solution 12: [3, 6, 4, 2, 0, 5, 7, 1] in 4097331 steps
Solution 13: [5, 3, 1, 7, 4, 6, 0, 2] in 4410973 steps
Solution 14: [5, 3, 6, 0, 7, 1, 4, 2] in 5304733 steps
Solution 15: [0, 6, 3, 5, 7, 1, 4, 2] in 5307120 steps
Solution 16: [5, 7, 1, 3, 0, 6, 4, 2] in 5441149 steps
Solution 17: [5, 1, 6, 0, 3, 7, 4, 2] in 5484941 steps
Solution 18: [3, 6, 0, 7, 4, 1, 5, 2] in 5557811 steps
Solution 19: [4, 7, 3, 0, 6, 1, 5, 2] in 5562620 steps
Solution 20: [3, 7, 0, 4, 6, 1, 5, 2] in 5564475 steps
Solution 21: [1, 6, 4, 7, 0, 3, 5, 2] in 5607217 steps
Solution 22: [0, 6, 4, 7, 1, 3, 5, 2] in 5611312 steps
Solution 23: [1, 4, 6, 3, 0, 7, 5, 2] in 5736353 steps
Solution 24: [3, 1, 6, 4, 0, 7, 5, 2] in 5736843 steps
Solution 25: [4, 6, 0, 3, 1, 7, 5, 2] in 5740084 steps
Solution 26: [5, 3, 0, 4, 7, 1, 6, 2] in 5830685 steps
Solution 27: [4, 0, 3, 5, 7, 1, 6, 2] in 5831364 steps
Solution 28: [4, 1, 5, 0, 6, 3, 7, 2] in 6152524 steps
Solution 29: [5, 2, 6, 1, 7, 4, 0, 3] in 6452117 steps
Solution 30: [1, 6, 2, 5, 7, 4, 0, 3] in 6453937 steps
Solution 31: [6, 2, 0, 5, 7, 4, 1, 3] in 6715926 steps
Solution 32: [4, 0, 7, 5, 2, 6, 1, 3] in 6761412 steps
Solution 33: [0, 4, 7, 5, 2, 6, 1, 3] in 6761440 steps
Solution 34: [2, 5, 7, 0, 4, 6, 1, 3] in 6767082 steps
Solution 35: [5, 2, 0, 6, 4, 7, 1, 3] in 6802453 steps
Solution 36: [6, 4, 2, 0, 5, 7, 1, 3] in 6803622 steps
Solution 37: [6, 2, 7, 1, 4, 0, 5, 3] in 7619542 steps
Solution 38: [4, 2, 0, 6, 1, 7, 5, 3] in 7838740 steps
Solution 39: [1, 4, 6, 0, 2, 7, 5, 3] in 7840161 steps
Solution 40: [2, 5, 1, 4, 7, 0, 6, 3] in 7895146 steps
Solution 41: [5, 0, 4, 1, 7, 2, 6, 3] in 7959301 steps
Solution 42: [7, 2, 0, 5, 1, 4, 6, 3] in 8002071 steps
Solution 43: [1, 7, 5, 0, 2, 4, 6, 3] in 8003961 steps
Solution 44: [4, 6, 1, 5, 2, 0, 7, 3] in 8137332 steps
Solution 45: [2, 5, 1, 6, 4, 0, 7, 3] in 8146026 steps
Solution 46: [5, 1, 6, 0, 2, 4, 7, 3] in 8266125 steps
Solution 47: [2, 6, 1, 7, 5, 3, 0, 4] in 8511090 steps
Solution 48: [5, 2, 6, 1, 3, 7, 0, 4] in 8631189 steps
Solution 49: [3, 1, 6, 2, 5, 7, 0, 4] in 8639883 steps
Solution 50: [6, 0, 2, 7, 5, 3, 1, 4] in 8773254 steps
Solution 51: [0, 5, 7, 2, 6, 3, 1, 4] in 8775144 steps
Solution 52: [2, 7, 3, 6, 0, 5, 1, 4] in 8817914 steps
Solution 53: [5, 2, 6, 3, 0, 7, 1, 4] in 8882069 steps
Solution 54: [6, 3, 1, 7, 5, 0, 2, 4] in 8937054 steps
Solution 55: [3, 5, 7, 1, 6, 0, 2, 4] in 8938475 steps
Solution 56: [1, 5, 0, 6, 3, 7, 2, 4] in 9157673 steps
Solution 57: [1, 3, 5, 7, 2, 0, 6, 4] in 9973593 steps
Solution 58: [2, 5, 7, 1, 3, 0, 6, 4] in 9974762 steps
Solution 59: [5, 2, 0, 7, 3, 1, 6, 4] in 10010133 steps
Solution 60: [7, 3, 0, 2, 5, 1, 6, 4] in 10015775 steps
Solution 61: [3, 7, 0, 2, 5, 1, 6, 4] in 10015803 steps
Solution 62: [1, 5, 7, 2, 0, 3, 6, 4] in 10061289 steps
Solution 63: [6, 1, 5, 2, 0, 3, 7, 4] in 10323278 steps
Solution 64: [2, 5, 1, 6, 0, 3, 7, 4] in 10325098 steps
Solution 65: [3, 6, 2, 7, 1, 4, 0, 5] in 10624691 steps
Solution 66: [3, 7, 4, 2, 0, 6, 1, 5] in 10945851 steps
Solution 67: [2, 4, 7, 3, 0, 6, 1, 5] in 10946530 steps
Solution 68: [3, 1, 7, 4, 6, 0, 2, 5] in 11037131 steps
Solution 69: [4, 6, 1, 3, 7, 0, 2, 5] in 11040372 steps
Solution 70: [6, 3, 1, 4, 7, 0, 2, 5] in 11040862 steps
Solution 71: [7, 1, 3, 0, 6, 4, 2, 5] in 11165903 steps
Solution 72: [6, 1, 3, 0, 7, 4, 2, 5] in 11169998 steps
Solution 73: [4, 0, 7, 3, 1, 6, 2, 5] in 11212740 steps
Solution 74: [3, 0, 4, 7, 1, 6, 2, 5] in 11214595 steps
Solution 75: [4, 1, 7, 0, 3, 6, 2, 5] in 11219404 steps
Solution 76: [2, 6, 1, 7, 4, 0, 3, 5] in 11292274 steps
Solution 77: [2, 0, 6, 4, 7, 1, 3, 5] in 11336066 steps
Solution 78: [7, 1, 4, 2, 0, 6, 3, 5] in 11470095 steps
Solution 79: [2, 4, 1, 7, 0, 6, 3, 5] in 11472482 steps
Solution 80: [2, 4, 6, 0, 3, 1, 7, 5] in 12366242 steps
Solution 81: [4, 1, 3, 5, 7, 2, 0, 6] in 12679884 steps
Solution 82: [5, 2, 4, 7, 0, 3, 1, 6] in 12947221 steps
Solution 83: [4, 7, 3, 0, 2, 5, 1, 6] in 13017340 steps
Solution 84: [3, 1, 4, 7, 5, 0, 2, 6] in 13131531 steps
Solution 85: [3, 5, 0, 4, 1, 7, 2, 6] in 13342763 steps
Solution 86: [5, 2, 0, 7, 4, 1, 3, 6] in 13422101 steps
Solution 87: [4, 2, 0, 5, 7, 1, 3, 6] in 13433364 steps
Solution 88: [3, 1, 7, 5, 0, 2, 4, 6] in 13700043 steps
Solution 89: [5, 2, 4, 6, 0, 3, 1, 7] in 15043861 steps
Solution 90: [5, 3, 6, 0, 2, 4, 1, 7] in 15081885 steps
Solution 91: [3, 6, 4, 1, 5, 0, 2, 7] in 15225651 steps
Solution 92: [4, 6, 1, 5, 2, 0, 3, 7] in 15477364 steps
DONE
Program ended with exit code: 0

First off, I would like to say that the program ran surprisingly quickly considering how poor the code is. At least I think it’s poor. I will point out a few places where the code could be improved in just a bit. Most of the surprise comes from the fact that I was running a brute force algorithm. This is because I’m not very good at math. You may have heard otherwise or even have a differing opinion, but solving interesting problems requires some math ability. On to the code.

Even though Apple is pushing Protocol Oriented Programming (about time too!), I did very little of that in this program. My only use of protocols was to inherit from ErrorType for the one error that my program can produce. That also brings up exception handling which is one of the new Swift features I use. I shall defer that discussion until after I have described in high level detail how the program works. Yes, that pun was intended. I didn’t use it in the program.

The first step to the puzzle was working out a strategy. There are a number available. Due to my lack of math ability, I went with one of the brute force approaches. I don’t know how it fairs compared to the Pascal code written by Niklaus Wirth published in the Wikipedia article. At least I can understand it, unlike Wirth’s solution which is totally befuddling. I reduced the level of brute force required by deciding to start with all eight queens on the board, each in its own file. I would then find some way of orderly iterating through all the possible combinations and finding the ones that passed the test.

To implement that strategy, I created a data type called Chessboard. As you can see, it is a struct that inherits no protocols. Within the scope of that struct, I defined an ErrorType to handle the one serious error I could expect and a single data member which happens to be an array of eight Ints. I should mention at this point that it would not be too difficult to generalize the program to deal with an NxN board where N > 3 and N is not so large that the program won’t complete in your lifetime. As this is a quadratic algorithm, that means N has to remain fairly small.

Conveniently enough, the array of integers can easily be interpreted to represent a number of arbitrary radix. I also chose to use a “big-endian” interpretation so I could work left to right. That was fairly arbitrary but also probably a bit easier to deal with than a “little-endian” representation. Each member of the array represents a file (column). The value represents the rank (row) that the queen is in. The member functions of the Chessboard struct manage the array accordingly. I made it private to mark that it should not be messed with by the outside world.

In this example, the numbers are from 0 – 7 (8 values like in Octal notation) to represent the eight ranks on the chessboard. There are eight of them to represent the eight files on the chessboard. This leads directly to going from one board position to the next. It’s a simple increment. The member function nextBoard() returns an incremented position. The work is handed off to init(b: Chessboard) which is labeled both private, because it does not state that it is delivering a different chessboard, and also labeled with throws because there is a situation where it may fail.

Let’s look at that. The private function inc() is responsible for doing the math of incrementing the board array as if it is an integer in big-endian format. It does no error checking. A guard is therefor placed in the initializer to throw an exception if all the queens are in the last rank. This is the one time the initializer may fail. Notice that I’m not using the failable initializer syntax from Swift 1.2. I’m using exception handling instead. This is a pattern I am familiar with and will certainly stick to. I’ve never even used the failable syntax before. nextBoard() handles the exception by simply returning self. This could lead to an infinite loop if there was no way to check that you had run out of board positions. That is what the isLast() method is for. It is used in the loop at the end to terminate the loop. The loop uses the new repeat-while syntax.

One other thing has to be done. The board position needs to be evaluated to see if it is a solution to the puzzle. isSolution() does that in two steps with the aid of the helper methods (which should be private) rankAttacks() and diagonalAttacks(). A little more work goes into diagonalAttacks() so it is on the tail end of the || operator for short circuiting purposes. That’s just a micro-optimization that probably doesn’t make much difference. I haven’t bothered to profile the program.

A quick word on rankAttacks() and diagonalAttacks(). They both have the same pattern. Only the contents of the inner loop differ. This is a screaming invitation to factor out the common functionality and use either Lisp style macros (which don’t exist in Swift) or a method that accepts a function as its argument to compute the Boolean result. Obviously I didn’t bother. Still, it should be possible to do with little to no performance impact. Something to think about.

There is also a method in Chessboard that breaks the abstraction barrier. That is getBoardRep(). It returns the board array. This is for simple convenience to run in the debugger without having to do any real work. Real work would mean passing back an object that is specified in such a way that another function or object could then present a textual or graphical representation of the chessboard and queen positions. This idea can be taken even further if the chessboard was  to represent an actual chess game.

I think I have pretty much described the entire program in depth now. In summary, eight queens are positioned in the 0th rank of the board. Each queen is confined to its file. The state of the board is iterated as if it is a number in big-endian notation. Each state is evaluated to see if it is a solution state. Solution states get printed out in the debugger. When all the states are exhausted, the program is finished. The run time is surprisingly short. A better algorithm would run in even less time (fewer steps). Some Swift 2 features are used, namely for error handling.

I hope you enjoyed this posting and the program. I was hoping for something that could run in a playground, but I’m not that clever.

 

Rick Rolled & Swift 2

There was a nice thunderstorm moving through my area on the night of the WWDC 15 keynote. That or the possibility that Apple was getting a lot of requests for the stream gave me many pauses. Usually they were timed to perfectly align with a good line by whoever was speaking at the time. During the demonstration of Safari for El Capitan, there was a cleverly placed “Rick Roll” to demonstrate muting the audio of a tab. I hope Apple realizes the gravity of the situation. At any rate, this was the clue to go to the Apple Developer Site and see what was new there.

There is a lot. Rather than enumerate the changes, I’ll just point to them. https://developer.apple.com/support/transition/ . I think this will make things easier. I also expect that people will now be very happy that they don’t have to pay for a membership to test their iOS apps on a device. This is a huge improvement. I’m sure I will be enjoying the upgrade. I haven’t read the new agreements yet. I tend to click through those things. But they are in my downloads folder.

What the big news is for me is Xcode 7. Finally there is exception handling in Swift. Except there is no finally. Damn I’m bad with jokes. Anyway, I’ve updated a project I’m working on to use the new Swift 2 syntax in Xcode 7. So far, the changes are not shocking because I’m not very far along with it.

So. Exception handeling. I was rather hoping for a Java style syntax which looks like this:

try {
    // stuff that may throw an exception
}
catch exception_type {
    // handle exception
}
catch another_exception_type {
    // handle exception
}
...
catch all {
    // handle lost cause
}
finally {
    // any cleanup code that needs to execute regardless
}

Presumably any stack unwinding that goes on will be in the thread that the exception is tried from (as opposed to stuff in the try clause executing code on another thread). Dancing around in threads makes things more interesting but is manageable. Objective-C has @try/@catch/@finally that will work with C++.

The throws/throw declarations and syntax appear to be sensible enough for either the above try/catch/finally arrangement and the one that Swift went with which is sort of like C++ except with an extra word (copied from the new Swift Reference):

do {
    try vend(itemNamed: "Candy Bar")
    // Enjoy delicious snack
} catch VendingMachineError.InvalidSelection {
    print("Invalid Selection.")
} catch VendingMachineError.OutOfStock {
    print("Out of Stock.")
} catch VendingMachineError.InsufficientFunds(let amountRequired) {
    print("Insufficient funds. Please insert an additional $\(amountRequired).")
}

It is worth mentioning that there is a defer clause available in the Specifying Clean-Up Actions section of the language reference.

You use a defer statement to execute a set of statements just before code execution leaves the current block of code. This lets you do any necessary cleanup that should be performed regardless of whether an error occurred. Examples include closing any open file descriptors and freeing any manually allocated memory.

defer statement defers execution until the current scope is exited. It consists of the deferkeyword and the statements to be executed later. The deferred statements may not contain any code that would transfer control out of the statements, such as a break or a returnstatement, or by throwing an error. Deferred actions are executed in reverse order of how they are specified—that is, the code in the first defer statement executes after code in the second, and so on.

The example given is:

func processFile(filename: String) throws {
    if exists(filename) {
        let file = open(filename)
        defer {
            close(file)
        }
        while let line = try file.readline() {
            /* Work with the file. */
        }
        // close(file) is called here, at the end of the scope.
    }
}

The above example uses a defer statement to ensure that the open(_:) function has a corresponding call to close(_:). This call is executed regardless of whether an error is thrown.

This may actually be better. You can chain the catches on type thrown. You can also prevent error propagation using try! instead of the regular try.

Since functions are proper types (AKA closures), this will avoid the thread dance as the code will be executed in the same lexical scope and thread. I’m being a little imprecise here, but I think you know what I mean. The functional style of the defer statement should keep the Swift programmers that use functional programming patterns a lot happy.

There is of course more to go through. Apple will be Open Sourcing Swift. That got a lot of applause. Linux will be supported which is brilliant because Swift would make a great programming language for server side applications. Linux is very popular on servers. The success of Swift on Linux will largely depend on the licensing model that Apple chooses. I expect Apple will want to retain control over the language itself rather than going through a traditional standards body. That is simply speculation on my part. But this has been the case with Java, C#, and rather a lot of other languages.