So, about this viral maths birthday problem …

Here’s a warm up joke:

Three logicians walk into a bar. The bar tender asks “Do all of you want a drink?”

The first logician says, “I don’t know.”

The second logician says, “I don’t know.”

The third logician says, “Yes!”

The following question went viral on Facebook. It had a sensationalising title: “Primary 5 [11 year old] mathematics question”, which later turned out to be incorrect as it was actually a Secondary 3 [15 year old] maths olympiad question.

I didn’t give much though to this question when I first saw it because I have seen such questions before so it wasn’t something new. But someone shared this with me in a private chat and so I thought might as well write a short blog post about how I solved it.

math1e

Continue reading So, about this viral maths birthday problem …

Manacher Algorithm

This post tries to explain the idea behind Manacher’s algorithm. It is written mainly for my own future reference so it might lack some clarity. I might improve upon it in the future when I have the time.

Introduction

Manacher’s algorithm is a O(N) solution for finding the longest palindromic substring of a given string.

A palindrome is a sequence of symbols or elements that reads the same forward or reversed.

It is a dynamic programming problem. We let dp[i] be the longest palindrome length for the palindrome that is centered at character i. We use a bottom up approach and fill the table dp. After that we find the maximum value in dp and retrieve the substring.

The transformation (preprocessing)

A clever trick to avoid splitting cases for odd and even as well as boundary checks is to transform the given string into one with delimiters added in between each character.

abacabb \mapsto \#a\#b\#a\#c\#a\#b\#b\#

preprocess

 

This will help us easily identify our palindrome because in our transformed string, the longest palindrome must start and end on a delimiter, and this maps nicely back to the index of the original string, providing an easy way to extract the substring. For example, to extract the palindrome bb, we note that it is a palindrome about index 12, and the left and right limits are 10 and 14 respectively. Dividing it by 2 gives us the indices of the original string, 5 and 7. And we can extract the substring by using s.substring(5,7).

The crux

The crux of the algorithm is noting that after calculating some dp[k] , we can save calculations of dp[n] for k < n \le k + dp[k] .

To see why. Let us denote the indices of left limit of the palindrome as L, right limit as R, and the center as C. Let T be the transformed string. Then let C = T[k], L = T[k-m], R = T[k+m] where m is the range on either side of the palindrome centered at C.

Suppose we are now calculating dp[i] where i is between C and R. There are two cases for this palindrome that is centered at i. Either it extends past R or it doesn’t. Suppose it doesn’t extend past R. Then by looking at the reflected point about C, that is dp[2C – i], we know that the palindrome centered at that point must not extend past L either. Therefore, dp[i] = dp[2C-i]. In the other case, the palindrome extends beyond R so we have to manually calculate the length of this palindrome centered at i. However, we can speed up this calculation by noting that since this extends past R, it’s length must be at least R-i, so we can start comparing characters after that distance.

This translate into code by setting dp[i] = min(dp[2C-i], R-i) and then updating dp[i] by trying to extend the palindrome.

Hiding your birthday on facebook

We share many information on Facebook, such as name, country, date of birth, and other details, personal or not. After all, Facebook wants to make the world more open.

However, I believe that there are still legit reasons for people to keep certain information to themselves. Sometimes, it’s an obvious judgement of whether certain information should be available (to friends) or not, but some other times, it is less clear. One such information that this post is concern about is birth date. Birth date is something that is not guarded against that strongly. After all, you share that information with your close friends, and it is on most identification card (to check if you’re legal to buy alcohol). As a result, most people are willing to share their birth date online, and may not be aware (or don’t really care) that they are making it accessible to people who are less than close friends.

What’s the harm there, you might ask. The risk here is possible identity theft. Some services try to authenticate you by asking you to verify your birth date (among other things, which can also be stolen in a similar manner). Some password recovery system for online services and call centers comes to mind.

That’s silly, I hear you say. But sometimes we willingly use our birth dates as an authentication method. For example, when choosing a memorable pin, birth date is a perfect candidate! (I’m sure most readers would have used their birth dates as their phone unlock PIN at least once). It’s all about risks, weighing the cost and benefits of using complex PINs.

A research was done on the distribution of 4-digit PINs, which shows that PINs are not as random as they should be. The following diagram shows the distribution of 4-digit PINs, the x-axis is for the first two digits, while the y-axis is for the last two digits.

pin

What readers would notice is that the dark regions, which represents high frequency, are not randomly distributed. For instance, we see that the dark vertical line corresponds to 19xx where xx is from the range 40 to 99. One might guess that it corresponds to birth year. The next observation is that at the bottom left there is a dark corner, almost like an L-shape. Here we see the boundaries are 30 and 12, corresponding to the number of days and months. It is not too far fetched to conclude that users probably use their birth dates as their PINs.

Would you make your PIN accessible to your friends (or acquaintances) on Facebook? If the answer is no, then it is sensible that people shouldn’t readily reveal their birth date on Facebook.

So I started a journey to try and make it harder for people who didn’t know me well to figure out my birth date. It starts with setting the visibility of birth date to “only me”. But I realised even without explicitly stating my birth date, an intelligent person might browse through my news feed and find out when people sent birthday greetings to me, hence deduce my birth date. (I have tried this one some of my Facebook friends and have successfully inferred their birth date despite not having direct access to that information on their “about” page.) So the next sensible thing to do in this endeavour is to hide those posts.

Annoyingly, Facebook doesn’t have the feature for people to hide multiple posts, and I wasn’t going to click through hundreds of birthday wishes just to hide them. So I decided to use some javascript to automate that process.

The first step is to load jQuery, which is simple enough. Once I got jQuery, it’s a matter of selecting all the posts that have birthday greetings, such as “happy birthday”, “HAPPY BIRTHDAY”, etc, and simulate mouse clicks to change the visibility from allowed to hidden. The code that does that is described bellow.

$(".pam ").each(function(x) {
    // test is the content of the wall posts
    var test = $(this).text();
    if (test.indexOf("birthday") >= 0 || test.indexOf("BIRTHDAY") >= 0 || test.indexOf("bday") >= 0 || test.indexOf("Birthday") >= 0) {
        // t2 is the edit button which brings out the menu
        var t2 = $(this).children().children().children().children().last().children().children().last().children();
        // check if it's currently allowed on timeline
        if (t2.attr("aria-label")!==undefined && t2.attr("aria-label").indexOf("Allowed") >= 0) {
            if(t2[0].click !==undefined) 
                t2[0].click()
            var n_id = t2.attr("aria-owns");
            // t3 is the button that says hide from time line
            var t3 = $($('#' + n_id).children().children().children()[2]).children()
            // check if it really is that button, or it might be a delete button, in that case the length is zero
            if(t3.length>0 && t3[0].click !==undefined) {
                t3[0].click()
            }
        }
    }
})

So after coming up with this tweak, I managed to make most posts about birthday wishes hidden from my time line. There are of course some hiccups along the way. For instance, finding the criteria for such posts proved to be not as trivial as searching for the word “birthday”. Some people might say “happy x-th” instead, but those are easy to spot from a list of circular icons and can be manually rectified later.

bday

One thing to mention here is the posts are not lost, they are still visible when I look through my own time line – so I can look back and reminisce on people sending me wishes. But at least it is currently more difficult to know my birth date without asking me.

The trade off between privacy and convenience is inevitable. In making my birth date private, I have made it difficult for people to send me birthday wishes on my birthday (without Facebook reminding them to do so). But I think I can make do without that social contract, and not make people feel bad by giving them an excuse – “because Facebook didn’t remind me to”. Similarly, I stopped posting birthday wishes on Facebook because I would be hypocritical to do that. This is probably also a good way to filter your friends to people who actually bother to remember your birthday. But readers be warned, you might not like what you learn.

To conclude, this method illustrates the usefulness of knowing some programming languages to automate mundane tasks such as the one I was trying to complete. It is a simple modification to change it to hide posts that meet some other conditions, or even like all posts from a person! (way to show that you actually appreciate their posts)

Interesting sequence catalan

[This was found in my stack of loose notes from May 2013]

Consider the following problems

  • Number of plane binary trees with n end points
  • Number valid k-ary parenthesis for a string of n characters?
  • Sequence of X and Y such that no initial segment of the sequence has more X than Y.
  • Number of path P in the (x,y) plane from (0,0) to (n-1,0) using steps (1,k), where k+1 in S or k = -1, with a total of m-1 steps of the form (1,-1) such that P never passes below the x-axis.
  • Number of dissections of a convex (m+1)-gon C into n-m regions, each a k-gon, by drawing diagonals that don’t intersect in their interiors

All these problems can be solved by the sequence known as the Catalan number. The first few numbers in the sequence are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

It can be computed using this formula:

equation

 

Or by the recurrence relationpasted_image001

 

 

 

Functional programming languages

When I first came across the functional paradigm, I thought that it sounded very cool and hip because other paradigms were too mainstream.

But when asked in several occasions to explain it, I found difficulty in conveying the essence of what it means to be a functional language. So I have decided to sit down and examine this issue.

While mainly emphasized in academia (standard ml, haskell), there have been many uses in the real world. Jane Street uses OCaml, some financial institutions use q. Many non-functional languages even support functional paradigm. In C++11 for instance, lambdas are introduced.

So what is a functional language? Firstly, a functional language is mostly pure. That is, given the same input, the function will always return the same output. This is similar to the mathematical definition of a function. Other forms of programming paradigm sometimes use function to mean a subroutine – jumping out of sequential execution to execute a block of code – and this may not be pure because the block might have some side effects such as modifying a global variable. Such pureness can lead to optimisations such as running code in parallel and memoization, which are attractive now that Moore’s law is arguably no longer true and people are looking at other ways to improve performance.

Secondly, a functional language will most likely have first class functions which means that functions are treated as values which can be returned by a function or passed around (to other functions). This is supported in most scripting languages like javascript, python, etc. Personally, I think this is a sensible way programme. Compare

for (int i = 0; i < Thing.length; i++) {doStuff(i)}

with

Thing.forEach(doStuff)

However, this comes at a cost because extra indirection is needed to treat functions as values.

I am not a big advocate of functional languages, but I think that a functional paradigm is inherently very elegant and neat (also readable) and this should be encouraged if it is the most natural way to write code for a use case.