Update

There is a revised version of this blog, showing how an algorithm implementation could be optimized.

The story behind this post

Recently I’ve received +10 karma on StackOverflow. I was curious for what question or answer and clicked to check this. It appeared to be a seven-year-old answer about a Floyd-Warshall algorithm. I was surprised with both my bad English (back those days…) and the very small value the answer had. So I’ve revised it and here it is – the brand-new version!

The definitions

Let us have a graph, described by matrix D, where D[i][j] is the length of the edge (i -> j) (from graph’s vertex with index i to the vertex with index j).

Matrix D has the size of N * N, where N is a total number of vertices in a graph because we can reach the maximum of paths by connecting each graph’s vertex to each other.

Also, we’ll need matrix R, where we will store the vertices of the shortest paths (R[i][j] contains the index of a vertex, where the shortest path from vertex i to vertex j lies).

Matrix R has the same size as D.

The Floyd-Warshall algorithm performs these steps:

1. initialize the matrix of all the paths between any two pairs of vertices in a graph with the edge’s end vertex (this is important since this value will be used for path reconstruction)

2. for each pair of connected vertices (read: for each edge (u -> v)), u and v, find the vertex, which forms shortest path between them: if the vertex k defines two valid edges (u -> k) and (k -> v) (if they are present in the graph), which are together shorter than path (u -> v), then assume the shortest path between u and v lies through k; set the shortest pivot point in matrix R for edge (u -> v) to be the corresponding pivot point for edge (u -> k)

But how do we read the matrix D?

Foreword

Some time ago I’ve published an article about bit O notation. I’ve mentioned its source but never published it. So here it is, the original article.

The article

Big O notation is the most widely used method which describes algorithm complexity - the execution time required or the space used in memory or in the disk by an algorithm. Often in exams or interviews, you will be asked some questions about algorithm complexity in the following form:

For an algorithm that uses a data structure of size n, what is the run-time complexity or space complexity of the algorithm? The answer to such questions often uses big O notations to describe the algorithm complexity, such as O(1), O(n), O(n^2) or O(log(n)).

At work, I’ve had a task to implement a Gantt chart diagram to show dependencies and order of some… let’s say, milestones. Given this feature is in a very unstable beta in Google Charts, I thought to myself: “Why don’t I implement it on my own?”. And tried to recall my D3 knowledge.

I’ve also found a minimalistic, but helpful example / screenshot of some Gantt chart implementation:

The challenges I’ve faced were:

1. order milestones on a timeline
2. scale milestones to fit in a viewport
3. create pretty connection lines
4. center text inside each milestone

And since D3 is a data-driven library, I’ve used map/reduce where possible.

Here’s how the result looked like:

The implementation details are under the cut.

Update August 2020

There are few updates to this original implementation in my new blog.

Entanglement?

Some time ago there was a game popular over there, called Entanglement:

There are a few implementations of this game under Android:

But there was no such game for iOS. And as I pursued my second M. Sc. degree, I have had a course “iOS development”, where we were learning to use Swift and iOS platform.

I decided to implement this game as my course project. In Swift. Originally the game was implemented in Swift 2 (there was no Swift 3 back those days).

And recently I decided to refactor the game a bit and update it to the most recent Swift version (which is Swift 3 at the moment of writing this post).

In this post I’ll describe some interesting decisions I made while creating this game.

libc.js

Recently I’ve written a post about functional programming techniques, coming into the world of front-end and the library I crafted as an experiment. That library, libc.js was highly inspired by Elm and Mithril. But it suffered two major features:

1. components were hardly able to be used in other components
2. the interaction between components was nearly impossible (or, at least, not very transparent)

What’s hidden beneath the next version of the library?

Have you ever asked anyone if assembly language might be useful nowadays? So, here’s the short answer: YES. When you know how your computer works (not a processor itself, but the whole thing - memory organization, math co-processor and others), you may optimize your code while writing it. In this short article, I shall try to show you some use cases of optimizations, which you may incorporate with the usage of low-level programming.

Recently I was reading through my old posts and found out there is a gap in the article about SSE - the post did not cover some of the implementation caveats. I decided to fulfill this and re-publish a new version.

In last couple of years the functional programming paradigm became very popular. A huge amount of libraries, tools, tutorials and blog posts appeared. Although the paradigm itself is rather old (lambda calculus was developed around 1930 and the Lisp language was introduced in 1950), its popularity blew up rapidly somewhere in 2014-2016 and that’s what is happening right now. Probably one of the most powerful influencers, giving FP (functional programming) that thrust is web development. Since Facebook introduced React, the community started incorporating many things from FP with React - including Redux and Immutable.js. But there are much more interesting things which were invented on this wave of FP popularity. One of them is Elm.

This is a story how I implemented invented yet another web framework wheel.

Once I wanted to have something like a pretty “match” operator from Scala (or Rust, or C# 7), but in Clojure. In this blog I explore some solutions for that available in Clojure world.

Use case

Generally, you would use pattern matching as a neat syntax for multiple if..else or switch..case statements. Consider this example of transforming values between two enums:

if (entityType == DBEntityType::ISSUE) {
    return UIEntityType::ISSUE;
} else if (entityType == DBEntityType::SUBTASK) {
    return UIEntityType::SUBTASK;
} else {
    return UIEntityType::UNKNOWN;
}

This could be written neatly with a switch..case statement:

switch (entityType) {
    case DBEntityType::ISSUE:
        return UIEntityType::ISSUE;
    case DBEntityType::SUBTASK:
        return UIEntityType::SUBTASK;
    default:
        return UIEntityType::UNKNOWN;
}

In C# starting with version 7 you could write this using switch expression:

return entityType switch {
    DBEntityType.ISSUE => UIEntityType.ISSUE,
    DBEntityType.SUBTASK => UIEntityType.SUBTASK,
    _ => UIEntityType.UNKNOWN
};

But what if you have multiple conditions to check?

if (entityType == DBEntityType::ISSUE && permissions.canEdit(user, DBEntityType::ISSUE)) {
    return UIEntityType::ISSUE;
} else if (entityType == DBEntityType::SUBTASK && permissions.canEdit(user, DBEntityType::SUBTASK)) {
    return UIEntityType::SUBTASK;
} else {
    return UIEntityType::UNKNOWN;
}

This can not be converted to switch..case nicely. But with switch expressions (or rather, pattern matching, in general) you can do something like this:

return entityType switch {
    DBEntityType::ISSUE when permissions.canEdit(user, DBEntityType::ISSUE) => UIEntityType::ISSUE,
    DBEntityType::SUBTASK when permissions.canEdit(user, DBEntityType::SUBTASK) => UIEntityType::SUBTASK,
    _ => UIEntityType::UNKNOWN,
};

Using cond

;; Note how this method does not check the `n > 3` case
(defn testFn [n]
    (cond
        (= n 1) "You entered 1!"
        (= n 2) "You entered two!"
        (= n 3) "You entered three!"
        :else "You entered a big number!"
    ))

(defn complexFn [entityType user permissions]
    (cond
        (and (= entityType :db-issue) (can-edit? permissions user :db-issue) :ui-issue)
        (and (= entityType :db-subtask) (can-edit? permissions user :db-subtask) :ui-subtask)
        :else :ui-unknown))

Using condp

;; Note how this method does not check the `n > 3` case
(defn testFn [n]
    (condp = n
        1 "You entered 1!"
        2 "You entered two!"
        3 "You entered three!"
        "You entered a big number!"))

(defn complexFn [entityType user permissions]
    (condp = [ entityType true ]
        [ :db-issue (can-edit? permissions user :db-issue) ] :ui-issue
        [ :db-subtask (can-edit? permissions user :db-subtask) ] :ui-subtask
        :ui-unknown))

Using guard macro

(defn generateGuardBody
    "Generates the function body required to support the guard macro"
    [args]
    (let [[thisBranch remainingBranches] (split-at 2 args)
            testCond (first thisBranch)
            testResult (second thisBranch)
            elseFunc (if (empty? remainingBranches)
                false
                (if (=  1 (count remainingBranches))
                    (first remainingBranches)
                    (generateGuardBody remainingBranches)))]
        `(if ~testCond
            ~testResult
            ~elseFunc)))

(defmacro defguardfn
    "Creates a haskell-style guarded function"
    [fnName args & body]
    `(defn ~fnName ~args
        ~(generateGuardBody body)))

(defmacro guard
    "Allows inline guard syntax without surrounding defn"
    [& body]
    `~(generateGuardBody body))


(defguardfn testFn [n]
    (= 1 n) "You entered 1!"
    (= 2 n) "You entered two!"
    (= 3 n) "You entered three!"
    (> n 3) "You entered a big number!")

(println (testFn 5))

(defguardfn fib [n]
    (< n 2) n
    (+ (fib (- n 1)) (fib (- n 2))))


(defn testFn-2 [x]
    (guard
        (= x 1) "One!"
        (= x 2) "Two!"
        true  "Something Else!"))

(println (map fib (range 0 10)))
(println (testFn-2 3)) ; "Something else!"

Using multimethods

;; Implementing factorial using multimethods Note that factorial-like function
;; is best implemented using `recur` which enables tail-call optimization to avoid
;; a stack overflow error. This is a only a demonstration of clojure's multimethod

;; identity form returns the same value passed
(defmulti factorial identity)

(defmethod factorial 0 [_]  1)
(defmethod factorial :default [num]
    (* num (factorial (dec num))))

(factorial 0) ; => 1
(factorial 1) ; => 1
(factorial 3) ; => 6
(factorial 7) ; => 5040

Using core.match

(defn div3? [x] (zero? (rem x 3)))
(let [y [2 3 4 5]]
  (match [y]
    [[_ (a :guard even?) _ _]] :a0
    [[_ (b :guard [odd? div3?]) _ _]] :a1))

(let [x [1 2 3]]
  (match [x]
    [[1 (:or 3 4) 3]] :a0
    [[1 (:or 2 3) 3]] :a1))
;=> :a1

(let [x {:a 3}]
  (match [x]
    [{:a (:or 1 2)}] :a0
    [{:a (:or 3 4)}] :a1))
;=> :a1

(let [v [[1 2]]]
  (match [v]
    [[[3 1]]] :a0
    [[([1 a] :as b)]] [:a1 a b]))
;=> [:a1 2 [1 2]]

The best big O notation explanation I’ve ever saw I’ve found on… Google Play Market! I was hanging around, looking for the suggested software and, for some reason, I’ve decided to install some educational application for programmers. And here’s what I’ve found…

This is a chicken. This 3D model I’ve made in 3.5 hrs in Blender (with texturing).

Taking into account the fact I’ve started learning Unity 3D, I will possibly use this in the remake of my old Shoot Them! game. Like this (early preview, made with Unity 3D in ~3 hrs):