I've written code in Free Pascal based on a contest problem (The contest insists that I have to write with Pascal). It works like charm, but I think it still need some improvements, from memory usage to runtime.

Input Format

First line is n (Number of people in the Yellow Pages) and q (Number of people to search) {1 <= n <= 10000} and {1 <= q <= 10000}

Next n lines are Yellow Pages entries, each line is the name and the phone number, space delimited. The name is uppercase letters with maximum length of 15, while the length of the phone number is exactly 7 digits.

Next q lines are the people to search, also in uppercase letters with maximum length 15.

Output Format

Output is q lines, where each line is the phone number of the people to search

Input Sample

10 5
AARON 8468431
BEN 1573457
GREGORY 1765743
JACK 3746843
JILL 1357891
MICHAEL 1375638
MONET 1357562
SHEILA 1378651
TERRY 8756345
YIN 1781945

Output Sample


My Code

program YellowPages;

type string7 = String[7];

  namearray : Array of shortstring;
  numberarray, searcharray : Array of string7;
  input, name, search : shortstring;
  number : string7;
  n, q, iter1, iter2 : word;

procedure SplitInput(input : shortstring; var name : shortstring; var number : string7);
  iter_proc, hitspace : byte;
  hitspace := pos(' ', input);
  name := '';
  number := '';
  for iter_proc := 1 to length(input) do
    if iter_proc < hitspace then name := name + input[iter_proc];
    if iter_proc > hitspace then number := number + input[iter_proc];

  readln(n, q);
  setlength(namearray, n);
  setlength(numberarray, n);
  setlength(searcharray, q);
  for iter1 := 0 to (n - 1) do
    SplitInput(input, name, number);
    namearray[iter1] := name;
    numberarray[iter1] := numberarray;
  for iter1 := 0 to (q - 1) do
    for iter2 := 0 to (n - 1) do
      if namearray[iter2] = search then break;
    searcharray[iter1] := numberarray[iter2];
  for iter1 := 0 to (q - 1) do

The first thing I would do is switch from using parallel arrays to using a single array of records. Create a record that holds both the name and the phone number of each person in the phonebook, like this:

    Contact = Record 
        name : shortstring;
        number : String7;

Once you've done that, you should sort the array based on each contact's name. The quicksort algorithm is fairly easy to implement and is usually quite fast in most cases.

Once you have the array sorted, instead of searching through the entire phonebook from the beginning, you can use a binary search to find each record you want and get the phone number from it. A binary search should never require more than log2(n) comparisons (where n is the size of the array you're searching). Whereas your search requires on average n/2 comparisons. So for 100 entries, you'd never perform more than ~8 comparisons with a binary search, whereas you'd usually do around 50 using a linear search.

I haven't used FreePascal or any other Pascal compiler in a long time. It's possible that they have some built-in sorting and searching procedures that you could use. But it's not hard to implement the ones mentioned above.

Also, in SplitInput() you're manually copying the data from one string to another. Usually there's a library with a procedure for copying a string or a part of a string. These will usually be faster than writing your own. (For example, in C you could use memcpy() or strncpy(). I'm not sure if there's an equivalent in Pascal.)

  • \$\begingroup\$ I think I don't need quicksort, because the yellowpage entry input is already alphabetically ordered. \$\endgroup\$ – possibility0 Jun 3 '15 at 6:45
  • \$\begingroup\$ Nice suggestion for the records. I've got SplitInput() updated to use Copy(). The only thing that bugs me is the binary search for the yellowpage record. Because the type to search is a string and the one doing comparing is an integer, I can't relate both. I'm considering doing an ord() check for the first character, but there will be names with same first character. What should I do? \$\endgroup\$ – possibility0 Jun 3 '15 at 6:53
  • \$\begingroup\$ @RyoArmanda good point about not needing the sort. Phone books are already sorted! It turns out that Pascal directly supports string comparisons. So if you have a < b where a and b are strings, you'll get the correct answer. \$\endgroup\$ – user1118321 Jun 3 '15 at 15:52
  • \$\begingroup\$ I didn't know about that, thanks! Binary search is a success. Any more tips? If no more tips, I'll wrap this code up nice. \$\endgroup\$ – possibility0 Jun 4 '15 at 6:49
  • \$\begingroup\$ That's all I can think of at the moment. Good luck! \$\endgroup\$ – user1118321 Jun 4 '15 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.