3D Surface Area HackerRank
Categories: hackerrank
Challenge:
Given a 2D array representing a square of stacks of blocks, calculate the total surface area of the blocks.
https://www.hackerrank.com/challenges/3d-surface-area/problem
This was a fun problem that sounds more challenging than it actually is. My thought process was that we need to first calculate the height of the stack of blocks at each index as if it had no neighbors, which is 2 + (height of stack x 4), and then subtract the height of any of its neighboring stacks (or just subtract it's own height if the neighboring stack is greater than the current stack). We also need to account for edges and corners, which is handled by making sure the index of each neighboring index is greater than 0 and less than the height/width.
My solution:
def surfaceArea(A):
total_area = 0
for index, row in enumerate(A):
for index2, column in enumerate(row):
column_area = 2 + (column * 4)
if index2 - 1 >= 0:
left = A[index][index2 - 1]
if left > column:
column_area -= column
else:
column_area -= left
if index2 + 1 <= len(A[0]) - 1:
right = A[index][index2 + 1]
if right > column:
column_area -= column
else:
column_area -= right
if index + 1 <= len(A) - 1:
down = A[index + 1][index2]
if down > column:
column_area -= column
else:
column_area -= down
if index - 1 >= 0:
up = A[index - 1][index2]
if up > column:
column_area -= column
else:
column_area -= up
total_area += column_area
return total_area
HackerRank: Matrix Layer Rotation (Part 3)
Categories: hackerrank
I figured out that the reasons my code was failing due to Run Time Errors were (1.) I was creating a new empty matrix with the same dimensions as the given matrix and then appending the rotated arrays to that, instead of simply replacing the elements in the given matrix with the elements from the rotated arrays, and (2.) I was deleting each section from the flat array after adding it to the new matrix, which I found easier at the time, since I wouldn't have to calculate the new index of the next section. This fix was pretty simple, since I just needed to keep an incremental index going while getting the correct slices from the rotated flat array.
It took me a little while to determine the best way to handle the first part, but I finally passed 12 out of 12 test cases with the following code:
def matrixRotation(matrix, r):
# Number of rows in the matrix
rows = len(matrix)
# Number of columns in the matrix
columns = len(matrix[0])
# New list that will contain each slice of the matrix in a new list
matrices = []
# The number of slices in the matrix
matrix_num = int(min(rows, columns) / 2)
i = 0
while i < matrix_num:
single_matrix = [matrix[i][i:columns-i],
[matrix[row][columns-1-i] for row in range(i+1, rows-i-1)],
matrix[rows-i-1][i:columns-i][::-1],
[matrix[row][i] for row in range(i+1, rows-i-1)[::-1]]]
i += 1
# Turn the single_matrix list of lists into a single list
single_matrix = [mat for mat in single_matrix if mat != []]
# Turn into a flat list
single_matrix = list(itertools.chain(*single_matrix))
# Rotate this flat list counter clockwise by r
# If r is more than the length of the matrix it's more efficient to use r % len
new_r = r % len(single_matrix)
# Rotate the list
single_matrix = single_matrix[new_r:] + single_matrix[:new_r]
# Append the rotated list to the matrices list
matrices.append(single_matrix)
flat_matrices = list(itertools.chain(*matrices))
m = 0
rs = rows - 2
cs = columns
index = 0
# Create new matrix from rotated matrix
while m < matrix_num:
# Create new top
matrix[m][m:m+cs] = flat_matrices[index:][:cs]
index += cs
# Create new right side
for k in range(rs):
matrix[k + 1 + m][-1-m] = flat_matrices[index]
index += 1
# Create new bottom
matrix[rows - 1 - m][m:m+cs] = flat_matrices[index:][:cs][::-1]
index += cs
# Create new left side
for k in range(rs):
matrix[rs - k + m][m] = flat_matrices[index]
index += 1
m += 1
rs -= 2
cs -= 2
# Print each row as a string joined by a space
for row in matrix:
print(' '.join(str(num) for num in row))It took me a bit longer than I expected to solve this problem, but as it was my first "Hard" level HackerRank problem, I'm just glad I was able to complete it. There are definitely ways of rotating each layer in place rather than creating flat arrays from each matrix layer and adding them back in, but I'm happy with my solution.
0 Comments
HackerRank: Matrix Layer Rotation (Part 2)
Categories: hackerrank
Continued from my last post. It looks like I'll need at least one more Blog post related to this problem, since although I found a solution, it is not optimized enough to pass all of the test cases. I'm getting timeouts on 3 of the 10 test cases in HackerRank, and I'm not quite sure where my bottlenecks are yet.
My first try had even more timeouts, but I realized that I can use mod against the number of rotations (rotations % len(array)), since a number of rotations that is more than the length of the array being rotated can be reduced. I implemented this, but am still getting timeouts.
I suspect that one of my bottlenecks is the fact that I'm creating an empty 2d array of the same number of rows and columns before adding my new rows of data to it, so one possible solution would be for me to figure out how to add the data directly to the given matrix, rather than creating a new empty matrix first.
Current (non-optimized) solution:
def matrixRotation(matrix, r):
# Number of rows in the matrix
rows = len(matrix)
# Number of columns in the matrix
columns = len(matrix[0])
# New list that will contain each slice of the matrix in a new list
matrices = []
# The number of slices in the matrix
matrix_num = int(min(rows, columns) / 2)
i = 0
while i < matrix_num:
single_matrix = []
# The top (left to right) of the matrix slice
top = matrix[i][i:columns-i]
# The right side (top to bottom) of the matrix slice
right = [matrix[row][columns-1-i] for row in range(i+1, rows-i-1)]
# The bottom (right to left) of the matrix slice
bottom = matrix[rows-i-1][i:columns-i]
bottom.reverse()
# The left side (bottom to top) of the matrix slice
left = [matrix[row][i] for row in range(i+1, rows-i-1)]
left.reverse()
i += 1
# Append each side of the matrix slice to the single_matrix list, with each side in its own list
single_matrix.extend([top, right, bottom, left])
# Turn the single_matrix list of lists into a single list
single_matrix = [x for x in single_matrix if x != []]
# Turn into a flat list
single_matrix = list(itertools.chain(*single_matrix))
# Rotate this flat list counter clockwise by r
# If r is more than the length of the matrix it's more efficient to use r % len
new_r = r % len(single_matrix)
for _ in range(new_r):
single_matrix.append(single_matrix.pop(0))
# Append the rotated list to the matrices list
matrices.append(single_matrix)
flat_matrices = list(itertools.chain(*matrices))
new_matrix = [[] for i in range(rows)]
i = 0
rs = rows
cs = columns
# Create new matrix from rotated matrix
while i <= matrix_num:
# Create new top
new_matrix[i][i:i] = flat_matrices[:cs]
del flat_matrices[:cs]
# Create new right side
for k in range(rs - 2):
new_matrix[k + 1 + i].insert(i, flat_matrices[k])
del flat_matrices[:rs - 2]
# Create new bottom
new_matrix[rows - 1 - i][i:i] = flat_matrices[:cs][::-1]
del flat_matrices[:cs]
# Create new left side
for k in range(rs - 2):
new_matrix[rs - 2 - k + i].insert(i, flat_matrices[k])
del flat_matrices[:rs - 2]
i += 1
rs -= 2
cs -= 2
# Print each row as a string joined by a space
for row in new_matrix:
print(' '.join(str(x) for x in row))Here is the problem I'm working on, if anybody is interested:
https://www.hackerrank.com/challenges/matrix-rotation-algo/problem
Hopefully I will have a Part 3 with an optimized solution soon.
0 Comments
HackerRank: Matrix Layer Rotation (Part 1)
Categories: hackerrank
I've been doing a few HackerRank problems each week since I started studying Python (sometimes other things such as take-home challenges for interviews take precedence) to get better at problem solving. I'm at the point now where the problems rated as 'Easy' are very doable for me in less than an hour, and the 'Medium' problems I can usually solve within a few sessions of work. This is my first 'Hard' rated problem attempt, and I thought it would be a good one to work on since the problem is easily understandable for me:
Given a matrix (2d list of lists in this case) and a number of rotations, rotate the entire matrix counter clockwise by the number of rotations and then return the new matrix.
The first thing I did in order to begin solving this problem is to get each matrix 'slice' (with each slice being a rectangular 'box' of elements, for example the outermost box, then the box smaller by 1 on each side, etc) into a string, in order around the box starting from the top left, so I could easily 'rotate' this slice the appropriate number of times:
import itertools
matrix = [[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36]]
r = 2
def matrixRotation(matrix, r):
# Number of rows in the matrix
rows = len(matrix)
# Number of columns in the matrix
columns = len(matrix[0])
# New list that will contain each slice of the matrix in a new list
matrices = []
# The number of slices in the matrix
matrix_num = min(rows, columns) / 2
i = 0
while i < matrix_num:
single_matrix = []
# The top (left to right) of the matrix slice
top = matrix[i][i:rows-i]
# The right side (top to bottom) of the matrix slice
right = [matrix[row][rows-1-i] for row in range(i+1, rows-i-1)]
# The bottom (right to left) of the matrix slice
bottom = matrix[rows-i-1][i:columns-i]
bottom.reverse()
# The left side (bottom to top) of the matrix slice
left = [matrix[row][i] for row in range(i+1, rows-i-1)]
left.reverse()
i += 1
# Append each side of the matrix slice to the single_matrix list, with each side in its own list
single_matrix.extend([top, right, bottom, left])
# Turn the single_matrix list of lists into a single list
single_matrix = [x for x in single_matrix if x != []]
# Turn into a flat list
single_matrix = list(itertools.chain(*single_matrix))
# Rotate this flat list counter clockwise by r
single_matrix = single_matrix[r:] + single_matrix[:r]
# Append the rotated list to the matrices list
matrices.append(single_matrix)
return matricesNow I have each slice of the matrix in a flat list and rotated the correct number of times. My next steps will be to turn this flat list back into a matrix of the same number of rows and columns as the original matrix, which for some reason feels more difficult than the steps I took get each slice into a list. My next blog post will (hopefully) detail how I achieved this.
To be continued...
0 Comments
0 Comments