### CMSC330 Fall 2015 ### Exercises for Week 2 # Topics: Ruby strings, hashes, regular expressions # Write a function is_palindrome?(s) that returns true if a # string is a palindrome (in other words, if you reverse the # string you get the same string back) and false otherwise. def is_palindrome?(s) s == s.reverse end # Write a function char_frequencies(s) that, given a string, # returns a hash relating characters to the number of times # they occurred. # For example: given the string “apple”, you should return the # hash { “a” => 1, “p” => 2, “l” => 1, “e” => 1 }. def char_frequencies(s) h = Hash.new for i in 0...s.length c = s[i] if h[c] then h[c] += 1 else h[c] = 1 end end return h end def char_frequencies2(s) h = Hash.new s.split('').each { |c| if h[c] then h[c] += 1 else h[c] = 1 end } return h end # Write a function is_natural_number?(s) that returns true if # s is a natural number and false otherwise. # Valid examples: “10” # Invalid examples: “-5” # Try writing two versions: one that allows whitespace at the # beginning and end, and one that doesn’t. def is_natural_number?(s) if s =~ /^\d+\$/ then return true end false end # Write a function is_integer?(s) that returns true if s is an # integer and false otherwise. # Valid examples: “+15”, “-15”, “15” # Invalid examples: “15.” def is_integer?(s) return true if s =~ /^[+|-]?\d+(\.0+)?\$/ false end # Write a function is_decimal?(s) that returns true if s is a # decimal number and false otherwise. # Valid examples: “+1.0”, “+1”, “-124.124”, “1”, “-1” # Invalid examples: “1,000.0”, “1.1.1” def is_decimal?(s) return true if s =~ /^[+|-]?\d+(\.\d+)?\$/ false end # Write a function find_all_decimals(s) that returns an array # of all valid decimal numbers in the string. def find_all_decimals(s) return s.scan(/[+|-]?\d+\.\d+/) + s.scan(/[+|-]?\d+/) end # Write a function find_all_date(s) that, given a string, returns # an array of all valid dates in the string. A valid date # is a substring in the format MM/DD/YYYY. def find_all_dates(s) s.scan(/\d\d\/\d\d\/\d{4}/) end # Write a function substring_frequencies(s, regexp) that, given a # string and a regular expression, counts the number of # occurrences of substrings matching that regular expression. # Return the substring frequencies in the same format as in # char_frequencies. # Note: this method should behave the same way as # char_frequencies if regexp is /./ def substring_frequencies(s, regexp) h = Hash.new s.scan(regexp).each { |match| if h[match] then h[match] += 1 else h[match] = 1 end } return h end # Write a function common_words(s, regexp) that, given a string # and a regular expression, returns the five most frequently # occurring substrings matching the regular expression along with # their frequencies in the same format as in # substring_frequencies. def common_words(s, regexp) h = substring_frequencies(s, regexp) Hash[h.sort_by{|k,v| -v}.first(5)] end ##### Challenge Question ##### # A sparse matrix is one that in which most of the elements consist of the same # (default) value. If the matrix is very large, then representing it as we # normally would require unnecessary space. # Below is a skeleton implementation of a class SparseMat. It implements a 2-d # square matrix whose representation assumes it will be sparse. Complete the # implementation such that the storage of non-default elements takes O(n), n is # the number of the elements you put into the matrix. And importantly, the # lookup time for an element should be O(1) given the coordinates x,y # (coordinates start at 0). Hint: you can assume that Ruby hashes have these # properties, so you might want to use them in your implementation (but you can # use other data structures, too, if you like). #Methods to implement: # the constructor takes the size of the matrix (the dimension), and the default # value # get(x,y) returns the value at x,y or throws an exception if out of bounds # put(x,y,e) updates the value at x,y or throws an exception if out of bounds # getall(cs) returns an array of values as indicated by the coordinates in cs # add(M) returns a matrix that is result of adding matrix M, throws an # exception if the dimensions differ # Example session: # irb> x = SparseMax.new(2,0) # => ... # irb> x.get(1,2) # IndexError: 1,2 outside of bounds of 2D-matrix size 2 # ... # irb> x.get(0,0) # => 0 # irb> x.put(1,1,5) # => 5 # irb> x.get(1,1) # => 5 # irb> x.getall([[1,1],[0,0]]) # => [5, 0]