What's your take on this little input processing task?

Question

I came across a little problem that looks very easy but requires a bit more thought than I first assumed. It can also be solved in many different ways and, I think, would be a perfect interview question. So what solution would you write down?

Your input is a stream of pairs (x, y), with each x and y on a separate line. A short example, starting with the pair (fruit, apple):

fruit
apple
book
Harry Potter
book
Bible
vehicle
car

You're asked to print the first n pairs, where adjacent pairs that all have the same x are counted as one. So, for n=2 you should output these lines:

fruit
apple
book
Harry Potter
book
Bible

What's your most elegant way to solve this problem (in a language of your choice)?

Answer 1

Unless I'm missing something, this seems to be a very simple algorithm. I don't have the time to write up code for it, but assuming you know n ahead of time:

1. Set i = 0
2. Read in x
3. Output x
4. If x != last x, increment i
5. Read in y
6. Output y
7. If not EOF and ((read in x) == last x or i < n), goto 3

I wouldn't even bother reading in input you're not going to use. You might want to handle the EOF case before step 5 in case of invalid input, however.

Edit: I was missing something - the case when the last key is repeated. I modified the loop condition and loop point to reflect it.

Answer 2

In Python, a (relatively) simple piece of code:

# Open file.
infile = open ("infile.txt","r")

# Only do two groups.
n = 2

# Loop until groups exhausted.
lastkey = None
while  True:
    # Get key and value, exit loop if EOF.
    key = infile.readline()
    val = infile.readline()
    if val == "":
        break

    # Remove newlines.
    if key[-1:] == "\n":
        key = key[:-1]
    if val[-1:] == "\n":
        val = val[:-1]

    # Special handling for first key.
    if lastkey == None:
        lastkey = key

    # New key means new group, print an decrement group counter.
    # Exit loop here if groups exhausted.
    if lastkey != key:
        lastkey = key
        n = n - 1
        if n == 0:
            break

    # Same group or not all groups finished, just print it.
    print "%s"%(key)
    print "%s"%(val)

infile.close()

For the input file:

fruit
Apple
fruit
Banana
fruit
Pear
book
Harry Potter
book
Bible
vehicle
Car
book
Earthsea

it produces:

fruit
Apple
fruit
Banana
fruit
Pear
book
Harry Potter
book
Bible

Answer 3

I'd adapt the container to the purpose. Don't try and find which language this is, it's a very personal combo (not that far from C++ though) ;-)

1) create a container that associates a string (first item of a pair) to a list of strings (successive second items of the pairs with same first item)

vector<pair<string, list<string> > > container;

int currentIndex = 0;
string currentKey;

forever
{
  string newKey;
  cin >> newKey;
  if( newKey == "" )
  {
    break;
  }

  if( newKey != currentKey )
  {
    ++currentIndex;
    container[currentIndex].first = newKey;
    currentKey = newKey;
  }
  string value;
  cin >> value;
  container[currentIndex].second.push_back( value );
}

2) iterate through the vector to count the number of printed strings (the internal lists won't be counted as more than one)

foreach( index in container ) until (index > n )
{
   foreach( seconditem in container[index].second )
   {
     print( container[index].first, seconditem );
   }
}

Is this elegant enough for you ? :)

Answer 4

import os
fp=open(myfile)
n=2 # or whatever
previous = None
count = n
for line in fp:
    print line
    print fp.readline()
    if line!=previous:
        count -= 1
    if count<0:
        break