rotn_equivalents.rb

# The Problem:
# From Wikipedia: "ROT13 ("rotate by 13 places", sometimes hyphenated ROT-13) is a simple letter substitution cipher 
# that replaces a letter with the letter 13 letters after it in the alphabet."

# Imagine a generic ROT-n on the ASCII lower-case alphabet.

# ROT-1 transforms "abbc" -> "bccd" and "zaab" -> "abbc".
# ROT-2 transforms "abbc" -> "cdde" and "zaab" -> "bccd".
# ...
# ROT-25 transforms "abbc" ->"zaab" etc.

# Write a function that takes a collection of strings (containing only lower-case letters) and determines and prints 
# which are ROT-n equivalents of each other.

# E.g. given as args:
# ["abbc", "bccd", "cat", "zaab", "yell", "bzs", "catch"]
# the function prints:
# abbc, bccd, zaab
# cat, bzs
# (order isn't important)

---
# My Solution:

# this method determines whether or not two strings are rotn_equivalents of each other
def rotn_equivalents(str1, str2)
  alphabet = ('a'..'z').to_a
  return false if str1.length != str2.length
  index_diff = other_diff = alphabet.index(str1[0]) - alphabet.index(str2[0])
  if str1[0] > str2[0]
    other_diff -= 26
  elsif str1[0] < str2 [0]
    other_diff += 26
  end
  possible_diff = [index_diff, other_diff]
  str1.split("")[1..-1].each_with_index do |letter, i|
    current_diff = alphabet.index(letter) - alphabet.index(str2[i + 1])
    return false if !(possible_diff.include? current_diff)
  end
  return true
end

# EXAMPLE INPUTS
# p rotn_equivalents("abbc", "bccd")    => true
# p rotn_equivalents("abbc", "cdde")    => true
# p rotn_equivalents("zaab", "abbc")    => true
# p rotn_equivalents("abbc", "zaab")    => true
# p rotn_equivalents("zaab", "bccd")    => true
# p rotn_equivalents("zaab", "bcce")    => false
# p rotn_equivalents("zaab", "abbc")    => true
# p rotn_equivalents("cat", "bzs")      => true

# this method takes in an array of strings and prints lines whose strings are rot-n equivalents
def rotn_sets(str_array)
  output = [[str_array[0]]]
  str_array[1..-1].each do |possible_equivalent|
    equivalent_found = false
    output.each do |word_array|
      if rotn_equivalents(word_array[0], possible_equivalent)
        word_array << possible_equivalent
        equivalent_found = true
        break
      end
    end
    if !equivalent_found
      output << [possible_equivalent]
    end
  end
  output.select { |arr| arr.length > 1 }.each { |arr| puts arr.join(", ") }
end

rotn_sets(["abbc", "bccd", "cat", "zaab", "yell", "bzs", "catch"])
#=> abbc, bccd, zaab
#=> cat, bzs

rotn_sets(["abc", "cde", "fg", "cat", "mn"])
#=> abc, cde
#=> fg, mn

# I believe this solution works, though it must have like n^2 time complexity or slower.. n for the first loop (on line 54) 
# times n for the second loop (on line 56). Possibly slower because the method rotn_sets calls the method rotn_equivalents, 
# which has a time complexity of n too...

# Space complexity should be n - the only major data structure in the method rotn_sets being created is the array "output", 
# which contains n strings. Though I'm thinking space complexity might be higher given the array of letters in the method 
# rotn_equivalents ...