[Tutor] Comparing lines in two files, writing result into a third file

[Danny Yoo]

On Wed, 23 Apr 2003 stuart_clemons@us.ibm.com wrote:

> So, anyway, now that I think about it a little bit, perhaps sorted order
> doesn't really matter.  One responder suggested that I use dictionaries
> in my code structure.  My understanding is that dictionaries are
> mappings, not sequences, so I guess ordering is not really relevant
> here.  FWIW, It does turn out that the files I'm working with are always
> ordered sequentially when I get them.
>
> Concerning dictionaries, do you think dictionaries is the structure to
> use ? If so, I'll try to spend some time reading up on dictionaries.  I
> do remember having problems reading a file into a dictionary when I
> tried it a year ago or so.

Hi Stuart,


Yes, dictionaries will work.

It's also very possible to do the problem without dictionaries if we use a
"merging" method.  I'll try describing the idea of the "merge"  method in
terms of cards and hands; maybe it will appeal to the card game players
here.  *grin*


Imagine that we have two lists in each of our hands:

###
left_hand = [1, 3, 5, 7, 9]
right_hand = [2, 4, 6, 8, 10]
###


And imagine that our task is to bring these two hands together into one
big pile, but make sure that the big pile is sorted.  If we do this in
real life, we'll notice that we'll do something like

    put down left card (1)
    put down right card (2)
    put down left card (3)
    put down right card (4)
    ...

and so we, in a sense, shuffle the cards into order.



Now say that our left and right hands hold something like this instead:

###
left_hand = [1, 2, 4, 6]
right_hand = [3, 5]
###

We'll still assume that each pile in our hands is individually sorted.
When we try to merge these lists together, our actions are similar, but we
do a little more to figure out which hand we should put down:

                                 left = [1, 2, 4, 6], right = [3, 5]
    put down left card (1)       left = [2,4,6],      right = [3, 5]
    put down left card (2)       left = [4, 6],       right = [3, 5]
    put down right card (3)      left = [4, 6],       right = [5]
    put down left card (4)       left = [6],          right = [5]
    put down right card (5)      left = [6],          right = []
    put down left card (6)       left = [],           right = []

If we do this by hand, we notice that we have to look at the top cards
from each hand, and do something based on what we see.  But what we do is
fairly simple:

###
### pseudocode
while we have cards in both left and right hands:
    if top left card < top right card:
        put_down top left card
    else:
        put_down top right card
put any remaining hand cards into large pile.
###

The pseudocode above isn't totally correct, because it doesn't take care
of the case when the top left card is the same as the top right card.
That's where you probably want to flag one of the the card with an
asterisk before putting it into the large pile, and discarding the other.


This should give some impression of the merging approach; you may need to
adjust it so that it works with files rather than left and right hands
though.  *grin*


Good luck!