ZIO 2004 Problem 01
Editorialist: Darshan Bari
Problem Code: ZIO04001
Full explanation:
Two words are called “neighbors” if one word can be converted to another by
- Removing one letter
- Adding one letter
- Modifying one letter
The problem can be solved using graph theory. This approach is explained below.
Each of the given words can be considered as a node. Also, one bidirectional edge is present between two neighboring words. The edge is bidirectional because of the following reasons:
- Consider if one letter of the word A is removed to form another word B, then B can be converted to word A by adding that letter.
- Consider if one letter x of the word A is modified to y forming another word B, then B can be converted to word A by modifying the letter y in B to x.
- Consider if one letter is added to word A to form another word B, then the same letter can be removed from word B to obtain word A.
The problem requires to find the longest sequence of words without repetitions where each pair of consecutive words in the sequence are neighbors. Once the graph is built, the problem reduces down to finding and printing the longest path in the graph. The graphs for the sets of words are given below
{be, bed, bet, bud, but, dig, do, dog, dug, get, go, god, got}
All possible longest paths in the graph are:
The four possible longest paths in the graph are
- be - bed - bud - but - bet - get - got - god - go - do - dog - dug - dig
- but - bud - bed - be - bet - get - got - god - go - do - dog - dug - dig
- be - bed - bud - but - bet - get - got - god - go - do - dog - dig - dug
- but - bud - bed - be - bet - get - got - god - go - do - dog - dig - dug
{fat, fate, fight, fit, fright, gait, gate, light, mite, quit, quite, right, sat, sigh, sight, sit, site, suite, writ, write}
One of the longest paths in the graph is quit - quite - suite - site - sit - fit - fat - fate - gate
{age, bat, batch, bath, bathe, bather, batter, cache, cat, catch, catcher, fat, fate, father, fresh, garb, garbage, heathen, later, lather, mash, mate, matt, matter, rash, rat, thrash, thresh, trash}
Hence, one of the longest paths in the built graph is observed to be
matt - mate - fate - fat - cat - rat - bat - bath - bathe - bather - father - lather - later
