Four color theorem with Prolog

On this post I’ll talk about the four color theorem and how to solve it using Prolog, this is a very common exercise when you start studying Prolog and you can find a lot of examples on the internet with small maps, this examples can be easily replicated to large maps, on this example I’ll use the map of Brazil that contains 27 federative units.

Four Color Theorem

How many different colors you think are sufficient to color a map considering that you can’t use the same color on two adjacent regions? Let’s imagine that you want to color the world map with this rule, how many pencils do you need? This is already solved and you need only four colors! This is the four color theorem.

“In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet.”

A good curiosity is that four color theorem can only be proved by computers.

Example:

Four color theorem example

Solving

To solve it, as the title of the text describes, we will use Prolog a programming language that applies the logic paradigm of programming, I already wrote about an if you are interested you can check here.

Brazil Map

We will apply this theorem on Brazil map, I chose the Brazil map because, with 27 federative units, it can be considered a large map, but the algorithm that we’ll be used can be replicated to any map.

Brazil Map

Solving the Problem

The first thing that we can do is to transform Brazil map in a graph to see more clearly which states are adjacent.

Brazil States Graph

After this we already know our facts that Prolog need to solve our problem, the first thing that we can do is to choose four colors to paint our map, just declare the facts:

color(black).
color(byzantine).
color(sapphire_blue).
color(screamin_green).

After this the next thing that we can do is to write the rule of two adjacent states, this rule needs to tell Prolog that two states can’t have the same color.

adjacent(State1Color, State2Color) :-
    color(State1Color), color(State2Color),
    State1Color \= State2Color.

Explaining the code: On the first part of the rule we declare that the rule names are adjacent and that it will receive two states as params called State1Color and State2Color, after this, we give a color for states and a rule that these colors can’t be the same.

This rule is simple, it receives two states, give a color to them respecting the rule that colors can’t be the same. With all these steps done we can write all the adjacent states as facts.

We can test our rule on some region of our graph, for this, I chose these regions that in my opinion is a complex region:

Complex region of Brazil graph

Now, just make a query asking for Prolog solve it using or adjacent rule:

?- adjacent(TO, BA), adjacent(TO, GO), adjacent(TO, MT),
   adjacent(BA, GO), adjacent(BA, MG), adjacent(BA, ES),
       adjacent(BA, SE), adjacent(BA, AL), adjacent(BA, PE),
   adjacent(PE, AL), adjacent(AL, SE),
   adjacent(MG, ES), adjacent(MG, GO), adjacent(MG, DF),
   adjacent(GO, DF), adjacent(GO, MT).

And the output result will be:

AL = ES, ES = GO, GO = sapphire_blue,
BA = DF, DF = MT, MT = byzantine,
MG = PE, PE = SE, SE = TO, TO = black

After this, we can paint our graph and conclude that it is correct:

Complex region of Brazil colored with four colors

Ok, now we know that our rule is working as expected, we have two options or we make a query passing all adjacent states (like the one that we did before but all states), or we code a rule and just call this rule as a query. I think that the first option is equal to the previous example, so let’s create a rule to paint the Brazil map, this rule is very simple, it’s only map all adjacent states and put inside a rule:

brazil(AC, AM, PA, RR, RO, AP, MT,
       MA, TO, GO, MS, DF,
       PI, CE, RN, PB, PE, AL,
       SE, BA, ES, MG, RJ,
       SP, PR, SC, RS) :-
    adjacent(AC, AM), adjacent(AC, RO),
    adjacent(AM, RO), adjacent(AM, RR), adjacent(AM, PA),
        adjacent(AM, MT),
    adjacent(PA, RR), adjacent(PA, AP), adjacent(PA, MA),
        adjacent(PA, TO), adjacent(PA, MT),
    adjacent(RO, MT),
    adjacent(MT, TO), adjacent(MT, GO), adjacent(MT, MS),
    adjacent(MA, PI), adjacent(MA, TO),
     adjacent(TO, PI), adjacent(TO, BA), adjacent(TO, GO),
    adjacent(GO, BA), adjacent(GO, MG), adjacent(GO, MS), adjacent(GO, DF),
    adjacent(MS, MG), adjacent(MS, SP), adjacent(MS, PR),
    adjacent(DF, MG),
    adjacent(PI, CE), adjacent(PI, PE), adjacent(PI, BA),
    adjacent(CE, RN), adjacent(CE, PB), adjacent(CE, PE),
    adjacent(RN, PB),
    adjacent(PB, PE),
    adjacent(PE, AL), adjacent(PE, BA),
    adjacent(AL, SE), adjacent(AL, BA),
    adjacent(SE, BA),
    adjacent(BA, MG), adjacent(BA, ES),
    adjacent(ES, MG), adjacent(ES, RJ), adjacent(MG, SP),
    adjacent(MG, RJ), adjacent(MG, SP),
    adjacent(RJ, SP),
    adjacent(SP, PR),
    adjacent(PR, SC),
    adjacent(SC, RS).

This rule only receive 27 federation units, map them as adjacent and will output the colors, now we just need to make a query passing the states on the correct order:

brazil(AC, AM, PA, RR, RO, AP, MT,
       MA, TO, GO, MS, DF,
       PI, CE, RN, PB, PE, AL,
       SE, BA, ES, MG, RJ,
       SP, PR, SC, RS).

And the first result output will be:

AC = AP, AP = BA, BA = CE, CE = DF, DF = MA, MA = MT, MT = RR, RR = SC, SC = SP, SP = black,
AL = GO, GO = PA, PA = PB, PB = PI, PI = PR, PR = RJ, RJ = RO, RO = sapphire_blue,
AM = ES, ES = MS, MS = PE, PE = RN, RN = RS, RS = SE, SE = TO, TO = byzantine,
MG = screamin_green

After some minutes painting our map, I got:

Brazil map colored with four colors

The map is correct and a fun fact about this solution is that only one state needs screamin_green color.

Our experiment is done, but another question can be answered now, how many different solutions it has? We only used the first solution that Prolog has given to us. Fortunately, we have a way to calculate it, just use the predicate aggregate_all/3 and it will count how many results it finds.

?- aggregate_all(count, brazil(AC, AM, PA, RR, RO, AP, MT, MA, TO, GO, MS, DF, PI, CE,
      RN, PB, PE, AL, SE, BA, ES, MG, RJ, SP, PR, SC, RS), Count).

And the result is huge:

Count = 384860160.

three hundred eighty-four million, eight hundred sixty thousand, one hundred sixty of combinations found.

And finally, we finished our experiment.

Conclusion

As I said in my last post about logic programming here, Prolog is worth learning, and for solving this kind of problem it shines but you’ll need to expend a lot of time giving the facts (as we did with adjacent states).

Final thought

If you have any question that I can help you, please ask! Send an email (otaviopvaladares@gmail.com), pm me on my Twitter or comment on this post!

Follow my blog to get notified every new post:

Demystifying Linked Lists / Complete tutorial/implementation with TDD

This text is not recommended for

  • People who have solid knowledge of Data Structures and Linked Lists
  • People who don’t know ruby and object oriented programming basics

What I’ll explain on this post

  • What is Linked Lists
  • What is Dubly Linked Lists
  • How to make our Linked List Gem
  • Benchmarking

Code

All the code written with this post you can find here

Introduction

On this post I’ll start a serie of posts talking about data structures implementations using Ruby. Some years ago I studied Data Structures but coding each one in C, I think C is a good language to learn because of pointers and struct, but implement in Object Oriented Language like Ruby is good for learn new concepts, plus I’ll use TDD to train and learn more about MiniTest (Because on my day/job I always use Rspec).

What is Linked List?

Linked List is the simplest data structure in my opinion, it consist in set of information/data linked by pointer/link to the next data, the object/struct that stores the data if often called Node/Item.

Linked List

On this image we can see a list of nodes storing values linked by next_node arrow.

But on this tutorial we’ll study doubly linked list that we’ll see below.

Doubly Linked List

Doubly Linked List is the same as Liked List, the unique major difference is that doubly have one pointer to the next node and one to the previous.

DoublY Linked List

Now we have all the information that we need to start coding.

Appplication’s Architeture

Doubly linked list is a simple data structures project, we’ll create a gem that implements it. We’ll have two core classes, linked_list and Node.

Developing

Creating a Gem

On this tutorial we’ll build our linked list in a gem like application, that’s why with gem we can easily build and use the list just including gem in our IRB/Pry session.

So, first we need to create our application, for this just use the command:

bundle gem linked_list

After this, bundler will ask if we want to generate test with our gem, and if yes what gem we prefer, Rspec or Minitest, as I talked above on this tutorial we’ll use Minitest so just write minitest and press enter. Next all that ruby ask, you can say yes and everything will be ok.

After all steps you’ll see ruby creating our gem first files.

      create  linked_list/Gemfile
      create  linked_list/lib/linked_list.rb
      create  linked_list/lib/linked_list/version.rb
      create  linked_list/linked_list.gemspec
      create  linked_list/Rakefile
      create  linked_list/README.md
      create  linked_list/bin/console
      create  linked_list/bin/setup
      create  linked_list/.gitignore
      create  linked_list/.travis.yml
      create  linked_list/test/test_helper.rb
      create  linked_list/test/linked_list_test.rb
      create  linked_list/LICENSE.txt
      create  linked_list/CODE_OF_CONDUCT.md

On this tutorial I’ll not exaplain the basic of a gem architeture, if you’re courius about this project structure go and search for yourself but it’s not really necessary if you know object oriented programming basics

After this, you have a linked_list directory created, now if you try to run any command to your gem, like rake test, it won’t run. Why? Because you will get the fallowing error:

Please fix this gemspec. (Gem::InvalidSpecificationException)
The validation error was '"FIXME" or "TODO" is not a description'

If you already created a gem before you know what it is, is only the rubygems telling you that our description is not completed at file linked_list/linked_list.gemspec. Now let’s fix quickly this.. Open this file and replace the summary and description at line 12 and 13 for anything you want.

  spec.summary       = %q{Linked List}
  spec.description   = %q{Just another one linked list gem that I've coded for study}

But now if you run your tests with rake test, it will not pass yet, because rubygems generates a fail test on our linked_list/test/linked_list_test.rb, if you run test you’ll get the fallowing error:

LinkedListTest#test_it_does_something_useful [/home/otavio/Documents/blog/linked_list/test/linked_list_test.rb:9]:
Expected false to be truthy.

So, open this file and remove the fallowing test:

  def test_it_does_something_useful
    assert false
  end

After this, everything is ok, just run rake test and everything is ok for we start coding.

Creating Node Class

Now that we have our gem created, let’s create our first class, this class we’ll be our node class.

First of all let’s start with test, creating our test and writing the basic structure of a minitest test.

test/node_test.rb

# frozen_string_literal: true

require "minitest/autorun"

class NodeTest < Minitest::Test
end

Now, where to start? I like to start creating a test to assert that we can create our Node class.

  def test_creating_node
    node = Node.new()

    assert_instance_of Node, node
  end

Now if you run this test rake test you’ll get the fallowing error:

  1) Error:
NodeTest#test_creating_node:
NameError: uninitialized constant NodeTest::Node

This error is telling that Ruby didn’t find Node class, to fix this let’s create our class and run test again.

lib/node.rb

# frozen_string_literal: true

class Node
end

And don’t forget to add require "node" at linked_list.rb to don’t get errors when trying to using our gem

Now yoour test should pass right? No, if you try to run your test you’ll get the same error:

  1) Error:
NodeTest#test_creating_node:
NameError: uninitialized constant NodeTest::Node

But you know why? Because we missed to require our node class in our NodeTest, some people aren’t used to require class in Ruby because Rails does it automatically, but pure Ruby no. So go to our NodeTest class and require our Node class:

lib/node.rb

require "node"

Run again your tests, finally we’ll get our test passing.

Now we need to create tests to assert that our class have attributes and can store and returning each one. (If you are familiar with languages like java, this test is to assert our getters/setters).

Let’s create a test to assert that our node are storing and returning its attribute value.

  def test_node_value
    value = 10
    node = Node.new(value: value)

    assert_equal node.value, value
  end

Run tests again, you’ll get the fallowing error telling that we sent one value to the node constructor and it was expecting 0.

  1) Error:
NodeTest#test_node_value:
ArgumentError: wrong number of arguments (given 1, expected 0)

But.. Why is our linked list expecting 0? Because we don’t have a constructor yet, let’s do this.

lib/node.rb

  attr_reader :value

  def initialize(value: nil)
    @value = value
  end

Dont forget to add the attr_reader do make getter method

If you run again your test it will pass, with this class now we have a node storing a value, if we build and install our gem now with rake install we’ll see the fallowing response:

linked_list 0.1.0 built to pkg/linked_list-0.1.0.gem.
linked_list (0.1.0) installed.

Now our gem are builded and installed on our system and we can open our IRB and do the fallowing commands:

require "linked_list"

Node.new(value: 12)
Node.new(value: 10)
Node.new(value: 05)

And we’re creating nodes, but this nodes isn’t linked between each other, they’re just in our memory storing values.

Nodes not linked

Now we need to create our links between each node, this links will be our next node and previous node, as you already know, let’s start with test.

  def test_next_node
    node2 = Node.new(value: 13, next_node: nil)
    node = Node.new(value: 12, next_node: node2)

    assert_equal node.next_node, node2
  end

  def test_previous_node
    node2 = Node.new(value: 13, previous_node: nil)
    node = Node.new(value: 12, previous_node: node2)

    assert_equal node.previous_node, node2
  end

I gave myself the freedom os write both tests because each one is very similar

Now just run your test and see the error:

1) Error:
NodeTest#test_next_node:
ArgumentError: unknown keyword: next_node

 2) Error:
NodeTest#test_previous_node:
ArgumentError: unknown keyword: previous_node

Now, like the error is telling, we need to add next_node and previous_node to our node constructor, and attr_accessor for each one. (We need attr_accessor on each one because we’ll need to set these previous and next nodes)

class Node
  attr_reader :value
  attr_accessor :previous_node, :next_node

  def initialize(value: nil, previous_node: nil, next_node: nil)
    @value = value
    @previous_node = previous_node
    @next_node = next_node
  end
end

Our tests are passing now, to test our nodes with previous and next node, just run again "rake install" to install our builded gem and run IRB requiring "linked_list":

2.4.1 :001 > require "linked_list"
 => true
2.4.1 :002 > node1 = Node.new(value: 12)
 => #<Node:0x00561c467f07c0 @value=12, @previous_node=nil, @next_node=nil>
2.4.1 :003 > node2 = Node.new(value: 10)
 => #<Node:0x00561c467dd1c0 @value=10, @previous_node=nil, @next_node=nil>

Now if we imagine, we’ll have something like this:

Two unlinked nodes

Now with our previous_node and next_node we can link each node forming two interconnected nodes.

2.4.1 :004 > node1.next_node = node2
 => #<Node:0x00561c467dd1c0 @value=10, @previous_node=nil, @next_node=nil>
2.4.1 :005 > node2.previous_node = node1
 => #<Node:0x00561c467f07c0 @value=12, @previous_node=nil, @next_node=#<Node:0x00561c467dd1c0 @value=10, @previous_node=#<Node:0x00561c467f07c0 ...>, @next_node=nil>>

Now if we run node2.previous_node ruby will return node1 and if we run node1.next_node ruby will return node2.

Two linked nodes

We’ve finished our Node logic, now we need to start working on List logic.

Creating LinkedList Class

Follow my blog to get notified every new post:

We created all Node logic and we’ve free way to start creating all list logic, but you can ask me, what’s logic?

  • First Node, a method called .first_node to return the first node of the list.
  • Last Node, a method called .last_node to return the last node of the list.
  • Add Nodes, for this logic I want that our list have a method called .add().
  • Remove last node, create a .pop method, similar to Array#pop from Ruby.
  • Remove first node, create a .shift method, similar to Array#shift from Ruby.
  • Add first node, method called .unshift, similar again to Array#unshift.
  • Print our list, I want a method that I can call with .print method and receive a graphical output on my terminal of my list.

So let’s start defining our head of list (first node)

First Node of the List

Starting from the beginning, we need to store the first node of our list in a var of our LinkedList class, I’ll name this variable head because this will be the "head" of our list.

Starting from the test, let’s create a test that assert that we’re storing the head of the node when creating our list.

Create file test/list_test.rb

# frozen_string_literal: true

require "minitest/autorun"
require "node"

class ListTest < Minitest::Test
  def test_list_head
    node = Node.new(value: 123)
    list = List.new(head: node)

    assert_equal list.head, node
  end

  def test_list_head_setter
    node = Node.new(value: 123)
    list = List.new
    list.head = node

    assert_equal list.head, node
  end
end

Running our test now, we’ll get the fallowing errors:

  1) Error:
ListTest#test_list_head:
NameError: uninitialized constant ListTest::List

This error is simple, is telling that we don’t have a class named List, to fix this just create List class.

lib/list.rb

# frozen_string_literal: true

class List
end

Dont forget to require "list" at our lib/linked_list.rb

Running our tests again:

  1) Error:
ListTest#test_list_head:
ArgumentError: wrong number of arguments (given 1, expected 0)

As we already know, this error is telling that we don’t have a constructor on our class, so let’s create it and test will pass.

Note the use of attr_accessor, with this, the user don’t need to pass the node when creating list, and can write list.head = node, satisfying the second test.

class List
  attr_accessor :head

  def initialize(head: nil)
    @head = head
  end
end

Now running our test, everything will pass, if you want you can install our gem and test this, everything will be working.

Adding Node

Check my last posts:

We need to create a .add() method as I had described before… Starting from the test, what we need to test? I think a good point to start is asserting that we are calling the .add(value) method and we’re adding the new node at the end of the list (pointing the previous las node of th e list to this new last_node), and remember that if list is empty when we add node, this node will be the head node, on this test we’ve a lot of context but we’re not working with rspec so, we will write a lot of test.

Starting from the beginning, we need to assert that inserting a node in a empty list, this node will be the head.

Pay attention that this method will receive a value, not a node.

  def test_add_node_on_empty_list
    list = List.new
    list.add(12)

    assert_equal list.head.value, 12
  end

Now, we need to create the .add(value) method in the list and asserting that if list is blank, the head needs to be the node created from the passed value, this will be easy, is just check if head is nil, if is nil, create a node with value and stores at head.

  def add(value)
    self.head = Node.new(value: value) if head.nil?
  end

Running our test, it will pass but we need to add nodes when our list is not empty.. and how to do that? First we need to pass between each node until find the last node (to find the last node would just check if next_node is nil), and when we find the last node we add the new node after it. Creating a method to return the last node it will look like this:

  def last_node
    last_node = head

    until last_node.next_node.nil?
      last_node = last_node.next_node
    end

    item
  end

In a graphic view:

Searching last node algorithm

But, what’s problem with that method of find the last node? It’s that this method we’re passing between each node, and this is a O(N) algorithm (Don’t know what I’m talking about? Read my post when I tech Big O with simple approach here), ok O(N) isn’t a big problem with this example in image of four nodes but with a lot of nodes in our list, but with something like thousands of nodes it will be a problem.

To solve this problem, we have a good solution in this case, it’s to create a last_node and everytime that we add a new node, we store it at last_node of the list, with this, when we add a new node, we check the current last_node of the list and stores the new node after this and set last_node of the list again, with this simple solution we will not have problems adding new nodes for any size of list. On this post we’ll follow this approach.

Starting from the beginning..

Note that we’ll name last node of the list as tail.

Creating the test and the method for the tail. (I’ll skip some steps here because is the same as head).

  def test_list_tail
    node = Node.new(value: 123)
    list = List.new(tail: node)

    assert_equal list.tail, node
  end

  def test_list_tail_setter
    node = Node.new(value: 123)
    list = List.new
    list.tail = node

    assert_equal list.tail, node
  end

And the code:

  attr_accessor :head, :tail

  def initialize(head: nil, tail: nil)
    @head = head
    @tail = tail
  end

Backing to our add method, let’s create the test.

  def test_add_node
    list = List.new

    for number in 1..10 do
      list.add(number)
    end

    list.add(99)

    assert_equal list.tail.value, 99
  end

Running this test, obviusly it will fail, and now we need to complete our .add method, at this point we need to store the tail of our list. We have two context, one when list only have one node, this node will be the head and the tail of our list, and the second context when list have more than one node and we need to change the tail to the new node.

I’ll comment the fallowing code to be more clean on my explanation, but please, don’t make your code with comments like these.

  def add(value)
    new_node = Node.new(value: value) # Creating our Node

    # Checking if is the first Node of the list
    self.head = new_node if head.nil?
    self.tail = new_node if tail.nil?

    # Making the new node the tail of the list

    # The previous node of the new node is the current tail
    new_node.previous_node = self.tail

    # The next node of the current tail is the new node
    self.tail.next_node = new_node

    self.tail = new_node # Set new node as tail
  end

Note that we created the new_node to have the same node in all parts.

Adding new node

Run your test again and everything will be working, you can install your gem (as we done previously) and test if you want.

.pop method

Ok, the most difficult part already gone, now we need to create simple methods to interact with our list, starting from .pop method. As I described at the beginning of chapter:

  • Remove last node, create a .pop method, similar to Array#pop from Ruby.

This method is very similar to .add but we’ll remove the last node, in Ruby we’ve a garbage collector so everything we need to do is to set de previous_node of tail as new list tail and set his next_node to nil.

Implementing this in languages that doesn’t have garbage collector like C you’ll need to free the node that you’re removing.

Removing Node

Starting from Test, it just need to assert that after .pop the new tail is the expected.

  def test_list_pop
    list = List.new

    for number in 1..10 do
      list.add(number)
    end

    list.pop

    assert_equal list.tail.value, 9
  end

Obviusly it will fail because we don’t have the method, creating the method, we need that this method picks the previous_node of current list tail and sets it as new tail, after that point his next_node to nil, pretty simple isn’t it?

Again I’ll use comments but I repeat is just for learning purpose.

  def pop
    old_tail = self.tail # Saving the old tail

    # Picking the previous node of the old_tail to be the new tail
    self.tail = old_tail.previous_node
    # Pointing the new tail to nil
    self.tail.next_node = nil

    # Setting the previous_node of old_tail to nil to completely isolate it
    old_tail.previous_node = nil
  end

Note that on the last line of the method I set old_tail.previous_node = nil to completely isolate it from the rest of the list, facilitating for garbage collector of ruby eliminate it.

Run our test again and everything will pass, signaling that our .pop is complete.

.shift method

This method will be very similar to .pop but as I’ve described we’ll remove the head of the list.

  • Remove first node, create a .shift method, similar to Array#shift from Ruby.

Everything we need to do is to set the next_node of the current head to be the new head!

Removing Head

Test:

Just need to assert that after .shift the new head is the expected.

 def test_list_shift
    list = List.new

    for number in 1..10 do
      list.add(number)
    end

    list.shift

    assert_equal list.head.value, 2
  end

Now to make this test pass we need to create the .shift method. It is simple, is the same thing as the .shift just reversing the sides, look:

def shift
    old_head = self.head # Saving the old head

    # Picking the next node of the old_head to be the new head
    self.head = old_head.next_node

     # Pointing the new head previous_node to nil
    self.head.previous_node = nil

    # As I explained above, it's for garbage collector
    old_head.next_node = nil
  end

Everything is the same, if you understand one, automatically you understand another.

Run your test now and everything will pass.

.unshift method

As I described, now we’ve to create the .unshift method.

  • Add first node, method called .unshift, similar again to Array#unshift.

This method is very similar to .shift, but instead of move the head we’ll add a new head on the list.

How we do that? It’s simple, we create the node that will be the new head and point his next_node to the old head, sets old head previous node to the new node and after this set list head as the new node, pretty simple.

This test will be very simple, is just assert that after .unshift(value) our list head is this value.

  def test_list_unshift
    list = List.new

    list.add(10)
    list.add(20)
    list.add(30)
    list.add(50)

    list.unshift(5)

    assert_equal list.head.value, 5
  end

Running tests, obviusly it will fail because we don’t have .unshift() method created. Creating our method, it will be very similar, if you understand .shift and .pop you will easily understand this.

  def unshift(value)
    new_head = Node.new(value: value)

    old_head = self.head

    old_head.previous_node = new_head
    new_head.next_node = old_head

    self.head = new_head
  end

If you run your test it will pass and if you want you can install your gem and test it by using.

Note I’m not installing gem and testing each time we create a method because I’ll test everything on the final of post, feel comfortable to install and test if you want.

Printing our List

As I described in the beginning of the chapter.

  • Print our list, I want a method that I can call with .print method and receive a graphical output on my terminal of my list.

This will be very funny and useful, it will help us use our list more easy and understand what is happening when working with the list.

At this method we have a lot of solutions and print designs possible, but for this test I’ll use a very simple design, I want that when we call list.print the output looks like this:

12 <-> 23 <-> 45 <-> 12 <-> 56

Just each node pointing to the next/previous by an arrow.

Starting from the test, we need to create a test that assert the output of `.print` with a string of the expected output.

  def test_list_print
    list = List.new

    list.add(10)
    list.add(20)
    list.add(30)
    list.add(50)

    assert_equal list.print, "10 <-> 20 <-> 30 <-> 50"
  end

Pay attention that on head we dont have previous arrow, and at the tail we dont have next arrow.

Running our test and failing it, we need to create our method, for this method we’ve a lot of ways of create this, one simple way that I think is good is to stores every node value at one array and after that join the array with <-> and it will pass, the code will looks like this:

  def print
    node = self.head
    output = []

    until node.nil?
      output << node.value

      node = node.next_node
    end

    output.join(" <-> ")
  end

This solution is very simple, we pass between each array, stores and after this, joins with arrows. If you run your test it will pass.

This solution is good and simple, I know that for this problem we’ve a lot of solutions and I’ll love to learn more, if you have another idea, please comment, but for this post we’ll continue with this.

Another option is to include Enumerable module and pass between each node printing the arrows.

Bonus Methods

Implementing a .each method, and after this including Enumerable module, we can have access to all power of Enumerable provide to us, it includes .each, .map, .select and much more.

Don’t know what I’m talking about? I’ve made a post/tutorial explaining it, check out here.

Related Posts

Add include Enumerable at the beginning of our class, and implement it each method.

A nice test will be assert that our list is a kind_of? Enumerable

  def test_list_each
    list = List.new

    assert_kind_of Enumerable, list
  end

And the method..

  def each
    node = self.head

    until node.nil?
      yield node
      node = node.next_node
    end
  end

Manual Testing our Linked List

Ok, now everything we need to do is test, we already have .print method, so test, will be very funny.

Installing our gem with rake install and opening our IRB and requiring our gem with require "linked_list" we can start playing with our project.

2.4.1 :001 > require "linked_list"
 => true

And if we create our list, I should have nil head and tail.

2.4.1 :002 > l = List.new
 => #<List:0x005556db27b708 @head=nil, @tail=nil>
2.4.1 :003 > l.head
 => nil
2.4.1 :004 > l.tail
 => nil

And now if we add something it should be the head and tail of our node.

2.4.1 :005 > l.add(23)
# ...
2.4.1 :006 > l.head.value
 => 23
2.4.1 :007 > l.tail.value
 => 23

Fine, is working as expected, now let’s add a lot of nodes on our list.

2.4.1 :008 > l.add(324)
2.4.1 :009 > l.add(10)
2.4.1 :010 > l.add(15)
2.4.1 :011 > l.add(20)
2.4.1 :012 > l.add(100)

Now we have 6 nodes on our list, and this is perfect to test our print method.

2.4.1 :013 > l.print
 => "23 <-> 324 <-> 10 <-> 15 <-> 20 <-> 100"

Ok, print is working, now we need to test .pop, .shift, .unshift() and our bonus methods (Enumerable).

Testing on that order:

2.4.1 :014 > l.pop
 => nil
2.4.1 :015 > l.print
 => "23 <-> 324 <-> 10 <-> 15 <-> 20"
2.4.1 :016 > l.shift
 => nil
2.4.1 :017 > l.print
 => "324 <-> 10 <-> 15 <-> 20"
2.4.1 :018 > l.unshift(10000)
# ...
2.4.1 :019 > l.print
 => "10000 <-> 324 <-> 10 <-> 15 <-> 20"

# Testing Enumerable

2.4.1 :020 > l.each do |node|
2.4.1 :021 >   puts node.value
2.4.1 :022?> end
10000
324
10
15
20

We finished our tests, feel comfortable to test anything you want.

Finishing

Now we got our list finished and working and I hope that you have learned a lot with this post. I love to implement data structures because I think that we can learn a lot doing these simple exercises, In the next post I’ll talk about ordered datasets and sorting and search algorithms and I think it will be very fun. (depending on when you are reading this, probably I already wrote that post, you can check here)

Remembering, that the code of this is list you can find on my github here

And if you have any question please ask anywhere, you can comment this post, PM me on twitter or send me an email (otaviopvaladares@gmail.com), I’ll love it!

Don’t forget to follow me on my twitter

Have a great studies!

Follow my blog to get notified every new post:

Understanding the basic of Big O notation

Big O notation is a famous topic in computer science, but this topic still afraid of a lot of people. Some programmers don’t have a complete cs degree and never studied this, and those who have studied almost always didn’t understand very well.

In this text I will explain what really is Big O, and what you really need to know.

I’ll explain all the basics of Big O notation with examples written in Ruby.

This is not a complete guide of Big O notation if you want to know everything about, at the end of this post I give north of where to continue your study.

Introducing

This text is not recommended for:

  • People who have solid knowledge of Big O notation.
  • People who want to know advanced topics of Big O

What I’ll explain on this post:

  • What is Big O
  • The most common notations
  • Simple examples
  • Simple Benchmarks

First of all, what is Big O notation?

Big O notation is the language and metric we use when talking about growth rates and the efficiency of algorithms. It can be used to describe the behavior of an algorithm in terms of the growth in the number of operations as the number of elements processed increases, with this technique we can evaluate how our code will behave with a lot of data or operations.

If you want a long explanation you can read the big o article on Wikipedia here.

Why is it important? I’ll never use it.

A lot of methods or data structures of every programming language are described using Big O, like binary search that in Ruby can be called Array#bsearch.

First of all, if you always work with small sizes of data and operations, maybe you’ll never use it. But it’s good to understand the basic concepts of algorithms, because it can help you to make better design decisions and construct better algorithms.

Nowadays on the big data century, tons of data and operations are reality. You’ll probably need to design an algorithm thinking on his time or space complexity.

Nowadays on the big data century, tons of data and operations are reality. You’ll probably need to design an algorithm thinking on his time or space complexity.

It’s better to know because a lot of methods of your favorite programming language have different times, with Big O you can understand better the performance of each one.

And remember, a lot of big tech companies like Google, Facebook and Amazon asks for big o answers on their interview process, this is very common that is discussed on the legendary book Cracking the Code Interview.

Understanding

Visualizing the complexity

On Big O notation we have a lot of possibilities of notations, and we don’t have a fixed list of runtimes but the most common is:

Notation Short Description Denomination
O(1) The best solution possible Constant
O(log n) Almost good, binary search is the most famous algorith O(log n) Logarithmic
O(N) When you walk through each data. "ok" solution Linear
O(n log n) Not bad solution. Most famous algorithm is Merge Sort. nlogn
O(N^2) Horrible, you can see the example bellow Quadratic
O(2^n) Horrible, most famous algorithm is quicksort Exponential
O(N!) The most horrible solution, factorial is when you test each possible solution Factorial

Time or Space?

We can use Big O to describe both time or space, but what it means? Simple, one algorithm that uses O(N) runtime, will use O(N) space too, but it’s not that easy, some algorithms can be O(N) in time complexity but O(N^2) in space.

Time for What?

Data structures or algorithms can have multiple Big O times for multiple actions, for example An Array has O(1) time to access, but O(n) to search (depending on which algorithm you use), all depends on the scope of our code.

Big O, Big Omega, Big Theta?

On this text I’ll not talk about Big Omega and Big Theta because of two reasons:

  • This is a simple guide and I don’t want to dive into deep concepts of computer science.

  • The industry tends to use Big O notation.

Hands On!

Check my last posts:

Presenting our problem

On your life you never thought that some actions of your day spend a lot of time to be done, and you can make simple actions to reduce the time spent? Let’s use a simple example, dictionary(physical edittion, not google), how much time do you need to find a word? Depend of the way you search.

“The Second Edition of the 20-volume Oxford English Dictionary contains full entries for 171,476 words in current use and 47,156 obsolete words. To this may be added around 9,500 derivative words included as subentries.”

This is a lot of data right? Let’s imagine that we’re building an algorithm to search for a word.

Code

For learning purpose on all examples I’ll use an array of numbers not strings.

Let’s create the array that I’ll use on all the next examples. This array will be our dictionary, but instead of words(strings), we’ll use numbers. The word “zoo”, will be the last word of our dictionary and will be represented as number 1000000. As you can see below:

dictionary = []

0.upto(1000000) do |number|
  dictionary << number
end

Now, we have an array with one million numbers. Let’s assume that this array of numbers is our dictionary and the 1000000 on the last slot it’s our word “zoo”.

First Solution O(N)

Considering that this dicionary is in alphabetical order, how much time you’ll spend to find the word “zoo” (our 1000000) if you go through each word?

Yes, to find “zoo” you’ll spend a lot of time because you’ll need to go through all the words. These scenarios when we walk through each data, on Big O notation we call O(n), because our algorithm will take N times to find the word, where N is the number of words. Let’s see the code.

Code

Now let’s assume that we’re going though each word until we find the word.

def o_n(dictionary)
  dictionary.each do |word|
    word if word == 1000000
  end
end

o_n(dictionary)

This is a very common and as I described previously, is not a bad solution, but not good to. In terms of difficulty to understand is not hard too, a lot of algorithm O(n) we have iterators on lists.

Second Solution O(1)

Let’s assume that now you already knows what is the location of word zoo on dictionary, every time that you need to search for it you only need to open the dictionary on the page and just read. You don’t need to find for the word, you already knows its location.

Code

O(1) is a algorithm that is idependent of the input size it will always take the same time to execute, the time is constant. The best example of it, it’s access an array:

def o_one(dictionary)
  dictionary[1000000]
end

o_one(dictionary)

O(1) is always the best solution, and you probably use it every day, the most commond usage of it is with Hashes.

I think everybody here knows, but Ruby already have Hash implemented.

hash = {
  color: "red"
}

hash[:color]

# => "red"

Third Solution O(log n)

Follow my blog to get notified every new post:

Some people have a lot of difficult to understand the concept of O(log N) algorithm, but I hope that this example with dictionary can help you undersand:

Let’s assume that you don’t know where the word is located, but you know that if you search each word O(N) will spend a lot of time, and you don’t know where the word is located, what will you do? You could start opening the dictionary on a random page and search if the words of this page come before or after the word that you’re looking for if is after you open on another page after this page, and look again… and repeat it until you find the word that you’re searching for.

If you already studied algorithms you probably noted that I described one of the most famous algorithms of all time, the binary search and that is the most famous example of O(log n) algorithm.

Let’s see the code.

Code

For this example, I’ll use a simple binary_search implementation (Not recursive).

def binary_search(dictionary, number)
  length = dictionary.length - 1
  low = 0

  while low <= length
    mid = (low + length) / 2

    return dictionary[mid] if dictionary[mid] == number

    if dictionary[mid] < number
      low = mid + 1
    else
      length = mid - 1
    end
  end

  "Number/Word not found"
end

puts binary_search(dictionary, 1000000)

To identify an algorithm that is O(log n) you can follow two simple steps:

  • The choice of the next element on which to perform some action is one of several possibilities, and only one will need to be chosen.
  • The elements on which the action is performed are digits of n

You can check more here

Binary search is a perfect exemple of this steps because each time it cut by the half the remaining options.

Like many languages Ruby already have binary search built-in as array methods as Array#bsearch as you can see below:

array = [1,2,3,4,5,6,7,8,9,10]

array.bsearch {|x| x >= 9 }

# => 9

You can read more here

If you think that it’s not enough at you can find better references at the given links, I’ll not explain a lot of maths because it’s a text for beginners.

Fourth Solution O(N^2)

Imagine that you’re searching word by word like on O(N) but for some reason you need to make your search again, this is the O(N^2). This example applied to our history of the dictionary is hard to understand but with code is more easily.

The trick is basically to think that O(N^2) is when we pass through N, N times, so we’ll have N*N that is O(N^2), the most common example is a loop inside a loop.

Code

def o_n2(dictionary)
  dictionary.each do |word|
    dictionary.each do |word2|
      word if word == 1000000
    end
  end
end

o_n2(dictionary)

Don’t worry, this is a very common case too, almost every person already has done something like that, especially when we’re starting to code that we use the famous quicksort that is a nice example of O(N^2), but this code won’t have a good performance for large data. The best way is think if you can reduce this algorithm to O(log n), some times an O(N^2) can be reduced to O(log n).

Fifth Solution O(n log n)

This is the most hard definition for me, and I admit that I spend hours searching on internet because the definitions that I’ve found didn’t satisfy me (And don’t have much answers on internet).

The simplest explanation that I’ve found is:

O(n log n) is basically you running N times an action that costs O(log n).

O(n log n) is basically you running N times an action that costs O(log n).

This is obvious but, makes sense. Let’s examine:

In the binary tree, inserting one node (in a balanced tree) is O(log n) time. Inserting a list of N elements into that tree will be O(n log n) time.

O(n log n) code can be often the result of an otimization of quadratic algorithm. The most famous example of this type is the merge sort algorithm.

For this definition won’t have short history, I definitely didn’t think in anything that makes sense on our history with dictionary.

If you think that this is not enough at references you find links to better understand, I’ll not explain a lot of maths because it’s a text for beginners.

Sixth Solution O(2^N)

Exponencial runtime, this is a very hard definition, like O(n log n). This type of problem is when the number of instructions growth exponentially, it’s common to found it on recursive algorithms, or some search algorithms.

"When you have a recursive function that makes multiple calls, the run time will be O(2^n)"

If you search on internet you’ll probably see a lot of people talking that Fibonacci recursive solution is a good example:

def fibonacci(number)
  return number if number <= 1

  fibonacci(number - 2) + fibonacci(number - 1)
end

puts fibonacci(10)

For find a O(2^N) you can start following one simple rules:

  • O(2^N) denotes an algorithm whose growth doubles with each additon to the input data set. (Exponential growth)

For this definition won’t have short history, too, sorry guys.

Seventh Solution O(N!)

The factorial solution, is very horrible. But I think there’s no example in our history of finding words in dictionary, and I don’t want to dive inside a lot of math in this beginners guide.

O(N!) is every time that you calculate all permutation of a given array of size N.

The most common example of this notation is that solving salesman problem via brute-force(testing every solution possible). (A lot of sites such as wikpedia uses this example).

Code

In Ruby we have a method that returns all permutations of a given array.

array = [1,2,3]

array.permutation(3).to_a

# => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

This is actually O(N!)

Some Benchmarking

Let’s examine some benchmark of algorithms of each example and compare, for better understanding and understand that Big O really exists.

On this section I’ll use the same implementations of algorithms from previus chapter but using Ruby Benchmarking module to compare the execution times.

4.1 O(1) vs O(N)

For this example we’ll use the same dictionary array created on previus chapter with one million of data.

0.upto(1000000) do |number|
  dictionary << number
end

So if we run the algorithms created in th above chapter:

Benchmark.bm { |bench| bench.report("o(1)") { o_one(dictionary) } }
Benchmark.bm { |bench| bench.report("o(n)") { o_n(dictionary) } }

#       user     system      total        real
# o(1)  0.000000   0.000000   0.000000 (  0.000005)
#       user     system      total        real
# o(n)  0.060000   0.000000   0.060000 (  0.052239)

A very low difference, and that’s is why O(N) on the graph of complexity is not very bad, with one million of data he just needed 0.052239s, but and if we growth your dataset to almost 15 million, the O(N) solution will be good? Let’s see:

#       user     system      total        real
# o(1)  0.000000   0.000000   0.000000 (  0.000004)
#       user     system      total        real
# o(n)  0.750000   0.000000   0.750000 (  0.741515)

The time of O(N) solution increased 12.5x more than the array of one million while the O(1) solution stay constant at ~0.000004s, and that’s is very wrong if we’re talking about scalable systems on the big data century.

O(N) vs O(N^2)

First of all, let’s create again an array but this time with lil bit less data:

data = []

0.upto(20000) do |number|
  data << number
end

Yes, twenty thousand is good enought to this example, because O(N^2) is very bad, and if you growth you data, you’ll problaby get 100% cpu usage on Ruby process and it will be killed by OS.

Let’s examine the runtime of previus O(N) and O(N^2) algorithms of our dictionary example using benchmark module and the data array created:

Benchmark.bm { |bench| bench.report("o(n)") { o_n(data) } }
Benchmark.bm { |bench| bench.report("o(n^2)") { o_n2(data) } }

#       user     system      total        real
# o(n)  0.010000   0.000000   0.010000 (  0.000963)
#       user     system      total        real
# o(n^2) 19.550000   0.000000  19.550000 ( 19.560149)

Obviusly that this number will vary

This difference is pretty high, and that is where Big O came. Remember, on Big O we’re talking about the "behavior of an algorithm in terms of the growth in the number of operations as the number of elements" as I talked on previus chapter.

Ok, twenty thousand of data is pretty high from some people, and if we try an array of five thousand, is it enought?

       user     system      total        real
o(n)  0.000000   0.000000   0.000000 (  0.000252)
       user     system      total        real
o(n^2)  1.330000   0.000000   1.330000 (  1.329480)

If you’re thinking: “The difference is so much smaller, I don’t need to optimize this code.”

You’re pretty wrong depending of your situation, because if we get the difference between an execution of each algorithm we have 1.329228s of difference, and it can be an eternity for your costumer if you consider that your client wait for 1.329228s three times each day, we’re stealing 27.9s per week of your costumer, and we’re only working with five thousands of data, I’m sure that a lot of people work with a lot of more.

So, in this case of an O(n^2) I pretty recomend that you try to reduce this for an O(n log n)

O(N!)

This is a nice test because if we use one million of numbers the algorithm will take more than 10 hours to execute on my machine, and if I use five thousand of data (like on the previous example) it will take a nice time too, so to show the O(N!) in action I’ll need to use only 500 numbers.

On this example I’ll use the Array#permutation, method of Ruby.

dictionary = []

0.upto(500) do |number|
  dictionary << number
end

Benchmark.bm { |bench| bench.report("o(!n)") { dictionary.permutation(3).to_a } }

And the final output is weird:

#       user     system      total        real
# o(!n) 25.530000   1.650000  27.180000 ( 28.155015)

28.1s with 500 numbers.

Finishing

I’ll not benchmark all algorithms and data structures, but I pretty recommend that you study and test others one. Specially the O(log n)

What’s Next?

If you want to be a rockstar at *Big O* just keep studying, reading a lot.

You can read:

This last books, have one chapter 100% dedicated to Big O notation, and I pretty recommend for those who wants to study more deep.

You can fallow the reference links bellow and study by yourself.

Final thoughts

It was a very long post, and I know it, but I think that a good understand of the big o principles is important for a lot of software engineers, to the daily work or for coding interviews.

If you have any question that I can help you, please ask! Send an email (otaviopvaladares@gmail.com), pm me on my Twitter or comment on this post!

Reference