Commits

Anonymous committed f71dda1

Added the beginnings of the ruby solution. I am off to a good start.

Comments (0)

Files changed (9)

RubySolution/.project

+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>spellcheck</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>com.aptana.ide.core.unifiedBuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>com.aptana.ruby.core.rubynature</nature>
+		<nature>com.aptana.projects.webnature</nature>
+	</natures>
+</projectDescription>

RubySolution/lib/letter_node.rb

+
+class LetterNode
+  attr_accessor :letter, :parent, :nodes, :end
+  
+  def initialize()
+    @end = false
+    @nodes = {}
+  end
+  
+  def clone()
+    new_node = LetterNode.new
+    new_node.letter = @letter.clone
+    new_node.parent = @parent.clone
+    new_node.nodes = @nodes.clone
+    new_node.end = @end.clone
+    return new_node
+  end
+  
+  def get_word()
+    word = String.new
+
+    traverser = self
+      
+    begin
+      word.insert(0, traverser.letter)
+      traverser = traverser.parent
+    end while traverser != nil
+    
+    return word
+  end
+end

RubySolution/lib/letter_tree.rb

+require "#{File.dirname(__FILE__)}/traversal_data"
+require "#{File.dirname(__FILE__)}/letter_node"
+require "set"
+
+#Dir[File.dirname(__FILE__) + '/lib/*.rb'].each {|file| require file }
+
+class LetterTree
+  @@NO_SUGGESTION_TEXT = "NO SUGGESTION"
+  
+  # Create the object
+  def initialize()
+    @tree = {}
+    @bad_words = {}
+    @root = self.get_root()
+  end
+  
+  def get_root()
+    treeData = TraversalData.new
+    treeData.depth = -1
+    treeData.current_node = nil
+    treeData.nodes = @tree
+    return treeData
+  end
+  
+  def add(word)
+    traversal = self.traverse(word, self.get_root())
+    self.add_at_location(word, traversal)
+  end
+  
+  def add_at_location(word, traversal)    
+    if traversal.depth < word.length - 1
+      traversal.depth += 1
+      node = LetterNode.new
+      node.parent = traversal.current_node
+      node.letter = word[traversal.depth]
+      traversal.nodes[node.letter] = node
+      
+      if traversal.depth + 1 < word.length
+        traversal.current_node = node
+        traversal.nodes = node.nodes
+        add_at_location(word, traversal)
+      else
+        node.end = true
+      end
+    else
+      traversal.current_node.end = true
+    end
+  end
+  
+  def traverse(word, traversal)
+    begin
+      oldSpot = traversal.depth
+      traversal = self.traverse_one_step(word, traversal)
+    end while traversal.depth != oldSpot
+    
+    return traversal
+  end
+  
+  def traverse_one_step(word, traversal_ref)
+    traversal = traversal_ref.clone
+    current_node = self.traverse_node(word, traversal)
+
+    if current_node != nil
+      traversal.current_node = current_node
+      traversal.nodes = current_node.nodes
+      traversal.depth += 1
+    end
+    
+    return traversal
+  end
+  
+  def traverse_node(word, traversal)
+    if word.length > 0 && traversal.depth < word.length - 1
+      potential_key = word[traversal.depth+1]
+      
+      if traversal.nodes.has_key?(potential_key)
+        return traversal.nodes[potential_key]
+      end
+    end
+  end
+  
+  def spellcheck(word)
+    root = self.get_root()
+    new_word = self.recursive_spellcheck(word, root)
+    return new_word
+  end
+  
+  def recursive_spellcheck(word, traversal, changing_vowel = false,
+                           changing_case = false)
+    current_depth = traversal.depth
+    # If the word is not in the badword list, or if the depth is not in the set of depth
+    # checked for the bad word, run the spellcheck.
+    if !@bad_words.has_key?(word) || !@bad_words[word].include?(current_depth)
+      if traversal.current_node != nil
+        current_word = traversal.current_node.get_word()
+        
+        if traversal.current_node.end == true && current_word == word
+          return current_word
+        end
+      end
+      
+      next_location = self.traverse_one_step(word, traversal)
+      if current_depth != next_location.depth
+        returned_word = self.recursive_spellcheck(word, next_location)
+        
+        if returned_word != @@NO_SUGGESTION_TEXT
+          return returned_word
+        end
+      end
+      
+      # If a vowel was chanaged to cause the repeating character,
+      # don't remove the repeated character.
+      if (current_depth + 1 < word.length && !LetterTree.is_vowel(word[current_depth+1])) \
+         || !changing_vowel
+        returned_word = self.process_repeated_letter(word, traversal)
+        
+        if returned_word != @@NO_SUGGESTION_TEXT
+          return returned_word
+        end
+      end
+      
+      if !changing_vowel
+        returned_word = self.check_for_incorrect_vowel(word, traversal, changing_case)
+        
+        if returned_word != @@NO_SUGGESTION_TEXT
+          return returned_word
+        end
+      end
+      
+      if !changing_case
+        returned_word = self.check_for_improper_casing(word, traversal, changing_vowel)
+        
+        if returned_word != @@NO_SUGGESTION_TEXT
+          return returned_word
+        end
+      end
+      
+      if !bad_words.has_key?(word)
+        bad_words[word] = Set.new
+      end
+      bad_words[word].add(current_depth)
+    end
+    return @@NO_SUGGESTION_TEXT
+  end
+  
+  def check_for_improper_casing(word, traversal, changing_vowel)
+    depth_to_check = traversal.depth + 1
+    if 0 <= depth_to_check && depth_to_check < word.length
+      new_word = word.clone
+      new_word[depth_to_check] = new_word[depth_to_check].swapcase
+      
+      return self.spellcheck(new_word, traversal, changing_vowel, true)
+    end
+    return @@NO_SUGGESTION_TEXT
+  end
+  
+  def check_for_incorrect_vowel(word, traversal, changing_case)
+    
+  end
+end

RubySolution/lib/string_extension.rb

+class String
+  @@Vowels = ['a', 'e', 'i', 'o', 'u', 'y']
+  
+  def match_case(character_to_match)
+    if character_to_match == character_to_match.upcase
+      return self.upcase
+    else
+      self.downcase
+    end
+  end
+end

RubySolution/lib/traversal_data.rb

+
+class TraversalData
+  attr_accessor :depth, :current_node, :nodes
+end

RubySolution/spellcheck.rb

+#!/usr/bin/env ruby
+
+class MegaGreeter
+  attr_accessor :names
+
+  # Create the object
+  def initialize(names = "World")
+    @names = names
+  end
+
+  # Say hi to everybody
+  def say_hi
+    if @names.nil?
+      puts "..."
+    elsif @names.respond_to?("each")
+
+      # @names is a list of some kind, iterate!
+      @names.each do |name|
+        puts "Hello #{name}!"
+      end
+    else
+      puts "Hello #{@names}!"
+    end
+  end
+
+  # Say bye to everybody
+  def say_bye
+    if @names.nil?
+      puts "..."
+    elsif @names.respond_to?("join")
+      # Join the list elements with commas
+      puts "Goodbye #{@names.join(", ")}.  Come back soon!"
+    else
+      puts "Goodbye #{@names}.  Come back soon!"
+    end
+  end
+
+end
+
+
+if __FILE__ == $0
+  mg = MegaGreeter.new
+  mg.say_hi
+  mg.say_bye
+
+  # Change name to be "Zeke"
+  mg.names = "Zeke"
+  mg.say_hi
+  mg.say_bye
+
+  # Change the name to an array of names
+  mg.names = ["Albert", "Brenda", "Charles",
+    "Dave", "Englebert"]
+  mg.say_hi
+  mg.say_bye
+
+  # Change to nil
+  mg.names = nil
+  mg.say_hi
+  mg.say_bye
+end

RubySolution/test/letter_tree_population_tests.rb

+require "../lib/letter_tree"
+require "test/unit"
+
+class LetterTree
+  attr_accessor :tree, :badWord
+end
+
+
+ 
+class LetterTreePopulationTests < Test::Unit::TestCase
+  
+  def setup
+    @words = LetterTree.new;
+  end
+  
+  def test_populate_no_words_in_tree
+    assert_instance_of(Hash, @words.tree)
+    assert_equal(0, @words.tree.length)
+  end
+  
+  def test_populate_single_word_in_tree
+    @words.add("hi")
+    
+    assert_equal(1, @words.tree.length)
+    assert_equal(1, @words.tree['h'].nodes.length)
+    assert_equal(0, @words.tree['h'].nodes['i'].nodes.length)
+    
+    assert_equal('h', @words.tree['h'].letter)
+    assert_equal('i', @words.tree['h'].nodes['i'].letter)
+    
+    assert_equal(false, @words.tree['h'].end)
+    assert_equal(true, @words.tree['h'].nodes['i'].end)
+    
+    assert_equal("hi", @words.tree['h'].nodes['i'].get_word())
+  end
+  
+  def test_populate_non_overlapping_words_in_tree
+    @words.add("hi")
+    @words.add("a")
+    
+    assert_equal(2, @words.tree.length)
+    assert_equal(1, @words.tree['h'].nodes.length)
+    assert_equal(0, @words.tree['a'].nodes.length)
+    
+    assert_equal('h', @words.tree['h'].letter)
+    assert_equal('i', @words.tree['h'].nodes['i'].letter)
+    
+    assert_equal('a', @words.tree['a'].letter)
+    
+    assert_equal(false, @words.tree['h'].end)
+    assert_equal(true, @words.tree['h'].nodes['i'].end)
+    
+    assert_equal(true, @words.tree['a'].end)
+  end
+  
+  def test_populate_same_word_in_tree_twice
+    @words.add("a")
+    @words.add("a")
+    
+    assert_equal(1, @words.tree.length)
+  end
+  
+  def test_populate_overlapping_words_in_tree
+    @words.add("hi")
+    @words.add("ha")
+    
+    assert_equal(1, @words.tree.length)
+    assert_equal(2, @words.tree['h'].nodes.length)
+    
+    assert_equal('h', @words.tree['h'].letter)
+    assert_equal('i', @words.tree['h'].nodes['i'].letter)
+    assert_equal('a', @words.tree['h'].nodes['a'].letter)
+    
+    assert_equal(false, @words.tree['h'].end)
+    assert_equal(true, @words.tree['h'].nodes['i'].end)
+    assert_equal(true, @words.tree['h'].nodes['a'].end)
+  end
+  
+  def test_populate_smaller_word_using_same_characters_as_bigger_word
+    @words.add("high")
+    @words.add("hi")
+    
+    assert_equal(1, @words.tree.length)
+    assert_equal(1, @words.tree['h'].nodes.length)
+    assert_equal(1, @words.tree['h'].nodes['i'].nodes.length)
+    assert_equal(1, @words.tree['h'].nodes['i'].nodes['g'].nodes.length)
+    assert_equal(0, @words.tree['h'].nodes['i'].nodes['g'].nodes['h'].nodes.length)
+    
+    assert_equal('h', @words.tree['h'].letter)
+    assert_equal('i', @words.tree['h'].nodes['i'].letter)
+    assert_equal('g', @words.tree['h'].nodes['i'].nodes['g'].letter)
+    assert_equal('h', @words.tree['h'].nodes['i'].nodes['g'].nodes['h'].letter)
+    
+    assert_equal(false, @words.tree['h'].end)
+    assert_equal(true, @words.tree['h'].nodes['i'].end)
+    assert_equal(false, @words.tree['h'].nodes['i'].nodes['g'].end)
+    assert_equal(true, @words.tree['h'].nodes['i'].nodes['g'].nodes['h'].end)
+  end
+end

RubySolution/test/letter_tree_spellcheck_tests.rb

+require "../lib/letter_tree"
+require "test/unit"
+
+class LetterTree
+  attr_accessor :tree, :badWord
+end
+
+
+ 
+class LetterTreeSpellcheckTests < Test::Unit::TestCase
+  def setup
+    @words = LetterTree.new;
+  end
+  
+  def test_spellecheck_no_suggestion_word
+    actual = @words.spellcheck("ohaithar")
+    
+    assert_equal("NO SUGGESTION", actual)
+  end
+  
+  def test_spellcheck_properly_spelled_word
+    @words.add("hi")
+    @words.add("noise")
+    @words.add("morenoise")
+    @words.add("even more noise")
+    @words.add("hihihihihi")
+    
+    actual = @words.spellcheck("hi")
+    assert_equal("hi", actual)
+  end
+end

RubySolution/test/spellcheck_tests.rb

+require "test/unit"
+require "./letter_tree_population_tests"
+require "./letter_tree_spellcheck_tests"
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.