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:

	#!/usr/bin/ruby
	periodic_elements = ["h", "he", "li", "be", "b", "c", "n", "o", "f", "ne", "na", "mg", "al", "si", "p", "s", "cl", "ar", "k", "ca", "sc", "ti", "v", "cr", "mn", "fe", "co", "ni", "cu", "zn", "ga", "ge", "as", "se", "br", "kr", "rb", "sr", "y", "zr", "nb", "mo", "tc", "ru", "rh", "pd", "ag", "cd", "in", "sn", "sb", "te", "i", "xe", "cs", "ba", "la", "ce", "pr", "nd", "pm", "sm", "eu", "gd", "tb", "dy", "ho", "er", "tm", "yb", "lu", "hf", "ta", "w", "re", "os", "ir", "pt", "au", "hg", "tl", "pb", "bi", "po", "at", "rn", "fr", "ra", "ac", "th", "pa", "u", "np", "pu", "am", "cm", "bk", "cf", "es", "fm", "md", "no", "lr", "unq", "unp", "unh", "uns", "uno", "une", "unn"]
	$found_array = []
	$solution_array = []
	headless_word_arr = []
	$word = ARGV[0]
	=begin
	function check_solution, param = string
	if string is the word, we're done
	else
	loop through solution array, appending string to each element
	if we get the word, we're done
	if we get the first substring, add the substring to the solution array
	=end
	def check_solution(str)
	puts "found #{str}"
	$found_array << str
	print "found elements = "
	$found_array.each {|x| print x, " "}
	puts
	if str == $word then
	puts "Success. Word is composed of periodic table elements"
	exit(0)
	end
	for i in (0 .. $solution_array.length-1) do
	partial = $solution_array[i] + str
	if partial == $word then
	$solution_array << partial
	puts "Solution set so far..."
	$solution_array.each {|x| print x, " "}
	puts
	puts "------------------"
	puts "Success. Word is composed of periodic table elements"
	exit(0)
	end
	if $word.index(partial) == 0 then
	$solution_array << partial
	end
	end
	puts "Solution set so far..."
	$solution_array.each {|x| print x, " "}
	puts
	puts "------------------"
	end
	puts "Processing #{$word}"
	puts "------------------"
	$word = $word.downcase
	=begin
	take first character in word
	if character is a periodic_element
	add character to solution array
	else if word has more than one character and
	first two characters are a periodic_element
	add first two characters to solution array
	check solution
	if first character is u
	if first three characters are a periodic_element
	add first three characters to solution array
	=end
	found = false
	first_character = $word[0, 1]
	if periodic_elements.include?(first_character) then
	found = true
	$solution_array << first_character
	check_solution(first_character)
	end
	if $word.length > 1 then
	first_two_characters = $word[0, 2]
	if periodic_elements.include?(first_two_characters) then
	found = true
	$solution_array << first_two_characters
	check_solution(first_two_characters)
	end
	end
	if first_character == "u" then
	first_three_characters = $word[0, 3]
	if periodic_elements.include?(first_three_characters) then
	found = true
	$solution_array << first_three_characters
	end
	end
	if found == false then
	puts "Given word is NOT made up of periodic table elements"
	exit
	end
	=begin
	for each character in word from second position onwards
	if character is 'u'
	if u and two successive characters are a periodic element
	check solution with u and two successive characters
	if character is a periodic_element
	check solution with character
	if character + next character is a periodic_element
	check solution with character + next character
	=end
	headless_word = $word.slice(1, $word.length)
	headless_word.scan(/./) {|c| headless_word_arr << c}
	for i in (0 .. headless_word_arr.length-1) do
	if headless_word_arr[i] == "u" then
	if i < headless_word_arr.length-2 then
	if periodic_elements.include?(
	headless_word_arr[i] +
	headless_word_arr[i+1] +
	headless_word_arr[i+2]) then
	check_solution(headless_word_arr[i] +
	headless_word_arr[i+1] +
	headless_word_arr[i+2])
	end
	end
	end
	if periodic_elements.include?(headless_word_arr[i]) then
	check_solution(headless_word_arr[i])
	end
	if i < headless_word_arr.length-1 &&
	periodic_elements.include?(headless_word_arr[i] + headless_word_arr[i+1]) then
	check_solution(headless_word_arr[i] + headless_word_arr[i+1])
	end
	end
	# If we have reached here, can't make the word
	puts "Given word is NOT made up of periodic table elements"

view raw word_pe.rb hosted with ❤ by GitHub

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.