Last active
March 30, 2016 18:34
-
-
Save gohkhoonhiang/cd8294bb4036e3a78abd to your computer and use it in GitHub Desktop.
Code solution for Redmart's coding challenge see http://geeks.redmart.com/2015/01/07/skiing-in-singapore-a-coding-diversion/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
def create_map(filename): | |
f = open(filename, "r") | |
lines = f.readlines() | |
rows = int(lines[0].split()[0]) | |
cols = int(lines[0].split()[1]) | |
skimap = [[int(c) for c in lines[i].split()] for i in range(1,len(lines))] | |
return skimap, rows, cols | |
def go_north(skimap,lengths,levels,rows,cols,r,c): | |
return get_lg_lvl(skimap,lengths,levels,rows,cols,r-1,c) | |
def go_east(skimap,lengths,levels,rows,cols,r,c): | |
return get_lg_lvl(skimap,lengths,levels,rows,cols,r,c+1) | |
def go_south(skimap,lengths,levels,rows,cols,r,c): | |
return get_lg_lvl(skimap,lengths,levels,rows,cols,r+1,c) | |
def go_west(skimap,lengths,levels,rows,cols,r,c): | |
return get_lg_lvl(skimap,lengths,levels,rows,cols,r,c-1) | |
def get_lg_lvl(skimap,lengths,levels,rows,cols,r,c): | |
''' if current cell length and level have been calculated, retrieve and return from memory ''' | |
if lengths[r][c] != 0: | |
return skimap,lengths,levels,rows,cols,lengths[r][c],levels[r][c] | |
''' initialize local memory storage for comparison later ''' | |
local_lgs = [0 for x in range(4)] | |
local_lvls = [0 for x in range(4)] | |
curr_height = skimap[r][c] | |
LOCAL_NORTH = 0 | |
LOCAL_EAST = 1 | |
LOCAL_SOUTH = 2 | |
LOCAL_WEST = 3 | |
''' for each direction, if hit the boundary, length is 1 and level is 0 ''' | |
''' if current cell level is greater than adjacent cell level, retrieve the max length and step of the adjacent cell ''' | |
#north | |
if r-1 <= 0: | |
local_lgs[LOCAL_NORTH] = 1 | |
local_lvls[LOCAL_NORTH] = 0 | |
else: | |
north_height = skimap[r-1][c] | |
if curr_height > north_height: | |
skimap,lengths,levels,rows,cols,local_lgs[LOCAL_NORTH],local_lvls[LOCAL_NORTH] = go_north(skimap,lengths,levels,rows,cols,r,c) | |
local_lgs[LOCAL_NORTH] = local_lgs[LOCAL_NORTH] + 1 | |
local_lvls[LOCAL_NORTH] = local_lvls[LOCAL_NORTH] + (curr_height - north_height) | |
else: | |
local_lgs[LOCAL_NORTH] = 1 | |
local_lvls[LOCAL_NORTH] = 0 | |
#east | |
if c+1 >= cols: | |
local_lgs[LOCAL_EAST] = 1 | |
local_lvls[LOCAL_EAST] = 0 | |
else: | |
east_height = skimap[r][c+1] | |
if curr_height > east_height: | |
skimap,lengths,levels,rows,cols,local_lgs[LOCAL_EAST],local_lvls[LOCAL_EAST] = go_east(skimap,lengths,levels,rows,cols,r,c) | |
local_lgs[LOCAL_EAST] = local_lgs[LOCAL_EAST] + 1 | |
local_lvls[LOCAL_EAST] = local_lvls[LOCAL_EAST] + (curr_height - east_height) | |
else: | |
local_lgs[LOCAL_EAST] = 1 | |
local_lvls[LOCAL_EAST] = 0 | |
#south | |
if r+1 >= rows: | |
local_lgs[LOCAL_SOUTH] = 1 | |
local_lvls[LOCAL_SOUTH] = 0 | |
else: | |
south_height = skimap[r+1][c] | |
if curr_height > south_height: | |
skimap,lengths,levels,rows,cols,local_lgs[LOCAL_SOUTH],local_lvls[LOCAL_SOUTH] = go_south(skimap,lengths,levels,rows,cols,r,c) | |
local_lgs[LOCAL_SOUTH] = local_lgs[LOCAL_SOUTH] + 1 | |
local_lvls[LOCAL_SOUTH] = local_lvls[LOCAL_SOUTH] + (curr_height - south_height) | |
else: | |
local_lgs[LOCAL_SOUTH] = 1 | |
local_lvls[LOCAL_SOUTH] = 0 | |
#west | |
if c-1 <= 0: | |
local_lgs[LOCAL_WEST] = 1 | |
local_lvls[LOCAL_WEST] = 0 | |
else: | |
west_height = skimap[r][c-1] | |
if curr_height > west_height: | |
skimap,lengths,levels,rows,cols,local_lgs[LOCAL_WEST],local_lvls[LOCAL_WEST] = go_west(skimap,lengths,levels,rows,cols,r,c) | |
local_lgs[LOCAL_WEST] = local_lgs[LOCAL_WEST] + 1 | |
local_lvls[LOCAL_WEST] = local_lvls[LOCAL_WEST] + (curr_height - west_height) | |
else: | |
local_lgs[LOCAL_WEST] = 1 | |
local_lvls[LOCAL_WEST] = 0 | |
''' get the max length from the 4 adjacent cells, if current length equals max length, compare current level with max level ''' | |
curr_max_lg = 1 | |
curr_max_lvl = 0 | |
for i in range(len(local_lvls)): | |
lg = local_lgs[i] | |
lvl = local_lvls[i] | |
if lg > curr_max_lg: | |
curr_max_lg = lg | |
curr_max_lvl = lvl | |
elif lg == curr_max_lg: | |
if lvl > curr_max_lvl: | |
curr_max_lg = lg | |
curr_max_lvl = lvl | |
''' store the current max length and level in memory ''' | |
levels[r][c] = curr_max_lvl | |
lengths[r][c] = curr_max_lg | |
return skimap,lengths,levels,rows,cols,curr_max_lg,curr_max_lvl | |
if __name__ == '__main__': | |
if len(sys.argv) != 2: | |
print "try 'python challenge.py <filename>'" | |
sys.exit() | |
filename = sys.argv[1] | |
skimap, rows, cols = create_map(filename) | |
lengths = [[0 for x in range(cols)] for y in range(rows)] | |
levels = [[0 for x in range(cols)] for y in range(rows)] | |
curr_max_lg = 1 | |
curr_max_lvl = 0 | |
for r in range(rows): | |
for c in range(cols): | |
skimap, lengths, levels, rows, cols, max_lg, max_lvl = get_lg_lvl(skimap,lengths,levels,rows,cols,r,c) | |
if max_lg > curr_max_lg: | |
curr_max_lg = max_lg | |
curr_max_lvl = max_lvl | |
elif max_lg == curr_max_lg: | |
if max_lvl > curr_max_lvl: | |
curr_max_lg = max_lg | |
curr_max_lvl = max_lvl | |
print curr_max_lg, curr_max_lvl |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment