How Did Nepal Count Its People with Its First Computer?

Each card is one person. Column 1 is the ward they live in (1 to 9), column 2 their sex (1 for a man, 2 for a woman, a code we made up for this village), columns 3 and 4 their age in years, and column 5 whether they read and write (1 yes, 2 no). So the card 21242 is a woman of 24 in ward 2 who can’t read.

• a.Choose Ward and run the cards. Which ward has the most people? How many live in ward 9?
• b.Press Start again, choose Sex and run them. How many men and how many women live in the village?
• c.Now find how many women can read. You can’t do it in one pass. (Hint: once every card is in a pocket, tap a pocket to keep only its cards.)
• d.Press Start again. Sort on Age 10s, gather, then on Age 1s, and gather. Is the deck in age order? Start again, and do it the other way round: Age 1s first, then Age 10s.

The sorter never once compared two cards to see which person was older. It only looked at one hole at a time. And still, after two passes, the whole deck was in order. How?

A card for each person

A punched card is a stiff piece of paper with places for holes in rows and columns. The standard card IBM brought in in 1928 had 80 columns; a column with a hole in row 4 means the digit 4. So one card could hold a whole line of numbers, and a machine could read it with metal brushes or pins that touched where there was a hole.

Before anything could be punched, every answer on the census forms had to become a number: a code. In 1971 most questions on Nepal’s forms already had codes on the form, which made this easier. Then operators punched the codes into 80-column cards on a machine with a keyboard, like a typewriter that makes holes. It was slow work, so they worked in shifts, day and night.

The sorter: one column, one pocket

A card sorter reads one column of each card as it goes past and drops the card into the pocket for that column’s hole. IBM’s sorters had a pocket for each of the card’s 12 rows and one more for blank cards and rejects, and the later ones read 650 to 2,000 cards a minute. To sort on a number with several digits you ran the deck through again: one pass for each column of the number.

A sorter gives you counting for free: when all the cards are in the pockets, the size of each pile is a tally. That is exactly what a census needs. The 1971 census published the number of men and women in every ward of the country, a tally by two columns, ward and sex.

Why the last digit goes first

Here are four cards with ages 31, 25, 37 and 22. Watch what each pass does.

The pass on the tens puts 22 and 25 into pocket 2 and 31 and 37 into pocket 3. Here is the key: inside each pocket, the cards stay in the order they were read. 22 went into pocket 2 before 25 because the pass on the ones had already put it ahead. So the last pass decides the big order, by tens, and the earlier pass has already settled the order inside each pocket.

The other way round, a pass on the tens gives 25, 22, 31, 37, a good start, but a pass on the ones then puts 31 first again, and the tens order is lost. Whatever you sort on last wins, so the most important column must go last, and the least important first.

These steps are in Python, from Grade 8. A card is a string of five digits, and the village is a list of 30 of them, the same cards as in the sorter above. card[0] is the first column (Python counts from 0), so column 1 on the card is card[0] and the age is card[2] and card[3].

Step 1: punch a card

This program punches one card as a picture: ten rows, one column for each digit, a black square where the hole goes. (pixels is this page’s own little module for drawing squares; on a computer of your own you would use another library.)

from pixels import show_grid card = '21242'     # ward 2, a woman, age 24, can't read rows = []for row in range(10):    line = ''    for digit in card:        if int(digit) == row:            line = line + '#'        else:            line = line + '.'    rows.append(line)    print(row, line) show_grid(rows, {'#': 'black', '.': '#f3e2b0'})

0 .....1 .#...2 #.#.#3 .....4 ...#.5 .....6 .....7 .....8 .....9 .....

Picture

Change card to your own: your ward, your sex, your age, and 1 because you can read.

Step 2: count like the pockets

A sorter’s pockets are ten counters. In Python they are a list of ten numbers, and each card adds 1 to the counter of its hole.

village = ['11182', '21242', '21032', '21221', '41012', '42282', '22222', '51052', '32012', '62312',           '21111', '52042', '31582', '81061', '71332', '11052', '32262', '41162', '92172', '62042',           '41152', '51061', '42271', '21252', '82022', '41192', '12642', '72012', '21392', '51702'] def tally(deck, column):    counts = [0] * 10    for card in deck:        hole = int(card[column])        counts[hole] = counts[hole] + 1    return counts print('By ward:', tally(village, 0))print('By sex: ', tally(village, 1))print('Reads:  ', tally(village, 4))

By ward: [0, 3, 7, 3, 6, 4, 2, 2, 2, 1]By sex:  [0, 18, 12, 0, 0, 0, 0, 0, 0, 0]Reads:   [0, 5, 25, 0, 0, 0, 0, 0, 0, 0]

The same numbers as the pockets. [0] * 10 makes a list of ten zeros, and counts[hole] is the pocket for that hole. One pass through the list counts every ward at once.

Step 3: one pass of the sorter

A pass needs ten pockets that each hold cards, so the pockets are a list of lists: pockets[3] is the list of cards in pocket 3. Each card is added to the end of its pocket’s list with append, so the cards in a pocket stay in the order they were read. Gathering joins the ten lists into one, pocket 0 first.

village = ['11182', '21242', '21032', '21221', '41012', '42282', '22222', '51052', '32012', '62312',           '21111', '52042', '31582', '81061', '71332', '11052', '32262', '41162', '92172', '62042',           '41152', '51061', '42271', '21252', '82022', '41192', '12642', '72012', '21392', '51702'] def sort_pass(deck, column):    pockets = [[], [], [], [], [], [], [], [], [], []]    for card in deck:        pockets[int(card[column])].append(card)    new_deck = []    for pocket in pockets:        new_deck = new_deck + pocket    return new_deck def ages(deck):    line = ''    for card in deck:        line = line + card[2] + card[3] + ' '    return line deck = sort_pass(village, 2)      # tens firstdeck = sort_pass(deck, 3)         # then onesprint('Tens, then ones:', ages(deck)) deck = sort_pass(village, 3)      # ones firstdeck = sort_pass(deck, 2)         # then tensprint('Ones, then tens:', ages(deck))

Tens, then ones: 70 01 01 01 11 31 02 22 22 03 33 04 04 24 64 05 05 15 25 06 06 16 26 17 27 18 28 58 19 39 Ones, then tens: 01 01 01 02 03 04 04 05 05 06 06 11 15 16 17 18 19 22 22 24 25 26 27 28 31 33 39 58 64 70

Step 4: the whole country

The sorter’s way needs one pass a column, however many cards there are. Nepal’s 1971 count had 11,555,983 people. Suppose each had one card (the reports don’t say how many cards were used), and the cards were sorted by age on a sorter reading 1,000 cards a minute. Compare that with the bubble sort of Grade 8, which compares cards two at a time.

people = 11555983          # Nepal's census, 1971per_minute = 1000          # cards a sorter reads in a minute passes = 2                 # the age's ones, then its tenscards_read = passes * peoplehours = cards_read / per_minute / 60print('Sorter:', cards_read, 'cards read, about', round(hours), 'hours') comparisons = people * (people - 1) // 2print('Bubble sort:', comparisons, 'comparisons')years = comparisons / per_minute / 60 / 24 / 365print('At 1,000 comparisons a minute:', round(years), 'years')

Sorter: 23111966 cards read, about 385 hoursBubble sort: 66770365770153 comparisonsAt 1,000 comparisons a minute: 127036 years

• Two passes put the whole village in age order, ones first, then tens, and the machine never compared two cards. The other way round, the deck came out in order of the age’s last digit.
• The work grows with the cards, not with the cards squared. Sorting all 11,555,983 people by age: 2 passes, about 385 hours of one sorter, 16 days without stopping. Comparing every pair, as bubble sort does in the worst case: 127,036 years at the same speed.

The trick works because each pass keeps the order of the one before inside every pocket. Computers still sort this way when they have many numbers of the same length; it is called radix sort (radix is Latin for root, and also the word for a number system’s base, 10 here). It is one of the few ways to sort that never compares two items.

A three-column sort. Change Step 3 to sort the village by ward, and inside each ward by age. Which passes, in which order? (Challenge ★★★ asks for a function that does it for any columns.)

A dropped box. Now and then someone dropped a box of cards, and a program punched on hundreds of cards fell out of order. So programmers punched a sequence number into the last columns of every card, 73 to 80, and put a dropped deck back in order on the sorter. How many passes would a deck numbered 00001 to 99999 need?

Letters. With one hole in one of its 12 rows, a column can hold 12 different things: enough for the digits, not for the alphabet. How many different things could a column hold if it may have one hole or two? Write a program that counts them.

★ Count one hole (Python, from Grade 8)

The statistics office wants one number at a time: how many cards have a given hole in a given column? Write count_hole(deck, column, digit) that gives back how many cards in deck have the digit digit (a whole number from 0 to 9) in column (0 to 4).

def count_hole(deck, column, digit):    # how many cards have this digit in this column?    return 0 village = ['11182', '21242', '21032', '21221', '41012', '42282', '22222', '51052', '32012', '62312',           '21111', '52042', '31582', '81061', '71332', '11052', '32262', '41162', '92172', '62042',           '41152', '51061', '42271', '21252', '82022', '41192', '12642', '72012', '21392', '51702']print(count_hole(village, 4, 1))    # how many can read

★★ Women in every ward (Python, from Grade 8)

The 1971 census published the men and the women of every ward. Write women_by_ward(deck) that gives back a list of ten numbers: how many women (a 2 in column 2, card[1]) live in ward 0, ward 1, … ward 9.

def women_by_ward(deck):    # a list of 10 counts, one for each ward    return [0] * 10 village = ['11182', '21242', '21032', '21221', '41012', '42282', '22222', '51052', '32012', '62312',           '21111', '52042', '31582', '81061', '71332', '11052', '32262', '41162', '92172', '62042',           '41152', '51061', '42271', '21252', '82022', '41192', '12642', '72012', '21392', '51702']print(women_by_ward(village))

★★★ Sort on any columns (Python, from Grade 8)

Write sort_by(deck, columns) that sorts the deck on the given columns, the most important first, using only passes of the sorter. sort_by(village, [0, 2, 3]) sorts by ward, and inside each ward by age. Use sort_pass from Step 3; don’t use Python’s own sort.

def sort_pass(deck, column):    pockets = [[], [], [], [], [], [], [], [], [], []]    for card in deck:        pockets[int(card[column])].append(card)    new_deck = []    for pocket in pockets:        new_deck = new_deck + pocket    return new_deck def sort_by(deck, columns):    # columns: the most important first    return deck print(sort_by(['31042', '21242', '32012', '21032'], [0, 2, 3]))

• Grade 6, What Is a Computer?: Jacquard’s loom, the first machine run by punched cards, and Nepal’s first computer in the story of computing.
• Grade 7, Nepal’s own eras: why governments, not companies, had the first computers.
• Grade 8, Sorting: bubble sort and insertion sort, which compare two items at a time.
• Grade 10, Data Science: the census results of today, in tables you can study with Python.
• How does a barcode catch a typing mistake? Another way numbers are kept right when people type them.