Printing a Multiplication Table of the First 10 Prime Numbers

Ok, for a change of pace let’s break away from sorting algorithms and do this problem:

Printing a Multiplication Table of the First 10 Prime Numbers

Code Here

I got this as a coding challenge a few days ago and finally got a chance to tackle it this weekend. The prompt asks for the user to create a program that runs on the command line, and it should print out a multiplication table to STDOUT. I feel like I’ve seen similar problems elsewhere, but this one had the twist that it wanted the multiplier numbers to be primes.

Other rules: Make it flexible for N # primes, write some tests, don’t use Ruby’s Prime class, package yer code.

I started out this challenge by trying to understand clearly what the problem was. Print out a multiplication table? Like this?

039827b

Oooooooooooooh. Haven’t seen one of those in a long time.

So the top row and the first column would be populated with primes. Hmm…

Since I couldn’t use Ruby’s Prime class from the standard library, writing a method for finding primes seemed like the first thing to do.

def is_prime?(num)
divisors_array = []
(1..num).each do |n|
if num % n == 0
divisors_array << num
end
end
divisors_array.length > 2 ? false:true
end

I wanted to make my program flexible so you could create multiplication tables of different sizes. So I created a method to pull the first n primes into an array.

def pull_primes(num)
primes_array = []
counter = 2
until primes_array.size == num
if is_prime?(counter)
primes_array << counter
end
counter += 1
end
primes_array
end

And finally actually printing out the actual table! Formatting was the biggest pain here.

def print_table(num)
rows = pull_primes(num) #array
columns = rows
print " "
columns.each {|column_num| print " %-3d " % column_num}
print "\n\n"
rows.each do |row_num|
print "%-3d| " % row_num
columns.each {|column_num| print " %-3d " % (column_num * row_num)}
print "\n\n"
end

After I was done with these methods, I thought I was good to go. HA! Nope, still got to package it up and write some tests. I was going back and forth, but I’ll talk about the tests first.

I decided to go with RSpec, so I created a gemfile and added in the requirement. Then I created some spec docs and started going to town. I really only had 3 methods to test, and I decided to do 2 tests for each. It’s been a while since I watched ThoughtBot’s TDD lecture, and my subscription to their site has lapsed, so I decided to keep it as simple as possible. An RSpec tutorial I was reading was referencing a “Calculator” class in its tests, so I thought “Oh, I might as well bundle up the 3 methods into a MultiplicationTable class.” So I went back and changed that, and my tests.

All of the tests were pretty simple except for the print_tables one. Again, it all came down to formatting. I wasn’t sure how to check what was being printed to STDOUT. I came across stringio and some helper methods on StackOverflow, threw them into my spec_helper, and then it was on. I could capture and check what was being printed to the console. Still, it was tricky to figure out what string I was looking for here. RSpec failure messages came to the rescue as I just copied the extremely ugly failure string  (making sure #’s were correct) and pasted into my tests.

describe MultiplicationTable do
before do
@multiplication_table = MultiplicationTable.new
end
describe "#is_prime?" do
context 'testing the number 5' do
it "returns true" do
expect(@multiplication_table.is_prime?(5)).to eql(true)
end
end
context 'testing the number 10' do
it "returns false" do
expect(@multiplication_table.is_prime?(10)).to eql(false)
end
end
end
describe "#pull_primes" do
context 'testing with num = 10' do
it 'size is 10' do
expect(@multiplication_table.pull_primes(10).size == 10)
end
end
context 'testing with num = 2' do
it 'size is 2' do
expect(@multiplication_table.pull_primes(2).size == 2)
end
end
end
describe "#print_table" do
context 'testing with num = 4' do
it 'prints a 4 x 4 table' do
printed = capture_stdout do
@multiplication_table.print_table(4)
end
printed.should eq(" 2 3 5 7 \n\n2 | 4 6 10 14 \n\n3 | 6 9 15 21 \n\n5 | 10 15 25 35 \n\n7 | 14 21 35 49 \n\n")
end
end
context 'testing with num = 2' do
it 'prints a 2 x 2 table' do
printed = capture_stdout do
@multiplication_table.print_table(2)
end
printed.should eq(" 2 3 \n\n2 | 4 6 \n\n3 | 6 9 \n\n")
end
end
end
end

Hooray! My tests were looking for the right things now. Nevermind that when I ran the tests I got this little deprecation warning:

screen-shot-2016-10-16-at-2-16-45-am

Um… ok. Sure I can go back and change that easily. Nope, getting errors after I tried to fix it. I’ll go back and deal with it later.

I started out thinking about how to package my program. My mind wandered to gems, which of course made me think about my NPR Stories Gem. I looked at my gem to check out the basic structure, see what I was still missing in my multiplication table project. Then I got sidetracked for about 30 minutes trying to push my NPR gem to RubyGems. I hadn’t yet actually published my NPR gem for a variety of different failures, but this time I realized one major reason- I had to actually build the gem first with:

gem build npr_stories.gemspec

then I could push it to RubyGems. D’oh. That was embarrassing. Now that it was published, and robots were already scraping it, I wanted to make sure that it worked, so I spent some more time trying to edit and test my NPR gem, then I remembered that I had to finish this coding challenge. Right. And of course there was a typo in my gemspec file. Not worth doing a whole gem update for a single letter typo.

Ok, back to multiplication tables! So I could package this multiplication table as a gem for easy installation…But is it even worth it? If so, I should have set this up as a gem to begin with so I could have used this bundler command that pulls together all those files and folder structure for you:

$ bundle gem my_gem

I decided to do it anyways and created a new repo to play with. I just copied over my tiny amount of code thus far.

15 minutes later I abandoned ship and returned to my original repo. Creating a gem just didn’t make sense to me for something so small. Hmmmm… how did I want this to run on the command line? I created a bin folder & executable, and also a CLI class with a simple interface.

#!/usr/bin/env ruby
require "bundler/setup"
require "./lib/multiplication_table"
require "./lib/cli"
CLI.new.call

class CLI
def call
choice = nil
until choice == 'N'
puts "Let's Multiply!!!"
@multiplication_table = MultiplicationTable.new
puts "Enter an integer for table size"
table_size = gets.strip.to_i
@multiplication_table.print_table(table_size)
puts "Run again? Y or N?"
choice = gets.strip.upcase
end
puts "Now exiting. Thanks!"
end
end

And after a few hiccups it’s working!

screen-shot-2016-10-16-at-2-15-21-am

The last step I had was to write a README doc. Whew! That was a lot of work for such a simple little ask. It would have gone faster if I hadn’t indulged my little diversions to other projects and down multiple rabbit holes.

Algorithms: Insertion Sort

I wanted to make Insertion Sort part of a two-fer with Selection Sort, but it honestly took me a minute to figure out how to implement.

Continuing the card game analogy of earlier, if Selection Sort is scanning your hand and moving the smallest items down to the left, eventually ending up with a fully sorted hand…

Insertion Sort is like when a dealer gives you a new card. You look over what you’ve got so far, and add the card to its rightful spot. Similar to Selection Sort, Insertion Sort also operates on the idea of a “sorted” section and  an “unsorted” section.

When an item (let’s call it A) is larger than the element to its immediate left (B), the two aren’t swapped like in Bubble Sort. Instead, you hold on to A’s value, and then reassign B’s value to the spot array[A]. So it’s like you are sliding B’s value down the line. Then you compare A with the item in the index to the left again (C). If A > C, you can then put A down in array[B]’s original spot. Otherwise, you need to keep working to the left and shifting over elements until you find the right spot for A. When you finally assign A to its spot, you’re done with inserting A. Then you repeat the process with the next item in the “unsorted” section.

I had some issues wrapping my head around how to move items down the line, making room for the array, initially thinking about a recursive solution, but really all I needed was a while loop.

def insertion_sort(arr) # [3, 5, 2, 1]
# loops through to the next to last item in the array
# Building up the sorted section
for i in (0...arr.length)
temp = arr[i]
pointer = i
# Moves items on down to make space for the item
while (pointer > 0 && temp < arr[pointer - 1])
arr[pointer] = arr[pointer - 1]
pointer -= 1
end
# Put the item in its correct spot in the sorted section
arr[pointer] = temp
end
arr
end

 

Algorithms: Selection Sort

I’m still working my way through implementing the basic sorting algorithms in Ruby, so maybe I should just make this a special “Intro Sorting Week.” There, sounds like a fun holiday, right? Today we’re talking selection sort.

Selection Sort

Selection sort is where you scan the array, pick the smallest element, and then swap it with the first element. Then you scan the rest of the array again, look for the next smallest element, and then swap it with the second element… Y’all see where I’m going with this?

It creates a sorted subarray on the left, and an unsorted subarray on the right. You work your way through smaller and smaller subarrays until the entire array is sorted. The algorithm is called selection sort because it repeatedly SELECTs the next smallest element and swaps it into place.

A common example of real life selection sort is when you’re playing cards and you are organizing your hand. You look over your hand, and SELECT a card and move it to its rightful place on the left (creating a sorted section), and continue working through until your hand is sorted. To me this isn’t the greatest example, because you’re not necessarily swapping the items when you select and sort a minimum card. It’s more like the cards are individually going both left and right, and often you can move multiple cards at a time. But that’s just me and how I organize my cards… back to Selection Sort.

The good: Selection sort is easy to understand. It’s also faster than bubble sort, but given how awful BS is (ever notice that bubble sort is BS?) that’s not much of an accomplishment. Selection sort is also in place, so it saves you space.

Downsides: This sorting algorithm takes a long long time. O(n^2) even in its best case. Ouch! Also it’s important to note that it’s not stable.

Here’s my selection sort done with two for loops:

def selection_sort(array)
n = array.length
for first_num in 0...n
min_value = first_num
for following_num in (first_num + 1)...n
if array[following_num] < array[min_value]
array[following_num], array[min_value] = array[min_value], array[following_num]
end
end
end
array
end

Algorithms: Bubble Sort

Bubble sort! I stumbled across this clip while looking for video algorithm explanations.

Wow, even Obama knows what’s up. Bubble sort ain’t where it’s at.

The idea behind bubble sort is that given an array, you can go through the array, item by item, and compare each item with the item that is next in line. If the first item is larger (or comes after) the second item, then you should swap the pair. Continue these pair comparisons until you get to the end and then repeat. After enough times running through the array, you will come to the point where the array is sorted, and you’ll find that you’ve made no swaps.

There are some advantages to bubble sort. It’s easy to understand how it works. It uses up a constant amount of auxiliary space, it’s stable, and in the best case scenario, when the array is already sorted, it takes linear time.

Alas, bubble sort is mostly impractical. In application, bubble sort can take O(n^2). Not great.

Here’s my implementation of bubble sort in ruby. It’s really all about that swap flag.

** EDIT : After some thinking, I realized that during each iteration there is no need to check the items at the end since the largest item will “bubble up” to the top. The subarray that you are looping through will get smaller & smaller. This can be accomplished by iterating backwards over the array and decreasing the area searched, but I haven’t added this yet. Surprisingly, Bubble Sort could be a little less terrible.

# Time Complexity: O(n^2)
# Auxiliary Space Complexity: O(1)
def bubble_sort(array)
n = array.length
loop do
swap = false
(n - 1).times do |num| # don't have to bother checking the last item in the array
if array[num] > array[num + 1]
array[num], array[num + 1] = array[num + 1], array[num] # swap
swap = true # trigger the flag
end
end
# sorting is done after it's made it through a pass and didn't need to swap
break if swap == false
end
# return the final sorted array
array
end

Algorithms: Binary Search, Revisted

A while back I walked through the basic idea of binary search. Knowing what binary search is, and implementing it however, are very very different things.

I’ve been taking a technical interviewing course, in order to add some sort of method to the madness of my job hunt. Pretty much every day we’re whiteboarding and mock interviewing. Last night I received the following question while I stood at the whiteboard:

Number of Ones
Given a sorted bit array (values of 0, and 1) determine the number of 1’s in the array.

Input: Array of elements with values belong to the set S : { 0, 1 }
Output: Integer
Example
Input: [0, 0, 0, 1, 1, 1] => Output: 3
Input: [0, 0, 0, 0] => Output: 0

Constraints
Time Complexity: O(log n) A linear search is not acceptable for runtime.
Auxiliary Space Complexity: O(1)

So, the naive solution here would be to iterate over the entire array, and keep count of how many ones we encounter (or just use Ruby’s built in count method…). But of course to check every item in the array that would be time of O(n). Linear search runtime isn’t acceptable!!!

Several things made my mind jump to binary search. First off, the array is sorted. Second, the very obvious time complexity of O(log n). And also the entire array is binary. Isn’t that cute.

But just because you know what to do doesn’t mean that it will be easy. I decided in my approach to have a “middle_index” that I was moving around throughout the array, but I forgot to implement a start_index and an end_index to keep track of my new subarrays. GAH!!! I kept trying to make only middle_index work until I ran out of time. When I was told about the additional markers, it felt so so obvious to me, and so much simpler. In fact, when I was walking through my diagram of the problem on a test array, my hands were the natural bounds of the start_index and the end_index. It just didn’t register.

Anyways, today I went back and finished up my ruby method for this problem. I almost forgot to account for the two cases that might drive me into an infinite loop: an array of all 0’s or all 1’s. I think it will take me several more runs of this, but hopefully someday implementing binary search will be fast and breezy.

# Number of Ones
# Given a sorted bit array (values of 0, and 1) determine the number of 1’s in the array.
# Input: Array of elements with values belong to the set S : { 0, 1 }
# Output: Integer
# Example
# Input: [0, 0, 0, 1, 1, 1] => Output: 3
# Input: [0, 0, 0, 0] => Output: 0
# Constraints
# Time Complexity: O(logN) A linear search is not acceptable for runtime.
# Auxiliary Space Complexity: O(1)
# Naive solution: Going through the entire array and keeping count of ones ,
# or [0, 0, 0, 1, 1, 1].count(1) , but that's linear runtime
# Other option: Implement binary search here
def number_of_ones(input_array)
start_index = 0
end_index = input_array.length - 1 # 5
middle_index = ((end_index - start_index)/ 2).round
until input_array[middle_index] == 1 && input_array[middle_index - 1] == 0
if middle_index == 0 && input_array[middle_index] == 1
return input_array.length
elsif middle_index == input_array.length - 1
return "There are no ones here"
elsif input_array[middle_index] == 0
start_index = middle_index + 1 # from 0 to 4
elsif input_array[middle_index] == 1 && input_array[middle_index -1] == 1
end_index = middle_index -1
end
middle_index = ((end_index + start_index)/ 2).round
end
return input_array.length - (middle_index) # 3
end

And here’s my general Ruby implementation of Binary Search.

# Array is sorted
def binary_search(array, search_item)
start_index = 0
end_index = array.length - 1
middle_index = (end_index + start_index)/2
return "#{search_item} ain't here" if !array.include?(search_item)
while array[middle_index] != search_item
if array[middle_index] < search_item
start_index = middle_index + 1
middle_index = (end_index + start_index)/2
elsif array[middle_index] > search_item
end_index = middle_index - 1
middle_index = (end_index + start_index)/2
end
end
return "#{search_item} is at index #{middle_index}."
end

Scroll To Top