Forem: Micah Shute

Strategy and Decorator Design Patterns

Micah Shute — Tue, 19 Mar 2019 04:27:16 +0000

Why do I use a Decorator or Strategy?

Or any design pattern, for that matter? In general, design patterns are created and used to promote object composition over inheritance, allow for (black-box) code reuse, better enforce the single responsibility principle, and reduce the size and unwieldiness of your code's classes in general.
Like any design pattern, Decorators and Strategies have specific scenarios when they are there are beneficial to use. These two patterns can have similar use cases, and it can be easy to confuse when you should use one or the other. According to [1], both Decorators and Strategies can be employed when your goal is an "alternative to extending functionality by subclassing". Strategies can also be used when you have classes with algorithmic dependencies, and Decorators can be used to easily alter the functionality of a class which itself is not easily changed.

So what actually are they and how do you use them?
Let's get specific. Decorators and Strategies are just extra classes I write to alter/extend the functionality of a class I have already written. The way they alter this functionality is different, and therefore they are useful in different scenarios. First, let's look at the class diagrams [1]:

Decorator

What is this saying? If you haven't looked at too many class diagrams, or you are only familiar with dynamically typed languages, it can be confusing. Each box with a bold title represents a class. In Ruby, we won't actually be programming all of the classes we would in Java or C++, for example.

All of the boxes which do not say Concrete are the architecture of our inter-class APIs that we are designing. In statically typed languages, we have to define these in code as Interfaces, Prototypes, Abstract Classes, etc. depending on the language. In dynamically typed languages, they are defined in the documentation and in our minds as the engineers of the class ecosystem. There are ups and down to both statically and dynamically typed languages; statically typed classes error check for you, help you be more precise and cleaner in your code, and ensure you are designing your system correctly, while dynamically typed languages require less code and can be a lot simpler to create and read IF designed well and properly documented. If designed badly, they can be much harder to read and debug.
But now getting back to the Decorator Class Diagram; basically, this diagram tells us that we have a class ConcreteComponent and we want to extend its functionality. This class has the functions and properties as defined by Component. So, we make another class with the same API as ConcreteComponent (i.e. it conforms to the Component design) except that it has one extra reference: a Component (which is going to be the original class you wanted to extend the functionality of or any decorator it is already wearing), and we call this new design Decorator. We can make as many different types of Decorator classes, as long as it adheres to this design.

Above you can see that the Component can do an Operation(). So, our Decorator also has to be able to do an Operation(). Since our Decorator has a reference to Component, it just looks at how Component does Operation(), mimics that output, and then changes what it needs to and returns this new-and-improved output from its Operation() method. That is what the dotted lines are showing you above.

Pseudo-Code:

class NumberComponent
   func operation(x){
      return x
   }
end

class BinaryNumberDecorator
   constructor(component){
      this.c = component 
   }  
   func operation(x){
      return this.c.operation(x).toBinary()
   }
end

c = new NumberComponent()
d = new BinaryNumberDecorator(c)
x = 2
c.operation(x) // outputs what your original class returns
d.operation(x) // extends functionality of NumberComponent using the same function call

I'll show more complex, working ruby code below.

Strategy

Here, the Context is the class I want to extend the functionality of. So, I make a Strategy class that can perform that function. It is interchangeable because each ConcreteStrategy conforms to the same Strategy interface. Note that unlike the Decorator, the Strategy does not need to share an interface with Context. This design pattern is convenient when the functionality I want is complex and can be implemented with different algorithms. Let's say I am creating a class which needs to perform the Fast Fourier Transform (FFT). Since the FFT can be calculated in different ways, and I may want to switch to a faster/better algorithm in the future, I can implement a Strategy to perform the calculation.

Pseudo-Code:

class DataContext
   constructor(data, fftStrategy = new Radix2Strategy()){
      this.data = data
      this.fftStrategy = fftStrategy
   }
   func fft(){
      return this.fftStrategy.fft(this.data)
   }
end

class BruteForceFFTStrategy
   func fft(data){
      ...perform brute force fft
      return calculated_fft
   }
end

class Radix2Strategy
   func fft(data){
      ...perform radix 2 strategy
      return calculated_fft
   }
end

Intuition

Decorators are kind of like Russian nesting dolls. You take an object you want and nest it inside of your class which uses the inner functionality and adds onto it to makes it more functional. So actually, decorators are more like in MIB when the little Arquillian is controlling the humanoid body inside the head. He is like the original Component and the body is like a Decorator. He could then decorate himself further by having his human decoration operate some sort of exoskeleton. At that point, the little alien and his exterior would have the same methods, like moveArm() or push(), but the decorated exoskeleton would have a much different output (i.e. he could push harder). As such, the decorator has to have the same interfaces as the underlying class. It eats the original Component and allows the world to interact with it the same way it would interact with the original Component.
Strategies, on the other hand, are kind of like replaceable cards in a robot. Imagine you pulled off the back plate and there were slots with digital cards inserted for each function such as eating, walking, talking, etc. You could take any of them out and replace them when an algorithm was updated or you wanted to change the behavior of the robot.
In general, if you are wondering whether to use a Strategy or Decorator design pattern, a rule of thumb is to keep the base class simple in a decorator. If the Component is too complicated, you will have to mirror too many methods in each decorator, and it will be better to use a strategy.
Also, decorators are widely used when you want to dynamically add functionality to an object, not necessarily an entire class (and perhaps withdraw this functionality at a later time). Strategies are commonly used to perform a function which is very complicated and can be performed in different ways (perhaps with different time/space complexities).

Code Example

Decorators:


class IceCream

    def initialize(price: 1.0)
        @price = price
    end

    def price=(amt)
        @price = amt
    end

    def price
        return @price
    end

    def ingredients
        "Ice Cream"
    end

end


class WithJimmies
    def initialize(item)
        @item = item
    end
    def price
        @item.price + 0.5
    end

    def ingredients
        @item.ingredients + ", Jimmies"
    end
end

class WithChocolateSyrup
    def initialize(item)
        @item = item
    end
   def price
        @item.price + 0.2
    end

    def ingredients
        @item.ingredients + ", Chocolate Syrup"
    end
end

class WithOreos
    def initialize(item)
        @item = item
    end
    def price
        @item.price + 1.0
    end

    def ingredients
        @item.ingredients + ", Oreos"
    end
end


class FroYo

    def initialize(price: 1.5)
        @price = price
    end

    def price=(amt)
        @price = amt
    end

    def price
        return @price
    end

    def ingredients
        "Froyo"
    end
end


treat = IceCream.new
treat = WithJimmies.new(treat)
treat = WithOreos.new(treat)
treat = WithChocolateSyrup.new(treat)
puts treat.ingredients # "Ice Cream, Jimmies, Oreos, Chocolate Syrup"
puts treat.price # 2.7
another_treat = FroYo.new
another_treat = WithJimmies.new(another_treat)
puts treat.ingredients # "Froyo, Jimmies"
# Froyo and Ice Cream (Components) and all of the Decorators have #price and #ingredients
# methods, making them conform to the same interface.

Strategies:

class ChocolateSyrup
    def price
        0.2
    end 
    def ingredients
        "Chocolate Syrup"
    end
end


class Jimmies
    def price
        0.5
    end
    def ingredients
        "Jimmies"
    end
end

class Oreos
    def price
        1.0
    end
    def ingredients
        "Oreos"
    end
end

class IceCream

    attr_accessor :toppings, :price_strategy

    def initialize(toppings: , price_strategy: CalculatePriceStandardStrategy )
        @toppings = toppings
        @price_strategy = price_strategy.new
    end

    def price
        self.price_strategy.calculate(self.toppings)
    end

    def ingredients
        self.toppings.length > 0 ? "Ice Cream, " + self.toppings.map(&:ingredients).join(", ") : "Ice Cream"
    end

end

class CalculatePriceStandardStrategy
    def calculate(toppings)
        return 1.0 + toppings.reduce(0){ |cum, curr| cum + curr.price }
    end
end

class CalculatePriceRewardsMemberStrategy
    def calculate(toppings)
        return 0.5 + 0.8 * (toppings.reduce(0){ |cum, curr| cum + curr.price })
    end
end


toppings = [ChocolateSyrup.new, Jimmies.new, Oreos.new]
strategy = CalculatePriceStandardStrategy
treat = IceCream.new(toppings: toppings, price_strategy: strategy)
puts treat.ingredients # Ice Cream, Chocolate Syrup, Jimmies, Oreos
puts treat.price # 2.7
treat.price_strategy = CalculatePriceRewardsMemberStrategy.new
puts treat.price # 1.86

That covers the basics. You can see more in-depth descriptions and discussion in the reference below.

References:

[1] DESIGN PATTERNS Elements of Reusable Object-Oriented Software, Gamma, Helm, Johnson, Vlissides

Resource Summary for Simple Rails Features

Micah Shute — Thu, 20 Dec 2018 06:44:02 +0000

I made my first rails app last week, and here are some resources and strategies I used to make it work

Google Authentication

Google OAuth gem

# config/initializers/omniauth.rb

Rails.application.config.middleware.use OmniAuth::Builder do
    provider :google_oauth2, ENV['GOOGLE_KEY'], ENV['GOOGLE_SECRET']
end

You can add a google_uid column and a google_refresh_token to the user table if you need a unique property with which to query a user, or you want to use more advanced features of Google's API (and allow an offline refresh of the token). Because I have a uniqueness validation of a user's email and I am only using Google for authentication, I didn't need those columns but added them anyway just in case I had a design change in the future.
In my schema, I made a user's email validate uniqueness so that logging in with Google could create a whole new account, or find an account with that email and update a google_uid property to it without altering the password.
- To make this method foolproof, it would be important to have a user verify their email if the account is made traditionally (ie without OAuth).
You need to have an action dedicated to handling the OAuth callback.
- This action needs to be associated with the callback route you specify in the Google API page (the link to that page is on the GitHub of the Google OAuth gem linked above.)
- My custom route for the callback that I defined in my routes.rb file was: get 'auth/google_oauth2/callback', to: 'sessions#googleAuth'
- My callback action in my SessionsController utilized a custom class method written in the User model, to which it passed the return from the OAuth process, like so:

#  SessionController#googleAuth
    access_token = request.env["omniauth.auth"]
    user = User.from_google(access_token)

#  User.rb

    def self.from_google(auth)
        refresh_token = auth.credentials.refresh_token
        if (found_user = User.find_by(email: auth.info.email))
            found_user.google_uid = auth.credentials.token
            found_user.google_refresh_token = refresh_token if refresh_token.present?
            return found_user
        else
            new_user = User.new do |u|
                u.email = auth.info.email
                u.name = auth.info.name
                u.google_uid = auth.credentials.token
                u.google_refresh_token = refresh_token if refresh_token.present?
                rand_password = RandomPasswordStrategy.random_password
                u.password = rand_password
                u.password_confirmation = rand_password
            end
            return new_user
        end

    end

From there, you just check to see if the user is valid, and log them in if it is, and otherwise display an error.
The RandomPasswordStrategy is just a class I made that uses the sysrandom/securerandom method SecureRandom.hex(64) combined with random ordering of required symbols and numbers (as required by the password policy) to create a complex, valid random password.

Authorization Methods, Error Pages

I put a lot of private methods in my ApplicationController to abstract away authorization throughout my app, making it easier to authenticate a user in the correct manner and display an appropriate message to them if there was an issue.
I wanted logged out users to be able to see most of the app, and then restrict other parts of it to only users with accounts. There are some aspects that only specific users have access to, such as editing your own posts, etc.
Some pages will show differently based on whether or not the user is logged in. To accomplish this simply, I added two methods to the ApplicationController so it is available to all Controllers (which inherit from ApplicationController), as well as adding them as helper_methods to make them available in the Views if necessary:

#  application_controller.rb

helper_method :logged_in?
helper_method :current_user


private

def current_user
    User.find_by(id: session[:user_id])
end

def logged_in?
    !current_user.nil?
end

These are primarily used as decision-makers on what is shown on certain pages, or building blocks to more advanced authorization methods.
If an unauthorized user tries to access a page you don't want them to, it is appropriate to show a 403 error page. I accomplished this by creating a public/403.html.erb file, and calling it via another method in ApplicationController

# application_controller.rb

def not_authorized(msg = "You are not authorized to view that page")
    flash[:danger] = msg
    render(:file => File.join(Rails.root, 'public/403.html.erb'), :status => 403, :layout => false)
end

Which can accept a custom flash message as a parameter, and which serves as a good building block for other methods, like this:

# application_controller.rb

def authorize(user=nil)
    if user.nil?
        not_authorized('<a href="/login">Login</a> or <a href="/signup">Signup</a> to view this page!') unless logged_in?
        !!current_user
    else
        if user == current_user
            not_authorized
            false
        else
            true
        end
    end
end

If the above is called without a user parameter, it will only display a 403 error page if the user is not logged in. If it is called with a user, the 403 will be called unless that specific user is logged in. It also returns a boolean to indicate success or failure. If you need to use current_user in the controller after calling authorize, you will get an error if the authorization fails. An easy way to fix this is to use an if-else block with the authorization check rather than using it as a standalone function so that any code which calls current_user will not be run unless authorization succeeds. For this to work, a boolean (or at least truthy and falsy) value must be returned. If the authorization fails, it will return false and then once the controller action is complete it will render the 403 error page.

Following Users, Sending Messages, Reacting to Posts, Scope Methods

For some relationships, ActiveRecord relations aren't as simple as has_many :classes, through: :user_classes or something like that. 3 Situations particularly I had to get more creative to make work:

Following other Users:

Many to many relationships, ie a user is following many users and is followed by many users.
The answer to the problem is just a simple join table, but it's just slightly different than a standard join table, as it joins a table to itself, and requires a few extra words in the ActiveRecord class methods. The join table I used was:

# schema.rb

create_table "following_users", force: :cascade do |t|
    t.integer "following_id"
    t.integer "follower_id"
    t.datetime "created_at", null: false
    t.datetime "updated_at", null: false
end

And then to make the User model work correctly:

# user.rb

has_many :following_users, foreign_key: "follower_id", dependent: :destroy
has_many :follower_users, class_name: "FollowingUser", foreign_key: "following_id", dependent: :destroy
has_many :followers, class_name: "User", through: :follower_users, foreign_key: "follower_id"
has_many :following, class_name: "User", through: :following_users, foreign_key: "following_id"

Messaging

This was pretty similar to implementing following/followers, except the model Message is the join table, and is also the model that we are interested in, so it is simply just:

# schema.rb

create_table "messages", force: :cascade do |t|
    t.integer "sender_id"
    t.integer "reciever_id"
    t.text "content"
    t.boolean "viewed", default: false
    t.datetime "created_at", null: false
    t.datetime "updated_at", null: false
end

# user.rb

has_many :sent_messages, :class_name => "Message", :foreign_key => "sender_id", dependent: :destroy
has_many :recieved_messages, :class_name => "Message", :foreign_key => "reciever_id", dependent: :destroy

Reacting to Posts

There were a few solutions to this problem I considered, but I decided to make a table ReactionType which has a many-to-many polymorphic relationship to anything that is reactable, in my case Topics and Posts. Reactions were the join tables between the reactables and the ReactionTypes. I did this instead of Reaction holding the reaction type via a string in order to minimize errors (ie spelling errors), and allow for flexibility, for example, easy expansion of allowed ReactionTypes in the future.
- Doing it this way made Reactions a 3-way join table between User, reactables, and ReactionType
- ReactionTypes have to be seeded to the types you want to be available to the user. I had like, dislike, genius, and report.

# schema.rb

  create_table "reaction_types", force: :cascade do |t|
    t.string "name"
    t.datetime "created_at", null: false
    t.datetime "updated_at", null: false
  end

  create_table "reactions", force: :cascade do |t|
    t.integer "user_id"
    t.string "reactable_type"
    t.bigint "reactable_id"
    t.integer "reaction_type_id"
    t.datetime "created_at", null: false
    t.datetime "updated_at", null: false
    t.index ["reactable_type", "reactable_id"], name: "index_reactions_on_reactable_type_and_reactable_id"
  end

# reaction.rb

  belongs_to :user
  belongs_to :reaction_type
  belongs_to :reactable, polymorphic: true

# post.rb

has_many :reactions, as: :reactable, dependent: :destroy
has_many :reaction_types, through: :reactions

#topic.rb

has_many :reactions, as: :reactable, dependent: :destroy
has_many :reaction_types, through: :reactions

In the same fashion using polymorphic relationships, you can create tags that can be attached to taggables, and post replies to things which are postable.

Advanced ActiveRecord class methods

When I was trying to make the correct ActiveRecord class methods to retrieve specific "statistics" for a user dashboard or to find popular topics for my homepage, I found that the best resource for me was to see other advanced and specific class methods and use those examples as a reference. I will put some of mine here in the hopes that others can use it as a reference.
- To create a "spotlight topic" of the day for my homepage - take the most positively reacted topic in the past 24 hours:

# topic.rb

def self.trending_today
    Topic.joins(:reaction_types).where(reaction_types: {name: ['like', 'genius']}, classroom_id: nil).where(reactions: { created_at: ((Time.now - 24 * 3600)..Time.now)}).group('id').order(Arel.sql('count(reaction_type_id) DESC')).limit(1)
end

Find the most reacted Topic by User and reaction_type:

#topic.rb

def self.most_liked_by_user(user, limit=5)
    most_reacted_type_by_user(user, 'like', limit, false)
end

private

def self.most_reacted_type_by_user(user, type, limit, count)
    if count
        Topic.joins(:reaction_types).where(reaction_types: {name: type}, user_id: user.id).group('id').order(Arel.sql('count(reaction_type_id) DESC')).limit(limit).count
    else
        Topic.joins(:reaction_types).where(reaction_types: {name: type}, user_id: user.id).group('id').order(Arel.sql('count(reaction_type_id) DESC')).limit(limit)
    end
end

#user.rb

def most_liked_topics(limit=5)
    Topic.most_liked_by_user(self, limit)
end

Setting up Bootstrap

This post walks through how to set up your rails app with bootstrap in just a few minutes.
There is a complication with bootstrap that won't be ideal right 'out of the box' -> while rails will give your form_for fields the fields_with_errors class automatically when there are issues with the form inputs, Bootstrap will not respond to it. Instead, it responds to the class is-invalid.
- This blog shows a working good solution to make form errors work well with rails. It just includes adding a file and code to your config/initializers folder, and basically, all it does is change the default field-with-errors class to is-invalid instead, which is what bootstrap uses to indicate a field which was filled out incorrectly.

Rendering Markdown

I was between the two libraries redcarpet and kramdown. I ended up choosing kamdown because:
- It is more recently committed and seems to be maintained more
- Its popularity is growing while redcarpet is decreasing
- It allows integration with MathJax which allows LaTex rendering.
Getting basic integration was relatively simple. It got a little more complicated to achieve the following 2 goals:
- Syntax highlighting for code
- Being able to sanitize the user's input while allowing all of the Markdown features to implement correctly.
I decided to use rouge for syntax highlighting. I'll show you the code below to get it working with Kramdown, but the hard piece of information to find was how to get the proper CSS files that make the highlighting happen. Here's a good stack overflow answer that's hard to find. Basically, once you tell kramdown that you want to use rouge (and you have installed both the kramdown gem and the rouge gem), you can run rougify help style in your terminal, and you can see all of the custom CSS files you can add to your app/assets/stylesheets path. To get the raw CSS, type rougify style followed by one of the allowed styles. For example: rougify style colorful. The CSS will be printed in your terminal. You could also run

rougify style colorful > ./app/assets/stylesheets/rouge_style.css

Now, it's relatively easy to render markdown. I made a helper method to make it extra simple:

# application_helper.rb

def render_markdown(markdown)
    render 'components/content', markdown: Kramdown::Document.new(markdown, parse_block_html: true, syntax_highlighter: :rouge, syntax_highlighter_opts: {line_numbers: false}).to_html
end


<!-- views/components/_content.html.erb -->

<%= sanitize_markdown markdown %>

Custom sanitize method:
- As you can see here, I am not using raw or .html_safe to render this HTML data because ultimately it came from a user and cannot be trusted. However, the safe sanitize method disallows certain things I want to be rendered, such as tables. You can get proper sanitation AND your desired HTML tags by manually appending to the whitelisted tags allowed through sanitize by doing something like what is shown below.

# application_helper.rb

def sanitize_markdown(content)
    sanitize(content, tags:  Loofah::HTML5::WhiteList::ALLOWED_ELEMENTS_WITH_LIBXML2.to_a + %w(table th td tr span), attibutes: Loofah::HTML5::WhiteList::ALLOWED_ATTRIBUTES + %w( style ))
end

General tips

Set up the app with PostgreSQL
- Here's a blog post I wrote about setting up WSL, but there's a section at the bottom that covers using pgAdmin and setting up a Rails app with PostgreSQL
Save all secret keys as environment variables. I used Figaro to make it easy.
Avoid the N+1 problem
- This occurs when you get a collection of models, of which you want to query and show nested models. If you iterate over your models n times to do this, you are making n+1 database calls which can be quite expensive with large amounts of data, especially when requesting over a network. This is easily fixed by using the includes method when making your initial query. Check this site out and go to the section called "Solution to N + 1 queries problem" for more info.
Clean up the database automatically when objects are destroyed
- When you appropriately add

  dependent: :destroy

to your ActiveRecord class methods (examples can be seen in code snippets above), you are telling ActiveRecord to destroy these relations upon the destruction of the model. As you can see above, I implemented this for reactions within post.rb. This tells rails that when a post is destroyed, all user reactions to it should also be destroyed. This prevents disconnected likes and dislikes, etc, from floating around in your database for no reason. Also, note this should be a one-sided relationship. You would not want a post to be destroyed if a user destroys their one reaction to it.

Adding custom files and classes
- There are going to be things you want your app to do that are outside of MVC. This means you are going to want to add files outside of the standard model, view and controller directories. Here are some resources with advice on how to do this:
- A StackOverflow answer
- A GitHub gist post
Personally, I used a lib directory in my app directory because it is eagerly loaded in production and lazy loaded in development. I did not need to alter any configuration or environment files for the classes within files in that directory were referenced.

Divide and Conquer the Fast Fourier Transform

Micah Shute — Wed, 07 Nov 2018 07:18:06 +0000

What is the Fourier Transform and why should I care

Simply put, the Fourier Transform allows humans or machines to see time domain signals in the frequency domain. Common applications are data visualization in oscilloscopes and function generators, radar, sonar, spectral analysis, digital communication signal processing, and instrument monitoring.

There is also a broad range of uses for the Fourier Transform beyond visualization or even an end game of frequency analysis. Linear Time Invariant (LTI) systems and signals respond to each other through convolution, which can be a mathematically impractical operation to evaluate. These system outputs can be modeled accurately by simply multiplying their Fourier Transforms together and then converting them back to the time domain, given that we avoid aliasing when doing so.

Lastly, a lot of data compression uses algorithms similar to the Fast Fourier Transform. For example, JPEGs use the Discrete Cosine Transform which is very similar to the Discrete Fourier Transform.

Why and how does it work

This is a question with a long answer. Here's the short and dirty:

This is the equation to convert a time domain signal x(t) to a frequency domain signal X(f):

Where t is time and f is frequency in Hz.

If you haven't seen this before it doesn't make much sense. Without getting caught up in the math, here's what you need to know:

Almost all signals that exist can be made up of a summation of cosine and sine signals, even aperiodic continuous time signals.
- For example, a decaying exponential signal

has the frequencies:

whose magnitudes look like this:
-
- You may recognize that a capacitor responds to a voltage impulse via an exponential decay, slowly discharging its built up voltage over time. So, the fact that the frequency makeup of the exponential decay is large for lower frequencies and small for higher frequencies makes sense intuitively, because the voltage across a capacitor will only look like the input when the input changes values slowly enough to allow this discharge process to take place. This is why the frequency range looks the way it does in this case.
- Note: Negative frequencies are part of both sine and cosine signals. it is what keeps time signals "real" when we mathematically model them as will be explained below.

We can make mathematically convenient equations using Euler's property:
- - Don't be confused about the imaginary numbers. They are a way to show phase angle data in the frequency domain. Real time signals will never become "imaginary" time signals - the imaginary parts will always cancel out to give you a mixture of sines and cosines.
  - Note that this shows why negative frequencies are necessary to model sinusoids in this way.

So, if we know from (1) that all signals can be made up of a summation of sines and cosines, we can manipulate that fact to retrieve those cosines and sines from a time signal. These retrieved sines and cosines are our frequency domain signal. It is done mathematically via the equation above, like was shown in the example.

Ok ... so I don't see how I can make a program that does this

As of now, our equation acts on a continuous time (CT) signal via an infinite integral. That is not conducive to digital processing and programming. Before we can try to write a program to get the information we need, you have to do a few things to get a signal we can manipulate.

Turn the infinite CT signal into a discrete time, limited size signal. This can be done by sampling and quantization for a limited number of samples. If you sample at a rate >= twice the highest frequency component of the signal (ie the Nyquist frequency), you can avoid aliasing. This is usually done by dedicated hardware. However, we care now about how we use these samples, not how we get them.
Change the equation for getting the frequency domain of our signal so it can work with a size-limited array of sampled data points instead of an infinite continuous time signal. So, instead of an integral we need a summation, and instead of an infinite size we use the size of our sampled data array:
- One more problem though - the frequency domain of an aperiodic signal, discrete or not, is still continuous - so we can't manipulate it on a computer. The answer to this is the Discrete Fourier Transform, a periodically sampled version of the Fourier Transform for a discrete time signal. To get this, we can replace the frequency term with a term that divides it into equal parts over the N samples: where we are evaluating for the k^th sample and there are N total samples.
  - If you are curious if we can recreate the time domain samples accurately from this sampled version of the frequency domain, the short answer is yes, as long as we avoid time-domain aliasing by ensuring the total samples of our frequency domain are greater than or equal to the length of our time domain sample. We can increase the sample rate of our frequency domain without increasing the length of our sampled data by adding zeros to the end of the time domain signal. This will make the samples of our frequency domain be closer together.
- Anyway, the end story is that we get this equation to get a frequency domain transform function from an array of sampled data:

How do you compute it

Now that we have the equation, this part is easy!

signal = ->(t){Math.cos(2 * Math::PI * t)} # 1 Hz cosine signal
sample_times = (0..1000).map{ |int| int / 100.0} # Sample for 10 seconds every 0.01 seconds (100 times per period over 10 periods)
data = sample_times.map{ |time| signal.call(time) } # turn time into sample values

#Discrete Fourier Transform
ft = []
for k in 0...data.length do
    tot = 0
    data.each_with_index do |x_n, n|
        tot += x_n * Math::E ** (Complex(0,-1) * 2.0 * Math::PI * k * n / data.length.to_f)
    end
    ft << tot
end

Too easy! Done, right?

Not quite. You get the right answer, but that looks like a nested loop to me. ϴ(n^2) is rearing its ugly head to let us know we can't do any real-time processing with this algorithm.

Since the FFT is needed in so many real-time applications, and sampled signals are usually very long, we need to find a way to severely cut down on processing time.

How to compute it well: Divide and Conquer

So here's where the Fast Fourier Transform (FFT) comes in, which allows us to use this signal in real time.

First, let's get intuition to what the shortcuts are that we can take advantage of, which makes it advantageous and possible to cut this problem down into smaller sub-problems. The characteristics we want to use are twofold, and come from the fact that we are manipulating complex roots of unity by multiplying by

on each iteration. What does that mean? Well, remember from above that

Let's first see what an example of that looks like; I did a little back-of-a-napkin demonstration:

So you can think of the Real and Imaginary axis like East/West and North/South lines, and as a compass needle that points to the angle and changes with time t. The properties we want to take advantage of are based off of the situation where we divide the 2π radians into N even segments, as we are doing to calculate the Discrete Fourier Transform. That can be visualized:

Can you see the properties we want to exploit? They are:

The i^th partition is the complex conjugate of the N-i^th partition. This means that if we have 8 partitions (and k = 1), the 1^st partition is and the -1^st partition (ie the 7th partition) is .
- n = 1:
- n = 7:
- As you can see, the 1 and N-1 signals are related because their real components are the same, and their imaginary components are negatives of each other. You can see that visually above.

2_ This circle is periodic, so when the variable k begins to increase, we just loop around the circle as n increments.

Now let's finally see how to exploit these characteristics using the Radix 2 FFT algorithm.

We know that in order to divide and conquer, we want to break down a problem in halves (or some radix). We notice from our drawing that if we take the even partitions in the case of 8 partitions, we will be left with the partitions as if we had 4 complex roots of unity instead of 8 (ie 4 even divisions of 2π), thus giving us a smaller problem to solve, which is what we want. Mathematically, let's see what it looks like if we broke the signal up into even and odd samples:
- This reduces to an equation of 2 sub-arrays of data which are half the size of the original dataset, and will be multiplied by the roots of unity of N/2 instead of N, essentially creating 2 identical sub-problems:
- We can now just recurse with our even and odd subarrays until you hit the base case of N = 1 (here n and k will be zero so you are just multiplying this one value by e^0 = 1), and return that value as the DFT of itself. Then combine per the equation above.
Awesome, but there is still one more thing we can do. Remember how we said that the i^th and N-i^th roots are complex conjugates of each other (ie, the roots of unity drawing is a mirror image across the x axis)? Well, that means that once we solve the two sub-problems for size of N/2, we can combine them to get the N DFT values by creating their corresponding "mirror image" values at the same time. This will stop us from having to loop through the N/2 sub-problems' data twice to create the N data values required to make X(k) one level up. We want to take the k^th result of the DFT of the even array and we add it to times the k^th result of the DFT of the odd array, and put it into an array that will be for the 0...N/2 values of X(k). We again take the k^th result of the DFT of the even array but now we subtract from it times the k^th result of the DFT of the odd array, and put it into an array that will be for the N/2...N values of X(k). We do this N/2 times. Lastly, we append the N/2...N array to the end of the 0...N/2 array to get the full answer for the next level up, X(k). In an equation, each level's combine step looks like this:

3_ A necessary detail:

This premise of being able to divide the problem by 2 and make even partitions of the unit circle requires that the sample data array be a power of 2. This is a simple metric to meet. All you have to do is add 0s to the end of your data until your data array's length is a power of 2. This ensures the algorithm works, and it creates closer "sample points" in your Discrete Fourier Transform, making the visualization better.

Show me how you implemented it

class Radix2Strategy 

    E = Math::E
    PI = Math::PI

    attr_reader :data

    def initialize(data: )
        @data = data
        zero_fill
    end

    def calculate(data = @data)
        recursive_fft(data)
    end

    private

    def recursive_fft(arr)
        n = arr.length
        return arr if n == 1
        w_n = E ** ((-2 * PI * Complex(0,1)) / n)
        w = 1
        a0 = get_even(arr)
        a1 = get_odd(arr)
        y0 = recursive_fft(a0)
        y1 = recursive_fft(a1)
        y = Array.new(n, 0)
        for k in 0...(n/2) do
            y[k] = y0[k] + w * y1[k]
            y[k + n/2] = y0[k] - w * y1[k]
            w = w * w_n
        end
        return y
    end

    def get_even(arr)
        even = []
        arr.each_with_index { |a, i| even << a.dup if i.even? }
        even
    end

    def get_odd(arr)
        odd = []
        arr.each_with_index { |a, i| odd << a.dup if i.odd? }
        odd
    end

    def zero_fill
        len = self.data.length
        @data = @data.concat Array.new(closest_pow_of_2(len) - len, 0)
    end

    def closest_pow_of_2(num)
        2 ** Math.log(num,2).ceil
    end
end

Developing Style: Big O, Sorting

Micah Shute — Wed, 17 Oct 2018 15:49:33 +0000

A continuation of the documentation of my studies as I learn the foundations of programming. Feedback is welcomed.

Big O

What is it

It describes the asymptotic nature of a system as the input grows. Usually, we are describing runtime of an algorithm, but it can also be used to describe space complexity or even systems outside the realm of computer science. Here I will assume it describes runtime of an algorithm unless stated otherwise. Asymptotic analysis means that you focus on how the runtime of the algorithm grows as the input grows and approaches infinity. The input is usually denoted as n. As our datasets get larger, it is the growth function which will be the dominating factor of runtime. For example, O(n) suggests that the runtime changes linearly with the input n. O(n^2 ) suggests that the runtime changes proportionally to the size of the input squared. With large datasets, this is usually enough information to tell you which one will be faster.

When you analyze asymptotic characteristics of a function, you want to discount added constants, as well as drop coefficients and lower-order terms. For example, f(n) = 100 * n * lg(n) + n + 10000 is described as O( n * lg(n) ), because as n goes to infinity, the constant and the coefficient become insignificant. Check these graphs out:

As you can see, in small datasets, big O notation may not be telling the whole story, but even going from 50 to 500 data points in the above graph made the asymptotic nature of the functions take over.

Certainly, there are merits to optimizing code within a certain asymptotic runtime to maximize performance, but that should be done only after the proper asymptotic algorithm is being used.

Although it seems that colloquially "big-O" is used to mean the asymptotic runtime which describes a function's 'tight asymptotic' nature, (ie describes both upper and lower bound), this isn't actually accurate. The formal definitions of asymptotic runtime are briefly described below [1]:

Big - ϴ (theta) :
- Formally, for ϴ( g(n) ) to describe a function f(n), there exist positive constants c1, c2, and n_o such that 0 <= c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n_o
- To clarify: imagine you have an algorithm that is defined by a complex equation f(n). You can characterize f(n) in big-theta notation by a very simple equation g(n) which has all constants, coefficients, and lower-order terms dropped IF you can re-add 2 arbitrary constants to g(n) which can "sandwich" your original equation f(n) past a certain input data size n_o.
- Example: let's say your f(n) = 100*n^2 + 4*n*lg(n) . We can show that n^2 can meet this definition with the following equations and graph
- Now, if we tried to sandwich our f(n) with nlgn, we see that the upper bound is inevitably passed by f(n) as n grows, regardless of the constant that we set:
- So, technically every time I called a function big-O above, what I should have said is big-theta, ie ϴ(n) instead of O(n).
Big-O:
- Only provides an asymptotic upper bound as opposed to an upper and lower bound provided by ϴ notation.
- Formally, for O( g(n) ) to describe a function f(n), there exist positive constants c and n_o such that 0 <= f(n) <= c*g(n) for all n >= n_0
- So it is actually correct to say an algorithm defined by f(n) = 3*n + 100 is O(n^3 ), even though it is ϴ(n).
There also exist other less-used notations defined similarly as the above:
- Ω (big-omega) notation defines an asymptotic lower bound only
- o (little-o) notation defines an upper bound which is NOT asymptotically tight (such as the example above where we describe a ϴ(n) function as O(n^3 ) - that is an asymptotically not-tight definition and you could therefore say it is also o(n^3 ). o(n) would be incorrect)
- ω (little-omega) notation defines a lower bound which must NOT be asymptotically tight.

When describing algorithms, the most used concept is ϴ notation, and it is usually communicated as O notation.

Although algorithms can be analyzed by their best-case, average-case, and worst-case runtimes, we usually (with a few exceptions below) focus on worst-case for 3 main reasons:

It is easier to calculate the worst-case runtime than the average runtime (fewer factors to account for)
A worst-case analysis is a guarantee that we will never take any longer
It is not uncommon that the worst-case scenario happens frequently when implemented

It turns out that lgn (shorthand for log base 2 of n) is important to a lot of runtime discussions. A quick review of logarithms:

A logarithm describes what power the base must be brought to in order to create a certain number. For example, since our base is 2, if we want to find lg(8), we ask ourselves: "To what power can I take 2 to in order to obtain the answer 8?". In this case, since we know 2^3 is 8, we know that lg(8) = 3. You are kind of "deconstructing" an exponential. This is an important concept because if we can make an algorithm that is defined by a log, it grows super slowly! It actually grows as slowly as exponentials grow quickly, which is a lot.
- Imagine you have a dataset of size 262144, and you are performing an algorithm with runtime f(n) = n on it. If it grows to 524288, you are doing 262144 more operations! If your f(n) = n^2, you are doing 68719476736 MORE operations! If your f(n) = lgn, you are doing 1 more operation. If your f(n) = lgn, every time your dataset doubles, you do 1 extra operation.

Why is it important?

When you work with a large dataset or a dataset which may become large as you gain users or gather more information, your runtime will be determined by its asymptotic growth. As described above, constants, coefficients, and lower-order terms have relatively minor significance compared to the highest-order component. The difference between an O(n*lg(n)) algorithm and an O(n^2 ) algorithm can easily be the difference between a well-performing app and an absolutely unusable app.

How do you use O-notation practically?

Understand when it is important
- If you are working on a small dataset and it has absolutely no way of getting big, it may not be worth your time developing super-optimized code or trying to get a better runtime for your algorithm.
If your dataset is or may get very large, it is important to understand how your algorithms are affecting your runtime (and your memory!). Thus, you have to be able to tell what the asymptotic runtime is of your code. Some ways to do this:
- Look through your loops. If you are iterating through a collection once, you most likely have a ϴ(n) algorithm. If your loop has an inner loop which iterates through all of your data (or n-1 each time), you most likely have a ϴ(n^2 ) algorithm, which is very dangerous.
- Understand the "behind-the-scenes" code that occurs when you call a function which you did not write yourself or that is native to the language. There could be a better-suited way to do something, and not understanding the guts of the methods you are calling can make it very hard to optimize.
- Look through your code for functions which are linked to the size of the input data, and disregard constants or repetition of that code which is not dependent on data size. This can help you more easily determine your ϴ( g(n) )
Adopt a divide and conquer mindset
- (1) Divide the problem into smaller problems, (2) Conquer the subproblems recursively until they are small enough to have a simple solution. (3) Combine the subproblem solutions to create the overall solution.
- Basically when using divide and conquer, if you can keep dividing your problem into equal halves (which is usually the division point) until it is small enough that it is trivial (easy) to solve. Then you can solve that small, easy problem and combine those easy answers into a full answer. It is very possible you have just changed your algorithm from ϴ(n^2 ) to ϴ(nlgn) runtime.
- The reason this transformation happens is that if you break down your code into equal halves, you can make that division lgn times (ie how many times can I multiply by 2 to get my data size n?). Each time you divide your problem by 2, we iterate through our data to do something to it, hence n * lgn. The sorting algorithms below will show instances of this.

Sorting

This is a simple application of big O and is something that every programmer should have a basic understanding of.

Why is it important?

Most languages have built-in sorting algorithms, but it is still important to understand how sorting works. Why?

It has a lot of important use cases:

Arguably the biggest use is increasing the speed of search through an array from O(n) to O(lgn) - a huge improvement. (ie ability to use binary search)
Delivering data to a user in a certain format (price from high to low)
Manipulating data based on its location in a sorted list (ie display the most recent posts)

Also, although I have never been in one myself, you can apparently get asked about it in technical interviews.

Sorting algorithms can have vastly different runtimes based on the data on which they are being run. Although many given sorting algorithms work pretty well on most data, it is important to know what different algorithms may work better for your use case. It might not be the best choice to simply use the language's standard sorting algorithm.

Lastly, and perhaps most importantly, it helps you get an understanding of why big O matters, and how to go about problem-solving in a way more elegant than a brute-force solution.

How can we do it, with what time complexity?

Disclaimers:

These examples are focused on time complexity and space complexity will not be taken into account.

Also, better metrics for these algorithms are the number of switches and comparisons they make, not the runtime on a specific machine. For ease, intuition, and clarity I will be providing runtimes. My RAM was never fully used, and IO to disk did not factor into the runtimes.

Algorithms annotated with a ! in the method name sort in place.

Algorithms

Bubble Sort

Characteristics
- ϴ(n^2 ) worst-case and average-case
  - Notice the nested loops giving an indication of ϴ(n^2 ) runtime
- ϴ(n) best-case
Description
- Iterate through the list checking each element with its adjacent element. Swap them if they are out of order. Repeat this until all are swapped. As an optimization, you can iterate through n minus i elements each time, where i is the number of iterations you have already done. This is because after the first sweep you guaranteed the smallest number has "bubbled" to the top (or largest number has dropped to the bottom, depending on your iteration direction), so you only need to check the indices below (above) it.
- The wikipedia page for bubble sort shows a simpler implementation of bubble sort at first and works its way to the "optimized" version.
- Even while optimized, bubble sort is extremely slow on large datasets. You can program it to return if no swaps are made, which means that the data is in order, but this only helps if you have a nearly perfectly sorted array. I did not include this optimization - for clarity, and because this characteristic is better utilized in insertion sort than bubble sort.
Code

def bubble_sort(coll)
    for i in 0...(coll.length - 1) do
        for j in (i+1)...coll.length do
            if coll[i] > coll[j] 
                coll[i], coll[j] = coll[j], coll[i]
            end
        end
    end
    coll
end

Insertion Sort

Characteristics
- ϴ(n^2 ) worst-case and average-case.
- ϴ(n) best-case
  - This best-case scenario happens when the list is already sorted (or very close to being sorted)
Description
- Imagine your collection is broken up into two parts. The farthest index on the left (ie index 0) is a "sorted array" of one element. The rest of the array is an unsorted mess. We can go one by one in our unsorted righthand side and insert that element correctly in the lefthand side of the array in order to maintain the left side sorted and to make the sorted side grow by one. By the time that we get to the end of the array, the whole lefthand side (ie the entire array) is sorted.
- This is ϴ(n^2 ) because, for each index in our unsorted side, we have to search through the sorted side for its correct location. Not only that, but we have to shift every element over on the way to make room for our insertion, which is also costly.
  - It is important to note both the number of comparisons and the number of swaps.
- For every index in the righthand side of the array, we are looking through 1 up to n other elements in the lefthand side for the correct insertion position. The summation of 1 to n is of order ϴ(n^2 )
- We can evaluate this algorithm via a "loop invariant"
  - A loop invariant is a way to prove the correctness of an algorithm which performs repetitive tasks. To do this correctly, we have to show a loop invariant (LI) statement correct for:
    - Initialization - your LI statement is true before the first time you loop
    - Maintenance - your LI statement is true throughout the duration of each subsequent loop
    - Termination - your LI statement is at the end of the program and gives a way to 'prove' your algorithm is correct.
  - In this case, a loop invariant can be stated (paraphrased from [1] ): "At the start of each iteration of our for loop, the subarray from 0 to j-1 (inclusive) consists of the elements originally in that range of indices but now in sorted order"
    - Initialization: Because the lefthand side is a single element (ie 0 to j=1-1=0 inclusive), it is sorted by definition.
    - Maintenance: Each time you loop, you insert an item from the unsorted side to the correct position on the sorted side. Then you update your indices so you know where that divide is. Your sorted side is bigger by one and still sorted. Before the loop, and after the loop, the subarray 0 to j-1 is sorted, but at the end of the loop, j is one unit larger than before.
    - Termination: Your loop is over when j is equal to your array length minus 1. So, we know that the array from 0 to (array length - 1) inclusive is sorted. That is every index in our array. Our whole array is sorted.
- As you will see below, although most of the time Insertion Sort is very slow, it is a rockstar at sorting almost-sorted data.
Code

def insertion_sort!(coll)
    for j in 1...coll.length do
        key = coll[j]
        # insert coll[j] into sorted sequence coll[0..j-1]
        i = j-1
        while i >= 0 && coll[i] > key
            coll[i+1] = coll[i]
            i -= 1
        end
        coll[i+1] = key
    end
    coll
end

Merge Sort

Characteristics
- ϴ(n*lgn) best case, worst case, and average case
Description
- Divide and conquer algorithm:
  - Divide the problem by half until the array size is 1
  - Conquer the sorting problem when the size equals one -- its already done for you because there is only one element. This will give you your first return from the merge_sort function instead of a recursion. This return will always be a sorted array (either of length 1 or merged into a sorted array) and allows you to proceed with the algorithm by now just preserving the 'sorted' status of these arrays as you combine them.
  - Combine your two smaller halves which are both of size 1 (and sorted)together by comparison to make a sorted array of length 2.
  - One level up the recursion will now have 2 arrays of size 2 which are sorted. Combine them together to create a new sorted array of length 4, and so on until your entire array is sorted.
- Merge Loop Invariant [1], (references the code below):
  - Statement: At the start of the while loop, merged_arr will contain the smallest (i + j) elements from the arrays left and right, in sorted order. left[i] and right[j] will contain the smallest numbers in their respective arrays for indices greater than i and j respectively.
  - Initialization: merged_arr is empty, and i + j = 0. left and right are sorted arrays, so both of their 0th elements will be the smallest in their entire arrays.
  - Maintenanance: The smaller of the two numbers from left[i] and right[j] is appended to the end of merged_arr. Since both arrays are in sorted order and i and j are both incremented from 0, we are guaranteed that each iteration of the while loop only considers numbers to append to merged_arr which are larger or equal to the numbers already appended to merged_arr, and smaller than or equal to the numbers of higher index remaining in left and right. This ensures the sorted condition of merged_arr. When an element is appended to merged_arr from left, only i is incremented by 1, and when an element is appended to merged_arr from right only j is incremented by 1. This ensures that merged_arr.length is equal to i + j, that merged_arr's values are in sorted order, and the next two numbers left[i] and right[j] are greater than or equal to all of the numbers in merged_arr, and less than or equal to all other values left in their respective arrays. IE, they are the two smallest values their arrays have to offer which have not already been put in merge_arr.
  - Termination: The loop breaks when one of the arrays is 'empty'. We know that at this point merged_arr is in sorted order, and has all the values of the expended array and all the values of the other array up to the index of i or j. This termination is great but requires just a little cleanup. You have to now push the remainder of the array with values left over onto the end of merge_arr. You know you can just push them at the end, because the array with leftover values is already sorted, and its lowest valued number was determined greater than or equal to the largest value in the other array.
    - Note that sometimes two "sentinels" are placed at the end of left and right and given the value of infinity. Then, the while loop is replaced by a for loop which runs left.length + right.length - 2 times, so that only the two infinity sentinel values are left. In Ruby, you can represent infinity with Float::INFINITY, in Python float("inf"), in Javascript Infinity, and in Java Double.POSITIVE_INFINITY.
Code (uncomment to see it in action - this is helpful to see how the sorting works)

def merge_sort(coll)
    len = coll.length
    return coll if len == 1
    left = coll[0, len / 2]
    right = coll[len / 2, len]
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    merge(left_sorted, right_sorted)
end

def merge(left, right)
    merged_arr = []
    i, j = 0, 0
    while i < left.length && j < right.length
        #puts "Comparing lhs #{left[i]} to rhs #{right[j]}"
        if left[i] <= right[j]
            #puts "Adding lhs #{left[i]}"
            merged_arr << left[i]
            i += 1
        else
            #puts "Adding rhs #{right[j]}"
            merged_arr << right[j]
            j += 1
        end
    end
    merged_arr.concat right[j, right.length] if i == left.length
    merged_arr.concat left[i, left.length] if j == right.length
    #puts merged_arr.to_s
    merged_arr
end

Quick Sort

Characteristics
- ϴ(n*lgn) best case, average case
- ϴ(n^2 ) worst case (when nearly sorted)
  - If you look at the code below, you can see that this is because the pivot, in the sorted case, splits the problem into two sizes n - 1 and 1, instead of n/2 and n/2. For a randomized array, it is more likely that the pivot will be a value closer to the median value. This will be described more below.
Description
- Divide and Conquer
  - Divide Choose a 'pivot point' as the last index in the array. Iterate through the array and switch values which are on the 'wrong side' of the pivot value until all values larger or equal than the pivot are on the right side of some index, and all the smaller values are on the left side of that same index. Divide the array by that index to create two smaller subproblems.
  - Conquer When the sizes are small enough (ie 1 or 2), this divide procedure will cuase the subsets to be sorted. Grouping the numbers by greater than or less than a pivot on a large scale ensures that the algorithm done on a smaller scale array of 2 (which actually causes sorting of the array) is done at a location in the array that will cause the overall array to be sorted, and not just have clumps of localized sorted data.
  - Combine Just like the Conquer of the Mergesort algorithm was trivial because all of the work was done in the Mergesort Combine, the Combine of quicksort is trivial because all of the work is done in the Divide step. After the array is divided down to sets of 1 and 2, it is sorted in place. And the algorithm will stop recursing when the size of the subarray become equal to or less than zero.
- Partition Loop Invariant (see code below)
  - Statement: Values of arr from the original argument value lo to the current value of lo are all less than or equal to the pivot value. Values of arr from the original argument value hi to the current value of hi are greater than or equal to the pivot value.
  - Initialization lo and hi are initialized to be one lower and greater than their initial values, respectively. Being outside of the array and not associated with values, you trivially meet the requirement that the related values of arr are as stated in the LI.
  - Maintenance After a single loop, thelo index value is incremented up past any indices whose value are smaller than the pivot. When the loop finally breaks,lo is therefore guaranteed to be fixed at an index whose value is greater than or equal to the pivot value, with all values to the left of it guaranteed to be less than the pivot value (or equal to the pivot value if it was swapped to the left of lo). 'hi' is decremented in the same manner, stopping on an index whose value is less than or equal to the pivot value, guaranteeing that all values to the right of 'hi' are greater than the pivot value (or equal to the pivot value if it was swapped to the right of hi). If hi > lo, we swap them because we know that the inner loops stopped on values which should be associated with 'the other side' or the 'middle' of an array divided by the pivot value, and we have not yet reached the 'middle'. This means that the new value for arr[lo] must meet the requirement for the arr[hi] loop to break (ie <= pivot), and the new value for arr[hi] must meet the requirement for the arr[lo] loop to break (ie >= pivot). So, it is maintained that all values at index lo and below are either less than the pivot (if they passed over by the loop) or less than or equal to the pivot value (if they were swapped from a point previously at an index hi). In other words, they are all less than or equal to the pivot value. Conversely, it is maintained that all values at index 'hi' and greater are either greater than the pivot value or equal to the pivot value.
  - Termination If lo >= hi, we know we have hit the place in the array which is divided numerically by the pivot value. We return the higher of the two indices, allowing us to create a subdivision of the array in which all values below the partition_index - 1 are less than or equal to the pivot and all values above the partition are greater than or equal to the pivot. Also, by subdividing the array the way that we do in quicksort! we prevent an infinite loop by preventing a partition index to subdivide into an empty array and the original array. When the subarray is of size 1 or 2, partition results in a sorted subarray section, which is also in its correct position relative to the entire array.
Code

def quicksort!(coll, lo = 0, hi = nil)
    hi = coll.length - 1 if hi.nil?
    if lo < hi
        partition_index = partition(coll, lo, hi)
        quicksort!(coll, lo, partition_index - 1)
        quicksort!(coll, partition_index, hi)
    end
end

#Hoar Partition
def partition(arr, lo, hi)
    pivot = arr[hi]
    lo -= 1
    hi += 1
    loop do
        loop do
            lo += 1
            break if arr[lo] >= pivot
        end

        loop do
            hi -= 1
            break if arr[hi] <= pivot
        end
        return lo if lo >= hi
        arr[lo], arr[hi] = arr[hi], arr[lo]
    end
end

Algorithm runtime on randomized and nearly-sorted data

numbers = []
1000000.times do 
    numbers << r.rand(500000)
end

Random Numbers:

Bubble sort (1 million numbers): 33323.8596392 s, (555.4 mins)

Insertion sort (1 million numbers): 13213.5302226 s, (220.2 mins)

Merge sort (1 million numbers): 2.0483875 s

Quick sort (1 million numbers): 3.6877069 s

Ruby's native #sort (1 million numbers): 1.0330547 s, (a very optimized Quicksort algorithm)

It is a very common use case to have to sort a collection which is already mostly sorted. Let's see how the algorithms do with that:

Ruby's native #sort (mostly sorted 1 million nums): 0.6229407 s (a very optimized Quicksort algorithm)

Merge sort (mostly sorted 1 million nums): 1.5681328 s 

Insertion sort (mostly sorted 1 million nums): 0.1712918 s

If you know you need to frequently sort a collection which is very nearly already sorted and you want to have the fastest possible sort time, a simple Insertion Sort algorithm actually beats out the fully-optimized built-in Ruby #sort, in this case by a factor of about 3.

QuickSort: Avoiding Worst Case
- When I attempted to run QuickSort on the mostly-sorted list, it crashed the program until I brought the dataset size all the way down from 1 million to about 15,000.

Quick sort (mostly sorted 15670 nums): 3.8133098 s

At this point, the runtime for these 15,000 sorted elements was the same as QuickSort running on 1 MILLION randomized elements, and while the number of quicksort recursions was smaller, the number of loops which occurred in the partition method was drastically larger.
As described above this happens because the pivot point is at the end of the array, so every single other element in arr is less than the pivot point! Instead of making two even subproblems to achieve the nlgn runtime, we are creating 2 subproblems of size 1 and n-1. The summation of 1 to n is ϴ( n^2 ). Think about the summation of 1 to 10. It is (10 + 1) * (10 / 2) = 55. Replacing 10 with n, (n + 1) * (n/2) = (n^2 )/2 + n/2. Drop coefficients and lower order terms to get n^2.
To solve this problem of ϴ(n^2 ) runtime for a nearly sorted list, we can be smart about how we choose a pivot element. If I run optimize_pivot to choose my pivot point, I find the median value between the values of the low, hi, and med indices in the subarray. I then switch that value with arr[hi] and continue to use hi as my pivot index. If the array is already sorted, I am now using the median value of the list rather than an extreme and can achieve ϴ(n * lgn) runtime on a sorted list because I am back to breaking my problem in halves rather than subtracting one from the size.
Better QuickSort Code

def quicksort_opt!(coll, lo = 0, hi = nil)
    hi = coll.length - 1 if hi.nil?
    if lo < hi
        partition_index = partition_opt(coll, lo, hi)
        quicksort_opt!(coll, lo, partition_index - 1)
        quicksort_opt!(coll, partition_index, hi)
    end
end

def partition_opt(arr, lo, hi)
     optimize_pivot(arr, lo, hi)
     pivot = arr[hi]
     lo -= 1
     hi += 1
     loop do
         loop do
             lo += 1
             break if arr[lo] >= pivot
         end

         loop do
             hi -= 1
             break if arr[hi] <= pivot
         end
         return lo if lo >= hi
         arr[lo], arr[hi] = arr[hi], arr[lo]
     end
end

def optimize_pivot(arr, lo, hi)
    mid = (lo + hi) / 2
    arr[lo], arr[mid] = arr[mid], arr[lo] if arr[mid] < arr[lo]
    arr[lo], arr[hi] = arr[hi], arr[lo] if arr[hi] < arr[lo]
    arr[mid], arr[hi] = arr[hi], arr[mid] if arr[mid] < arr[hi]
end

Here is a second performance metric of all the algorithms including the optimized quicksort

Ruby's native sort (1 million numbers): 1.1003078 s
Merge sort (1 million nums): 2.1523891 s
Quick sort (1 million nums): 3.8681517 s
Quick sort optimized (1 million nums): 3.8711199 s
Ruby sort (mostly sorted 1 million nums): 0.5628704 s
Merge sort (mostly sorted 1 million nums): 1.453362 s
Optimized quicksort (mostly sorted 1 million nums): 2.6978179 s
Insertion sort (mostly sorted 1 million nums): 0.1951487 s

Resources

[1] Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein

Developing Style: Sinatra Security, Decorator Design Pattern

Micah Shute — Tue, 25 Sep 2018 01:32:04 +0000

I intend on documenting all that I learn in these early stages of my programming education for 3 reasons:

If nothing else, to solidify what I learn
Receive negative feedback from those more experienced
Help other beginners through what I write and the feedback I receive.

The most important part to me is item 2 - I am a firm believer that negative feedback is one of if not the most important ingredient to intellectual growth. I have never had a programming mentor, and I don't see the possibility for one in the near future, so I want to make up for the lack of that feedback element as much as I can. So I encourage any experienced developer reading this, if you see something inaccurate or inefficient in what I am writing, please feel free to drop some knowledge bombs on me. In this article specifically, I am open to feedback on security best practices, because that seems like a too-often neglected area, and one in which I have a lot to learn.

That being said, I am writing today on lessons learned from making my first web app, which I did using the Sinatra framework. I will touch on what I learned about implementing proper application security, and then on a Decorator Design Pattern which I utilized in the project.

Security

I was really excited to learn about and try to implement an OOP design pattern, but that wasn't the first area of further study I encountered while making the app. Instead, it was the hurdle of instituting proper security. While this perhpas didn't have the elegance that I was hoping for,

it is an essential tool which is extremely practical and needs to be taken as seriously as any new algorithm or efficient design pattern.

Even in a simple web app, proper authentication and authorization are not trivial. If not taken seriously, you risk exposing your users' information, your app's information, and even compromising your server. [2] Furthermore, you don't develop the skills and the muscle memory which you may need later on to secure a more sensitive application.

So, what steps are necessary for a simple Sinatra App? Well, we have to consider how users are authorized and authenticated. We check their username and password at login against the database. Then we persist a session with cookies. These are the two major areas of vulnerability for our use-case. Fortunately, using ActiveRecord abstracts away guarding against SQL injection at login by using prepared statements (using parameterized queries) OWASP's SQL Injection Cheat Sheet. Sinatra also provides us (almost) all of the tools we need to keep our cookies secure if we take the time to properly use it.

As you may or may not know, cookies are hashes (which are just dictionaries) sent to the user from the server to store on their browser. This is so subsequent HTTP requests from the user to the server can be sent with that cookie, and the server can know information about this user - for example, that they have been previously authenticated (ie, it is used to persist state).

One problem is that cookies which are altered by the user or a third party can cause unexpected, and potentially "bad" things to happen, especially if these changes were done with malicious intent. To help stop "intelligently" transforming cookie data in a specific way to harm the operation of the application, we could encrypt our cookies. That would still potentially allow changing the data, but the person will probably not know how they are changing it. Sinatra does one better by encrypting our cookies by default AND signing them, which encrypts the data AND can tell the server if the data has been tampered with. This is done via the "session_secret".

So, if Sinatra does this, why do we care about doing anything else?

(Note: you can also have your cookies stolen, and then used by a third party pretending they are you even through your own browser - this is something I learned after making the site, and I will discuss it below. Sinatra provides some protection against this by making the cookies HTTP only)

Rack (Sinatra Middleware) signs cookies using HMAC-SHA1 via OpenSSL, using the session_secret and the encoded data in the session. While the HMAC-SHA1 hashing is a one-way process (which means an attacker can't reverse it), it is also a very fast process - which means that an attacker can run it over and over very quickly with different guesses to what your secret word is. They can get your session_secret by running their guess and their cookie data through the same HMAC-SHA1 algorithm and seeing if their output hash equals your cookie hash. If it does, their guess was correct, and now they can fool the server. This is called a dictionary attack. And they don't have to code this process themselves; they can download software made to do this quickly and efficiently. They can also get pre-assembled dictionaries of common passwords and secret phrases. I saw an example where someone cracked a Sinatra app with a session_secret of "super secret" within 45 seconds of a dictionary attack [2]. This is the danger of HMAC-SHA1 being fast - the shorter our string we use, the faster we can get hacked. Sinatra's GitHub page recommends at least a 32-byte session_secret. At one byte per character

"a".bytesize # => 1

we are significantly undershooting that recommendation by using "secret" or "super secret" (which are 6 bytes and 13 bytes respectively).

Also, it should go without saying, that if we make our session_secret available publicly (i.e. put it on GitHub by accident during a commit), no guessing would even have to be done to hack your cookies.

So, what did I do to combat this?

[X] Obtain a random 64-bit hex that won't be in a dictionary. Generate it via the sysrandom gem which creates the hex using the Native OS's method, which is more secure. Copy the output of the code below to obtain a random 64-byte hex string.

ruby -e "require 'sysrandom/securerandom'; puts SecureRandom.hex(64)"

It should be noted that this is a 64 bit hex value, so each character (even though as a string it is 1 byte) represents 4 bits (or half a byte) per character. (Note that 2^4 = 16, which is the number of possible symbols in a single hex character). So the output as a string is actually 128 bytes (ie there are 128 hex symbols).

[X] Save my session_secret 64-byte hex string as an environment variable as recommended by The 12 Factor App along with my API Key, so they don't end up anywhere I don't want them to, I can change them easily, and they are language and OS-agnostic. Retrieve it for your app by saying:

set :session_secret, ENV.fetch('SESSION_SECRET')

(Read more about Environment Variables here)

A few days after making the app, I was reading about Cross-Site Request Forgery, (CSRF). I read that people can use posts on sites that do not properly sanitize user input to cause a user to cause a user's browser to visit a site without the user's knowledge (usually via using an img tag with a src to that site). I know very little about Javascript, AJAX, etc, but this prompted me to learn more about it (which I will be sharing soon). Anyway, I decided to go to my site and do some messing around, and I found that I was able to insert scripts into the site via posting comments. This allows an attacker a whole host of options, from stealing other user's cookies, conducting CSRF attacks on them, or writing over that web page. I decided I was going to pretend to be someone trying to sow discontent among the users of the site (I got all of the query information by inspecting the site in the browser, not from the process of making it):

To fix this problem, I needed to sanitize my input. At first I was going to filter it myself, but the best way is probably to use an established method. So I ended up using the sanitize gem, and now my hacking attempts look like this:

I am dissapointed that I got to the point of making a web app and this very basic concept slipped by me. It should be prerequisite knowledge to anyone designing a web app.

My First Design Pattern - The Decorator

My App:

Let users follow and react to entities with a lot of information being pulled from an API
Allow users to post and react to posts, as well as react to entities within the app.

Complications:

My app will be displaying LOTS of data from the API calls - all of which can change rapidly. So, I don't want to save this in my database, because:
- The information would have to be pulled from the API frequently and overwritten in the database frequently - it would be too much redundant work for it to be useful.
- It is too much information for the size of my free cloud database.
But, I need my database objects for these entities to keep track of what users decide to follow, all posts related to them, likes and dislikes, etc.

Problem To Solve:

I want to access my database relations and all of my API data in one class for each type of object. For example, I want my Entity class to have all of the ActiveRecord::Base functionality, AND have all of my API data available via method calls. But I want to do this without saving extraneous information.

This problem is solvable in some elementary ways. But Design Patterns aren't always used to transform a problem from being un-solvable to solvable - lots of times they are to make a problem's solution elegant, flexible, and easy for us as developers once it's instantiated.

My Answer The Decorator.

Decorator: Attach additional responsibilities to an object dynamically. Decorators define a higher-level interface that makes the subsystem easier to use. [1]

Coming to a decision of what design patterns to use seems to me to be just as hard as implementing them, if not harder - here's a graphical representation of how they interrelate, helping us to decide which one to use in relation to others:

That is a lot to take in for my first time. So this is how I came to my decision.

Design Patterns [1] provides a methodology for choosing a pattern. This methodology includes a list of general problems which you may be trying to solve, and corresponding possible design pattern solutions. Reading this list, I came across Extending functionality by subclassing. I wanted to extend functionality, but I didn't want to subclass. Check.
I compiled the listed possible design pattern solutions:
- Bridge
- Chain of Responsibility
- Composite
- Decorator
- Observer
- Strategy
I analyzed the intents of each, as described in [1]:

Bridge

Decouple an abstraction from its implementation so that the two can vary independently

This wasn't quite right. Neither the API nor the database model was an abstraction of the other.

Chain of Responsibility

Avoid coupling the sender of a request to its receiver by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it.

Not applicable.

Composite

Compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly.

I wasn't working with hierarchical structures. This one wasn't correct for my particular situation.

Observer

Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically

No, because I am not trying to ensure unified actions between connected objects.

Strategy

Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it

I think I could have solved the problem using a Strategy design pattern. I was unsure which one would work best, and I ended up deciding to go with the decorator.

Decorator

Attach additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality.

Sounds about right.

However, I want to add here that my use for a decorator here (even though it worked well for me) is probably not the perfect one. A decorator as a concept is fully utilized when you specifically want dynamic responsibilities allocated (ie they can be given and withdrawn whenever you want) to many individual objects, not whole classes. This prevents this augmentation of functionality affecting other objects. That being said, I do have a plan to refactor to better use the design pattern, and by using it already, it is easier to refactor now.

So first let's do a simple example which explains a 'perfect' scenario for a decorator: imagine I'm buying ice cream. How does a decorator help us?

Set up our Universe:

class PriceError < StandardError
    def initialize(msg="That is not a valid price")
        super
    end
end

class IceCream

    def initialize(price: 1.0)
        @price = price
    end

    def price=(amt)
        raise PriceError if !amt.is_a?(Float)  && !amt.is_a?(Integer)
        @price = amt
    end

    def price
        return @price
    end

    def ingredients
        "Ice Cream"
    end

end

Now, we want to be able to choose the ice cream we want and change ingredients and price accordingly. To do this, we can create Decorator classes.

class WithJimmies
    def initialize(item)
        @item = item
    end

    def price
        @item.price + 0.5
    end

    def ingredients
        @item.ingredients + ", Jimmies"
    end
end

class WithChocolateSyrup
    def initialize(item)
        @item = item
    end

    def price
        @item.price + 0.2
    end

    def ingredients
        @item.ingredients + ", Chocolate Syrup"
    end
end

class WithOreos
    def initialize(item)
        @item = item
    end

    def price
        @item.price + 1.0
    end

    def ingredients
        @item.ingredients + ", Oreos"
    end
end

So now we can make our ice cream!

my_snack = IceCream.new
my_snack = WithJimmies.new(my_snack)
my_snack = WithOreos.new(my_snack)
my_snack.ingredients # => "Ice Cream, Jimmies, Oreos"
my_snack.price # => 2.5

my_friends_snack = IceCream.new
my_friends_snack = WithChocolateSyrup.new(my_friends_snack)
my_friends_snack.ingredients # => "Ice Cream, Chocolate Syrup"
my_friends_snack.price # => 1.2

There's the functionality we want. I start out with just an IceCream class which is a dollar. That's all I want the class to do. I can check out with just an ice cream, without specifying I don't want the other stuff. I can manually change or 'decorate' my ice cream without the original class having to do anything except for it to adhere to the interface of having price and ingredients attributes. My friend can do the same thing with the same class, but choose different options, getting his own personalized outcome.

I can even add other classes into the mix which can be decorated by the same decorators, provided they adhere to the 'interface' requiring them to have a price and ingredients. Other than that, they can be completely different!

class FroYo 
    def initialize(price: 1.5)
        @price = price
    end

    def price
        return @price
    end

    def price_to_s 
        return "$#{'%.2f' % @price}"
    end

    def ingredients
        "Froyo"
    end
end

Now just replace the first line in the last example with my_snack = FroYo.new, and you can have the same output except with froyo instead of ice cream!

"So why can't you just program that functionality in as methods into a superclass and then subclass out the functionality?" Well, you can. But a big goal of the implementation of design patterns in OOP design is to favor object composition over class inheritance Why?

Object composition is also called black-box reuse. It is where we use a bunch of different types of objects to accomplish larger tasks through the way in which they are related to each other at runtime. It's a more modular and flexible way to do things.
Inheritance can arguably be said to "break encapsulation" - changes to the parent class can (unexpectedly) alter the way the child behaves due to unnecessary overlap.
It is easier to re-use compositional patterns than inheritance patterns.
[1] states: "Ideally, you shouldn't have to create new components to achieve reuse. You should be able to get all the functionality you need just by assembling existing components through object composition." It goes on to admit that this is not always feasible, however.
All that being said, inheritance is easy to use and supported by the language, so there is a benefit to using it at times.

While both ways can solve a problem, object composition helps to prevent large, unwieldy superclasses, allows easier dynamic appropriation of responsibilities, and helps us adhere to the single responsibility principle

Now that we have an intuition of what a decorator is, I think it is important to see a formal definition, in the form of a Class Diagram

So, how did I use a decorator?

I wanted a lightweight database, so I only wanted to save an entity's string identifier in the database, which is enough to get all of the information from the API. Furthermore, I didn't want to save EVERY entity identifier in the database, only ones that users were interested in and interacting with. So, I built a decorator, which took as an initialize argument a class with the API's unique identifier as an attribute. This class needed in the Decorator's initialize method could be one of two things: a "Placeholder" class (which I made), or an ActiveRecord instance (both of which were required to have the entity_identifier attribute). The ability to use a Placeholder or an ActiveRecord class was the main reason I chose using a Decorator over a Strategy, because it allowed me to only save into the database entities users were actually interacting with (ie have an interface which allowed me to use an ActiveRecord class an a "throwaway" class). I gave the decorator the ability to retrieve its relationships (if it was an ActiveRecord::Base instance) by mirroring the ActiveRecord methods. For example, I still wanted entity.user_likes to return ActiveRecord user instances. I wanted to be able to create new database relationships and to call .save on the decorator class as if it were an ActiveRecord object. I also wanted any user interaction to cause the entity to be saved into the database if it had not yet been saved while simultaneously replacing the Placeholder object with an actual ActiveRecord object in the Decorator so I could save and retrieve all relationships. So I included methods in the decorator to do this. Some examples:

def entity_identifier
    self.entity.entity_identifier
end

def save
    saved = self.entity.save 
    # note: the EntityPlaceholder #save method returns an ActiveRecord object
    self.entity = saved if self.entity.is_a?(EntityPlaceholder)
    !!saved
end

def following_users
    self.save if self.entity.is_a?(EntityPlaceholder)
    self.entity.following_users
end

I also gave the decorator the ability to retrieve information from the API via an APIManager class. The decorator would populate itself with that extra data upon instantiation.

This pattern will let me extend functionality of my app when I have reprisentations of entities in different parts of my app where I will want to display different attributes, get its information from different API endpoints, and interact with the user differently. Any new functionality I want changed / added can be done so on an ActiveRecord object or a Placeholder object via different decorators.

While maybe not the best use-case for a decorator, or I may have implemented it sloppily, or there may be some design pattern that may have worked better, using this pattern certainly made my code easy to work with, gave me practice searching through and choosing design patterns, and awarded me a better understanding of the decorator design pattern. Next time I have a problem, I will be able to have a new way to potentially tackle it, and I will be able to improve on my concrete implementation of the idea.

References

[1] "Design Patterns Elements of Reusable Object-Oriented Software", Gamma, Helm, Johnson, Vlissides, 1995

[2] One Line of Code that Compromises Your Server

[3] Sinatra GitHub README

[4] SysRandom GitHub README

[5] A Rubyist's Guide to Environment Variables

Understanding the Monty Hall Problem

Micah Shute — Fri, 21 Sep 2018 14:30:11 +0000

This isn't exactly about development or coding, but it is an exercise in problem solving, logic and probability, all of which are fundamentals of our trade. As engineers and programmers, logic and mathematics, particularly probability and induction, are areas in which we should pursue mastery.

I was recently listening to a podcast that was recommended by a blogger on this site, and during one episode discussing big-O theory, the Monty Hall problem was mentioned. The commentators talked a little about it, at which point they admitted to not 'getting it' and moved on. This motivated me to share my understanding of the problem because I think that as engineers we should be the ones who are able to grasp this concept and problems like it.

So here's how I 'got it'. It took some thinking, but in the end, it's actually not too complicated.

In case you are unfamiliar with the problem, the Monty Hall problem is as follows:

You are presented with 3 doors. Behind only one is a prize.

You pick a door which you think the prize may be behind.

After you pick the door, a 3rd party (ie the gameshow host) opens up a door which does NOT have the prize.
You are then given the option to either stay with your initial guess or switch your guess to the door which the game show host did NOT open.

Which should you do? Switch or stay? Does it matter?

The initial intuition for most people is that once you are shown the door with no prize, the possibility is now 50-50 between the two remaining doors, so it doesn't matter if you switch or not. But this is not the case. It is actually probabilistically in your best interest to switch to the other door. But let's be good engineers and follow the scientific process with an initial hypothesis that you have a 50% chance of winning either way.

We have our hypothesis, so let's experiment.

Code:

rand_gen = Random.new
prize_locations = []
switch_wins = 0
stay_wins = 0

#generate winning spots
10000.times do
    # rand_gen.rand(3) returns  0, 1, or 2
    prize_locations << (rand_gen.rand(3) + 1)
end


prize_locations.each do |prize_loc|
    # contestant chooses a random location
    initial_choice = rand_gen.rand(3) + 1
    # monty opens a door without a prize -> init. choice is prize ? (random opening of one of the remaining 2 doors) : (since 1, 2, and 3 must all be an option, 6 minus the other two will always give us the leftover one)
    opened_door = initial_choice ==  prize_loc ? (prize_loc + rand_gen.rand(2)) % 3 + 1 : (6 - initial_choice - prize_loc)
    # Universe split 1: I decide to stay with my choice.
    stay_wins += 1 if prize_loc == initial_choice
    # Universe split 2: I switch 
    switch_wins += 1 if prize_loc == (6 - initial_choice - opened_door)
end

puts "Total wins if you stay: #{stay_wins}, which is #{stay_wins / 10000.0}%"
puts "Total wins if you switch: #{switch_wins}, which is #{switch_wins / 10000.0}%"

Output:

[07:28:18] monty_hall  
//⚓   [⚛ micah] ruby monty_hall.rb  
Total wins if you stay: 3344, which is 0.3344%  
Total wins if you switch: 6656, which is 0.6656%  

[07:28:20] monty_hall  
//⚓   [⚛ micah] ruby monty_hall.rb  
Total wins if you stay: 3316, which is 0.3316%  
Total wins if you switch: 6684, which is 0.6684%  

[07:28:21] monty_hall  
//⚓   [⚛ micah] ruby monty_hall.rb  
Total wins if you stay: 3348, which is 0.3348%  
Total wins if you switch: 6652, which is 0.6652%

Another way you could do it which can give you a litte more info is randomly switch between staying and switching your doors:

Code:

rand_gen = Random.new
prize_locations = []
switch_wins = 0
stay_wins = 0

#generate winning spots
10000.times do
    #rand_gen.rand(3) returns  0, 1, or 2
    prize_locations << (rand_gen.rand(3) + 1)
end


prize_locations.each do |prize_loc|
    #contestant chooses a random location
    initial_choice = rand_gen.rand(3) + 1
    #monty opens a door without a prize -> init. choice is prize ? (random opening of one of the remaining 2 doors) : (since 1,2, and 3 must all be an option, 6 minus the other two will always give us the leftover one)
    opened_door = initial_choice ==  prize_loc ? (prize_loc + rand_gen.rand(2)) % 3 + 1 : (6 - initial_choice - prize_loc)
    #This time, let's just keep one universe and randomly choose
    switch_or_stay = rand_gen.rand(2) # 0 means stay, 1 means switch
    stay_wins += 1 if prize_loc == initial_choice && switch_or_stay == 0
    switch_wins += 1 if prize_loc == (6 - initial_choice - opened_door) && switch_or_stay == 1
end

puts "Total wins from when you stay: #{stay_wins}, which is #{stay_wins / 10000.0}%"
puts "Total wins from when you switch: #{switch_wins}, which is #{switch_wins / 10000.0}%"
puts "Total wins: #{wins = switch_wins + stay_wins}, which is #{wins / 10000.0}%"

Output:

[07:43:07] monty_hall
//⚓   [⚛ micah] ruby monty_hall.rb
Total wins from when you stay: 1685, which is 0.1685%
Total wins from when you switch: 3303, which is 0.3303%
Total wins: 4988, which is 0.4988%

[07:43:08] monty_hall
//⚓   [⚛ micah] ruby monty_hall.rb
Total wins from when you stay: 1689, which is 0.1689%
Total wins from when you switch: 3307, which is 0.3307%
Total wins: 4996, which is 0.4996%

[07:43:09] monty_hall
//⚓   [⚛ micah] ruby monty_hall.rb
Total wins from when you stay: 1662, which is 0.1662%
Total wins from when you switch: 3398, which is 0.3398%
Total wins: 5060, which is 0.506%

Ok, our hypothesis is wrong. Looks like we should probably switch doors. Time to refine my hypothesis and this time rely on more than just naive intuition. (Maybe you saw some new intuition above: that the only way you get a stay_win is if you guessed right initially)

There are a few ways to look at the problem. First, let's look at a split universe timeline:

You have 3 doors and a prize behind one of them. So, for your initial pick, what is the probability that you correctly choose where the prize is?
- That's right - 1/3
Let's freeze time right here and do a little more analysis. There are 2 possibilities that just happened in your choice. So let's split our universe.
- Universe 1: You fell within the 33.3% chance and chose correctly. Now, the game show host can open either of the remain doors, as neither of them has a prize. Now you have ANOTHER CHOICE (another split!)
  - Universe 1.1 You stay with your initial pick. (Human factor, let's say 50%)
    - You win. (100%)
  - Universe 1.2 You switch. (50%)
    - You lose. (100%)
- Universe 2 You initially choose wrong, which happens 66.7% of the time. Now, the game show host can ONLY open the door without the prize behind it (leaving the other door with the prize) SPLIT Universe 2
  - Universe 2.1 You stay with your initial pick. (50%)
    - You lose (100%)
  - Universe 2.2 You switch. (50%)
    - You win. (100%)

Analyzing mathematically: So what's our problem statement? We want to know whether we win more if we switch or stay, right? So let's calculate the probability of winning given that you stay with your initial door, and then the probability of winning given that you switch doors. Note that we are giving the person a random 50% chance that they choose to switch or stay with their original door.

P(win | stay) = [P(win) * P(stay | win)] / P(stay)  

P(win) = (Universe 1 && Universe 1.1) || (Universe 2 && Universe 2.2) =  (1/3) * (1/2) + (2/3) * (1/2) = 1/2    

P(stay | win) = Out of wins possibilities only, what percentage of those did you stay for?  
=  (Universe 1 && Universe 1.1)  / [(Universe 1 && Universre 1.1) || (Universe 2 && Universe 2.2)] = (1/3) * (1/2) / (1/2) = 1/3

P(stay) = (Universe 1 && Universe 1.1) || (Universe 2 && Universe 2.1) = (1/3) * (1/2) + (2/3) * (1/2) = 1/2

P(win | stay) = [1/2 * 1/3] / 1/2 = 1/3

You could also say "Out of the times that I stay, how many times did I win?" That would give you the same answer:

P(win | stay): all wins which lie within stay universes
P(win | stay) = (Universe 1 && Universe 1.1) / [(Universe 1 && Universe 1.1) || (Universe 2 && Universe 2.2)] = (1/3) * (1/2) / [(1/3) * (1/2) + (2/3) * (1/2)] = (1/3) * (1/2) / (1/2) = 1/3
P(win | stay) = 1/3

Now, let's see the probability of winning given you switch. (While Baye's doesn't really buy us anything since we have a short timeline which describes everything for us, I'll do it both ways for the sake of thoroughness).

P(win | switch) =  [P(win) * P(switch | win)] / P(switch)  

P(win) = (Universe 1 && Universe 1.1) || (Universe 2 && Universe 2.2) =  (1/3) * (1/2) + (2/3) * (1/2) = 1/2    

P(switch | win) = Out of wins possibilities only, what percentage of those did you switch for?  
=  (Universe 2 && Universe 2.2)  / [(Universe 1 && Universre 1.1) || (Universe 2 && Universe 2.2)] = (2/3) * (1/2) / (1/2) = 2/3

P(switch) = (Universe 1 && Universe 1.2) || (Universe 2 && Universe 2.2) = (1/3) * (1/2) + (2/3) * (1/2) = 1/2

P(win | switch) = [1/2 * 2/3] / 1/2 = 2/3

Or, you could say:

P(win | switch) : all wins which lie within switch universes
P(win | switch) = (Universe 2 && Universe 2.2) / [(Universe 1 && Universe 1.1) || (Universe 2 && Universe 2.2)]
P(win | switch) = [(2/3) * (1/2)] / [(1/3) * (1/2) + (2/3) * (1/2)] 
P(win | switch) = (2/3) * (1/2) / (1/2) = 2/3

From our mathematical analysis, we can see that you are twice as likely to win if you switch than if you stay. You will also win more (2/3 of the time) if you switch every time than if you randomly choose to switch or stay (in which case you win 1/2 of the time)

Analyzing with logic: If you choose to always switch, you will always be right if you initially chose the wrong door. So, since you initially choose wrong ( 1- 1/3 = ) 66.67% of the time, you will be guaranteed to choose the correct door 66.67% of the time if you always switch. If you choose never to switch, you are guaranteed to be correct only if you initially picked the correct door out of the 3 on your first try, which was a 33.3% chance.

Expanding this problem out to get a better intuition: Sometimes when a problem seems hard to grasp, I like to take the numbers to extremes while maintaining the necessary relationships. In this case, we know that after your choice of 1 door, the host will open all of the doors but one other (even though in our case with 3 doors, this is just him opening one door) AND these doors must have no prize. So, using this relationship, let's expand our situation to 1 million doors with one prize. Now after you choose a door, the game show host has to open all the rest but one. And he can't open the one with the prize. So, unless you think you chose right on your first try with a million to one odds, don't you think this is a pretty good deal, as the host is practically forced to show you where the prize is?! This is the exact same concept, except now our odds for getting the prize when we switch are 999,999/1,000,000 instead of 2/3. It's much easier to have intuition on this concept when it is expanded in this way.

Now, our hypothesis matches our experimental data, and we can call it a day.

Setting up Windows Subsytem for Linux

Micah Shute — Wed, 19 Sep 2018 19:27:15 +0000

I am relatively new in the world of programming, and I have decided to document new concepts and other things that took me a while to figure out - not only to solidify my learning but to help others who may be trying to learn or accomplish the same things.

I set up Windows Subsystem for Linux (WSL) using a conglomerate of different blogs and resources, with varying levels of being out of date. I did not come across one that was recent and had all I needed in it, so hopefully this can serve that purpose for someone.

Setting up Windows Subsystem for Linux for Development

It is no longer necessary to enable developer mode for Windows Subsystem Linux to work

Getting Windows Ready

1) Make sure you are running Windows 10. Windows Subsystem Linux (WSL) is not automatically enabled on windows. So, to start off, we need to enable it!

a) Go to your Windows Search bar and type in turn windows features on or off

b) Click on the result that matches your query. It will be in your Control Panel. You should see something like this:

c) Scroll down until you see "Windows Subsystem for Linux" - ensure its box is checked!

2) Restart your computer

3) Check your Windows 10 version by going to System Information and checking your Version. If your build is earlier than 16215, skip step 4 and proceed to step 5.

4) Open up Microsoft Store. Search for "Ubuntu"

a) Choose "Ubuntu" (I didn't use 16.04 or 18.04 LTS)

5) If you run into errors or if you have an early version of Windows 10, see further information here

6) Open up the Ubuntu app. Follow the prompts, which will include making a username and password. Don't forget your password!

Note: if you get an error at this step that says Windows Subsystem for Linux has no installed distributions. Distributions can be installed by visiting the Windows Store: https://aka.ms/wslstore Press any key to continue..., try manually starting or restarting LxssManager in your Services Desktop App (just search services in your windows search bar). In the L section, you can right-click LxssManager and choose Restart or Start.

Start Outfitting your new Linux Subsystem: RVM / Ruby, git, NodeJS, and Rails

1) Once everything is set up, we can start setting up our system! Start off by running the following to download our dependencies:

sudo apt-get update    
sudo apt-get install git-core curl zlib1g-dev build-essential libssl-dev libreadline-dev libyaml-dev libsqlite3-dev sqlite3 libxml2-dev libxslt1-dev libcurl4-openssl-dev software-properties-common libffi-dev libpq-dev libgdbm-dev libncurses5-dev automake libtool bison gnupg postgresql postgresql-contrib

2) Install RVM by running:

    gpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3 7D2BAF1CF37B13E2069D6956105BD0E739499BDB

followed by

   \curl -sSL https://get.rvm.io | bash -s stable --ruby

and finally

   source ~/.rvm/scripts/rvm

3) Let's install the bundler gem:

    gem install bundler

4) And set up git:

    git config --global color.ui true

For the next few commands, make sure to input your specific information:

    git config --global user.name "your_name"
    git config --global user.email "your_email@example.com"

You can either communicate with your remote repositories via HTTPS or SSH. If you want to use SSH (which means you will not have to authenticate with your GitHub username and password before each push) - follow these instructions.

5) Now let's get NodeJS installed, and then Rails so we can make a bunch of stuff!

First, nodejs:

curl -sL https://deb.nodesource.com/setup_10.x | sudo -E bash -
sudo apt-get install -y nodejs

Next, Ruby on Rails:
```
gem install rails
```

Choose your programming editor: VSCode

You can use any editor you want, but I am going to be walking through setting up VSCode.

1) Download VSCode here. Choose the Windows download, not the Linux download. Any required Linux downloads will be done via the Ubuntu terminal, and everything else should be downloaded for your Windows OS.

2) To configure your Ubuntu terminal to be available in VSCode:

open up VSCode
open the Command Palette via F1 or Ctrl+Shift+p
begin typing the following: Terminal: Select Default Shell until you see it. Select that option.
Once you select it, a few options will pop up. You want to select WSL

3) Now, you can use your Ubuntu terminal in VSCode. Select "New Terminal" in the "Terminal" drop-down, or type Ctrl+Shift+` in order to use it!

4) Additional User Settings:

You can add a few things to your User Settings to customize and improve your programming experience. Most importantly, we can make VSCode treat .erb files like .html files, allowing us to use all the same shortcuts and get the same syntax highlighting.
To open up user settings, again open up the Command Palette using F1 or Ctr+Shift+p and type Preferences: Open Settings (JSON)
You will see a screen like this:
To have your erb files treated like html, add the following to your user settings (circled above):
```
    "emmet.includeLanguages": {
        "erb": "html"
    }
```

Some optional personal preferences that I like:

    "window.zoomLevel": -1,
    "editor.acceptSuggestionOnEnter": false,
    "editor.fontSize": 11,
    "editor.fontFamily": "Hack, Consolas, 'Courier New', monospace",

Note that for the Hack font to be usable, you have to download it. You can check it out here.

Important Knowledge: Basic Use

Your terminal is actually accessing an Ubuntu Virtual Machine which is running inside of your Windows OS. If you ever cd in your terminal, you will be sent to the 'user home' of your Linux VM. That is also the default location you will be in when you open your Ubuntu app. You actually want to do all of your business inside of your normal Windows file space, not your Linux VM file space. So, you will need to know how to navigate in your terminal from your Ubuntu file system to your Windows file system. This is pretty simple if you understand how the system is set up, so let's go over that quickly.

To allow you to access the functionality of a Linux machine, Windows stores the Ubuntu OS and file system inside of its own file system. You should NEVER access your Ubuntu files via your Windows machine. What you SHOULD do is save everything you are working on in your normal Windows file space, and access that via your Ubuntu terminal. So, how do you do that? Well, from the Ubuntu's point of view, it is just a normal Linux machine, but Microsoft has made a pathway between the Linux VM and your Windows OS via the /mnt directory in your Ubuntu's root.

Here is a quick visual of what the first few levels of any Linux file system look like:

As you can see, the mnt directory is made for other filesystems, so that is where Microsoft connected your Linux to your Windows machine:

So, you can get there from your starting point by typing:

cd /mnt/c/users/your_windows_username

cd ../../mnt/c/users/your_windows_username

If you put either of those lines as an alias in your .bashrc file (found in /home/your_linux_username/.bashrc) you can quickly move into your windows home directory (in the example below by just typing home into your terminal):

alias home="cd /mnt/c/users/your_windows_username"

You can easily change your .bashrc file by navigating to your Linux home (by running just cd) and typing:

nano .bashrc

You are going to want to backup your .bashrc file first though so you don't mess it up. You can do that by copying a backup using

cp .bashrc .bashrc.bak

You save a file you have modified in nano by following the directions at the bottom of the screen: click Ctrl+X and then y and then Enter to save your changes.

If you feel uncomfortable with these commands, check out the basic Linux commands link below in the resources.

Remember, put all of your stuff in your windows directories! That way, you have access to it via your Linux Terminal or your Windows OS, and your VSCode editor can open to the correct location when you use

code .

(if you are in your Linux file system, VSCode will open, but not to the right spot).

PostgreSQL Database Setup

Setting up PostgreSQL allows simple production-level database integration into a Rails project. This allows easy hosting on Heroku with only a little setup.

1) First, we want to Download PostgreSQL for Windows - download the Interactive Installer.
2) Once everything is downloaded and installed, you can verify proper operation by typing in your terminal

psql -p 5432 -h localhost -U postgres

once connection is verified, you can quit by typing

\q

3) There are a few ways to do the next few steps but the easiest way is to use pgAdmin. Open up pgAdmin, which is a Graphical User Interface for PostgreSQL.

This should open up pgAdmin in your browser. Start a server by right-clicking "PostgreSQL" and selecting "Connect Server"

Enter the password you defined during the download
Your PostgreSQL server is running, and can now be integrated into your projects.
You also want to set up a new user/role and password that you want to use with your rails app. Ensure you give your user/role all available permissions during setup.
During setup, ensure to fill out Name in the General tab, Password in the Definition tab, and enable all permissions in the Privileges tab.

EXAMPLE: CONNECTING YOUR POSTGRESQL SERVER TO YOUR RAILS APP

Make sure your server is connected and roles are configured as described above.
Make sure you are in a suitable directory (in your Windows file system space) and create a Rails app configured to use PostgreSQL:

rails new my-first-app --database=postgresql
Now, let's configure our database.yml file to allow our app to connect to our database. Add the following to your config/database.yml file under BOTH development: and test: You will need to add a user and password which will correspond to the roles we created in pgAdmin.
```
host: localhost
user: your-postgres-username
password: your-postgres-usernames-password
```
We can now test our database and rails interoperability by first setting up some architecture in our app:
```
rails g scaffold Post title:string body:text
```
now create and migrate a database:
```
rake db:create
rake db:migrate  
```
If these fail, ensure you have added your database.yml configurations under both the development AND test sections
Now, start a server:
```
rails s  
```
If you navigate to localhost:3000 you should see that we are on Rails!

Let's test our database by going to 'localhost:3000/posts'

Now just follow the crud links and try to make a post! We should be seeing our database working great with our rails app!

Hopefully, everything is working for you! Now you're ready to develop using WSL!

Resources

Microsoft Documentation: Windows Subsystem for Linux

Setting up a SSH Key with GitHub

Basic Linux Commands

Forem: Micah Shute

Strategy and Decorator Design Patterns

Why do I use a Decorator or Strategy?

Decorator

Strategy

Intuition

Code Example

Decorators:

Strategies:

References:

Resource Summary for Simple Rails Features

I made my first rails app last week, and here are some resources and strategies I used to make it work

Google Authentication

Authorization Methods, Error Pages

Following Users, Sending Messages, Reacting to Posts, Scope Methods

Following other Users:

Messaging

Reacting to Posts

Advanced ActiveRecord class methods

Setting up Bootstrap

Rendering Markdown

General tips

Divide and Conquer the Fast Fourier Transform

What is the Fourier Transform and why should I care

Why and how does it work

Ok ... so I don't see how I can make a program that does this

How do you compute it

How to compute it well: Divide and Conquer

Show me how you implemented it

Developing Style: Big O, Sorting

Big O

What is it

Why is it important?

How do you use O-notation practically?

Sorting

Why is it important?

How can we do it, with what time complexity?

Disclaimers:

Algorithms

Bubble Sort

Insertion Sort

Merge Sort

Quick Sort

Resources

Developing Style: Sinatra Security, Decorator Design Pattern

Security

My First Design Pattern - The Decorator

Bridge

Chain of Responsibility

Composite

Observer

Strategy

Decorator

References

Understanding the Monty Hall Problem

Setting up Windows Subsytem for Linux

Setting up Windows Subsystem for Linux for Development

Getting Windows Ready

Start Outfitting your new Linux Subsystem: RVM / Ruby, git, NodeJS, and Rails

Choose your programming editor: VSCode

Important Knowledge: Basic Use

PostgreSQL Database Setup

Resources