06/21/16

HackerRank ‘Sherlock and The Beast’ Solution

Short Problem Definition:

Sherlock Holmes suspects his archenemy, Professor Moriarty, is once again plotting something diabolical. Sherlock’s companion, Dr. Watson, suggests Moriarty may be responsible for MI6’s recent issues with their supercomputer, The Beast.

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beastwith a virus; however, he also gives him a clue—a number, . Sherlock determines the key to removing the virus is to find the largest Decent Number having digits.

Sherlock and The Beast

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

I am presenting two solutions. The naive brute force solution executes in O(N) and passes all the tests. Yet further optimisations and a runtime complexity of O(1) are possible.

When observing the possible output space we realise that there can only be 0, 5 or 10 threes in the output. If there would be 15 threes, it is better to use fives instead. The number of trailing threes can therefore be defined by K = 5*((2*N)%3). Let us plug some numbers into the equation:

• 1 -> 5*(2%3) = 10 -> INVALID
• 2 -> 5*(4%3) = 5 -> INVALID
• 3 -> 5*(3%3) = 0 -> 555
• 4 -> 5*(8%3) = 10 -> INVALID
• 5 -> 5*(10%3) = 5 -> 33-33-3
• 8 -> 5*(16%3) = 5 -> 555-33-33-3
• 10 -> 5*(20%3) = 10 -> 33-33-33-33-33
• 15 -> 5*(30%3) = 0 -> 555-555-555-555-555
Solution:
def sherlockBeast(N):
K = 5*((2*N)%3)
if K > N:
return -1
else:
return '5' * (N-K) + '3'*K

if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
print sherlockBeast(n)

def sherlockBeastNaive(N):
if (N < 3): return "-1" three_cnt = N//3 five_cnt = 0 while three_cnt >=0:
rem = N - three_cnt*3
if rem % 5 == 0:
five_cnt = rem/5
break
three_cnt -= 1

if three_cnt <= 0 and five_cnt == 0:
return "-1"

return "555"*three_cnt + "33333"*five_cnt

if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
print sherlockBeastNaive(n)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

06/14/16

Martinkysel.com is now HTTPS

I would like to give a quick shoutout to the folks at Let’s Encrypt that have done a great job at making the web a better place. Do you ask why I care about SSL protected web pages?

Because HTTPS:

• prevents possible intruders from tampering with the communications between this website and you, my fellow readers. Intruders include intentionally malicious attackers, and legitimate but intrusive companies, such as ISPs or hotels that inject ads into pages.
• prohibits intrusions. It is possible to exploit unprotected communications and to trick users into giving up sensitive information or installing malware, or to insert their own advertisements into website resources. For example, some third-parties inject advertisements into websites that potentially break user experiences and create security vulnerabilities. It is probably not my case, but the greater Encrypt the web initiative is a cause worth pursuing.
• protects resources that travel between this website and your browser. Images, cookies, scripts, HTML… they’re all exploitable. Intrusions can occur at any point in the network, including a user’s machine, a Wi-Fi hotspot, or a compromised ISP, just to name a few.

Would you give your PC to a complete stranger in Starbucks and leave? I would not and therefore I will not do the same to my page. I agree that reading some page on the web is different than giving someone access to your Facebook pictures. But is it really? How often do you open web pages over a insecure Wi-fi? Do you trust each and every wire you are connected over?

Letsencrypt is a free SSL certificate authority by the folks from Mozilla, Cisco, Akamai, Facebook and many others. If you own, manage or run a page, give them a try. Make the web a better place.

Without further ado I announce that martinkysel.com is now HTTPS.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

06/10/16

Demystifying Virtual Tables in C++ – Part 2 Non-virtual inheritance

Introduction

In this post we will continue our dive into the C++ dynamic dispatch. So far we have verified that gdb does not create a virtual table for simple classes and default constructors [Part 1 Trivial Constructors].

In part 2 we will look at non-virtual derived classes, their construction and memory layout.

When creating a class, instead of writing completely new data members and member functions, the programmer can designate that the new class should inherit the members of an existing class. This existing class is called the base class, and the new class is referred to as the derived class.

I assume that readers have a familiarity with C++. I will not be explaining why a class should be derived from another class neither will I explain assembly in detail. We will verify common knowledge about c++ using the gdb debugger on a 64bit Ubuntu linux machine.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

05/21/16

Demystifying Virtual Tables in C++ – Part 1 Trivial Constructors

Introduction

This won’t be an easy read. After each claim I will provide supporting code in both C++ and assembly.

Recently I was working on a particularly sneaky bug. A thing happened to me in C++, that should not be possible under normal circumstances. By normal, I mean that 1+1 is guaranteed to 2; the sun rises in the East and sets in the West; all water is wet and the earth is dry…. Yet is still happened. Namely: the vptr of a fully constructed virtual object was pointing to the virtual table of it’s base class. To debug this particular issue one needs to dive deep into the compiler world and into the dreaded waters of assembly.

I hope that I do not have to point out that when I started I had absolutely no clue what is going on. I knew what virtual pointers do and that the compilers are reasonably smart about them. As every modern software engineer I consulted the web oracle only to realise that there is very little written online. I wanted to know how vptrs and vtables are implemented. Not your typical high level theory explaining how dynamic dispatch works. I wanted to know what makes it tick. And while doing so I might improve the world a bit by sharing my journey. So I hopped on my trusted GDB and rode of to the assembly land.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

05/13/16

HackerRank ‘Bigger is Greater’ Solution

Short Problem Definition:

Given a word w, rearrange the letters of w to construct another word in such a way that is lexicographically greater than w. In case of multiple possible answers, find the lexicographically smallest one among them.

Bigger is Greater

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

This task challenges us to find the next permutation of any given array. There are many implementations available online and it is worthwhile comparing them . I would recommend reading the article by Nayuki or re-implementing the std::next_permutation.

Solution:
def next_permutation(arr):
# Find non-increasing suffix
i = len(arr) - 1
while i > 0 and arr[i - 1] >= arr[i]:
i -= 1
if i <= 0:
return False

# Find successor to pivot
j = len(arr) - 1
while arr[j] <= arr[i - 1]:
j -= 1
arr[i - 1], arr[j] = arr[j], arr[i - 1]

# Reverse suffix
arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
return True

def main():
t = input()
for _ in xrange(t):
s = list(raw_input())
if next_permutation(s):
print "".join(s)
else:

if __name__ == '__main__':
main()


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/4/16

HackerRank ‘Castle on the Grid’ Solution

Short Problem Definition:

You are given a grid with both sides equal to N/N. Rows and columns are numbered from 0/0 to N−1/N−1. There is a castle on the intersection of the aath row and the bbth column.

Your task is to calculate the minimum number of steps it would take to move the castle from its initial position to the goal position (c/d).

It is guaranteed that it is possible to reach the goal position from the initial position.

Castle on the Grid

Complexity:

time complexity is O(N^2) or O(N^3)

space complexity is O(N^2)

Execution:

This solution works with the task as a 2D array. There are options available where you treat the task as a graph problem. In both cases each node it visited exactly once using BFS. On each node, I generate all nodes that are connected to this node in a straight line that is not broken by a ‘X’. I keep the distance data (integer) in the array itself. I store the nodes that have to be visited in a FIFO queue. Once the top element in the queue is the end, I terminate the algorithm. The data stored in the array are these:

• X        – blocked
• .          – not visited yet
• (int)   – already visited. Value is the number of steps from the beginning.
Solution:
from collections import deque

class Point:
def __init__(self, x, y):
self.x = x
self.y = y

def __str__(self):
return "X=%d,Y=%d" % (self.x, self.y)

def getPointsFromPoint(N, arr, point):
x = point.x
y = point.y
points = []

while x > 0:
x -= 1
if arr[x][y] == 'X':
break
points.append(Point(x,y))

x = point.x
while x < N-1:
x += 1
if arr[x][y] == 'X':
break
points.append(Point(x,y))

x = point.x
while y > 0:
y -= 1
if arr[x][y] == 'X':
break
points.append(Point(x,y))

y = point.y
while y < N-1:
y += 1
if arr[x][y] == 'X':
break
points.append(Point(x,y))

return points

def solveCastleGrid(N, arr, start, end):
q = deque([start])
arr[start.x][start.y] = 0

while q:
current_point = q.pop()
current_distance = arr[current_point.x][current_point.y]

points = getPointsFromPoint(N, arr, current_point)
for p in points:
if arr[p.x][p.y] == '.':
arr[p.x][p.y] = current_distance + 1
q.appendleft(p)
if p.x == end.x and p.y == end.y:
return current_distance + 1
return -1

if __name__ == '__main__':
N = input()
arr = [0] * N

for i in xrange(N):
arr[i] = list(raw_input())

start_x, start_y, end_x, end_y = map(int, raw_input().split())

print solveCastleGrid(N, arr, Point(start_x, start_y), Point(end_x, end_y))


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/2/16

RDF parse of DBPedia showing all Death Metal band members and their connections

Death Metal members and their connections

To anyone who likes Death Metal and would like to know who played with who in a graphical form. For you there is a DBpedia RDF parse that I’ve done over the last two days.
Recently I replaced the PDF by a vector graphic to allow better scaling. I suggest you view the image in a new tab or download it. Also notice that bands have the format db:BAND_NAME.

Tutorial

You can download the data as RDF or JSON from DBpedia using SPARQL.


SELECT *
WHERE {
{?band_uri dbo:genre dbr:Death_metal }
UNION {?band_uri dbo:genre dbr:Melodic_death_metal}
UNION {?band_uri dbo:genre dbr:Folk_metal}
UNION {?band_uri dbo:genre dbr:Pagan_metal}
UNION {?band_uri dbo:genre dbr:Black_metal}
UNION {?band_uri dbo:genre dbr:Viking_metal}
UNION {?band_uri dbo:genre dbr:Gothic_metal}
UNION {?band_uri dbo:genre dbr:Power_metal}.
{?band_uri dbpedia2:currentMembers ?member_uri}
UNION {?band_uri dbpedia2:pastMembers ?member_uri}.
}


I prefer a simple script in R

library(SPARQL)
library(igraph)
library(network)
library(ergm)

endpoint <- "http://live.dbpedia.org/sparql"
options <- NULL
prefix <- c("db","http://dbpedia.org/resource/")
sparql_prefix <- "PREFIX owl: <http://www.w3.org/2002/07/owl#>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX dc: <http://purl.org/dc/elements/1.1/>
PREFIX : <http://dbpedia.org/resource/>
PREFIX dbpedia2: <http://dbpedia.org/property/>
PREFIX dbpedia: <http://dbpedia.org/>
PREFIX skos: <http://www.w3.org/2004/02/skos/core#>
"
q2 <- paste(sparql_prefix,
'SELECT *
WHERE {
{?band_uri dbo:genre dbr:Death_metal }
UNION {?band_uri dbo:genre dbr:Melodic_death_metal}
UNION {?band_uri dbo:genre dbr:Folk_metal}
UNION {?band_uri dbo:genre dbr:Pagan_metal}
UNION {?band_uri dbo:genre dbr:Black_metal}
UNION {?band_uri dbo:genre dbr:Viking_metal}
UNION {?band_uri dbo:genre dbr:Gothic_metal}
UNION {?band_uri dbo:genre dbr:Power_metal}.
{?band_uri dbpedia2:currentMembers ?member_uri}
UNION {?band_uri dbpedia2:pastMembers ?member_uri}.
}')
res <- SPARQL(endpoint,q2,ns=prefix,extra=options)$results member_band_matrix <- as.matrix(ifelse(table(res$member_uri, res\$band_uri) > 0, 1, 0))

a_m <- graph.incidence(member_band_matrix)

write.graph(a_m,'death_members.graphml',format="graphml")


Afterwards you can use tools such as Gephi to visualise the data.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

02/23/16

HackerRank ‘Sherlock and Valid String’ Solution

Short Problem Definition:

A “valid” string is a string S such that for all distinct characters in S each such character occurs the same number of times in S.

Sherlock and Valid String

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

I optimised this solution to the minimal case that passes all tests on HackerRank. It seems that each character occurs 1 or 2 times. I did not pay the Hackos to verify the input :). The logic of the solution is as follows: count the character counts for each character.

• if they are all equal – it means that all characters occur exactly N times and there is no removal needed
• if 2 or more have less or more characters – there is no way to fix the string in just 1 removal
• if exactly 1 char has a different count than all other characters – remove this char completely and S is fixed.
Solution:
from collections import Counter

def isValid(S):
char_map = Counter(S)
char_occurence_map = Counter(char_map.values())

if len(char_occurence_map) == 1:
return True

if len(char_occurence_map) == 2:
for v in char_occurence_map.values():
if v == 1:
return True

return False

S = raw_input()
if isValid(S):
print "YES"
else:
print "NO"


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

04/6/15

The Aha! Moment

We have all experienced the great moments of clarity, when suddenly everything makes sense. Your heart starts beating faster, a smile creeps up on your face and you gain real wisdom – wisdom that changes your perception of the world. Some call this feeling the Eureka Effect based on a story of Archimedes jumping out of a public bathroom and shouting Eureka! as he realized how to solve a difficult problem he was facing. I prefer to call this experience the Aha! Moment based on the German Aha-Erlebnis as I am not an ancient Greek philosopher and I certainly do not like public bathrooms.

You do not only encounter these moments when finally solving coding challenges, but when hearing jokes also. Have you ever heard a joke that did not seem funny at first? And right the second silence fell on the room, your brain finally made a click, you realized why the cute girl on the other side of the table was laughing so hysterically and you start laughing too. Just like… 3 seconds too late. It maybe does not happen to you, but it surely does happen to me and the wave of emotional satisfaction feels exactly the same like solving a hard coding problem.

These Aha! moments occur when your brain redistributes and reanalyzes the available information to forms a novel conclusion. The region of the brain responsible for this change is the hippocampus, widely know for its role in the formation of long- and short-term memory as well as spatial navigation.

Theoretically, “insight” means the reorientation of one’s thinking, including breaking of the unwarranted “fixation” and forming of novel, task-related associations among the old nodes of concepts or cognitive skills. Processes closely related to these aspects have been implicated in the hippocampus.

In their fMRI study Jing Luo & Kazuhisa Niki (abstract cited above) fabricated these experiences on a study group using Japanese riddles. As far as the riddles go I do understand that there are concepts that can not move a nail, but.. I do not feel any smarter after reading that the answer to the riddle is a river. I would not be a good study candidate. (I do love participating in brain imagining studies though and whenever I get the opportunity I participate gladly). What we should learn from that research (jokes aside) is that whenever you experience a Aha! moment, your brain just integrated new information into your memory and somehow connected it to whatever already was in there. That is important. That is why we all push our boundaries and challenge ourselves with previously unseen programming tasks. To force ourselves to be better, smarter and more versatile thinkers. Because after your hippocampus formed new connections, you will later discover them again and again, when you need them most.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/30/15