Uncompetitive Programming (part 2)

 This is a continuation of the part 1 of this article. It presents an example of solving a problem that appears in a competitive programming site. The method of solving is utterly useless if you look at from the CP lens. It took me an order of magnitude more time and effort to come up with this solution. I don't know if my solution would pass in the online evaluation, particularly in terms of time-performance. I will try to procure a typical CP-style solution which would do well in CP evaluation and paste it here. My solution doesn't claim to be that.

And yet, I claim that this solution is superior in many important ways than a typical CP solution.

• It was built systematically.
• Options were given their due attention before one was taken and proceeded with while others were let go of.
• I spent quite a lot of time writing down my thoughts clearly in a way that is understandable to a reader.
• The code follows closely the final design.
• The code is readable to anyone who knows CS and programming. No special training for competitive programming is needed. There is some focus on performance, but not at the expense of readability or intuitiveness of the solution. 

I claim that this style, which is very very different from that of competitive programming, is the de facto style of practical programming. It is not something that any competitor programmer would be able to do given enough time. It involves a style of thinking, communication and programming that is very difficult if not impossible to learn in a CP setting. It requires a shift in mindset.

I hope that you will read the rest of this article and you will be able to see the differences w.r.t. to CP that I am trying to bring out here. I don't want to disparage CP. To do well in CP, one requires certain skills which are also quite valuable in real world. All I want to say is that CP not even the most important take on programming, let alone being the only one. Takeaways:

• Programming is like an art. It's as much about experience as about output.
• Ability to do thorough thinking is more important than thinking fast.
• Ability to communicate through written words and pictures is more important than hacking. 
• Readability is a far more important quality of a code than squeezing every cycle out of your processor.

Case Study

Problem

The problem can be found here. We solve a slight variant (or subproblem) of this problem. 

Our variant: We consider a sequence of slots. Some of these slots are empty while some are filled. The goal is to bring all elements to occupy contiguous slots. For this, we allowed to move any element from one slot to another (empty) slot with unit cost. Our algorithm has to compute the minimum cost to achieve this for a given initial state.

Our solution can be easily extended to solve the original problem.

Code

The code can be found in this GitHub repository.

Analysis and Design (Informal)

Our objective is to place all identical symbols adjacent to each other. The goal is to do so in minimum number of moves. The cost of each move, irrespective of the distance of the move, is 1.

The algorithm should compute the cost of moving, not necessarily do the moves as such.

The algorithm tries to avoid the following:

• Make repeated moves
• 
  Cause a gap to be created.
• 
  
  
  
  
• Move a ball to a place/position from which an identical ball has been moved out.

Strategy 1

Identify sets of contiguous positions occupied by balls (symbols) of a particular colour (description).

For example:

Use interval as a pivot and compute the cost of filling the gap on either sides of the pivot.

For example: For the above example, using I1 as the pivot.

However, the above is not the most optimum way of achieving contiguous interval.

The above transformation results in a contiguous interval in just one move.

Each pivot interval may have up to 2 adjoining gaps. To fill any gap, we follow the policy of using the extreme balls (symbols).

Hence, after identifying a pivot, we have to identify the adjoining gaps. For, filling each gap, we have to explore using the extreme balls, which could be up to two on each direction.

Heuristic: If there exists a gap whose length is greater than or equal to the length of an extreme interval, use the same to fill the gap.

Why: Removal of an extreme interval causes a gap to disappear.

The above method has a serious shortcoming, it looks like. For each pivot, there are two gaps adjoining. For each of these gaps, the candidate balls to use are also up to two (from extreme interval). This is a fertile pattern for an exponential growth in complexity. Each step will lead to 4 options as the subsequent step. N such steps will lead to 4 raised to N options proliferating. Of course, in the worst case.

Dynamic Programming to the Rescue

I think, dynamic programming can help here.

Suppose a trace of creating a contiguous interval has the following steps:

The total cost of 

Recursively:

This is good because can be recursively defined in terms of its tail.

If there is another trace 

If we wish to find the minimum cost of getting from a state s, it's just the minimum of the sum of the cost of getting from s to its next state plus the minimum to get to a contiguous state from there.

For example, in the following figure:

Now, the implication of this observation is that once the minimum cost of getting from a state to a contiguous state is computed, it can be memoised and used/reused anytime we reach that state through any other path. This will collapse a tree of states into a dag potentially contracting the state space explosion caused by the 4 raised to N growth discussed earlier.

There are still an exponential number of states. Suppose there are N slots and M balls. Then the number of states possible is N choose M, which unfortunately can be an exponential, and this may kill our algorithm.

The way to restrict the above explosion may be to avoid exploring non-viable options and making only smart moves. For example,

is a useless transition. Our initial idea of moving balls from the extremes can be a good option.

Local Summary

• We are gravitating towards a recursive design.
• We memoise the minimum cost per state
• We may want to remember the states visited in the current trace being explored to prevent looping.
• It's better to design computation of the next steps in a way that they inherently prevent us from visiting an already visited state.
• prevent exploring useless states, by preferably ensuring that each step leads to the improvement in some 'health' indicator (greedy approach).
• However, a greedy approach mustn't lead us to miss out on optimal solutions.

The skeleton of the algorithm now looks like this:

ALGORITHM

Note that the above is a recursive algorithm.

M(s) = nil will happen when s is being visited for the first time.

The rate of convergence of the algorithm will depend on nextstate function. The smaller the average size of n, the faster will be the convergence.

Computing next states

Let's use a simple method to begin with.

As long as a state has gaps, we keep filling those gaps by moving balls in the end (extremes) to the gaps. To limit useless possibilities, we can fill each gap starting from its left end.

For a state with g gaps the number of next states could be 2g.

Each step by definition has unity cost.

Note that we have (at least for now) given up our earlier representations of intervals.

I would like to note down a couple of observations here:

1. By choosing always a ball at the extreme end to fill intermediate gaps, we are sure to always shrink the spread, never extend it along any of its ends. Hence, the length of the slots (strings) is not important.
2. We have taken the above strategy with gut feeling that it will not miss out the best moves leading to a minimum cost. This should ideally be proved.

State representation

Again, following gut feeling, let's choose binary string representation. It appears that it will lead to simpler implementation of the functions we wish to implement. We may or mayn't be right here.

Move

We begin by defining the move function.

move: state ⤫ int ⤫ int --> state

For example:

move([0, 1,1,1,0,1], 5, 4) = [0, 1, 1, 1, 1, 0]

Gaps:

FIGURE

gaps([0,1,1,0,0,1,0,0,0,1,1,0]) = {[3,4], [6,7,8]}

Note that we exclude the unoccupied slots in the two ends.

So,

gap: state -> set of (list of int)

A function that gets us the extreme positions of the state would be helpful.

Ends

ends: state --> (int, int)

For example:

• ends([0, 1,1,1,0,1] = (1, 5)
• ends([0,1,1,0,0,1,0,0,0,1,1,0]) = (1, 10)

Now, next move functions:

Next Moves

nextmoves: state --> set of (int, int)

nextmoves computes the cross product of the ends and gaps.

For example:

Using nextmoves, we can compute the next states.

Next states

next_states(s) = {move(s, a, b) for all (a,b) in next_moves(s)}

This function can be plugged into the min_cost function above to obtain the complete algorithm.

Conclusion

To conclude, I would (again) like to bring your notice back to the point that this post comprises of rough notes; they have been written more as an aid to my own thinking, not as a representation of the final output of my thoughts. Consequently, some of the ideas which we broached in the early part of the article disappear as we proceed along. For example, the idea of representing intervals (because it was too unnecessarily complicated), or the first iterative algorithm (because our main approach itself changed). Similarly, there was a thought (almost a passing one) about making the algorithm greedy. Turns out that the algorithm we settled with is greedy. But we never again put a conscious thought in that direction after mentioning it once. A more finished article would be shorter, including only the ideas which survived till the end and found their way into the final implementation. However, that would lose track of all the ideas we explored and rejected, and the chronological order in which they appear and sometimes faded away. Note that even the ones we drop on the way have their value: they are the steppingstones to where we finally arrived. 

So, there! An uncompetitive style of programming! In this, we look at the problem from various angles. We contemplate on various options. Sometimes, our contemplation may seem idle -- as if we are more interested in the beauty of the process of thinking, instead of the result. I will share a secret here: the above is actually not fully untrue! We do care about the result, but we don't want to miss out on the fun part.

We are concerned about efficiency. We are also concerned about the time it takes to implement the program. We are concerned about the brevity of our code. But above all these, we are concerned about the readability of our code. We write a code which is understandable by a lay programmer and follows our design very closely. Programs are not just instructions to machines; they are meant to be read by humans too!