Paint the Tiger, Carve the Swan

One program I tend to get around to writing in any new language I learn is a Sudoku solver. I originally wrote one in python, that solved every puzzle I could throw at it (although it had to guess and backtrack on failure in some cases).

Recently, I wrote one in Java. It was three classes plus a Driver/Main class. It took hours to write (at least the whole length of Phar Lap), and eventually it worked. I spent quite a while fixing up all of the syntactic errors I make in Java after programming in better languages again.

I then wrote one in Prolog. It was amazingly simple - it just defines a sudoku puzzle as a list of lists (each of which is 9 elements long), states that each element in each of the lists must be unique, and that each element in the first position of each list (columns) must be unique. Next, it states that each 3×3 grid must be unique, and that each element must be an integer of range 1-9.

That’s it. Solved.

My unique/1 predicate takes a list of items, and succeeds only if each item in the list is unique. This is simple:

1. An empty list is unique.
2. A list of one item is unique.
3. A list of the form [A,B|X] is unique if A and B are different, and [A|X] and [B|X] are also unique-lists.

I also use a predicate that indicates a variable should be of the value 1-9, it’s possible to use advanced techniques and something called “Domains”, but I couldn’t get this figured out.

The only trick then is in the definitions. The simplest to understand, but messiest is to define the elements in the sudoku puzzle as each having unique names ([[A1,A2,...,A9],[B1,...]] and so on), and then passing some lists to unique, ie all ‘Ax’ elements, all ‘X1′ elements, and so on.

The coolest thing about Prolog is that you don’t need to say how things will happen, but just what the desired outcomes are. This can be dangerous - it’s rather easy to write something that will be executed in a ridiculous amount of time, so you often need to think about how to narrow the search space as quickly as possible. In Java, I needed to have methods that would remove elements from a possibles list, and then check to see if there was only one element, in which case it’s the actual value that belongs there, and so on. This is all error-prone code, wheras Prolog’s backtracking does all of this for you.

The biggest benefit is that in a puzzle that is fiendishly hard, Prolog will still come up with a solution, wheras some other languages, using the algorithm I defined above may not. And, in Prolog, you will automatically get multiple solutions to a problem if they exist.

Can you tell I love Prolog?

View Comment (1)  

As a class, we have the choice of what the focus of one of my topics this semester is going to be.

I’m voting for Compiler Construction. Even though we’ll be doing it in Java (ugh!), it is something I was disappointed to find wasn’t otherwise offered.

If you need convincing, read Stevey’s Blog Rants: Rich Programmer Food.

Now, if only I can convince the rest of the class!

View Comments (2)  

I finally got around to updating Xcode to 3.1 yesterday.

There’s some great stuff in there. At last, the autocomplete of method names puts in tokens for the arguments, so you can just click on the token and then overtype - or just delete it in one go with (forward) delete.

Another cool thing is something that I’ve seen in NetBeans, but the default settings there for it are just annoying. Previous instances of the currently selected variable are highlighted. In Xcode it is a much subtler underline, much better than bright yellow.

This is better than NetBeans in another way - you can click on the item, and access a special contextual menu that allows you to edit every instance of the variable name in your current scope. Thus, refactoring is made much easier.

I’m sure there was something else I really liked too, but I can’t recall what it was.

View Comments (0)  

I got tripped up by how C represents Boolean values today.

To save space, but more to make comparisons easy, I was storing a series of bits (representing hours in a day) as integers. I had built up some structure so that my sub-classed NSMatrix could use Cocoa Bindings and be connected to a Controller, so that changing the values in an NSArray of Integers in that controller would change the selected cells in the matrix, and changing the cell selection similarly affects the values stored in the array.

But, and it took me a while to figure this out, I was having problems getting the data back from the array properly. For some reason, numbers greater than 255 were not displaying properly. Basically, I seemed to be losing bits off the top. So I spent ages rewriting the code using longs, long longs, and unsigned long longs, but nothing seemed to work.

Eventually, I pinpointed the error to this: in C an integer with the lower 8 bits all set to 0 evaluates to FALSE.

It doesn’t seem to matter if the integer is a long, or whatever.

Thus, when I checked, using a bitwise AND (& operator), the stored value against a value representing the cell value, and stored it directly in a BOOL, and then used said BOOL to set the selection of that cell, it was evaluating to False for all values greater than 255.

All I needed was to change one line of code:

BOOL highlight = (value & bin);

becomes:

BOOL highlight = (value & bin) > 0;

All fixed.

View Comment (1)  

You can’t have a class with the name “Availability” in a project built with XCode 3.1.

You can with XCode 3.0, but CFNetwork, and I assume a heap of other classes use a class called “Availability” to define if objects are available in a particular version of the OS.

View Comments (0)  

I’m trying to make a control that allows me to indicate when a record in my application is synced with the AddressBook person of the same name - I have made it so that I can only enable syncing when a person with the exact same name exists in both places, but to indicate it, I want to use a button that shows a pressed-in state, but also alters the image.

I want the image to be black-and-white by default, but when pressed in, it becomes coloured.

Apparently, this isn’t possible. You can either have a button which changes it’s image, or displays a pressed in look.

Might have to subclass it.

Update: You can subclass it, but there’s no need to. Just give yourself a reference to it (myButton, for instance), and then:

[[myButton cell] setShowsStateBy:NSPushInCell | NSCellLightsByContents | NSCellLightsByBackground];

View Comments (0)  

It’s not possible to directly hook up an NSSegmentedControl (or NSSegmentedCell) to a Core Data controlled NSArrayController (or any, for that instance). I wanted to be able to use one of these controllers to allow the user to select one, many or all items from the array.

To define the behaviour a little bit more: You can select the first item in the control (which will be called “All”), and it will select or deselect all of the other items, depending on what it’s state becomes. If you click on another segment, then it will toggle the selection of that segment. If all segments are ON after pressing a segment, then the first segment must also display ON, otherwise it will be OFF.

I did it by creating a new class: SegmentController. (I know, I should put on a prefix…)

SegmentController has two required IBOutlet variables, which refer to the NSSegmentedControl, the NSArrayController, and a property NSMutableIndexSet, which stores, sets and gets the selection indexes (I think this should be indices, but I’ll stick with Apple’s convention). I also have a sortDescriptors array, so that this object can sort the array controller.

There are a couple of limitations, which I might look at how I deal with - for instance, the NSSegmentedControl must have exactly one more segment than the NSArrayController has items. I’m using it to select one or more days, and this number doesn’t change. It should be possible to dynamically create the right number of segments, and populate them with values (I even have a readonly field called shortName set aside in my Day objects for this), but at awakeFromNib the NSArrayController is still empty, and I can’t figure out a nice neat way to force a fetch.

Hooking up the elements in Interface builder is easy. Create the NSArrayController, and set that up however you need to. Do the same with the NSSegmentedControl - at this stage you’ll need to put values in each of the segments. Now, create a new instance of SegmentController (you might need to add the class files to your XCode project first). Connect the two outlets up to the required objects.

Now, in the Bindings Inspector, connect up you’ll want to make the Selection Indexes parameter point to the selectionIndexes model key of your Segment Controller object.

Finally, make the selector of the NSSegmentedControl point to the selectSegment: action of the Segment Controller.

I did notice a slight delay between deselecting one segment and the “All” segment deselecting. A simple optimisation - moving the call to segmentCount out of the loop test and into a local variable made it much smoother.

That should probably do it. It might need a bit of tweaking. You should be able to have multiple instances of this in your project, if it is required. It’s been designed that you’ll need a seperate one for each Segmented Control, as it refers to the objects it is connected to, rather than the sender of the message.

My source code is here: SegmentController.zip

View Comments (0)  

I’m enamoured with Mercurial for all of my version control needs. I’d like Versions to work with it, but the response I got from the developer suggests it never will. “UI of Versions is designed completely around the concept of centralized version control ” I can see that the same type of interface would work quite well with Mercurial, or another DVCS, without too many hassles.

Still, even just with the CLI, I’m coping.

A couple of days ago I started playing with Trac for bug tracking. I had used Bugzilla (not for my own projects, but I use it at work), and it doesn’t work properly with Mercurial. The good news is that Trac does, almost out of the box.

The trac-post-commit-hook works fine, and allows me to have a repository linked in with my trac store, and when changes are checked in that have “fixes ticket:X”, it automatically updates the trac for that ticket. It’s a bit of a repetitive process to set it up (you have to manually edit both the repo/.hg/hgrc file, and the trac/trac.ini file to add support for each other, but it’s easy enough to do).

The only annoyance is that the username isn’t quite the same in both - so changes made in Trac have the username matt, whilst those made in mercurial have the default username there - which includes my full name and my email address.

View Comments (0)  

I’m currently learning stacks (and maybe developing a useful application along the way) about Core Data and Cocoa Bindings.

I managed to hook up all of the “first level” Entities to UI elements, but was struggling a bit figurng out how to get the to-many relationships to work.

To make all elements of the type Person appear in an NSTableView, you can create an NSArrayController, set it to the Entity type, and put Person in the relevant field. Then all people will appear in the list.

If you have a manager, who might supervise zero or more people, then how do you get a sub-set of People. More specifically, how do you get a just the other side of a To-many relationship.

I thought I was going to have to resort to actually writing some code, and use a Predicate, or something like that. But there is an IB only method.

You can create an NSArrayController, and as well as putting in the Entity type (and hooking it up to the Managed Object Context), just put that it gets it’s Content Set from another object - in this case it would be People.selection.supervises (or whatever it is called).

This isn’t quite flawless - if you just hook up a button to the “add:” outlet, then it doesn’t quite add properly - the reverse of the attribute is not set. I had to make up an IBOutlet in my window controller that creates a new component, and sets the relationship up.

Which meant I ended up having to write two lines of code. For each relationship.

View Comment (1)  

Three languages. Three different Object Relational Mapping systems. One operating system.

Over the past couple of days, I’ve been madly learning how to create programs in Core Data, using Objective C and Cocoa. It’s given me plenty of food for thought, and made me perhaps think that it’s not that SQL Alchemy rocks my world, it’s just that J2EE/EJB is just ORM done wrong.

I actually got exposure to SQL Alchemy in detail before J2EE - I first came across them at the same time, but using SQL Alchemy was at work, and I basically had to learn in 2 days what a full semester worth of J2EE taught me. Perhaps that was just because learning the python stuff was so damn easy.

Now that I understand just how cool an Object Relational Mapping is, getting into Core Data was easy. Creating the same schema in SQL Alchemy (actually, using Elixir, so it was just object creation), and then in a Core Data xcdatamodel - basically the same process, was even simpler in Core Data: simply because it is a GUI tool, and you can see the whole model in one go, instead of having to scroll through a text file examining classes.

But doing GUI programming using the ORM is where Core Data really shines. Using Cocoa Bindings, you can just plonk down an NSTableView, and tell the object where it gets it’s data from. If you have two GUI widgets using the same data model, and you change selection in one, it even changes the selection in the other!

Core Data also helps look after Undo, Saving and all other sorts of goodness I haven’t even come across yet.

The only thing that Core Data isn’t good for is a multi-user system - or more precisely, a system where multiple users are accessing the data at the same time. I’ve used SOAP as the messenger format, where I had a rich client accessing services provided by my server, but this is cumbersome. I’ll just use Pylons, or perhaps Django to do a web application - where the interface is largely a Web Browser. In this instance, it will probably be best to just stick to a python-based approach. I’m tempted by WebObjects, but that would still require me to use Java.

If only Apple would release a distributed Core Data. I might be able to do something kind of cool with Distributed Objects, for a rich client, at least, but for Web, I may as well do the whole thing in python.

View Comments (0)