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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
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.

Death Metal Parse


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.

Facebooktwittergoogle_plusredditpinterestlinkedin