# Interesting problems

## Bug?

The following C code has a bug in it. Can you find it? (From The Practice of Programming by Brian W. Kernighan and Rob Pike)

```int read(int *ip) {
scanf("%d", ip);
return *ip;
}

.
.
.

insert(&graph;[vert], read(&val;), read(&ch;));
```

## The middle state in one dimensional binary automata

I came across the following problem on Alife.

Consider a one dimensional binary automaton defined as follows:

• Its state consists of 10 bits.
• At time t=0, its state is "0110101110".
• At time t=2, its state is "0010101001".
• Let i denote a bit position; i is in the range [0,9].
• The state bits are "circular". That is, state bit i is adjacent to state bit (i - 1) mod 10 and state bit (i + 1) mod 10.
• The binary automaton has a radius of 1. Its neighborhood is 3. That is, the next state of bit i is computed by examining bits (i - 1) mod 10, i and (i + 1) mod 10.
• The problem is to determine the state of the automaton at time t=1.

Some thoughts on the solution:

• One may solve this problem by enumerating all 256 possible automata of radius 1. This is hardly an efficient solution to the problem.
• Consider the general case where there is an arbitrary number of state bits and an arbitrary radius. There is a suprising similarity between this problem and the classic SAT problem. I suspect that this problem maybe NP-complete.

## Weighing coins

This problem is quite well known. However, I had not thought of it in an information theoretic way until I came across it in Elements of Information Theory by Thomas M. Cover and Joy A. Thomas.

• Suppose one has n coins, among which there may or may not be one counterfeit coin.
• If there is a counterfeit coin, it may be either heavier or lighter than the other coins.
• The coins are to be weighed by a balance.
• Find an upper bound on the number of coins n so that k weighings will find the counterfeit coin (if any) and correctly declare it to be heavier or lighter.
• What is the coin weighing strategy for k=3 weighings and n=12 coins?

## Computing area

This problem came up at our local programming contest in 1997. The question was designed by David Neto.

• You are to compute the area of the polygon described a set of vertical and horizontal lines.
• The input to your program describes a path around the polygon.
• The path is described as a set of directions:
• North: 'n'.
• East: 'e'.
• South: 's'.
• West: 'w'.
• The path description will be terminated by a period, '.'.
• The path will never cross itself and will never go over the same area twice.
• You may assume that the path is made up of no more than 50000 segments.
Here is some same input:
```e
n
w
s
.
n
e
s
e
n
e
s
s
w
w
w
n
.
```
and the output corresponding to the input:
```1
5
```

How quickly can you compute the area of a polygon described in this fashion?
What is the order of the computation that needs to be performed?
How small a program can you write to perform this computation?

## A self reproducing program

This problem is a classic.
Write a program in C that produces an identical copy of its source code as output.
Here is my version: sr.c. Take a look at it only after trying the problem yourself.

## A doubly linked list with just a single pointer

This problem is a slightly modified version of a problem in Introduction to Algorithms by T. H. Cormen et al, 2nd edition, McGraw Hill, 2001.

A doubly linked list is usually implemented using two pointers: prev and next.
Can you implement a doubly linked list with just a single pointer?
You may assume that you are writing the doubly linked list code in C/C++.
You should also think about the portability of the code you are writing.
Apart from the memory savings, are there any other advantages to the single pointer implementation?

Updated December 19, 2001