Monday 1 April 2013

Saturday Ruby Algorithm

I didn’t sleep much on Saturday night - I barely got to sleep 2 to 3 hours. Why? Quite unexpected and unplanned were the task I did and this blog entry.

The plan on Saturday morning was to go to Ruwi & Rayyan’s school for the parent-teacher meeting to collect their annual grades reports. We wanted to start from home at noon. Since I had some time after the late Saturday breakfast, I was on the net and somehow landed on Vic Gundotra’s plus entry of Valentine’s day. I think the “somehow” trail, though I am not 100% sure, was Latest from Blogger buzz on the +sign before Google profile becoming a link → link to Gregory Fair → just scrolling down → Vic Gundotra’s entry.

Anyways, the post was about Vic’s son writing a “geeky cool” Valentine’s card to his girlfriend :
“First, I need to know what you’re made of, because you seem to be composed of Copper and Tellurium, which explains why you’re so CuTe.”
I liked the message. Over that, one of the thoughts I had after reading it was,
given a word, how can we know if it is composed of periodic table chemical elements symbols and what those elements are. Like, can the word “nice” be expressed as periodic table elements’ symbols?
Once a thought enters your mind intensely, you don’t need a pencil and paper to write the steps. Your mind does it, and it happened even as I took bath, and continued after we reached our kids’ school and Mahiba was meeting the teachers discussing the feedback from them.

Back home around 4 p.m., I opened a new ruby file in Editra and did a brain dump of the pseudo code. My first cut was: Input is a given English word. Build a solution string until it matches the given word. Check if first character of the word is a periodic element symbol. If yes, add it to a solution string array. Check if the first two characters of the word is a periodic element symbol. If yes, add it to the solution string array. If both these checks are negative, the word cannot be formed and the algorithm stops.

From the second character onwards, for each character of the word, check if it is a periodic element symbol. If yes, loop through the solution string array, appending to existing members. After appending if the solution string is the first substring of the given word, then replace the string with the appended (expanded) string. Check if the character and its next character together are a periodic element symbol. If yes, loop through the solution array appending the pair to existing members. After appending if the solution is the first substring of the given word, then replace the string with the appended (expanded) string. As we loop through the solution string array, if any member is the same as the given word, we have a match and the algorithm stops.

It was 6 p.m., and the second engagement of the day was to go to Vanasthalipuram for a private family function. We left around 6:20 p.m. from home, spent a few hours with my sister and brother, and their families along with my mother. By the time we returned home, it was nearly midnight. I was back at my iMac with a Diet Coke.

I started writing the code. One thing I observed was that in the periodic table, there were three-character symbols starting with “U”. So I added a check, in both the blocks for the first character and the second character onwards, for processing of the character is “U”. The program checks if “U” and the next two characters are a periodic element table symbol.

I kept on coding and around 3 a.m., the Ruby program was ready. I had put a lot of print statements to help check various steps. As I was testing it with various words and verifying manually with the symbols, I found that the program was giving wrong output. For example, the words “I” and “nandini” can be formed with periodic table element symbols, but the program was stating that these words cannot be.

I was back in the code, thinking of the solution but instead of a systematic analysis, I tried one small hack. Whenever, the algorithm finds that the appended string is the first substring, instead of replacing the existing string with the appended string, I just leave the existing string and add the appended string to the solution array. This small change did the trick and the program worked.

After that, I spent some more time cleaning up the program - removing all the print statements, using better format for the output and splitting the pseudo code to convert it to comments. By the time it was all over, the time was 6 a.m. at which time I went to bed and got up at 9 a.m., as we had planned to visit my cousin Sabreena. Her husband Zubair is off to Germany for a year-long project. Hence the lack of sleep on Saturday night.

The complete program is given below:
A few more thoughts: The program can be refined. Perhaps, sort the periodic_elements array. Eliminate from the found elements those symbols that do not add up to the given word that is, retain only those symbols that can be mixed to form the word. Check that one and only one command line argument is passed.

Another interesting question would be : What are all the words in the English dictionary that can be formed from periodic table elements’ symbols? What will be the algorithm? How much time will it take to run? As the week starts I will get drawn into work and I don’t have much motivation to answer these questions. Best I can do is, shoot these questions to a fine brain like Skiena and if I get a reply, I will post the same on my blog.

In the meanwhile, here’s what I posted on Vic Gundotra’s entry, of course very much aided by my program : Vanadium-iodine-carbon, fluorine-oxygen-uranium-neodymium thorium-iodine-sulphur lanthanum-tellurium. Nickel-cerium phosphorous-lutetium-sulphur sulphur-uranium-phosphorous-erbium-boron.

No comments:

Post a Comment