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.

$$\mathrm{\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 n^th Fibonacci Number:

$$F(n)=\frac{log(\mathrm{\Phi }{)}^n}{\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:

$$\frac{log(\mathrm{\Phi }{)}^n}{\sqrt{5}}>{10}^{999}$$

Expand the formula a little bit more:

$$n\times log(\mathrm{\Phi })-\frac{log(5)}{2}>999\times log(10)$$

$$n\times log(\mathrm{\Phi })>999\times log(10)+\frac{log(5)}{2}$$

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

$$n=\frac{999\times log(10)+\frac{log(5)}{2}}{log(\mathrm{\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)=\frac{log(\mathrm{\Phi }{)}^{4782}}{\sqrt{5}}=SomeLargeNumber$$

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

• Fibonacci Number Sequence
• Golden Ratio
• Golden Rectangle

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

• The Game of Life by Stanford University

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

Last week, I was migrating my company's website from our in-house IIS Virtual Private Server to a Dedicated Apache Server in order to improve the website's overall performance and handle more traffic efficiently. For those of you who have hosted a website using Microsoft's IIS Manager, you'll know that it makes use of an XML document named web.config file, whereas in an Apache Server, it's an .htaccess file, which is also used to store rules to write clean and friendly URLs.

Converting from .htaccess to web.config is easy as it's a matter of importing the rules directly on IIS Manager's URL Rewrite module but doing the other way around was also possible but only if you did it manually and I really don't want to waste time on such mundane tasks.

How did I convert it?

A little bit of Regular Expressions, a dash of Javascript and an understanding on how Apache's *mod_rewrite* works, I decided to build a tool that converts web.config to .htaccess format.

How to use this converter:

• Paste your web.config XML code on the textfield
• Hit "Convert" to convert to .htaccess format
• Please use a valid XML format before converting your code

Code snippet:

//web.config to .htaccess converter
function webConfigToHtaccess()
{

    // Take input from textarea
    // and parse it into XML

    var xml = $("#webconfig-xml").val(), 
    xmlDoc = $.parseXML(xml), 
    $xml = $(xmlDoc);


    // - Inside each "rule", look for the "action" child node
    // - If it contains multiple parameters, follow the 
    // regular expression pattern: /{R:(d{1})}/
    // - Replace that pattern with a dollar sign and it's parameter
    // - Append "RewriteRule" along with the url and it's rules

    $xml.find('rule').each(function(){
        var str = $(this).find("rule>action").attr('url');
        var regex = /{R:(d{1})}/;
        while(regex.test(str))
        {
            str = str.replace(regex, '$' + RegExp.$1);
        }

        $("#htaccess-code").append("RewriteRule " + $(this).find("rule>match").attr('url')
            + " " + str + "<br>"
        );
    });
}

Although, I can't really say that it's perfect because I had to make some changes but hey, it's just minor changes and yes, it did save me a lot of time!

Hope you found this article useful!

Have you ever downloaded minimal and beautiful looking SVG icons and added them into your HTML code as an <img> instead of <svg> tag? The answer is: "yes, you're right!".

Okay, how about another question?

What would you do if you want to change all of those SVG icons to black, red or blue? Your answer would be: "Well, I would edit the colors of all the vector images in Adobe Illustrator and then refresh my page to see the changes.", if that's your answer, then what would you do if you have to do it for multiple icons in multiple pages in a short amount of time?

Two weeks ago, I faced this same scenario and I found a quick solution to it and I will be sharing it in this article on how to convert SVG from image to code using Javascript and how it allowed me to play around with attributes and properties.

Why convert from Image to Code?

Well, as a developer, it allows me to interact with every part of the SVG such as changing the colors, adjusting the height and width, animate it and so on. In this article, I will show you an example on how I could do a simple color change on an SVG image that I had downloaded from flaticon.

How to convert from Image to Code?

Simple, just convert the SVG image into an XML format using XMLSerializer() then give it a class name like "custom-svg-icon" and execute the code! Below, I have provided a code snippet, I hope the comments will help you out!

Code snippet:

    $(function(){
     //Change the class name, if it has to be applied for more SVG elements
     jQuery('img.custom-svg-icon').each(function(){
     var $img = jQuery(this); // The image
     var imgID = $img.attr('id'); // ID attribute
     var imgClass = $img.attr('class'); // Class Name
     var imgURL = $img.attr('src'); // URL of the SVG image

     jQuery.get(imgURL, function(data) {
     //The data param contains the XML data of the SVG image
     //alert(new XMLSerializer().serializeToString(data));

     // Get the SVG tag, ignore the rest
     var $svg = jQuery(data).find('svg');

     // Give the image's ID to the SVG
     if(typeof imgID !== 'undefined') 
     {
     $svg = $svg.attr('id', imgID);
     }

     // Give the image's class to the SVG
     if(typeof imgClass !== 'undefined') 
     {
     $svg = $svg.attr('class', imgClass+' replaced-svg');
     }

     // Remove any invalid XML tags as per http://validator.w3.org
     $svg = $svg.removeAttr('xmlns:a');

     // Check if the viewport is set, else we gonna set it if we can.
     if(!$svg.attr('viewBox') && $svg.attr('height') && $svg.attr('width')) 
     {
     $svg.attr('viewBox', '0 0 ' + $svg.attr('height') + ' ' + $svg.attr('width'))
     }

     // Replace image with new SVG
     $img.replaceWith($svg);

     }, 'xml'); //Returns as XML
     });
    });

Give it some custom CSS to change the color and width of the SVG image:

    svg path, svg rect
    {
        fill: #ff5a5f;
    }

    .custom-svg-icon
    {
        width: 170px;
        height: 170px;
    }

Right-click on the image, hit "Inspect Element" and view the converted image below but this time, you'll see it as an SVG element:

However, there are a few downsides to this as SVG code is hard to maintain, pretty messy and sometimes quite complex especially if it contains a lot of paths, circles and rectangles but in a scenario that is similar to what I have faced, I think it's pretty useful, otherwise, just stick to adding your SVG images using the <img> tag.

Hope you have found this article useful!

Credit

Icons made by Eucalyp from www.flaticon.com is licensed by CC 3.0 BY

Hello Folks!

Happy New Year! I know I'm late at this point but hey, it's better late than never!

As the year had begun, I got busy with work and I barely found any time to post anything new but that doesn't mean I didn't do anything new.

At the end of December, I decided to get back on solving algorithmic and programming puzzles again (The last time I did was back on 2016) and for starters, I decided to solve Project Euler problems by adding a new programming language to my tech arsenal, Python.

Why solve it using Python?

Previously, I'd solved around 57 problems using C++ and it got paused for a while after I got into internships and work life. But now that I have found the time for it, I thought that this would be the perfect opportunity for me to learn Python. It has a really good community, good documentation and the code looks so clean, simple and readable without those curly brackets!

What is Project Euler?

It's a website that hosts a series of challenging algorithmic and mathematical programming puzzles in which you will have to produce solutions that'd clock in under a minute with decent computer specifications.

By solving these puzzles, you will be experiencing an inductive chain learning i.e. when you solve one problem, you'll be exposed to a completely new concept that allows you to delve into unfamiliar areas of mathematics and programming.

As I'm writing this article, I'm taking it slow and I have solved around 21 problems in 3 weekends. I will be posting a walkthrough for each problem but for now, I will talk about one of my favorite problems: Maximum Path Sum.

Maximum Path Sum

Problem definition of Problem 18:

By starting at the top of the Binary Tree below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23. Now, find the maximum total from top to bottom of the Binary Tree below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Since there are fifteen rows, you can solve this puzzle using Brute Force by trying every route possible but if you're going to use that same technique for Problem 67 that has a Binary Tree containing one hundred rows, it will not be efficient. So this problem forces you to avoid brute force and instead wants you to come up with a clever solution!

Solution

As I had mentioned above, a brute force technique is going to be very inefficient, instead I did a bottom-up approach:

Implementation of the method(s):

# Sum of numbers
def sumOfNumbers(n):
    return (n*(n+1))/2

# Return the maximum path sum in a Binary Tree
# Bottom Up Approach
def maxPathSum(list):
    # the last number of the list
    last = len(list)

    # number of rows in the Binary Tree
    nrow = 1

    # count the number of rows in the Binary Tree
    # use the sum of numbers method to count the number of rows
    while sumOfNumbers(nrow) < last:
        # print (sumOfNumbers(nrow))
        nrow += 1

    last -= 1

    for i in range(nrow, 0, -1):
        # print list[last - i]

        # iterate through each number in each row
        for j in range(2, i+1):
            # pick a number from the row above the current row
            # and pick the 2 numbers from the current row
            # Find the max between the two numbers and add it
            list[last - i] = list[last - i] + max(list[last - 1], list[last])

            # shift to the next number in the row above
            last -= 1

        # shift to the next number in the row above
        last -= 1

    # return the max sum
    return list[0]

Final code:

# Project Euler: Problem 18 and 67 - Maximum Path Sum I and II

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

num_str = ""

# read text file
f = open("triangle2.txt", "r")
for line in f:
    num_str += line
f.close()

# convert the string numbers to integers in the list
list = map(int, num_str.replace('n', ' ').split(' '))

start = time.time()
print pe_lib.maxPathSum(list)
print "Finished: %f seconds" % (time.time() - start)

The maximum path sum for Problem 67 is 7273 and it compiled in 0.003990 seconds.

*Note: This solution and the library named pe_lib.py was built using the Python programming language. The source code for this solution can be found on Github.*

Stay tuned for more!

This is the eighth challenge of Set 1 in The Cryptopals Crypto Challenges website. Previously, I spoke about these challenges and provided walkthroughs for the previous challenges, if you haven't read them, here are the links:

• The Cryptopals Crypto Challenges
• The Cryptopals Crypto Challenges: Set 1 - Convert Hex to Base64
• Base64 Encoding / Decoding using Bitwise Manipulation in C++
• The Cryptopals Crypto Challenges: Set 1 - Fixed XOR Cipher
• The Cryptopals Crypto Challenges: Set 1 - Single-Byte XOR Cipher
• The Cryptopals Crypto Challenges: Set 1 - Detect Single-Character XOR
• The Cryptopals Crypto Challenges: Set 1 - Implement Repeating-Key XOR
• Hamming Distance Algorithm in C++
• The Cryptopals Crypto Challenges: Set 1 - Break Repeating-Key XOR
• The Cryptopals Crypto Challenges: Set 1 - AES in ECB Mode

For this challenge, you are given a file, which contains a bunch of ciphertexts that has been encrypted using AES-128 Cipher but only one of them has an ECB (Electronic Codebook) mode. Find the string the string that has the ECB mode.

In the previous post, I had explained that ECB is a cipher mode that is used to repeat the key until it covers the entire plaintext i.e. the same 16 byte plaintext will have the same 16 byte ciphertext.

Well, the solution is pretty much trivial, so here's the solution:

Implementation of the method(s):

//Detect ECB Mode in AES Cipher
bool CryptoLib::detect_ecb_mode(string str, int keyLength)
{
    //Divide into equal amount of blocks
    int blocks = str.size() / keyLength;

    /*
        Theory: the problem with ECB as I had mentioned
        in the previous post, it uses the exact number of bytes of the ciphertext
        to encrypt the plaintext repeatedly.

        In that case, just do the reverse.

        Divide it into equal amount of blocks, in this case, we
        know the key is "YELLOW SUBMARINE", which is 16 bytes.

        Then, all you have to do is take two substrings of a string and compare,
        if they have the same string, we found it!
    */
    for(int i=0; i<blocks; i++)
    {
        //Take a substring of x number of bytes
        string strA = str.substr(i*keyLength, keyLength);

        for(int j=i+1; j<blocks; j++)
        {
            //Take another substring of x number of bytes
            string strB = str.substr(j*keyLength, keyLength);
            if(strA == strB)
            {
                //Found
                return true;
            }
        }
    }
    return false;
}

Final code:

//The Cryptopals Crypto Challenges - Set 1 Challenge 8
#include "crypto.h"

int main()
{
    CryptoLib crypt;

    string str;

    ifstream infile;
    infile.open("8.txt");

    int count = 0;
    while(!infile.eof())
    {
        getline(infile, str);

        //Check if this string has ECB mode
        if(crypt.detect_ecb_mode(str, 16) == true)
        {
            cout << "FOUND AT LINE " << count << " => " << str << endl;
            break;
        }
        count++;
    }
}

Note: This solution and the library named crypto.h was built using the C++ programming language. The source code for this solution can be found on Github.

Well, this challenge marks the end of Set 1 from The Cryptopals Crypto Challenges. However, I do intend to continue solving all these crypto challenges, let's see how it goes!

Until next time, then!

This is the seventh challenge of Set 1 in The Cryptopals Crypto Challenges website. Previously, I spoke about these challenges and provided walkthroughs for the previous challenges, if you haven't read them, here are the links:

• The Cryptopals Crypto Challenges
• The Cryptopals Crypto Challenges: Set 1 - Convert Hex to Base64
• Base64 Encoding / Decoding using Bitwise Manipulation in C++
• The Cryptopals Crypto Challenges: Set 1 - Fixed XOR Cipher
• The Cryptopals Crypto Challenges: Set 1 - Single-Byte XOR Cipher
• The Cryptopals Crypto Challenges: Set 1 - Detect Single-Character XOR
• The Cryptopals Crypto Challenges: Set 1 - Implement Repeating-Key XOR
• Hamming Distance Algorithm in C++
• The Cryptopals Crypto Challenges: Set 1 - Break Repeating-Key XOR

For this challenge, you are given a file, which contains a ciphertext that has been encrypted using AES-128 Cipher with ECB (Electronic Codebook) mode and then encoded using Base64. Decrypt it.

In order to decrypt it, you are given a key:

YELLOW SUBMARINE

What is AES?

Advanced Encryption Standard a.k.a Rjindael, which was developed by two belgian cryptographers, Vincent Rijmen and Joan Daemen. Rjindael is a family of ciphers with various block and key sizes.

AES-128 is commonly used but there are also larger key sizes such as 192 and 256 bits. Similar to XOR cipher, it uses the same key to encrypt and decrypt the message. Till date, there isn't any publication that states if whether AES is broken but even if you were to break it, it will take atleast a billion years with a supercomputer, which could beyond the age of the universe.

What is ECB Mode?

What if your plaintext is longer than (in this case, 128 bits) the keysize? This is where ECB comes into the picture. ECB (Electronic Codebook) is a cipher mode that is used to repeat the key until it covers the entire plaintext (similar to Repeating-Key XOR Cipher) and then each block is independently encrypted using the AES algorithm to produce the desired ciphertext.

This challenge is not that hard, in fact, it's completely trivial and more like an introduction of AES Cipher. There are so many ways to solve this problem but I chose to solve this problem using OpenSSL and other commandline tools such as xxd (used to print the hexdump of a file) on my UNIX terminal.

Here's the solution:

openssl enc -aes-128-ecb -d -a -in secret.txt -K $(echo "YELLOW SUBMARINE" | xxd -p) -iv 1 | head

This is the decrypted message:

I'm back and I'm ringin' the bell
A rockin' on the mike while the fly girls yell
In ecstasy in the back of me
Well that's my DJ Deshay cuttin' all them Z's
Hittin' hard and the girlies goin' crazy
Vanilla's on the mike, man I'm not lazy.

I'm lettin' my drug kick in
It controls my mouth and I begin
To just let it flow, let my concepts go

Initially, I was planning to write an implementation of AES for fun, but then I decided to make it a side project that I can work on as there are a lot of things about AES that I'd like to talk about in the future.

Stay tuned for the next challenge!