Forem: Alejandro Bezdjian

Add changes to previous git commits

Alejandro Bezdjian — Wed, 28 Dec 2022 15:25:27 +0000

When we are developing, it is always recommended to commit our changes often and in logical units. For example, in a web application, we might need to add some field in the database and let the user change that field in a form. Using an MVC framework the steps would look like:

Add a migration that adds the field in the database
Add the field in the model
Pass the user input from the controller to the service that creates/updates the model
Add the input in the form

A common git practice would be to create commits for:

Adding the migration
Change the model, controller and service
Modify the form

Now, a very common scenario is that when we are changing the form we find out there was a bug in the service, or we want to change the field name to something more meaningful, or that we forgot to add the field in the model, etc. So how do we add those changes to previously committed files without removing our commits?

I'm going to show you 2 ways you can do this depending on how many commits behind you want to put those changes.

Put your changes in the last commit

This is the simplest case, and you can use the following command that you may already know:

git add ...files

git commit --amend --no-edit

The --no-edit flag will skip the step where you can edit the commit message, if you don't pass this flag git will show you a text editor.

Put changes in older commits

This is the more complex case and we are going to need the commit's hash we want to change. Following the previous MVC example, running git log returns something like this:

commit cc8a75f6753d07afaf0ece2b1a4eb26fbbfb3ec6 (HEAD -> main)

    Changed form

commit fa4f42bd629de581b48024465f90e61bf71734ae

    Changes in backend

commit 94b3af6d73d1c17518785a15a5e26c1ec3ce36fd

    Added migration

Let's say that we want to change the field name in the database, so out target commit is the one we added the migration (94b3af6d73d1c17518785a15a5e26c1ec3ce36fd). To do this you can run:

git add migration_file
git commit --fixup=94b3af6d73d1c17518785a15a5e26c1ec3ce36fd
git rebase --interactive --autosquash 94b3af6d73d1c17518785a15a5e26c1ec3ce36fd^

The git commit --fixup=HASH will create a commit with the same message as the mentioned commit with a prepended fixup!.
Then the git rebase --interactive --autosquash HASH^ will automatically change the rebase message for you putting the fixup commit in the correct place (if the commit hash is correct and you used ^ at the end) and changing the word edit to fixup. After saving the message git will perform the desired changes.

Another way to make changes in older commits

The previous way is a simplified version of a more complex process that you can do:

git stash
git rebase -i HEAD~3

Mark the commit you want to change by replacing edit with pick

git stash pop
git add ...files
git commit --amend --no-edit
git rebase --continue

In this case we stash our changes, then perform an interactive rebase. When changing edit to pick you are telling git to stop the rebase in that commit so you can add all the changes that you want. After doing the changes (in this case by doing a stash pop) you ammend the changes into the commit that you picked and then continue the rebase process.

Very important

The 3 methods mentioned will change the hash of the modified commit and ALL it's children! This is very important because if a colleague is working on the same branch or if there are branches coming out of any of those commits you will find a lot of conflicts and commit dupications.

Let's discuss: programming as you get older

Alejandro Bezdjian — Thu, 07 Jan 2021 17:35:04 +0000

The other day I came across this interesting article about "old coders", that made me reflect a lot.

There is a very famous estimation which says that every 5 years the number of programmers double. Another way of putting it is that every 5 years, half of the programmers have less than 5 years of experience. I still have like 35-40 years until I retire (if laws stay the same)...

Let's do a little bit of math: I'm already in the 50% with 5 or more years of experience, so (assuming that the estimation is correct and that I want to work as a programmer until I retire) in 35 years I'll be part of the 0.39% oldest programmers. Which also means that I will have to compete against the rest of the 99.61% of the programmers for a job. That is a pretty scary number.

It looks like programmers fight this by transitioning into management oriented positions even though most of engineers I know don't like managing people.

What are your thoughts about this?

Memory efficient file streaming from AWS S3

Alejandro Bezdjian — Thu, 03 Dec 2020 16:31:09 +0000

In my previous post I talked about how you could efficiently stream database rows for processing. This time I want to talk about how you can implement the same to process lines in a file. I am going to use the same principles here, so I recommend you to read that post.

If you have to process large files, you don't want to load them completely in memory because you can run out of memory. Knowing how to efficiently read a file is an essential skill in any programming language and even though I am going to show you code in Ruby, I hope you can transfer the ideas of this post into your favourite programming language.

This post already covers very well the subject of file streaming in Ruby, so, in order to make it more interesting I am going to show you how you can stream a file stored in AWS S3 line by line without downloading it completely. Of course, for most cases, it's probably a better idea to download the whole file and then process it, but let's assume that there is a limit on the amount of disk you can use, or that you don't want to wait until the whole file is downloaded to process it.

The title of the post lies a little bit, because we are going to download the file, but the idea is to download small pieces of it and discard them after processing. So the first thing we should know is how to download a piece of file from S3, fortunately we can do that using URI parameters according to their documentation. I will not make the requests by hand, instead I'll use the official S3 gem. The AWS documentation specifies that the range of the file must respect the RFC 2616 specification, so if we want to get the first 100 bytes of a file we have to do something like:

require 'aws-sdk-s3'

def build_range(range_start, range_end)
  "bytes=#{range_start}-#{range_end}"
end

object = Aws::S3::Resource.new.bucket('some-bucket').object('some-file')
object.get(range: build_range(0, 100)).body.read

Great! With this we can have a buffer in memory that stores the downloaded bytes and work with that. Before going into the implementation, let's consider the possible situations we can run into and think what we should do:

We download a slice of the file that contains a new line character: we just return the first part of the buffer and keep the rest.
The downloaded bytes do not have a new line character: we have to keep downloading until we get a new line character or we reach the end of the file.
Reached the end of the file: we return the remaining bytes of the buffer.

Now that we have an idea of what to do I'll show you my implementation:

class RemoteFileIterator
  include Enumerable

  KILOBYTE = 1024
  MEGABYTE = 1024 * KILOBYTE

  def initialize(file_name, new_line_character: "\n", batch_size: MEGABYTE, bucket:)
    @object = Aws::S3::Resource.new.bucket(bucket).object(file_name)
    @content_length = @object.content_length
    @new_line_character = new_line_character
    @batch_size = batch_size
    reset_cursors!
  end

  def each
    if block_given?
      while (line = read_buffer_or_fetch!)
        yield line
      end
      reset_cursors!
    else
      to_enum(:each)
    end
  end

  private

  def reset_cursors!
    @cursor = 0
    @buffer = nil
  end

  def read_buffer_or_fetch!
    if buffer_has_new_line_character?
      take_line_from_buffer!
    elsif @cursor < @content_length
      @buffer = (@buffer || '') + @object.get(range: build_range!).body.read
      read_buffer_or_fetch!
    end
  end

  def buffer_has_new_line_character?
    !buffers_new_line_character_idx.nil?
  end

  def buffers_new_line_character_idx
    @buffer&.index(@new_line_character)
  end

  def take_line_from_buffer!
    new_line_character_idx = buffers_new_line_character_idx
    line = @buffer[0..(new_line_character_idx - @new_line_character.size)]
    @buffer = @buffer[(new_line_character_idx + @new_line_character.size)..-1]
    @buffer = nil if @buffer.empty? # Doing str[str.size..-1] returns ''
    line
  end

  def build_range!
    range_start = @cursor
    range_end = @cursor + @batch_size - 1
    @cursor = range_end > @content_length ? @content_length : (range_end + 1)
    "bytes=#{range_start}-#{range_end}"
  end
end

As you can see it is very similar to the class in my previous post (I won't explain the Enumerable tricks in this post again). The build_range! method is pretty much the same as the one I showed you in the beginning of this post, but it also keeps track of the cursor.

In the take_line_from_buffer! method we first find the position of the first new line character and then we split the buffer in two parts, returning the first one and keeping the last one in the buffer.

The read_buffer_or_fetch! method recursively fetches data until we find a new line or we downloaded all the file. There is another way of writing this without checking if cursor < content_length:

  def each
    ...
    while (line = next_line!)
      yield line
    end
    ...
  end

  def next_line!
    read_buffer_or_fetch
  rescue Aws::S3::Errors::InvalidRange => _e
    # Since we don't check if we ask for bytes outside the length
    # we can take advantage of the exception thrown by the AWS gem
    final_line = @buffer
    @buffer = nil
    final_line
  end

  def read_buffer_or_fetch
    if buffer_has_new_line_character?
      take_line_from_buffer!
    else # Removed the condition
      ...
    end
  end

Both implementations work but I prefer to avoid using exceptions for control flow because I consider that an anti-pattern.

As a final thougth, it's worth noting that if you use this implementation with a file that does not have a new line character you will end up downloading the whole file in memory (which is what we wanted to avoid). For those cases you should consider other techniques that are outside of the scope of this post.

Conclusions

Even though this might not be a great idea for regular files (since it makes several requests to download), this might be useful in specific use cases, for example if you have no disk space (or very little) or if the files you have to work with are very large and the download takes too much time (or fails) while your processing workers are idle in the meantime.

Re-Wheel series part 1 - How does Rails' find_each work?

Alejandro Bezdjian — Tue, 24 Nov 2020 19:10:09 +0000

Over the years I found that in order to learn something I have to understand it. For software concepts, this means that sometimes I write code that has already been written, and probably much better. This is usually referred to "reinventing the wheel", which is something that I don't recommend when writing code professionally, but since it's a very good learning exercise I decided to create a series of posts in which I'll try to dissect some interesting and commonly used techniques to help you understand them and thus, learn.

For the first post of my Re-Wheel series I wanted to talk about ActiveRecord's find_each. This method lets you process database records in batches, which reduces the memory consumption of your app and increases the amount of queries you make (one for each batch). You have to think about memory consumption on every project (not only Rails ones), so you can port this idea to whatever language or framework you are using.

Let's say you have 1 million users and you want to print all their emails on the screen, you could do something like User.all.each { |user| puts user.email } but this will load all the records in memory (which is not good). The equivalent and memory efficient way to do it is: User.all.find_each { |user| puts user.email }.

But how is this implemented? Well, if you use pagination in your index methods with gems like pagy, kaminari or will_paginate you will find that the same idea is happening here, they are using the power of SQL's LIMIT and OFFSET to fetch only a portion of the data each time. So in the 1 million users example, find_each will perform 1000 thousand queries with a limit of 1000 while changing the offset properly so we don't miss any record.

There is another cool thing about the find_each method. As you can see, it receives a block which is executed with each row, making use of the powerful Ruby's enumerable module.

There is a small limitation in this method, it doesn't work with the pluck method. Since we are doing this to reduce the memory footprint, selecting only the required columns from the table is a reasonable thing to do, so let's add that feature in our implementation.

I'll show you the code I wrote and then explain each part:

class DatabaseStream
  include Enumerable

  DEFAULT_BATCH_SIZE = 1000

  def initialize(sql, options = {})
    @sql = sql
    @pluck = options[:pluck]
    @batch_size = options[:batch_size] || DEFAULT_BATCH_SIZE
    reset_cursors!
  end

  def each
    if block_given?
      while (row = read_from_buffer_or_fetch)
        yield row
      end
      reset_cursors!
    else
      to_enum(:each)
    end
  end

  private

  def reset_cursors!
    @gobal_cursor = 0
    @buffer_cursor = @batch_size
    @buffer = []
  end

  def read_from_buffer_or_fetch
    fetch_data if @buffer_cursor == @batch_size

    row = @buffer[@buffer_cursor]
    return nil unless row

    @gobal_cursor += 1
    @buffer_cursor += 1
    row
  end

  def fetch_data
    @buffer = @sql.limit(@batch_size).offset(@gobal_cursor)
    @buffer = @buffer.pluck(@pluck) if @pluck.present?
    @buffer_cursor = 0
  end
end

To test this code you can run:

query = User.all
stream = DatabaseStream.new(query)
stream.each { |user| puts user.email }

stream = DatabaseStream.new(query, batch_size: 100, pluck: 'id, email') # pluck: %i[id, email] also works
stream.each { |user| puts user[1] } # pluck returns an array

The main idea is to have 2 pointers, one for the current element in the batch and one for the overall position (used for the offset). The fetch_data method performs the query setting the limit and offset and selecting the columns if the pluck parameter was given. The result is then stored inside a buffer in memory and sets the cursor to point the first element on it.

When creating the instance, I set @buffer_cursor = @batch_size and then in the read_from_buffer_or_fetch method I check for this condition before making the query. This allows me to lazy initialize the object, to perform the query only when it's really needed. There are other ways of achieving lazyness but I think this one makes the code look clean.

As you can see, I included the Enumerable module so I had to implement the each method which iterates over all the elements. In it, I made a few (non crucial) tricks:

First I check if a block was given. If it was, I simply yield the row to the block. But if the block is not given, and here is the trick, I call the to_enum method which creates a new enumerator from my method each. This last part is important because now I can chain my enumerator with others and do things like: stream.each.with_index { |row, idx| puts idx }.
Reset the buffer and cursors to allow multiple iterations of the collection. Without this, if I want to iterate over the elements again I have to create a new object.

And that's all for this Re-Wheel part, I hope you can pick up a trick or two from this!

Implement a kafka like consumer strategy to process records in your database

Alejandro Bezdjian — Fri, 13 Nov 2020 21:25:50 +0000

Let's say you have a table in your database which contains data about some files that you would like to process in batch jobs (this is just an example, it can be anything other than files). You have some job that runs every X minutes and does something like:

SELECT * FROM files
WHERE processed = false
LIMIT 100;

Then, it process each row and updates it by flipping the processed. This simple implementation should work just fine if the worker can process the incoming data as fast as it is generated, but it will start lagging if not (or if you want to re-process all the rows in a reasonable time).

The natural thing to do in that case would be to add more workers to parallelize the process. The problem is that the query we are making can lead to problems, for example, since there is no mechanism to stop 2 workers from getting the same rows, some rows can get processed more than once.

I want to show you one way to solve this problem borrowing an idea from Kafka. In kafka you can scale a topic by adding more partitions to it, this will allow you to increase the number of consumers and your throughput. You can read more about kafka consumers here.

Kafka guarantees that the messages written into a topic will be stored in only one partition and will be consumed by only one consumer in a consumer group, and that's exactly what we want in our case here.

In order to achieve this we can use a few useful SQL functions. First we are going to need a unique hash_code for each of our rows:

ALTER TABLE files ADD COLUMN hash_code BIGINT;

The "partition" will be calculated from to this number, so make sure to use a good hashing function.

Every worker instance will act as a "consumer" in kafka, so they need a unique number to avoid processing the same rows, and just like kafka, we won't be able to have more "consumers" than "partitions". How to assign that number depends on your application and is out of the scope of this post.

The other important number that we need is the total amount of workers. Once we have those, let's change our query to get the results we want:

SELECT * FROM files
WHERE processed = false AND MOD(hash_code, :instances) = :instanceId
LIMIT 100;

The main idea behind this query is to use the modulo operation to find the "partition", so MOD(hash_code, :instances) will return that number (starting from 0).

Now, there is a problem with this query. Since we just added the hash_code column, there might be a lot of null values. To solve this issue, we can use the coalesce function to turn each null value into a number. The final query should look like this:

SELECT * FROM files
WHERE processed = false AND MOD(COALESCE(hash_code, 0), :instances) = :instanceId
LIMIT 100;

By doing this, you avoid the need to do a massive update in that table before being able to process the data, in this example all the null values will be processed only by the worker with ID 0.

And that's it!

Of course this method isn't perfect, you could have idle workers if the distribution of your data is not perfect.

What I like about this approach is that is easy to understand, and the required code is simple and elegant. Other solutions may involve the use of locks which are harder to get right in my opinion.

I hope you enjoyed this as much as I did! If you try it in your application let me know!

Implement a simple AWS S3 multi-file downloader in Ruby

Alejandro Bezdjian — Mon, 09 Mar 2020 20:53:27 +0000

Recently, I was requested to implement a multi-file download feature like Google drive's. If you use AWS S3 like me, you know that there isn't a direct way to do this, so in this post I'll show you a reference implementation for that.

We are going to need a few dependencies in our project:

# Gemfile
gem 'aws-sdk-s3', '~> 1.17'
gem 'rubyzip', '~> 2.2'

This post assumes you know how to configure your AWS credentials.

Now let's get to the code! The goal here is to create a zip file which has all our desired files so we can send it to our users. The first thing to do is to download the files, with the official SDK this is quite simple:

@filepaths = @s3_keys.map do |key|
  new_path = "#{@dir}/#{key.split('/').last}" # Keep the filename but avoid the fill path
  # This should go in a separate service
  Aws::S3::Resource.new.bucket(@bucket).object(key).download_file(new_path)
  new_path
end

Now that we have the files in the machine, lets create a zip with all of them. Following the rubyzip's documentation, we can do create the zipped file like this:

Zip::File.open('Archive.zip', Zip::File::CREATE) do |zipfile|
  @filepaths.each do |filepath|
    zipfile.add(filepath.split('/').last, filepath)
  end
end

These simple steps will create our desired zip file! Now we need to put the file somewhere our users can access them. In my case I upload the zip in S3 and create a presigned url for it, but you can change this to fit your needs:

object = Aws::S3::Resource.new.bucket(@bucket).object('Archive.zip')
object.upload_file('Archive.zip')

download_url = object.presigned_url(:get)

Now that you get the idea, let me join everything to get this code working:

It's better to have a class that hides the S3 related code as much as possible:

# s3_service.rb
require 'aws-sdk-s3' # This is not needed in Rails

module S3Service
  class << self
    def upload_file(from:, to:, bucket:)
      object = object(to, bucket: bucket)
      object.upload_file(from)
      object.presigned_url(:get)
    end

    def download_file(key:, to:, bucket:)
      object = object(key, bucket: bucket)
      object.download_file(to)
    end

    def get_download_link(file_name, bucket:)
      object(file_name, bucket: bucket).presigned_url(:get).to_s
    end

    private

    def object(file_name, bucket:)
      bucket(bucket).object(file_name)
    end

    def bucket(bucket)
      Aws::S3::Resource.new.bucket(bucket)
    end
  end
end

Now we are ready to build another class that handles the download, zip and upload of the zipped file:

# multi_file_zipper_download.rb
require 'zip'

class MultiFileZipperDownload
  ZIPPED_FILE_NAME = 'Archive.zip' # Same as Google drive :P

  def initialize(s3_keys, bucket)
    @s3_keys = s3_keys
    @bucket = bucket
  end

  def call
    zip_files(download_objects)
    build_zipped_s3_key
    upload_zip
    delete_tmp_file
    @zipped_s3_key
  end

  private

  def download_objects
    @s3_keys.map.each_with_index do |key, idx|
      # Avoid replacing files with same name by using the index, you can skip this if you like
      new_path = "#{tmp_dir}/#{idx} - #{key.split('/').last}"
      S3Service.download_file(key: key, to: new_path, bucket: @bucket)
      new_path
    end
  end

  def zip_files(files)
    ::Zip::File.open(zipped_file_path, Zip::File::CREATE) do |zipfile|
      files.each do |filepath|
        zipfile.add(filepath.split('/').last, filepath)
      end
    end
  end

  def tmp_dir
    @tmp_dir ||= Dir.mktmpdir
  end

  def zipped_file_path
    "#{tmp_dir}/#{ZIPPED_FILE_NAME}"
  end

  def build_zipped_s3_key
    # I use the hash of the file to avoid collisions, but you can change this to whatever you like
    hash = Digest::SHA256.file(zipped_file_path).to_s

    @zipped_s3_key = "multi_downloads/#{hash}/#{ZIPPED_FILE_NAME}"
  end

  def upload_zip
    # I upload the zipped file to S3 so we can send a link to tje file afterwards
    S3Service.upload_file(from: zipped_file_path, to: @zipped_s3_key, bucket: @bucket)
  end

  def delete_tmp_file
    # Remove all the files to avoid disk usage leaks
    FileUtils.rm_rf(tmp_dir)
  end
end

In order to use this class you can create a simple Sinatra server to test it:

# app.rb
require 'sinatra'
require 'json'

# Here you can initialize the AWS config, use ENV variables or any other valid configuration method

require_relative 's3_service'
require_relative 'multi_file_zipper_download'

BUCKET = 'my-bucket'

get '/keys' do
  # Here you can send the list of available s3 keys using your desired storage
end

post '/download' do
  # Get the keys from the JSON body
  params = JSON.parse(request.body.read)

  zipped_key = MultiFileZipperDownload.new(params['keys'], BUCKET).call
  url = S3Service.get_download_link(zipped_key, bucket: BUCKET)

  [200, { url: url }.to_json]
end

This code will get you going with this feature, but you need to consider that downloading and uploading files from S3 will block your Ruby's server, so you should run this code in background. I'll leave that as an exercise for the reader.

Six degrees of Wikipedia

Alejandro Bezdjian — Sun, 22 Sep 2019 14:22:24 +0000

A few years ago, I read an interesting article about the degrees of separation between Facebook users. Regardless of the result in the article, I thought it would be exciting to find the separation between other things, like Wikipedia articles.

For this problem, we are going to receive 2 valid Wikipedia articles and return a minimum list of articles that connects the two given. Two articles are connected if there is a link in one of the articles to the other (the other way around is not needed).

Let's divide the problem into parts that we can solve separately:

Get an article from wikipedia.
Get all the links in an article to other articles.
Find the minimum path between 2 articles.

For the first two, we need to fetch an article using HTTP and then, find all the a tags that reference other articles. Inspecting the HTML we can see that every article has links that we want to skip (like the main page and external links):

module Services
  class Wikipedia
    BASE_URL = 'https://en.wikipedia.org'.freeze

    class << self
      def article_links(article)
        article = get_article(article)

        article.css('a').each_with_object([]) do |link, array|
          href = link['href']
          array << href if internal?(href) && !array.include?(href)
          array
        end
      end

      private

      def get_article(article)
        uri = URI.parse("#{BASE_URL}#{article}")
        Nokogiri::HTML(uri.read)
      end

      def internal?(link)
        link =~ /^\/wiki\/*/ && !link.include?(':') && link != '/wiki/Main_Page'
      end
    end
  end
end

I used the Nokogiri gem to parse the HTML and easily search the a tags.

Playing with the code I found that it would be nice to have some sort of cache so we don't loose the data fetched from Wikipedia. I used Redis for this:

module Repositories
  class Redis
    REDIS_URL = 'redis://localhost:6379'.freeze

    def initialize
      @connection = ::Redis.new(url: REDIS_URL)
    end

    def get_links(path)
      return Oj.load(@connection.get(path)) if @connection.exists(path)

      links = Services::Wikipedia.article_links(path)
      @connection.set(path, links.to_json)

      links
    end
  end
end

The last part of the task is the actual algorithm. In this case, we can think of the articles as nodes of a graph and the links as the vertices, forming a directed graph. Since accessing each node has the same cost (an HTTP request), we can pretend this is an unweighted graph or a weighted one with the same cost on every edge.

To build the graph I'll use a gem called RGL and it also gives us a search algorithm so we don't have to implement one. Since we don't have the graph, we have to be smart about the way we create it. Traversing the links using DFS (depth-first search) may lead us to create a graph with an unnecesary amount of nodes, so I think it's better to use BFS (breadth-first search) to build it:

module Crawlers
  class Graph < Base
    def call
      graph = RGL::DirectedAdjacencyGraph.new

      queue = []
      queue.push(@from_path)

      while (current = queue.shift) != nil
        links = @repository.get_links(current)

        links.each do |link|
          unless graph.has_vertex?(link)
            graph.add_edge(current, link)
            queue.push(link)
          end
        end

        if links.include?(@to_path)
          return graph.dijkstra_shortest_path(EdgeWeightHack.new, @from_path, @to_path)
        end
      end
    end

    class EdgeWeightHack
      # The dijkstra_shortest_path expects a hash
      def [](key)
        1
      end
    end
  end
end

As you can see I used a queue for adding the nodes in a BFS manner and skipped them if the graph already had the link. I found that the RGL gem didn't have a search algorithm for unweighted graphs but it did have Dijkstra's algorithm for weighted ones. It expected a hash with the edge values, but since every edge has the same value and I didn't want to use unnecesary extra memory, I hacked a class called EdgeWeightHack taking advantage of Ruby's duck typing.

Now let's see this in action! Let's find out how separated is Chuck Norris from Computer programming:

################################################################
Chuck_Norris is 3 degrees separated from Computer_programming.
################################################################
/wiki/Chuck_Norris
/wiki/Republican_Party_(United_States)
/wiki/Internal_Revenue_Service
/wiki/Computer_programming
################################################################

The algorithm had to search 1113 links to find the answer, and we (programmers) are only 3 degrees separated from Chuck! Nice!

After having something working, I always try to see if I can improve it. I feel that making a BFS to add the nodes and then searching the path is making double work, because the BFS will find a minimum path in this case!

Since I don't want to search, every node I put in the graph has to know the path I used to get to it, so let's build this custom graph:

module Crawlers
  class Custom < Base
    def call
      queue = []
      queue.push(Node.new(@from_path))

      answer = []

      while (current = queue.shift) != nil
        return current.complete_articles_path if current.article == @to_path

        links = @repository.get_links(current.article)

        if links.include?(@to_path)
          return (answer = current.complete_articles_path << @to_path)
        end

        links.each do |article|
          unless current.previous_articles.include?(article)
            queue.push(Node.new(article, current.complete_articles_path))
          end
        end
      end

      answer
    end

    class Node
      attr_reader :article, :previous_articles

      def initialize(article, previous_articles = [])
        @article = article
        @previous_articles = previous_articles
      end

      def complete_articles_path
        @previous_articles + [@article]
      end
    end
  end
end

Now it's time to benchmark both solutions and see which one is best:

Benchmarking 100 times

       user     system      total        real
Custom 63.772801   9.894999  73.667800 (249.561173)
Graph 197.834715  10.884686 208.719401 (378.234052)

Memory usage of Custom ---------------------------
        Total allocated: 155287889 bytes (2223856 objects)
        Total retained: 546 bytes (2 objects)
Memory usage of Graph ----------------------------
        Total allocated: 259432021 bytes (2015009 objects)
        Total retained: 97485111 bytes (517055 objects)

Wow! That's actually a very big improvement in both speed and memory!

Conclusion

Even though the result of solving this problem is not very useful, I had a lot of fun doing it. I was able to use the algorithms I've learned in a more "realistic" way (compared with the exercises found in books).

I hope you enojoyed this as much as I did! You can check the full implementation on my github account!

Infinite list of prime numbers using Python generators

Alejandro Bezdjian — Sat, 14 Sep 2019 21:55:14 +0000

Sometimes we want to create collections of elements that are very expensive to calculate. The first option is to create a list and wait until all the elements are calculated before we use it. Although this works, it is not very efficient. To make it a bit more efficient, modern languages provide a way to create custom iterators so each element is calculated only when needed (this is also called lazy initialization). Also, iterators allows us to create infinite collections!

Python has, in my opinion, one of the most succint and elegant ways to declare iterators: generators.

Without further ado, let's try to create an infinite list of prime numbers.

The first thing we need is a way to detect if a number is prime:



from math import sqrt

def is_prime(n):
    if (n <= 1):
        return False
    if (n == 2):
        return True
    if (n % 2 == 0):
        return False

    i = 3
    while i <= sqrt(n):
        if n % i == 0:
            return False
        i = i + 2

    return True

Now, using our is_prime function we can do:



def prime_generator():
    n = 1
    while True:
        n += 1
        if is_prime(n):
            yield n

And that's it! Just call the function and get elements from it:



generator = prime_generator()

for i in range(10):
    print(next(generator))

Or create a list of the first N prime numbers:



from itertools import islice

array = [x for x in islice(prime_generator(), 10)]

As you could see, the iterator definition is one of the shortest and simplest among all languages.

Text editor tips and tricks to boost your productivity

Alejandro Bezdjian — Fri, 13 Sep 2019 00:38:11 +0000

Recently, I was peer programming at work and, whithout thinking, I started to use a few editor tricks I had learned a while ago. My co-worker was amazed with them and picked up a few. At first I thought it was no big deal, but a few days later I began to observe that there are a lot of people who don't know many of these tricks. Since the tools we use have a lot of functionalities to make us more productive, it's a shame that we spoil them. That's why I thought it would be a good opportunity to transfer this useful knowledge and help others improve their productivity.

Building blocks

All the tricks I'll show you are a combination of small pieces that seem insignificant at first sight, but are very powerful when they are combined. At the end I will show you some examples that (hopefully) show how useful these tricks are.

The examples were created using VS Code on a mac, but all these functionalities should be available in every editor and IDE.

Moving cursor

Let's start slowly but surely.

Use the arrows of your keyboard to move the cursor one step at a time:

Using option + cursor move the cursor between words:

User cmd + cursor to move the cursor to the end or beginning of line:

Using the option key, you can move any line:

I use cmd + x to delete a line, this actually cuts it, but I don't really care (if you do care, use cmd + shift + k):

Highlighting

This also seems silly, but it's important that we know them all.

Using shift + cursor we can highlight words character by character:

To improve this, we can use shift + option + cursor to highlight whole words:

We can boost this using shift * cmd + cursor to select the entire line:

Multiple cursor magic

Now we are getting to the most important thing in my opinion, controlling multiple cursors.

First let's create them, we can use cmd + click using the mouse or cmd + option + up/down cursor with the keyboard only:

Normally, the selections of each cursor are copied separately and you can copy and paste them anywhere. If you have the same number of cursors as when you copied this is what happens:

If you have a smaller or larger number of cursors than when you copied, all the copied selections will be pasted on every cursor you have at the moment.

I use the next one a lot. When you select something, you can use cmd + d to select the next matching selection. This is extremely useful as we will see in one of the examples at the end. Each selection will create a cursor for it:

Auto closing characters

These is similar to the HTML auto closing tags function (that I also recommend) but with characters that have a closing pair, for example:

Examples

All the previous blocks will be useful in %90 of the times (more or less). The examples I'll show you are simplified real case scenarios and I hope the animations are self-explanatory (if there is something unusual I will try to explain what I did).

Here I added a space at the beginning so I would get a cursor where I wanted (this is another trick that you learn from practice).

Of course there are other ways to solve them, your creativity is your limit!

Extras

There are other features that editors have that you definitely should know:

Find and open a file by name: in my case is cmd + d but other editors and IDEs have them mapped differently.
Use autocompletion: if you develop in Java or similiar you are probably used to this, but editors have a lot of plugins for other languages that can help you.
Find words in a file using regexp. This one is a bit more difficult (because you have to know regular expressions) but is very useful from time to time:

Once you found the text you want with your regexp, use shift + cmd + L to select it.

I hope you found these tricks useful and help you be more productive!

Pascal's triangle in Ruby for fun

Alejandro Bezdjian — Sat, 07 Sep 2019 15:21:14 +0000

The other day I came across a blog post talking about the Pascal's triangle and all of it's interesting properties and I thought it would be fun to implement it using Ruby.

The Pascal's triangle is a triangular array of the binomial coefficients, but you don't have to calculate them in order to create the triangle because each row can be constructed using the previous one, like this:

Forming something like this:

What amazes me is that this simple construction can be used to calculate a lot of interesting things. Even though there are more efficient ways to do the same calculations I thought it'd be fun to do it this way.

Pascal's triangle itself

First, we are going to need something that calculates the triangle, let's create a class for this:

class PascalTriangle
  def initialize
    @triangle = [[1]]
  end

  def get_file(param)
    return @triangle[param] if @triangle[param]

    previous_file = get_file(param - 1)
    @triangle << calculate_new(previous_file)

    @triangle[param]
  end

  private

  def calculate_new(previous_file)
    current_file = [1]
    (0..(previous_file.size - 1)).each do |idx|
      next if idx == previous_file.size - 1

      current_file << previous_file[idx] + previous_file[idx + 1]
    end
    current_file << 1

    current_file
  end
end

I used a recursive function to create each row when needed and dynamic programming to store the intermediate results to make it faster for successive calls.

Fibonacci

Let's start with my favourite application of the triangle, the Fibonacci sequence. Basically you can get the elements of the sequence doing:

We can implement a method like this:

@triangle = PascalTriangle.new

def fibonacci(n)
  return 0 if n <= 1
  return 1 if n == 2

  result = 0
  (0..n).reverse_each.with_index do |n, idx|
    coefficients = @triangle.get_file(n - 2)
    next unless coefficients[idx]

    result += coefficients[idx]
  end
  result
end

(1..20).map { |n| fibonacci(n) } #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Binomial coefficient

Each element of the triangle corresponds to a binomial coefficient:

So it's super easy to get the value:

def binomial_coefficient(n, k)
  file = @triangle.get_file(n)
  file[k]
end

Binomial expansions

Coefficients of the expansion of a binomial raised to a positive integer N appear in the Nth row of the Pascal's triangle:

(x + y)^2 = x^2 + 2xy + y^2 = 1*x^2 + 2*xy + 1*y^2

With this not only wee can get the coefficients, but calculate (x+y)^n:

def binomial_power(a, b, n)
  coefficients = @triangle.get_file(n)

  result = 0
  coefficients.each_with_index do |coefficient, idx|
    result += coefficient * a**(n - idx) * b**idx
  end

  result
end

Powers of 2

If we sum each number of the Nth row of the triangle we get 2^n!

def power_of_2(n)
  coefficients = @triangle.get_file(n)
  coefficients.sum
end

Powers of 11

Here is a more complicated one. We can build the powers of 11 concatenating each number of a row.

Things get more complicated when the numbers start to get bigger. So we need to carry the tens place over to the number on it's left:

def power_of_11(param)
  coefficients = @triangle.get_file(param)

  if param <= 4
    coefficients.join.to_i
  else
    coefficients_with_carry = [0]
    coefficients.reverse_each.with_index do |coefficient, idx|
      coefficient_with_carry = coefficient + coefficients_with_carry[idx]

      if coefficient_with_carry < 10
        coefficients_with_carry[idx] = coefficient_with_carry
        coefficients_with_carry[idx + 1] = 0
      else
        coefficients_with_carry[idx] = coefficient_with_carry % 10
        coefficients_with_carry[idx + 1] = (coefficient_with_carry / 10.0).floor
      end
    end
    coefficients_with_carry.reverse.join.to_i
  end
end

Series

We can find some series of numbers in the triangle

Perfect squares

Perfect squares are numbers that can be expressed as the product of two equal integers, for example 4 is a perfect square becase you can express it like 2^2 = 4. The perfect squares are found in the third column of the triangle, the trick is that you have to sum the element of the previous row:

We can create a class that returns all of the perfect squares one by one:

class PerfectSquaresSeries
  def initialize(triangle)
    @triangle = triangle
    @current_file = 3
  end

  def next
    previous_file = @triangle.get_file(@current_file - 1)
    file = @triangle.get_file(@current_file)
    @current_file += 1

    file[2] + previous_file[2]
  end
end

series = PerfectSquaresSeries.new(@triangle)
series.next #=> 4
series.next #=> 9
series.next #=> 16
series.next #=> 25
series.next #=> 36
series.next #=> 49
series.next #=> 64
series.next #=> 81

Natural numbers

If we take a look at the second column we see that the natural numbers appear:

This is not something very interesting, but if we see the succesive columns we observe the triangular, tetrahedral, pentalope numbers and so on (which I generalized calling them the N-hedral numbers).

N-hedral numbers

All the series can be found in the Nth column of the triangle, and we can get them like this:

class NHedralSeries
  def initialize(triangle, n)
    @triangle = triangle
    @current_file = n - 1
    @n = n
  end

  def next
    file = @triangle.get_file(@current_file)
    @current_file += 1
    file[@n - 1]
  end
end

natural = NHedralSeries.new(@triangle, 2)
(0..10).map { natural.next } #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

triangular = NHedralSeries.new(@triangle, 3)
(0..10).map { triangular.next } #=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66]

tetrahedral = NHedralSeries.new(@triangle, 4)
(0..10).map { tetrahedral.next } #=> [1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286]

pentalope = NHedralSeries.new(@triangle, 5)
(0..10).map { pentalope.next } #=> [1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001]

I hope you enjoyed this exercise as much as I did! You can find my complete implementation here.