megacolorboy

Abdush Shakoor's Weblog

Writings, experiments & ideas.

Built a 2048 clone in 15 minutes

An implementation of the famous 2048 game using JavaScript and HTML5 Canvas.

Before you read more about this article, play with the above game. You can move the tiles around using your or WASD keys. The rule is simple, when two tiles with the same number touch, they merge into one tile. Press the R key to restart the game.

Please make sure that you have JavaScript enabled and running in your browser, otherwise you won't be able to play this game. Oh, just a little heads up, it might get a little buggy and freeze your browser window, so keep calm and play patiently.

As for the source code, you can view it in my GitHub repository or can be found near the end of this article.

Background

I was always fond of puzzle games and 2048 is one of them. The first time I got to play this game was back in 2014 and I would play it on my iPhone during my train commute to university.

Yesterday, I thought of building a clone and turns out it wasn't as hard as I had expected it to be, in fact, I was able to build a functional version in just 15 minutes.

What are the game mechanics?

The sliding-puzzle game is played on a four-by-four grid with numbered tiles that is moved by the player in all four directions.

In every move, a new tile would randomly appear in an empty spot in the grid with a value that consists of 2 or 4. These tiles are moved towards any direction as far as it could and if there are two tiles that collide with the same value, they merge into one tile and as a result, the score is updated.

The player wins the game once the tile of 2048 appears on the grid, thus is the name of the game.

Source code

Well then, that's all for the game. Just like the previous ones, I had fun building this sliding-puzzle game. I'm looking forward to building more puzzle games and talking about them in my blog.

Hope you guys liked reading this article and have fun playing the game as many times as you like!

Stay tuned for more!

Can we eliminate traffic congestion with the help of Computer Vision?

Writing out my thoughts on eradicating traffic congestion in highly populated cities.

Whether it's being implemented or not, I have been thinking on how we could use Computer Vision to solve traffic congestion.

Since, I live in the United Arab Emirates, I have always observed that people who commute from Sharjah to Dubai and vice-versa face a lot of traffic jams despite all the new roads and toll-gates (yes, I don't seem to understand how does that solve the problem).

Traffic in Al Ittihad Highway.

Well, the problem is not only faced in this country but many countries such as China, Indonesia and so on.

What are the causes of traffic congestion?

Anyways, I jotted down some facts to consider what causes traffic congestion in the first place:

  • Tail-gating
  • Inconsistent travel speeds
  • Uneven vehicular distances
  • Spontaneous accidents and road rages
  • Changing from one lane to another
  • Increase in car population
  • Peak hours i.e. people going to work and leaving from work

I'm sure that there could be more but these are the facts that I can come up with for now.

How can Computer Vision solve this problem?

Computer Vision is a field that intersects with multiple areas of technologies in which it aims to develop an understanding of objects by extracting information from various digital media sources like images and videos and automate those tasks that a normal human would do in their daily lives.

Visualization of Computer Vision.

There are various types of problems that Computer Vision algorithms are able to solve but not limited to:

  • Object Recognition or Object Classification
  • Identification of Objects
  • Object Detection
  • Analysis of Motion

Now, it's not only about implementing these CNN-based (Convolutional Neural Network) algorithms but you also need hardware to be able to compute and process data. 

How would this work?

There are two scenarios that I had thought while writing this article and I hope that I'm able to translate my thoughts into accurate examples.

Let's pretend we have four car drivers: Alex, Bob, Charlie and Dylan.

Speed-Distance equilibrium

Alex, Bob and Charlie are driving on the same lane. Alex hits the brake slowly to shift to another lane, the sensors of Bob's car detects a change in speed in Alex's car, Bob's car adjusts it's speed to match Alex's current speed based on the variables of distance and travel time, Charlie's car adapts the changes of Bob's car and thus, it's a chain reaction.

Shifting from one lane to another

Alex is driving in Lane A and Dylan is driving in Lane B. Alex wants to shift to Lane B, so he switches on the indicator and Dylan's car sensors identify that Alex's car wants to change lanes. So Dylan's car slows down and Alex is able to shift lanes with ease. I thought of it to be some sort of a "elastic" effect when this occurs.

Well, you might argue that some cars have a system called "Cruise Control" but here's the part that I'm trying to pitch, as I had mentioned above, I just wanted to integrate sensors to the front and rear sides of a vehicle, which means that these sensors can be integrated in almost any vehicle.

How is this going to be helpful?

For starters, traffic congestion will gradually reduce, if not, be eliminated but there are other beneficial factors to it, such as:

  • Less fuel consumption
  • Less time is required to reach a destination
  • No tail-gating
  • Could prevent major road accidents

However, if the sensors fail to work, the car driver will still be safe because it's surrounded by other cars that have the sensors. This made me think of another question, does that mean do all cars require sensors or only a few? I find it quite intriguing.

Conclusion

Although, these sensors might require a vehicle to have some intelligent capabilities, it may not require the type of network found in an autonomous vehicle.

The idea of placing sensors in the front and rear of a vehicle can optimize the flow of traffic and thus, it might help eliminate traffic congestion.

Hope you liked reading this article!

Meet Blog Engine 2.0

Basically, a minimal blog engine with a paper-like user interface with better enhancements.

Blog engine updated!

As of March 1st 2019, I have changed my blog engine from a dynamic website to a custom-built static site generator. Read more →

Whenever I'm writing a new blog post, I would write it using HTML on my text editor i.e. using Sublime Text and copy-paste the source code into my blog engine and hit "Submit" and that was really annoying.

You might be thinking to yourself as to why I'm putting myself through such a tedious process to write a blog article when there are several WYSIWYG text editor plugins.

Truth is, I have to admit that I was lazy and I cared a lot about writing my blog articles but never cared about the tool I had built that to write my blog articles, so I decided to upgrade it and make it even better than what it was previously!

Why rewrite it?

For starters, the old one had a clunky and pretty much boring user interface. I used CKEditor text editor plugin but to be honest, I rarely used any of it's features as I was just directly copy-pasting my source code from Sublime Text to the text field box.

Over time, it became slow due to spaghetti code and it required a lot of code refactoring as I wrote this code during my earlier days of programming by following various programming tutorials.

Here's some screenshots of the old blog engine:

Fig.1: Index Page
Fig.2: List of blog posts
Fig.3: Edit page

And, last but not the least, it didn't make me feel like I was writing a blog but rather felt like writing HTML code in a more tedious manner.

Time for a change!

For the past two weeks, I have been working on a new version of the blog engine and I had decided to give it some new features like:

  • Clean and paper-like user interface by taking inspiration from Google's Material Theming Design guidelines
  • Minimal text editor built from scratch that can be extensible in the future
  • Auto-save article every minute
  • Emojis, LaTeX syntax, JavaScript files and IFRAME windows
  • Live search bar to filter articles by keywords or categories

In case, you're wondering, I built this using vanilla JavaScript and a custom-built MVC PHP framework with a MySQL database.

Here's some screenshots of the new blog engine:

Fig.4: Index page with a better UI
Fig.5: Minimal Text Editor

What I really wanted to achieve with the new blog engine is that I want to give myself an enjoyable writing experience besides, this blog post was written from the new blog engine.

Well, it's stable as of yet but I need to run a few tests and build more functionalities before deploying it on my production server and finally saying good-bye to the old version.

Hope you liked reading this article!

Build and Design software with Empathy

Can seeing things from another's perspective create empathy and help solve technical challenges?

Recently, I've started reading this book named Designing For Emotion by Aarron Walter and I've made it a point to read it during my free time and so far I have completed three chapters of the book.

In the first chapter of the book, I found a really interesting sentence, written by the author:

Keep in mind that ignoring human needs is not a history we are doomed to repeat. Through our designs, we can see and connect with other human beings.

Do you think a good software builds strong connections with other human beings? Well, we have good examples like Facebook, Google, Netflix, and Microsoft are proof that they have a massive pool of audience who likes to use their products on a daily basis.

In this article, I will share some of my thoughts on how empathy can be used to build and design powerful applications.

User Interface Matters

To any user, whatever is displayed on the application matters the most, in this case, it's the User Interface of an application. If it doesn't allow a user to perform their desired task, it will end up in their Recycle Bin.

Fig. 1: Apple's Ping

There are many examples in the book and one of the examples is about Apple's Ping (refer to Fig. 1), which was an attempt in creating a social network on iTunes but it turned out to be unsuccessful as users learned that they weren't able to share songs on Facebook or Twitter and it lacked basic features. As a result, users didn't come back to it again.

In my opinion, a good user interface should be relatively easy to use and be more reliable in terms of pagespeed or simple and easy navigation for the user. I mean, think about it, if your user is able to complete their desired task and that puts a smile on their face, the user will share their experiences to their friends and you'll get more people to use your application, thus making your application more powerful.

A Universal Design

A door knob comes with multiple designs such as rotating knobs and levers but what matters the most to the people? The design or the functionality? I personally prefer a lever knob over a rotating knob as I find it quite annoying. Weird analogy but the point is, it should just open the door, nothing fancy.

Similarly, when we build our software, by following proper techniques, we can choose to make it beautiful but also choose to make it accessible and functional for everybody, at all costs.

Listen to your users

When building and designing a piece of code, it should and always be for the people that uses or will use your product. By understanding what's important to the users, it can help you get to the core of the problem and surpass technical challenges easily.

This can be achieved by gathering user requirements in the form of surveys, user feedback and A/B testing. Remember, software is just an expressive form of bringing your ideas to life and writing code is building on top of the idea to achieve a certain goal but empathy is the secret sauce to the success of your application.

UX is not UI

What's the first thing that comes to your mind when a friend of yours tells you: "Hey, I'm working as a UX Designer at UberCoolCorp!"? Does he build User Interfaces? Is he a Visual Graphics Designer? Neither, actually!

User Experience is not about how your application looks but how it feels and makes it simple and easier to interact with your users. I'd like to share an interesting quote from Usabilla's UX Expert, Erik Flowers:

UX is the intangible design of a strategy that brings us to a solution.

User Experience encompasses a lot of elements such as Information Architecture, Interaction Design, Usability, Product Design and so on. Below is a picture for your reference about why User Experience is not User Interface:

Fig. 2: How UX wants to be seen.

Although, it does have a lot of elements, UI is a huge part of the design process because strong visual aesthetics are still essential in UX, which is also one of the aspects of your user's interactions with the application.

Progressive Enhancement

A strategy that is known to take you on journey from simplicity to complexity. It's about starting off with a strong, practical foundation and then building on top of it. It's easier to maintain and make small yet incremental changes, renders the application to be more robust and it works for all users.

Conclusion

Well, I'm sure there a lot of elements to this topic but I thought of highlighting some of the most important parts of building and designing software with empathy. As engineers or developers, it is our job to ensure that our final product is usable and accessible to our end-user.

Hope you liked reading this article!

Stay tuned for more!

Extras

Lexicographic Permutations

How to generate the next permutation of any given sequence in lexicographical order.

According to Problem 24 in Project Euler, you are asked to find the millionth permutation using the following sequence of 10 digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Well, if you do the math, there are around 10! = 3,628,800 unique permutations and that means, you have to come up with an efficient algorithm.

I tried writing a recursive function but it turned out to be a bit tricky, so I thought of writing a brute-force solution which seemed far more simpler to understand and it's quite efficient.

Algorithm Description

The following algorithm is quite simple and easy to understand:

1. Find i such that a[i-1] is greater than or equal to a[i].
2. Find j such that a[j-1] is less than or equal to a[i-1].
3. Swap a[i] with a[j].
4. Reverse the suffix from a[i+1] to the last element.

Suppose, if the first step fails, it means the current permutation is the last one because such an index that does not exist. However, it's simple to implement the following algorithm correctly and efficiently, so let's take a look at the implementation.

Python Implementation

The following method only generates the next permutation of any given sequence, so if you're interested in generating all the permutations, especially, for very large lists, this function can be useful.

Implementation of the method(s):

# Swap numbers in a list
def swap(list, i, j):
    list[i], list[j] = list[j], list[i]

# Get the next permutation
def nextPermutation(list):

    i = len(list) - 1

    # As long as the f(x-1) >= f(x), decrement the first index
    while list[i-1] >= list[i]:
        i = i-1

    j = len(list)

    # As long as the f(y-1) <= f(x-1), decrement the second index
    while list[j-1] <= list[i-1]:
        j = j-1

    # make a swap
    swap(list, i-1, j-1)

    i = i+1
    j = len(list)

    # keep swapping until you get the next permutation
    while i < j:
        swap(list, i-1, j-1)
        i = i+1
        j = j-1

    return list

Final code:

#!usr/bin/python
import math, time, pe_lib

start = time.time()

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

count = 1
limit = 1000000

while count < limit:
    pe_lib.nextPermutation(list)
    count = count + 1

print "".join(str(x) for x in list)
print "Finished: %f seconds" % (time.time() - start)

This code in executed in approximately 2.37 seconds with an algorithmic complexity of O(n) i.e. linear time complexity and the replacements of the numbers were done in-place since no extra space was used.

Hope you liked reading this article!

References

Finding the 1000 digit Fibonacci number using the Golden Ratio

Rather than sticking to using a brute force solution, I decided to find the 1000 digit fibonacci number using the Golden Ratio.

Back in February, I said that I'm going to start solving Project Euler problems using Python and yes, I have been doing it actively but sometimes, I don't find the time to post the solutions.

If you're someone who has tried Project Euler before, you'll know that you'll get to encounter problems that require you to implement smart solutions to crunch big numbers efficiently. One of those problems is Problem 25, which states to find the first term in the Fibonacci Sequence that contains 1000 digits.

This problem can be easily solved using a Brute Force solution, instead, I opted to try out a mathematical solution that makes use of the Golden Ratio and also, it gave me the perfect excuse to try writing those formulas using LaTeX markup.

What is Golden Ratio?

Famously known as Phi that represents the Golden Ratio is an irrational number that's approximately equal to 1.6180 and just like it's cousin, Pi, it has a never ending pattern of decimal digits.

\[\Phi = 1.6180339887... \]

According to the article in Wikipedia, back in the Twentieth Century, architects and artists had proportioned their works to approximate the Golden Ratio in the form of a Golden Rectangle, that is believed to be aesthetically pleasing.

Time for some Calculus!

This is the equation used to find the nth Fibonacci Number:

\[ F(n) = {log(\Phi)^n \over \sqrt{5}} \]

Now, let's modify this formula to find the smallest integer i.e. the first term of the 1000 digit number that fulfills this inequality:

\[ {log(\Phi)^n \over \sqrt{5}} \gt {10^{999}} \]

Expand the formula a little bit more:

\[ n \times log(\Phi) - {log(5) \over 2} \gt {999 \times log(10)} \]

\[ n \times log(\Phi) \gt {999 \times log(10)} + {log(5) \over 2} \]

We need to find n, so let's isolate it:

\[ n = {{999 \times log(10) + {log(5) \over 2}} \over {log(\Phi)}} = 4782.06 \]

\[ n \cong 4782 \]

So, the first term that contains the 1000 digit Fibonacci Number is 4782.

Here's the solution using Python that solved in 0.000194 seconds:

import math

limit = 999
golden_ratio = 1.6180

n = round(((limit * math.log(10)) + (math.log(5)/2))/(math.log(golden_ratio)))

print n

So, this is how it would look in our first equation above:

\[F(4782) = {log(\Phi)^{4782} \over \sqrt{5}} = Some Large Number \]

Well, if you try to find the number using a calculator or compile it on your computer, you'll end up having a compile error that says "Math Error"!

Hope you liked reading this article!

References

The Game of Life

An essay about The Game of Life and it's unpredictable behaviour of creating different yet unique patterns.

Life is full of surprises, isn't it?

We can't state what could possibly happen in the future based on the present events. It's like a pattern but except you don't know what it would turn to be in the end.

This is what the Cambridge Mathematician John H. Conway must have thought about when he invented the Game of Life, who was really interested in Cellular Automaton, a field of mathematical research, that is often used in the earlier days to simulate systems in real world scenario.

His work was influenced by Hungarian-American Mathematician John von Neumann, who aimed to build a machine that had the ability to self-replicate itself and thus, Conway became successful when he was able to simplify Neumann's ideas using a mathematical model that he had discovered.

I'd like to share a quote that I found really inspiring:

"You know, people think mathematics is complicated. Mathematics is the simple bit. Its the stuff we can understand. Its cats that are complicated. I mean, what is it in those little molecules and stuff that make one cat behave differently than another, or that make a cat? And how do you define a cat? I have no idea." - John H. Conway

What is Game of Life?

It's a zero-player game on a two-dimensional grid of squares that has no winners or losers except a certain set of simple mathematical rules that achieves an unpredictable behavior of whether a pattern (or population) will die, become stable or grow out of control.

According to the Wikipedia article, these are the following rules:

  1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overpopulation.
  4. Any dead cell with exactly three neighbours becomes a live cell, as if by reproduction.

This is one of the simplest examples of a self-organizing system. I find it really interesting as how unique yet different patterns emerge from a simple set of rules and might be considered as a form of mathematical beauty. However, did this help mathematicians or scientists to understand the diversity of life that has evolved on earth? Perhaps, but I do believe that Mother Nature is far more complicated than that. However, it did help me realize that I have to study and understand different patterns and behaviours in order to build complex systems.

Studying the behavior of cells or animals using a simple set of rules can help understand how things really work and this influences scientists and engineers to come up with brilliant solutions to solve existing problems in this world.

For example, studying the intelligent behavior of ants being able to build complex ant colonies, trying to understand the cause of traffic congestions and how to prevent them (which I will be talking about in another post), finding the cure for cancer and many other human diseases and so on.

Well, the point that I'm trying to make is, perhaps, the solution to all of today's current problems could be hidden inside the patterns of this simple game.

Hope you enjoyed reading this article!

Adios Amigo!

References

UI Design Pattern: Edit-in-Place

I implemented a design pattern that could help my team edit content on-the-fly instead of having to navigate through a sea of web pages in a separate portal.

Two weeks ago, I was thinking of making an improvement on my company website's custom-built Content Management System (CMS) in order to make it easier for my team to edit and push content with ease.

As a matter of coincidence, I came across a book named Designing Interfaces: Patterns for Effective Interaction Design by Jennifer Tidwell, which contains several User Interface and Interaction Design patterns that inspired me to implement one of the patterns that I had discovered in the book, "Edit-in-Place".

What's Edit-in-Place?

It's like a tiny WYSIWYG text-editor that allows users to change the text directly on top of the original text instead of going through a separate portal or dialog box.

Why did I build it?

The fact that my team has to navigate through a sea of pages in the CMS to edit content is annoying and sometimes, it could be just opening a lot of new tabs on the browser. Hence, a feature like this would allow them to edit content "on-the-fly" with zero navigation.

Below, I have made an implementation of it using Javascript and an experimental design for my blog.

How to use Edit-in-Place:

  • Hover on top of any text element.
  • Double-click on the selected element.
  • Click Save to save changes.
  • Click Cancel to cancel changes.

The book claims that Flickr is one of them who implemented this feature, you can find this feature in most modern Content Management Systems like Wordpress, Joomla or Drupal or a better example, you have used this feature while renaming a file on your computer.

However, there are some limits to this i.e. you can only apply this feature on dynamic webpages as you'll have to write a few additional lines of AJAX that sends a POST request to your server to reflect the saved changes on your database.

Hope you guys found this article useful!

Credit

Icons used are from www.flaticon.com is licensed by CC 3.0 BY