Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

Ruby practice 2

2016-04-28

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.

  1. 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”]).
  2. 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

Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2019. All rights reserved by melonskin. Powered by Jekyll.