How to solve a programming assignment

Solving problems is arguably what being a programmer is all about. Problems in programming broadly come in two levels of detail. For example the overall problem “Increase efficiency in de-icing operations at Copenhagen Airport” can be turned into a more detailed problem specification:

• Planes need to have as short a time as possible, from leaving the gate until take-off in frosty weather, under the following constraints:
• When the temperature is below freezing, they must be sprayed with de-icing liquid prior to take-off.
• The de-icing liquid freezes after 1 hour.
• De-icing takes 20 minutes.
• There are is one de-icing machine.
• Taxiing from the gates to the de-icing machine takes 3 minutes.
• Taxiing from the de-icing machines to the runway takes 7 minutes.
• There is only one runway. Take-off takes 10 minutes.

The top problem is something anyone could have specified, but going from that to the second problem specification is more difficult. This article is about going from the second type of specification to code however. If you want to read about going from overall problem to a detailed specification, it is introduced in the article ‘Solving problems on a grand scale’ (to be published).

Image courtesy of http://abstrusegoose.com/ under a Creative Commons license. (http://www.ccc.uga.edu/summer/programs/comic2.png) via Wikimedia Commons

Turning specification into code

The first step of doing this, is to understand what the problem is about. What form would the successful solution look like? In this case we could imagine a graphical user interface, it could be a program which reads a text file of planned flights and spits out another text file with a schedule of which de-icing and take-off times, or it could be interactive in the command line and so on. In other words, what is the input and what is the output of the program.

We are going to restrict ourselves to a problem which reads a text-file and prints the solution to the screen.

It could be a format like this:

SK376 19:05
OY953 17:05
SK194 18:40
...

And the expected output is:

OY953 GTCL,16:30 DICE,16:35 TKOF,17:05
SK194 GTCL,18:05 DICE,18:10 TKOF,18:40
SK376 GTCL,18:30 DICE,18:35 TKOF,19:05
....

So how do we go about solving a problem of this type? It may seem completely very difficult, but as I will show in this article, you can break it down into smaller pieces, which can then be solved one by one and combined into a full solution. Another part of the technique is to solve it on paper first, with pseudo-code.

Pseudo-code

We have all been there. It is late, the code grows more incomprehensible by the minute, and hmm, what was exactly we were trying to do again? Something about sorting a list and then outputting it in binary format? Or was it supposed to be converted first and then multiplied by some constant?

It is all so confusing and it does not help with all these variables and weird syntax and brackets all over the place.

Pseudo-code to the rescue. Despite its funky sounding name, there is nothing bad or threatening about pseudo-code, it is simply code that cannot be executed by a computer (necessarily), but looks like code to humans and works in much the same way.

When we write pseudo-code we chose the syntax ourselves, we can be as relaxed or tense about types as we want and even the semantics, as long as we are consistent and can understand it ourselves. That’s the key part!

So what is the use of pseudo-code I hear a faint whisper ask?

It’s a language for describing the solution (program) to a problem, without getting too nitty-gritty into the details of how to write a program that actually works. Maybe an example would be illustrative:

var s : String
s <= "Hello World!"
print(s)

This is a dialect of pseudocode, let us immediately name it Philip-code(TM), which expresses the following:

1. Declare the variable s of type String.
2. Assign the string literal “Hello World!” to s.
3. Print s to the terminal/console/output.

This seems trivial, but let us imagine that the task we are asked to solve is “write hello world, in Java”. The Java program is going to be long and relatively difficult compared with the short and (I think) easy to read pseudo-code above. When you write the program straight in Java, or any other language, there is a big risk that you will start focusing on getting the program to compile or run, rather than on the underlying task which should be your first priority. Only when you have a pseudo-code program which makes sense, and can even be hand-run, should you proceed to translating it into Java/Python/C#.

Translating pseudo-code

Translating pseudo-code is relatively simple, as we usually do not concern ourselves with classes and objects and the like, but only with procedures and loops and variables — the building blocks of programming, the rest is really just the icing on the cake.

Translating can usually be done more or less line by line, but to do that with our little example, we will have to turn it into a method (procedure/function):

Func Main()
  var s : String
  s <= "Hello World!"
  print(s)
End Func

This looks a bit like something which could be written in Java:

public static void main(String [] args)
{
  String s;
  s = "Hello World!";
  System.out.println(s);
}

The advantage when writing such a short problem is of course not as big, but when you write longer programs it can help you keep the formulation of the logical solution, and the annoying task of getting the syntax right, separate.

If you want to learn more about my dialect of pseudo-code you can take a look here: https://medium.com/computer-programming-and-so-can-you/philip-code-tm-ecbd4537d7c0 where I briefly introduce my dialect of pseudo-code.

Now, let us look at a technique which can help with formulating the solution, to problems that we may not be able to easily figure out an answer to.

Divide-and-conquer

This concept was, according to Wikipedia, invented by Philip of Macedonia(notice the name?) and back then meant something like dividing your enemies into smaller groups that each had less power, and thus was easier to deal with. When you solve a problem by divide-and-conquer in programming, it means something similar. You solve it by dividing it into smaller pieces that can then be solved.

It is used in two senses, one algorithmic and one of problem analysis, but it is the same thought that is behind both: break a problem down into small parts that you can solve easily, then combine those solutions to form bigger parts of the solution, combine these and so on, until you have the full solution.

I am going to first go through a simple example and then go back to the example from the beginning, outlining a solution for that one, but first:

Let’s say you are asked to sort a list of numbers and that you do not know how to do that. But let us imagine that the list consists of only two numbers, you would know how to solve those, right?

A simple pseudo-code program for sorting a list of two numbers could look like this:

var list : List<Integer>
list <= {a,b}
if (b > a) then
  temp <= a
  list[0] <= b
  list[1] <= temp
end if

What this means is: we have a list of two numbers, a and b. If b is greater than a, then we need to switch them around. This happens by assigning a to a temporary variable, assigning b to the first (zero-th) position in the list, then assigning the temporary variable (which was a) to the second position in the list, thus switching their positions.

Now we can solve a list of two numbers, but how about sorting a list of n numbers? That is, admittedly, a bit more complicated, but not as much as you might think. Again we can use our divide and conquer strategy. We solved a part of the problem, namely the special case of n=2 or two elements in the list.

For longer lists, we need repetition. We could imagine doing this for the whole list, such that the biggest element ends up in the end, that would at least be part of the way there. Consider:

# variable declarations
var list : List<Integer>
var i : Integer
list = [a,b,c,d] #a,b,c,d are integers like 1,2,3,4
For i <= 1, i<length(list),i<=i+1 
  if (list[i] > list[i-1]) then
    temp <= list[i] 
    list[i] <= list[i-1]
    list[i-1] <= temp
  end if
End For

Let us look into what this new and seemingly much more complicated code does. We have introduced a concept called the for loop. The for loop exists in most languages, for example Java and Python, and it is simpler than it may look at the surface.

The for loop in the example sets a variable i to 1, runs as long as i is smaller than the length of the list and every time the loop reaches the end at “End For”, it increases i by 1 (it increments i). Inside the loop we have a single if statement, which checks if the current position in the list, list[i], is bigger than the previous position in the list list[i]. If it is, it swaps the two elements by way of a temporary variable.

When we keep running this and swapping if an element at position i is bigger than the one at position i-1, for all i, then the biggest element should end up at the end of the list. That’s pretty good! It’s not really sorting the list, but we now know how to pick the biggest element and move it to the end. Surely we can build on this?

If we go through the list, find the biggest element, move it to the end, then we go through the remaining part of the list and do it again, in the end the list will be sorted when the remaining list is just two elements long. That sentence is a bit convoluted but this type of sorting is called bubble-sort and maybe it will help you to think of it this way: Each time we go through the list and the biggest element “bubble” to the top. Since that element is already at the end, it has already been sorted in other words, we just have to repeat our algorithm on the rest of the list.

This is not a particularly efficient way of sorting a list, but the algorithm is easier to understand than other more efficient ones.

The code looks something like this:

# variable declarations
var list : List<Integer>
var i : Integer
list = [a,b,c,d] #a,b,c,d are integers like 1,2,3,4
For j <=length(list)-1, j>1,j<=j-1
  For i <= 1, i<j,i<=i+1 
    if (list[i-1] > list[i]) then
      temp <= list[i-1] 
      list[i-1] <= list[i]
      list[i] <= temp
    end if
  End For
End For

We have packed the existing for loop in another for loop, which has j as its variable and starts from the end of the list instead and counts down from length(list)-1 to j=2 (j>1). The only modification of the inner loop is that it now runs for as long as i < j, which means that on each iteration it will stop one position earlier.

Implementing this in Java, or whatever language you choose, is left as an exercise for the reader.

I have made an implementation here: https://repl.it/@Philip_KaareKaa/BubbleSortJava which shows the bubbling happening along the way, but I encourage the reader to attempt the solution first.

An excellent animation from Wikipedia can be found here.

Getting the airplanes off the ground

This one is a bit more difficult, but the code may actually be easier to read than in the above example.

Let us have a look at the requirements again:

• Planes need to have as short a time as possible, from leaving the gate until take-off in frosty weather, under the following constraints:
• When the temperature is below freezing, they must be sprayed with de-icing liquid prior to take-off.
• The de-icing liquid freezes after 1 hour.
• De-icing takes 20 minutes.
• There are is one de-icing machine.
• Taxiing from the gates to the de-icing machine takes 3 minutes.
• Taxiing from the de-icing machines to the runway takes 7 minutes.
• There is only one runway. Take-off takes 10 minutes.

How do we solve something like this? We need to divide and conquer. There are more or less three parts here:

The input, the algorithm which figures our a solution to a given input, and the output. So we need to read the input and turn it into something our program can understand, then we need to make a solution, and then we need to print it. I have made an implementation in Java, but I suggest that you first try to follow along in the article before opening it. The link will be at the end of the article.

Input

Let us start with reading the input. We are only told that it looks like:

SK376 19:05
OY953 17:05
SK194 18:4

That looks like the flight id first and then a scheduled take-off time, separated by space. That is relatively easy to read, we could make a program that looks something like:

Func ParseInput() : List<(string, time)>
  var line : string
  var parts : List<string>
  var flights : List<(string, time)>
  While (input.hasMoreLines())
    line <= input.readLine()
    parts <= line.split(' ')
    flights.add((parts[0], time.parse(parts[1])))
  End while
  Return flights
End Func

Okay, so there is a lot going on here, we are reading from standard input with an object I just invented called input and while there are more lines to read, we read them, split them at their spaces and then we add the parts to a list called flights. Flights consists of pairs(2-tuples) of string and time, and time has some kind of way to read a string in standard 24-hour time format (here called time.parse). This is pretty close to a solution you could write in many programming languages so translating it should be relatively straightforward.

The tuple datatype

The tuple is a very useful datatype, and since we are going to be using it in this example (already have in fact), I better introduce it properly.

You may know the tuple from mathematics where it is a collection of numbers for example (4,3,6) is a 3-tuple of the numbers 4,3,6. They come in that order and the tuple has that value and it cannot be changed, once assigned.

In programming we extend the tuple to other data types like string, so we can declare a tuple of two strings and one number for example:

var tuple : Tuple<string,int,int>
tuple <= ("This is a tuple!", 1,2)

This declares a tuple of type string, int, int and assigns it the value (“This is a tuple!”, 1,2). The tuple is very useful for grouping different kinds of information together, like a flight id and a scheduled take-off time.

Output

The output is supposed to look like:

OY953 GTCL,16:30 DICE,16:35 TKOF,17:05
SK194 GTCL,18:05 DICE,18:10 TKOF,18:40
SK376 GTCL,18:30 DICE,18:35 TKOF,19:05
....

If you are not told anything that could be difficult to read, but luckily the customer explained at a meeting that it is to interpreted this way:

First comes the flight number, then the gate closing time, then de-icing time and finally actual take-off time. To be able to print this we need a data structure which can contain this information, and a 4-tuple seems ideal.

To print it we could declare a function which takes a 4-tuple and prints a line looking like the expected output. Then we could call that function for each 4-tuple:

Func printFlightLine(f : Tuple<string, time,time,time>)
  print(f[0] + " GTCL," + f[1] + " DICE," + f[2] + " TKOF," + f[3]
End func

The algorithm

So now we have a function which can read the input and give us a pair(2-tuple) of the flight id, and its scheduled takeoff time, and we have a function which can print a 4-tuple of flight id, gate closing time, de-icing time and expected take-off time.

Now all we need to do is the actual planning.

If we look at the requirements we can see that the time from arriving at de-icing until takeoff is at least 27 minutes.

That means that de-icing has to start, at the latest, 27 minutes before take-off to give time to actually complete the de-icing and get to the runway.

Gate closing has to happen at least three minutes before that. Let us imagine that we have just one plane which takes off at 12:00 noon exactly.

Then we can calculate backwards that de-icing has to happen at 11:33 at the latest (12:00–27 minutes). The gate then has to be closed at 11:30 (11:33–3 minutes). If we have another plane at 13:00 we can do the same kind of math, as the de-icing machine is not busy. This is very simple arithmetic, so the only problem is, what if the machine is busy?

We want to keep it as busy as possible, as it is the bottleneck for getting flights off the ground, so we just assign the next plan to the earliest possible de-icing time. The contours of a solution are beginning to show themselves.

How to figure out what the earliest de-icing time is for a given plane? Well that depends on the previous plane, as it will be 20 minutes after the first plane has finished de-icing.

So the algorithm looks like this:

• Sort all the flights be scheduled take-off time.
• If the next available de-icing time is before the scheduled takeoff time minus 27 minutes, then set the de-icing time to be scheduled takeoff time minus 27 minutes.
• If the next available de-icing time is after the scheduled takeoff time minus 27 minutes, then set the de-icing time to be the next available de-icing time.
• Set expected takeoff time to be 27 minutes after de-icing
• Set gate closing to be 3 minutes before de-icing.

Or in pseudo-code:

var input_flights = ParseInput() #list of 2-tuples
var i : int
var input_flight : Tuple<string, time>
var output_flight : Tuple<string,time,time,time>
var latestDeice : time
var scheduledTakeoff : time
var nextDeiceSlot : time
nextDeiceSlot <= time(0,0) //12 midnight
var scheduledDeice : time
var gateclosing : time
var expectedTakeoff : time
sort (input_flights) # sort them by scheduled take-off
For (i <= 0,i<flights.length;i<=i+1)
  input_flight <= input_flights[i]      
  scheduledTakeoff <= input_flight[1]
  latestDeice = scheduledTakeoff.minusMinutes(27)
  if nextDeiceSlot.isAfter(latestDeice) then #take it                               
    scheduledDeice <= nextDeiceSlot #Get next slot
  else                                  
    scheduledDeice <= latestDeice  
    #Next slot is earlier than we need
expectedTakeoff <= scheduledDeice.plusMinutes(27));
  gateclosing <= scheduledDeice.minusMinutes(3));
  nextDeiceSlot = scheduledDeice.plusMinutes(20); 
  #Next deice is 20 minutes later 
  output_flight <= (input_flight[0], gateclosing, scheduledDeice, expectedTakeoff)
End for

The example might be a lot to take in, but if you try to hand-run it line by line, I hope it will make sense. If you want you can also just jump straight to the code. You can run it here: https://www.jdoodle.com/a/G2Y. Please feel free to play around with it. You have to paste the input in the “ Stdin Inputs…” field.

I have embedded the code below as well: