Programming Challenge

Your task is to create a website that can find out which word in a provided dictionary has the most number of anagrams from the same dictionary and display the set of anagrams for that word.

Two words are anagrams of each other if they are the same length and contain the same set of letters.

Example dictionary: fred two tow show whos wot one red

The answer here is "two, wot, tow" as these 3 words are all anagrams of each other. "show" and "whos" are also anagrams but there are only 2 matching words in the dictionary. "fred", "one", and "red" do not have any anagrams.

A sample dictionary file is provided. This contains one word per line. Many of the words in the dictionary will not have any anagrams, but some of them will and some will have a number of possible anagrams.

The dictionary file may not be in alphabetic order, however you can assume that it only consists of words containing the letters a-z, is consistently formatted, has no punctuation characters or duplicated lines.

Method

The brute force approach would be to load the dictionary file into memory, and then for each word in the dictionary check if it's an anagram of every other word in the dictionary. You will also need to keep a tally of which word has the most anagrams and have some way to display your results. This would have a run-time of O(n2) and for large dictionaries is likely to take a long time.

Your task is to produce an efficient algorithm that can solve the problem on a large dictionary (>250000 words) within a reasonable time. We will be testing your application on a number of dictionary files.

There is no right answer to this problem. There are a number of possible algorithms that you could use for both limiting the amount of processing you need to do and for testing whether two given words are an anagram of each other.

Note: There may be more than one answer if the dictionary contains several words which all have the same number of anagrams.

Rules

  • Your application must be web site written in php. Its output will therefore be displayed as a web page. Javascript can also be used but the processing of the file must be done on the server side.
  • You can use any standard functions that are part of the language or normal development environment. Do not depend on any other code packages or 3rd party libraries.
  • You may not copy code from the internet.
  • Your application should initially display a form allowing the user to specify the name of the dictionary file as in the following example:
  • When the button on the initial form is pressed the page should change to show the results as in the following example (note: you should not expect to match the results shown!):
  • You should use CSS to make your pages attractive but you do not need to match the layout and styling in the examples above.

Sample Dictionary

Download the sample dictionary file

Submission

Please package your source code files in a .zip file and upload using the form below, your zip file must be smaller than 10 megabytes:

Testing

To test, Dolphin will copy your file(s) into a directory on a standard install of a LAMP server (latest version), or WAMP server, and launch your web page in Chrome. Please indicate which is the main page, if you have more than one .html and/or .php file

There may be minor syntax difference between different environments. Dolphin will take this into account when evaluating submissions and any minor tweaks needed to get it to run will not be considered detrimental.