If you practice programming puzzles regularly, you probably keep an archive of your solutions. This can be useful for reference when you encounter similar problems. And even if you never look at some of them again, disk space is cheap and source code is small, so why not?
The simplest way to save your solutions is to put all of the files related to each solution (source code, input text, sample output text, etc.) in a directory on your local disk. I suggest going one step beyond that, and using a source control system to keep track of your solution files. These days, it makes sense to use Git.
Why Use Source Control?
If you’re working on a software development team, then using source control is as basic as using a text editor. But why use it for solo development on code that you’ll only be working on for a short time?
One reason is getting experience with tools. Just as you’re gaining experience in coding fluency by working on programming puzzles, you can get more fluent in using Git by using it for your puzzle solutions. Git is a core developer tool that you want to be able to use unconsciously, without having to think about syntax or workflow.
But beyond that, there’s another reason using source control in this context is useful: When you work on a problem, you should go through a consistent set of problem-solving steps. I describe the process I use in How to Attack a Programming Puzzle. At each step in my process, I make changes to text files. Source control gives me a lightweight way to capture the state of my solution at each point.
Here’s an example you have surely encountered in programming: You’re in the middle of implementing a change when you realize that there’s something fundamentally wrong with how you’re approaching the solution. You need to go off in a different direction, but you don’t want to lose the code you have so far in case some of it can be salvaged. A simple approach to this problem is just to make a copy of your source file(s). That can work, but it’s a crude approach. A better solution is to use source control features designed for this scenario. Source control allows you to save reminders about why you’re branching off with an experiment, and your old and new source files can be easily compared.
To make the process of using Git for programming puzzle solutions more concrete, let’s go through an example workflow.
Tracking Your Puzzle Code with Git
If you don’t already have Git installed, you can get it from the official Git page (or go directly to the Downloads page). While you’re there, you can find links to a free book about Git, as well as Try Git, an interactive online tutorial.
Since I don’t know what platform you’re coding on, I won’t go into any more detail about installation steps. But the Git site has everything you need.
Since Git is popular, there are numerous cheat sheets and other tutorials to help you get started. But to really learn Git, you’ll want to use it for your own coding. The advantage of using it for programming puzzles is that you’ll get a lot of practice at the end-to-end process of using it.
One more thing before we get started: I’m going to use the command line in my examples. One reason for this is that it’s platform-independent. The command line tools have the same interface regardless of what operating system you’re using them on. But another reason is that it’s good to be familiar with how to do basic operations using the command line. GUI tools can be useful for some purposes like browsing through a commit log or checking diffs, but it’s good to know what’s going on behind the scenes.
git init is the command you use to create a new Git repository. It’s how you tell Git you want it to track the files and subdirectories in a particular directory.
In the early days of Git, Linus Torvalds, creator of Git and the Linux kernel, wrote:
In many ways you can just see git as a filesystem – it’s content-addressable, and it has a notion of versioning, but I really really designed it coming at the problem from the viewpoint of a filesystem person.
When you create a directory on your local disk, the files in it are managed using the file system provided by your operating system. The OS file system is general-purpose, designed to be used by all the applications you have installed. By running
git init, you get access to a special-purpose file system for programmers.
For programming puzzles, I’ll assume that you have a directory containing subdirectories for each problem. In the example I’m going to work through, I have created the directory structure
D:\Projects\UVa. If you’re in a unix-like environment, you can make the appropriate adjustments.
Here’s what happens when I run
git init in that directory:
D:\Projects\UVa>git init Initialized empty Git repository in D:/Projects/UVa/.git/
This message means that Git has created a hidden directory called
.git, where it will store the data it uses to keep track of the repository that I just initialized.
As I mentioned in my process article, I recommend starting your puzzle solution by copying a set of template files to a working directory. These files give you a starting point that lets you skip writing boilerplate code and get right to the important part of your solution.
Let’s assume for this example that I’m working on UVa 735: Dart-a-Mania, which I wrote about a couple of weeks ago. For this problem, the shell script that sets up my puzzle solution files would drop me in
D:\Projects\UVa\735 with the appropriate files open in my editor.
To find out what Git thinks about your files, the command to use is
git status. Here is the output I get from that command in my initial state:
D:\Projects\UVa\735>git status On branch master Initial commit Untracked files: (use "git add <file>..." to include in what will be committed) ./ nothing added to commit but untracked files present (use "git add" to track)
When you first create a file in a Git repository, it is known as an untracked file, which means Git sees it, but isn’t doing much with it.
From the status message, it should be clear what Git wants you to do next.
To have Git pay attention to a file or directory, you need
git add. In this example, where we have just created a directory and files, the simple thing to do is to run
git add . from the directory. In true Unix style, this command produces absolutely no output. But if you run
git status again, you can see what happened:
D:\Projects\UVa\735>git status On branch master Initial commit Changes to be committed: (use "git rm --cached <file>..." to unstage) new file: 735.txt new file: Main.java new file: go.cmd new file: input.txt
The four files from my solution template are now being tracked as new files.
Whenever you reach a logical stopping point in your development process, it’s a good idea to run
git commit. This command records the state of the files you have added and lets you specify a message describing that state. For this puzzle workflow example, I’ll be suggesting a few points where I recommend running
commit. This is the first one: right after you
git add your template files. Here’s how to do it:
D:\Projects\UVa\735>git commit -m "UVa 735: Initial commit" [master (root-commit) fed571f] UVa 735: Initial commit 4 files changed, 216 insertions(+) create mode 100644 735/735.txt create mode 100644 735/Main.java create mode 100644 735/go.cmd create mode 100644 735/input.txt
This commit saves your initial state, so you can compare it with changes you make as you write your solution.
git status now shows that your branch is ready for more changes:
D:\Projects\UVa\735>git status On branch master nothing to commit, working directory clean
Once the template is committed, I can proceed through the steps of my problem-solving process:
- Read the problem statement and take notes on it.
- Solve the problem at a conceptual level.
- Expand the conceptual solution into pseudocode.
- Translate the pseudocode into real code.
- Test and debug locally.
Here’s how my repository looks when I’m done with these steps:
D:\Projects\UVa\735>git status On branch master Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git checkout -- <file>..." to discard changes in working directory) modified: 735.txt modified: Main.java modified: input.txt Untracked files: (use "git add <file>..." to include in what will be committed) Main.class output-check.txt output.txt no changes added to commit (use "git add" and/or "git commit -a")
Notice that the output is divided into two sections:
Changes not staged for commit: These are the files I modified while solving the problem locally.
735.txtis the text file I use for taking notes as I work on my solution.
input.txtis the sample input from the problem statement. And of course,
Main.javais the solution source code.
Untracked files: These are new files that I created while working on my solution.
output.txtis the result of running
output-check.txtis the sample output from the problem statement.
Main.classis not a file that I want to track, so I’ll deal with that shortly.
One command that I like to use before committing is
git diff. By default, this command displays the changes you have made to your tracked but unstaged files. It’s a good habit to check your diffs to make sure you’re clear about what changes you’re making.
A couple of notes about
- The related command
git difftoolwill launch a graphical diff tool. That’s the version I use in most cases, since it makes it a lot easier to visualize the changes.
- By default,
difftoolonly diff files that are tracked but not staged for commit. There are arguments you can use to change this behavior, which I won’t cover here.
There are some files you want Git to ignore, usually because they are generated automatically so they don’t need to be tracked. Java
.class files are one example. To prevent these from being committed to the repository, you can use a file called
.gitignore. This file contains patterns that Git uses to decide which files it shouldn’t care about. For this example, I created
D:\Projects\UVa with a single line,
*.class. Note that the
.gitignore file itself will appear as an untracked file when you first create it! This is by design, since it’s an important file to keep track of.
At this point I can run
git add . in the repository root to stage all of my untracked and unstaged files (excluding
Main.class, which is now ignored). Then I can do another
git commit with a message like
UVa 735: First local implementation.
At this point in my problem-solving process, I always check uDebug for test data that’s more comprehensive than the sample input provided by the problem statement. That will often lead to another commit with some bug fixes. Finally, I make an official UVa Online Judge submission, fix any further issues if I don’t get an Accepted verdict, and commit those changes. If a problem is particularly interesting and I’m writing a blog post about it, I may also make changes while writing the post, and commit those as well.
To get a list of the commits you have made, you can use
git log. For my example process, the output might look like this:
commit 433c38cfc67691133de96d9d4c48bf2e38cad7b8 Author: Duncan Smith <email@example.com> Date: Sun Jan 17 20:52:46 2016 -0800 UVa 735: A few changes for blog post commit 53f88d6a579ac1d429eb352bbc1aad32145f2e2d Author: Duncan Smith <firstname.lastname@example.org> Date: Sun Jan 17 17:51:34 2016 -0800 UVa 735: Accepted solution commit 3f9bab696c69ab4e37d777cac2dae0135bcc3f67 Author: Duncan Smith <email@example.com> Date: Sun Jan 17 17:45:16 2016 -0800 UVa 735: Fixed some bugs found using uDebug input commit 08dce7a4723d050ba84ec904441b08f55acef7a6 Author: Duncan Smith <firstname.lastname@example.org> Date: Sun Jan 17 17:23:40 2016 -0800 UVa 735: First local implementation commit fed571fa6173cb55c1c843513909357d95d1e7d8 Author: Duncan Smith <email@example.com> Date: Sun Jan 17 16:46:19 2016 -0800 UVa 735: Initial commit
Keeping Track of Your Code
You can do a lot more with Git than what I have shown here. In particular, I haven’t said anything about branching or using a remote repository. But the workflow presented in this article gives you what you need to enjoy the benefits of tracking code on your local machine. Keeping track of your puzzle code and related text files in Git helps you be more systematic about your problem-solving process, especially with complex puzzles that take several tries to get right.
(Image credit: Yuko Honda)