Q1: Rock Paper Scissors Tournament
A rock, paper, scissors tournament is encoded as a bracketed array of games - that is, each element can be considered its own tournament.
[[
[ ["Kristen", "P"], ["Dave", "S"] ],
[ ["Richard", "R"], ["Michael", "S"] ],],
[[ ["Allen", "S"], ["Omer", "P"] ],
[ ["David E.", "R"], ["Richard X.", "P"] ]
]]
Under this scenario, Dave would beat Kristen (S>P), Richard would beat Michael (R>S), and then Dave and Richard would play (Richard wins since R>S); similarly, Allen would beat Omer, Richard X. would beat David E., and Allen and Richard X. would play (Allen wins since S>P); and finally Richard would beat Allen since R>S, that is, continue until there is only a single winner.
- Write a method rps_tournament_winner that takes a tournament encoded as a bracketed array and returns the winner
(for the above example, it should return [“Richard”, “R”]). - Tournaments can be nested arbitrarily deep, i.e., it may require multiple rounds to get to a single winner. You can assume that the initial array is well formed (that is, there are 2N players, and each one participates in exactly one match per round).
My Example Code
Recursively
#!/usr/bin/env ruby
# encoding: utf-8
require_relative 'rps_game_winner' #ensure code from series one Q3 is in the same dir
# check base case condition(if true, rps_game_winner()can be called)
def base_case?(player)
# eg [["Kristen","P"],["Dave","S"]] will return true
return player[0][0].class == String
end
def rps_tournament_winner(list)
# using recursion
if base_case?(list)
winner = rps_game_winner(list)
else
winner_a = rps_tournament_winner(list[0]) #divide
winner_b = rps_tournament_winner(list[1]) #divide
winner = rps_game_winner([winner_a,winner_b]) #as base case
end
# note where winner appears
return winner #as base case
end
tournament_list =
[[
[ ["Kristen", "P"], ["Dave", "S"] ],
[ ["Richard", "R"], ["Michael", "S"] ],
],
[
[ ["Allen", "S"], ["Omer", "P"] ],
[ ["David E.", "R"], ["Richard X.", "P"] ]
]]
if __FILE__ == $0
print rps_tournament_winner(tournament_list)
end
My Example Code
Iteration
# encoding: utf-8
# using iteration rather than recursion
require_relative 'rps_game_winner'
# some helper functions
# check base case condition(if true, rps_game_winner()can be called)
def base_case?(player)
# eg [["Kristen","P"],["Dave","S"]] will return true
return player[0][0].class == String
end
def mark(winner)
#help ensure only same level players compete
#[["Kristen","P"]] => ["Kristen","P",{:level=>num}]
if winner[2].nil?
winner << {:level=>1}
else
winner[2][:level] += 1
end
return winner
end
def unmark(winner)
# ["Kristen","P",{:level=>num}] => [["Kristen","P"]]
winner.delete_at(2)
return winner
end
def rps_tournament_winner(list)
# using iteration (here I use two stacks to help)
stack_p = [] #stack to keep divided players
stack_p << list #player
stack_w = [] #for winners,
while !stack_p.empty?
list = stack_p.pop
if base_case?(list)
winner = rps_game_winner(list)
winner_d = stack_w.pop # winner waitting in the winner stack
if winner_d.nil?
#when we just get the first winner
stack_w << mark(winner)
else
if winner_d[2][:level] = mark(winner)[2][:level]
#make sure player level match
winner = rps_game_winner([winner,unmark(winner_d)])
else
#if match fails, push into winner stack
stack_w << winner_d << mark(winner)
end
end
else
#divide into two groups again
stack_p << list[0] << list[1]
end
end
return unmark(winner)
end
tournament_list =
[[
[ ["Kristen", "P"], ["Dave", "S"] ],
[ ["Richard", "R"], ["Michael", "S"] ],
],
[
[ ["Allen", "S"], ["Omer", "P"] ],
[ ["David E.", "R"], ["Richard X.", "P"] ]
]]
if __FILE__ == $0
print rps_tournament_winner(tournament_list)
end
###Q2: Combine Anagrams
An anagram is a word obtained by rearranging the letters of another word. For example, “rats”, “tars” and “star” are an anagram group because they are made up of the same letters. Given an array of strings, write a method that groups them into anagram groups and returns the array of groups. Case does not matter in classifying string as anagrams (but case should be preserved in the output), and the order of the anagrams in the groups does not matter. Example:
# input: ['cars', 'for', 'potatoes', 'racs', 'four','scar', 'creams', 'scream']
# => output: [["cars", "racs", "scar"], ["four"], ["for"], ["potatoes"], ["creams", "scream"]]
# HINT: you can quickly tell if two words are anagrams by sorting their
# letters, keeping in mind that upper vs lowercase doesn't matter
def combine_anagrams(words)
# <YOUR CODE HERE>
end
My Example Code
def combine_anagrams(words)
anagram = Hash.new #use hash to store group values
words.each do |word|
# use sortted letters as key and original words as values
key = word.chars.sort{|a,b| a.casecmp(b)}.join
if anagram.has_key?(key)
anagram[key].push(word)
else
anagram[key] = [word] # assign a new array
end
end
return anagram.values
end
def combine_anagrams_1(words)
# or this one-line method
return words.group_by{|element| element.downcase.chars.sort}.values
end
words_list = ['cars','for','potatoes','racs','four','scar','creams','scream']
print combine_anagrams(words_list)
#print combine_anagrams_1(words_list)
Q3: Dessert
Create a class Dessert with getters and setters for name and calories. Define instance methods healthy?, which returns true if a dessert has less than 200 calories, and delicious?, which returns true for all desserts. Create a class JellyBean that extends Dessert, and add a getter and setter for flavor. Modify delicious? to return false if the flavor is black licorice (but delicious? should still return true for all other flavors and for all non-JellyBean
desserts). Here is the framework (you may define additional helper methods):
class Dessert
def initialize(name, calories)
# YOUR CODE HERE
end
def healthy?
# YOUR CODE HERE
end
def delicious?
# YOUR CODE HERE
end
end
class JellyBean < Dessert
def initialize(name, calories, flavor)
# YOUR CODE HERE
end
def delicious?
# YOUR CODE HERE
end
end
My Example Code
class Dessert
def initialize(name,calories)
# initialize instance variables
@name = name
@calories = calories
end
def healthy?
if @calories > 200
return true
else
return false
end
end
def delicious?
return true
end
# getters and setters
attr_accessor:name,:calories
end
apple = Dessert.new("apple",150)
puts apple.healthy?
#print apple.calories
class JellyBean < Dessert
def initialize(name,calories,flavor)
super(name,calories) # send arguments to parent
@flavor = flavor
end
def delicious?
if @flavor.downcase=="black licorice"
return false
else
return true
end
end
# getter and setters
def flavor
@flavor
end
def flavor=(value)
@flavor = value
end
# or attr_accessor
# attr_accessor:flavor
end
jelly = JellyBean.new("ijelly",1500,"black licorice")
puts jelly.delicious?
#puts jelly.name
