Word in string challenge

Problem statement
We say that a string, s, contains the word hackerrank if a subsequence of the characters in s spell the word hackerrank. For example, haacckkerrannkk does contain hackerrank, but haacckkerannk does not (the characters all appear in the same order, but it’s missing a second r).

More formally, let p_0, p_1, \dots, p_9 be the respective indices of h, a, c, k, e, r, r, a, n, k in string s. If p_0 \textless p_1, \textless p_2 \dots \textless p_9 is true, then s contains hackerrank.

You must answer q queries, where each query i consists of a string, s_i. For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Input Format
The first line contains an integer denoting q (the number of queries).
Each line i of the q subsequent lines contains a single string denoting s_i.

Output Format
For each query, print YES on a new line if s_i contains hackerrank; otherwise, print NO instead.

Sample Input 0

Sample Output 0

Solution

 

Recursive Digit Sum challenge

Problem statement
We define super digit of an integer x using the following rules:

  • If x has only 1 digit, then its super digit is x.
  • Otherwise, the super digit of x is equal to the super digit of the digit-sum of x. Here, digit-sum of a number is defined as the sum of its digits.

For example, super digit of 9875 will be calculated as:

You are given two numbers n and k. You have to calculate the super digit of P.

P is created when number n is concatenated k times. That is, if n = 123 and k = 3, then P=123123123.

Input Format
The first line contains two space separated integers, n and k.

Constraints
1 \le n \textless 10^{100000}
1 \le k \le 10^{5}

Output Format
Output the super digit of P, where P is created as described above.

Sample Input 0

Sample Output 0

Explanation 0
Here n=148 and k=3, so P=148148148.

Sample Input 1
recursive-digit-sum-input-1

Sample Output 1
recursive-digit-sum-output-1

Solution

 

Random video chat website using WebRTC

Seing as how many people are interested in my video-conference-webrtc project, I have decided to develop a random video chat website using WebRTC. The project is called rtcrandom and is hosted on GitHub. A live demo is also available at test.tengmo.chat.

Pitch

RTCRandom is an online (video)chat website that allows users to socialize with others without the need to register. The service       randomly pairs users in one-on-one chat sessions where they chat anonymously using the names “You” and “Stranger”.

For the project I have used GitHub for my online project hosting service using Git, issue tracking, collaboration and wikis. Node.js and JavaScript are the main programming languages used for development. For continuous integration I am using Jenkins with OpenShift as my hosting service. The wiki is available here.

I not going into great detail explaining the code. I will rather give you a brief overview on how rtcrandom works and leave the pleasure of examining the code to you.

Back-End
For the back-end Node.js is used with Express as the web application framework. I used winston for logging and EJS as the templating language for the views.

Front-End
For the front-end simple HTML with JavaScript (jQuery, socket.io) and CSS is used. In order to add WebRTC support for browsers like Safari (which does not support WebRTC yet) I have used the Temasys WebRTC adapter. If you do not wish to use such an adapter see release v0.1-alpha.

Main components
On the back-end the main component is server.js and on the front-end the magic happens in public/js/room.js, which is loaded by the views/room.ejs view.

How does the matching work
When a client first loads the page a bidirectional event-based communication is created between the client’s browser and the back-end using socket.io. I call this the default communication channel. The default communication channel is used by the client to let the server know, that the client wants to find a new chat partner etc. It also allows the server to inform a client about a new chat partner etc.

So once a client wants to find a new (or initial) communication partner he triggers a next event through the default communication channel, letting the server know about its ID and that he wants a new chat partner. The ID is a random hash that is generated once on client-side. The server then puts the client’s request into a queue and checks if the queue has at least two requests (note: no client is put twice in the queue). If at least two requests are in the queue (one from a different client and one from our current client), the two clients are polled from the queue. The server then generates a random room name (a random six digit alphanumeric string) and sends it to the two clients via the default communication channel.

Once each client receives the new room name, they send a message to the server via the default channel that they want to join the room. The client whose message arrives first at the server creates and joins the room and the second client simply joins the new room. The peer that simply joins the new room gets notified by the server that it just joined, so that it can broadcast the message to the default channel saying that it is a new participant that joined the room and wants to receive a WebRTC offer to open up a peer-to-peer WebRTC communication with the other client in the room (the one that created the room). The room creator then receives the new participant message in the default channel and creates an offer for the joining peer. This offer will be send via a private communication channel which both clients open using the room name as namespace. The room creator then sends the offer through this channel, which the other peer receives and responds to with an answer. Further WebRTC related communication messages to build the WebRTC peer-to-peer connection between the two clients are also exchanged through the private channel. Once a peer-to-peer connection is establish the video stream and chat messages are exchanged directly between the two clients (no server required).

Note: when a peer disconnects from one peer (e.g. because it wants to chat with a different person) the disconnect event is not immediately received by the other peer, due to WebRTC delays. This is why the disconnecting peer also sends a disconnect notification message to the other peer via the private channel, so that it can update its view. The notification is send using the private channel because it tends to be faster than waiting for the WebRTC notifications.

The source code is available here. A live demo is available at test.tengmo.chat.

 

Crossword Puzzle challenge

Problem statement
A 10 \times 10 Crossword grid is provided to you, along with a set of words (or names of places) which need to be filled into the grid. The cells in the grid are initially, either + signs or - signs. Cells marked with a + have to be left as they are. Cells marked with a - need to be filled up with an appropriate character.

Input Format
The input contains 10 lines, each with 10 characters (which will be either + or - signs).
After this follows a set of words (typically nouns and names of places), separated by semi-colons (;).

Constraints
There will be no more than ten words. Words will only be composed of upper-case A-Z characters. There will be no punctuation (hyphen, dot, etc.) in the words.

Output Format
Position the words appropriately in the 10 \times 10 grid, and then display the 10 \times 10 grid as the output. So, your output will consist of 10 lines with 10 characters each.

Sample Input 0

Sample Output 0

Sample Input 1

Sample Output 1

Solution

 

Password Cracker challenge

Problem statement
There are N users registered on a website CuteKittens.com. Each of them have a unique password represented by pass[1], pass[2], \dots, pass[N]. As this a very lovely site, many people want to access those awesomely cute pics of the kittens. But the adamant admin don’t want this site to be available for general public. So only those people with passwords can access it.

Yu being an awesome hacker finds a loophole in their password verification system. A string which is concatenation of one or more passwords, in any order, is also accepted by the password verification system. Any password can appear 0 or more times in that string. He has access to each of the N passwords, and also have a string loginAttempt, he has to tell whether this string be accepted by the password verification system of the website.

For example, if there are 3 users with password {abra, ka, dabra}, then some of the valid combinations are abra (pass[1]), kaabra (pass[2]+pass[1]), kadabraka (pass[2]+pass[3]+pass[2]), kadabraabra (pass[2]+pass[3]+pass[1]) and so on.

Input Format
First line contains an integer T, the total number of test cases. Then T test cases follow.
First line of each test case contains N, the number of users with passwords. Second line contains N space separated strings, pass[1] pass[2] \dots pass[N], representing the passwords of each user. Third line contains a string, loginAttempt, for which Yu has to tell whether it will be accepted or not.

Constraints
1 \le T \le 10
1 \le N \le 10
pass[i] \ne pass[j], 1 \le i \textless j \le N
1 \le length(pass[i]) \le 10, where\ i \in \left[1,N\right]
1 \le length(loginAttempt) \le 2000
loginAttempt and pass[i] contains only lowercase latin characters (‘a’-‘z’).

Output Format
For each valid string, Yu has to print the actual order of passwords, separated by space, whose concatenation results into loginAttempt. If there are multiple solutions, print any of them. If loginAttempt can’t be accepted by the password verification system, then print WRONG PASSWORD.

Sample Input 0

Sample Output 0

Explanation 0
Sample Case #00: wedowhatwemustbecausewecan is the concatenation of passwords {we, do, what, we, must, because, we, can}. That is

Note that any password can repeat any number of times.

Sample Case #01: We can’t create string helloworld using the strings {hello",planet`}.

Sample Case #02: There are two ways to create loginAttempt (abcd). Both pass[2] = "abcd" and pass[1] + pass[3] = "ab cd" are valid answers.

Sample Input 1

Sample Output 1

Solution
We can solve this problem recursively and use memoization to avoid running out of time. The basic algorithm goes as follows:
– Iterate over all indices i of loginAttempt:
– Split loginAttempt into two parts left = loginAttempt.substring(0,i) and right = loginAttempt.substring(i).
– Call isValid(left) and isValid(right).
– If both calls return true, then loginAttempt is valid.

Full code

 

How to setup Let’s Encrypt (SSL) Certificate on OpenShift

In previous posts I have described how to deploy a Node.js application to OpenShift. Now its time to add a custom alias to our Node.js application so that it is accessible through a custom domain, like test.testnode.com. Currently it is accessible only through testnode-lukesnode.rhcloud.com. Off course we also want valid SSL certificates for our custom domain testnode.com. For that we need to get a certificate (a type of file) from a Certificate Authority (CA). Let’s Encrypt is a free, automated, and open certificate authority brought to you by the non-profit Internet Security Research Group (ISRG). So obviously we will use that.

Create alias via OpenShift web console
From the Applications section choose your application (e.g. testnode) and then click on change alias. For Domain Name enter your custom domain. Mine is test.testnode.com. Leave the rest of the fields blank and click Save.

To successfully use this alias, you must have an active CNAME record with your DNS provider. The alias is test.testnode.com and the destination app is testnode-lukesnode.rhcloud.com.

My provider is united-domains.de. So I went ahead, logged in and under Subdomains -> New Sub Domain I have created a new subdomain test.testnode.com. Then under DNS Configuration for test.testnode.com, I was able to set the CNAME record to rtcrandom-lukesnode.rhcloud.com for *.test.testnode.com (test.testnode.com included).

And thats it!

Create certificates
We will need a valid certificate and its corresponding private key to upload to OpenShift for the new domain test.testnode.com. Under Mac OS X I have used certbot. So go ahead and install certbot:

Once installed run:

OK, that didn’t work. Obviously Let’s Encrypt wants us to prove that we are the truthful owners of test.testnode.com. The way it verifies ownership is trying to load the above URL (http://test.testnode.com/.well-known/acme-challenge/p1zEUvrrpAuTgj-b1bBk0zt9ypOn-BeLJWmxDi2xWXQ) and compare the received result with the expected result.

We need to modify our Node.js application to return the hash Let’s Encrypt requires when the above URL is GET. In my router.js I have added the below code snippet:

The above code reads the hash from the requested URL and returns it. OK, lets try it one more time.

Hmmmm, that didn’t work either. At this point I should probably read the manual. But apparently when the URL http://test.testnode.com/.well-known/acme-challenge/xxxxxxxxxxx is requested, it expects xxxxxxxxxxx.yyyyyyyyyyy as a result. So I went and modified my router.js again:

Giving it a try again, I finally got my certificates:

The generated certificate and private key is located under /etc/letsencrypt/archive/test.testnode.comc/cert1.pem and /etc/letsencrypt/archive/test.testnode.com/privkey1.pem respectively.

Upload certificates to OpenShift
For this we will use the OpenShift client tools:

Thats it! Our application is now accessible through https://test.testnode.com.

 

Reading SPIEGEL Plus articles

DISCLAIMER: The information below is for information purposes only.

I happened to be browsing on SPIEGEL Online the other day and noticed that articles published for non SPIEGEL Plus subscribers were still partially available on the article’s page in readable form while the largest portion of the text was blurred out and available only for paying subscribers.

So the first thing I did was to take a closer look at the blurred out text (which was just underneath an overlay with a CSS filter style). I noticed that the text structure was resembling an ordinary paragraph style (if I can express it like that), with the words just being gibberish:

In the above example you can see that the letter ‘/’ is used three consecutive times or that it is often followed by a space. This made me think that ‘/’ may be a replacement for the character ‘.’.

Another fun fact is that SPIEGEL Plus articles are only partially encrypted so that the reader can develop an interest for the article and then hopefully (for them) decide to buy it. The particular article that I happen to be reading was an interview like article, where SPIEGEL interviewed a guy named Butter, with SPIEGEL asking a question and Butter answering it. Fortunately for me this was a repeating pattern with participant names being styled in bold text in both the plain and encrypted text for easy detection. I could easily see that SPIEGEL: was always matching to TQJFHFM; and Butter: to Cvuufs; in the cipher text. Using this I could easily see that the letter ‘E’ was matching to ‘F’, ‘e’ to ‘f’, ‘:’ to ‘;’…

This made me think that this cipher was nothing more than a simple substitution cipher where each letter in the original message is replaced with some other predefined letter. Taking a look at the following ASCII table one can easily see that the ASCII code x of the plain text character has been replaced with the character represented by the ASCII code x+1: ‘E’ (ASCII 69) has been replace with F (ASCII 70), etc.

This cipher is also known as Caesar cipher. Anyhow, I thought it might be fun to write a small Firefox extension that I can use to view those articles. The extension basically removes the blurring overlay and replaces the encrypted text with their plain text version.

The source code is available here. If you don’t know how to temporary install a Firefox extension you can refer to this guide.

 

Adding version number in Node.js app using Jenkins/OpenShift deploy

In a previous post I have illustrated how to deploy a Node.js app to OpenShift from a private GitHub repository using Jenkins.

It is often the case that you want to display the revision of the current code deployed in your test environment so you can quickly see if the running version of your app uses the latest code base. In my opinion this is a task for your build tool (such as Ant, Maven, Gradle, etc) or your automation server such as Jenkins.

I want to keep the following information in a file called version.txt and serve it when a user tries to GET it. Since I am using express, all I have to do in order to serve static files is the following:

Now, all I have to do is tell Jenkins to create the file version.txt, fill it with the necessary information and save it under public in my app’s deployment directory on the OpenShift server. You can find out the OpenShift deployment directory using the predefined environment variable $OPENSHIFT_REPO_DIR:

As we saw in OpenShift’s Jenkins configuration, a shell command is executed that deploys our Node.js application. So go ahead and navigate to YOUR_PROJECT_NAME -> Configuration. Scroll down where it says Execute Shell. This field already contains a bunch of shell commands. Append the following:

And thats it! The next time Jenkins builds your project, it will execute the above shell command which will in turn create a version.txt file and place it under public in you Node.js app. You can then access it via https://testnode-lukesnode.rhcloud.com/version.txt:

 

Cipher challenge

Problem statement
Jack and Daniel are friends. They want to encrypt their conversation so that they can save themselves from interception by a detective agency. So they invent a new cipher. Every message is encoded to its binary representation B of length N. Then it is written down K times, shifted by 0,1,\dots, K-1 bits.
If B=1001010 and K=4 it looks so:

Then calculate XOR in every column and write it down. This number is called S. For example, XOR-ing the numbers in the above example results in

Then the encoded message S and K are sent to Daniel.

Jack is using this encoding algorithm and asks Daniel to implement a decoding algorithm.
Can you help Daniel implement this?

Input Format
The first line contains two integers N and K.
The second line contains string S of length N+K+1 consisting of ones and zeros.

Output Format
Decoded message of length N, consisting of ones and zeros.

Constraints
1 \le N \le N^{6}
1 \le K \le N^{6}
|S| = N + K - 1
It is guaranteed that S is correct.

Sample Input#00

Sample Output#00

Sample Input#01

Sample Output#01

Explanation
Input#00

Input#01

Solution

 

Sansa and XOR

Problem statement
Sansa has an array. She wants to find the value obtained by XOR-ing the contiguous subarrays, followed by XOR-ing the values thus obtained. Can you help her in this task?

Note: \left[5,7,5\right] is contiguous subarray of \left[4,5,7,5\right] while \left[4,7,5\right] is not.

Input Format
First line contains an integer T, number of the test cases.
The first line of each test case contains an integer n, number of elements in the array.
The second line of each test case contains n integers that are elements of the array.

Constraints
1 \le T \le 5
2 \le n \le 10^{5}
1 \le numbers\ in\ array \le 10^{8}

Output Format
Print the answer corresponding to each test case in a separate line.

Sample Input

Sample Output

Explanation
Test case #00:
 1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = 2

Test case #01:
 4 \oplus 5 \oplus 7 \oplus 5 \oplus (4 \oplus 5) \oplus (5 \oplus 7) \oplus (7 \oplus 5) \oplus (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7 \oplus 5) \oplus (4 \oplus 5 \oplus 7 \oplus 5) = 0

Solution
We will solve our problem based on the fact whether n is even or odd.

n is even
First we will consider the case when n is even. For each x in the array we know that it appears 1 times by its own and n-1 times with the other numbers in the array during the XOR equation (see explanation above). Consider for example the following array:

\left[4, 5, 7, 5\right]

We will consider the two 5‘s as different. So we just rewrite the array as follows:

\left[4, 5, 7, 5^{*}\right]

Then, 4 will appear once by its own and n-1 times within the other subarrays: 4 \oplus (4 \oplus 5) \oplus (4 \oplus 5 \oplus 7) \oplus (4 \oplus 5 \oplus 7 \oplus 5^{*}).

Similarly for 5. It will appear once by its own and n-1 times within the other subarrays: (4 \oplus 5) \oplus 5 \oplus (5 \oplus 7) \oplus (5 \oplus 7 \oplus 5^{*}).

7 will also appear once by its own and n-1 times within the other subarrays: (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7) \oplus 7 \oplus (7 \oplus 5^{*}).

5^{*} will also appear once by its own and n-1 times within the other subarrays:  (4 \oplus 5 \oplus 7 \oplus 5^{*}) \oplus (5 \oplus 7 \oplus 5^{*}) \oplus (7 \oplus 5^{*}) \oplus 5^{*}.

Since n is even and every integer 4, 5, 7 and 5^{*} appears even times in the XOR equation, the end result of the equation will be 0 when n is even. This can be easily seen by rearranging the XOR equation:

 4 \oplus 5 \oplus 7 \oplus 5^{*} \oplus (4 \oplus 5) \oplus (5 \oplus 7) \oplus (7 \oplus 5^{*}) \oplus (4 \oplus 5 \oplus 7) \oplus (5 \oplus 7 \oplus 5^{*}) \oplus (4 \oplus 5 \oplus 7 \oplus 5^{*}) = (4 \oplus 4 \oplus 4 \oplus 4) \oplus (5 \oplus 5 \oplus 5 \oplus 5) \oplus (7  \oplus 7 \oplus 7 \oplus 7)  \oplus (5^{*}\oplus 5^{*}\oplus 5^{*}\oplus 5^{*}) = 0 \oplus 0 \oplus 0 \oplus 0 = 0

n is odd
For the case when n is odd consider the array \left[1, 2, 3\right].
Then, 1 will appear once by its own and n-1 times within the other subarrays: 1 \oplus (1 \oplus 2) \oplus (1 \oplus 2 \oplus 3).

2 which is located at index i will appear i times with items to its left, once alone, (n-1)-i times with items to its right and once together with all items: (1 \oplus 2) \oplus 2 \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3). Altogether a total of i + 1 + ((n-1)-i) + 1 = n+1 which is an even number of times. An integer that is XORed with its self an even number of times results in 0.

3 will appear once by its own and n-1 times within the other subarrays: (1 \oplus 2 \oplus 3) \oplus (2 \oplus 3) \oplus 3.

In summary for the case that n is odd we only need to XOR items at indices 0, 2, 4, 6, \dots since the elements at those indices appear an odd number of times. XORing an element with its self an odd number of times, results in that same number.

This can be easily seen by rearranging the XOR equation:

 1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = (1 \oplus 1 \oplus 1) \oplus (2 \oplus 2 \oplus 2 \oplus 2) \oplus (3  \oplus 3 \oplus 3) = 1 \oplus 0 \oplus 3 = 2

Full code