Problem solving and runtime complexity exercises

algorithms.rb

# given an array of integers, find the largest value
def find_largest(numbers)
    # initialize our "largest number" to the first number in the array
    # because it is the largest so far
    largest = numbers[0]
    
    # looping over each number once
    numbers.each do |i|
        if i > largest
            # overwriting the largest if it's bigger as we go
            largest = i
        end
    end
    
    # now that we have checked each number, the variable "largest" will indeed
    # contain the largest number
    largest
end



# given a word, find the number of doubled up letters
def find_num_doubles(word)
    # initializing to nil guarantees that no letter will equal "last_letter" at first
    last_letter = nil
    # initialize our number of doubles to zero for obvious reasons
    double_count = 0
    
    # iterate over each character in the word
    word.chars.each do |x|
        # if the previous letter equals the current one, we have a double.
        if last_letter == x
            double_count += 1
        end
        # set our current letter to the last_letter, such that the next iteration
        # of the loop can check it for equality
        last_letter = x
    end
    double_count
end


# find the most frequently occuring letter in the text
def find_most_frequent(text)
    # initialize a hash table where the default value of keys that are
    # not created yet will be zero
    letter_hash = Hash.new(0)
    
    # iterate over each letter
    text.chars.each do |letter|
        # the key in the hash is our letter.
        # we know that the counts will start at zero, so we can safely increment by 1
        letter_hash[letter] += 1
    end
    
    # some ruby magic to return the key (letter) that has the largest value
    letter_hash.max_by{|k,v| v}[0]
end




# find all pairs that add up to 100 - TAKE 1
# complexity O(n^2) where n is the number of integers in our input array
def find_pairs(numbers, sum)
    pairs = []
    numbers.each_with_index do |number, index|
        numbers.each_with_index do |number2, index2|
            if index != index2 && number + number2 == 100
                pairs << [number, number2]
            end
        end
    end
    pairs
end

# find all pairs that add up to 100 - TAKE 2
# complexity O(n) where n is the size of input - More optimal
def find_pairs(numbers)
    num_pairs = 0
    pairs_hash = {}
    pears = [] # hhehehe
    
    numbers.each do |number|
        # if the current number is the pair of a previous number that was iterated over,
        # we know that this is the second value of a valid pair that exists.
        if pairs_hash.has_key?(number)
            pears << [number, 100-number]
        end
        
        # for the current number, we can KNOW what the pair should be by subtracting it
        # from our sum. we then set this value as a key in a hash, so we can later
        # check to see if the pair we're looking for exists earlier in the array
        pairs_hash[sum-number] = number
    end
    pears
end



# find the word with most number of anagrams in the english dictionary
def find_word_with_most_anagrams
    # open text file
    words = File.open('/usr/share/dict/words').read
    
    # just an empty hash. missing keys default to nil.
    hashes = {}
    
    # just in case there are no anagrams at all
    most_signature = ''
    
    # this keeps track of the most number of anagrams we have seen so far
    most = 0
    
    # each line in text file is an individual word
    words.each_line do |word|
        # remove whitespace from beginning and end of word (spaces/newlines)
        word = word.strip.downcase
        
        # make a signature of the word by sorting its letters
        # all anagrams will have matching signatures
        signature = word.chars.sort.join('')
        
        # initialize our place in the hash to an empty array
        if hashes[signature] == nil
            hashes[signature] = []
        end
        
        # add our current word into the array of anagrams we have for this signature
        hashes[signature] << word
        
        # if this word has more anagrams than the largest number we've come accross so far,
        # keep track of which anagram it is
        if hashes[signature].length >= most
            most_signature = signature
            most = hashes[signature].length
        end
    end
    # donesies
    return hashes[most_signature]
end