Why programming is hard? Because data and code are inextricable

This is my best-effort guess. Before you can rely on it you'll need a proof that is not supplied.

There is a mathematical property that makes programming difficult. It is that every operation done on a computer assumes many things about the information it operates on, through the representation that is picked for the information.

In short, you have to break your problem into numbers, then represent the problem through those numbers. In a logical problem-solving fashion. This part cannot be eliminated from programming.

Lets take a classical example from Seven Bridges of Königsberg. You get a map with land, rivers and bridges. You have to devise a walk that crosses each bridge exactly only once and you cannot cross the river by other mean than by crossing a bridge.

If you only care about the bridges, and about the path in terms of those bridges, you could get away with giving the following input about the bridges:

0 1  0 1  0 2  1 3  1 3  1 2  2 3

Here the land masses are numbered and we have two numbers for each bridge. The described kind of walk is impossible to construct for this specific input.

How do you prove that? One way is to deduce what kind of properties the correct answers have. The correct answer...

  1. Starts and ends to a mainland.
  2. Is a sequence of bridges being crossed.
  3. Includes every bridge.
  4. Subsequent bridges share a mainland.

Since the problem contains only 7 bridges, you can construct every valid walk and see that there is not a valid walk that includes all seven bridges. Longest walks you can construct are seven bridges long, here's an example of one:

0 1 2 5 3 4

In the input we also describe the numbers for bridges, in the index. The first bridge (0 1) is bridge 0, the second bridge (0 1) is bridge 1, and so on...

You can further reduce the search space by observing how many bridges are connected to a land. If the land has odd number of bridges, it must be a endpoint for the walk. If you have more than two land masses that connect with odd number of bridges, since you only have two endpoints, it means that you cannot produce a path that includes all seven bridges.

It also reveals that if you cannot include all seven bridges, if you can remove a bridge such that you end up with at most two land masses with odd degree, it means you can produce a walk that includes six bridges.

All landmasses in Königsberg's bridge problem have odd number of bridges connecting them. Since there are 4 of them, that's more than 2, therefore we cannot solve the problem without excluding a bridge.

The set of constraints and knowledge about the problem and the inputs allow you to construct a program that solves this problem.

The bridge problem in itself can be very interesting, but if you look at the code and data, you can probably imagine how they correspond. We have reduced bridges and landmasses to numbers, and further have pairs of numbers to describe which landmasses are connected by bridges. We assume that bridge cannot connect to a bridge, and that a landmass cannot work as a bridge. Furthermore we do not need an exact cartographic map about the bridges and landmasses.

Programs cannot be written without relating them to some sort of information or format. Therefore the representation of the information on the computer is a large part of programming and it has a large influence on how the program is written.

Similar posts