Description:
Welcome to KIMITE, the ultimate test of your problem-solving prowess! In this mind-bending puzzle challenge, you'll be tasked with navigating a treacherous path filled with twists, turns, and obstacles represented by a 2D grid. The goal is to find the shortest path to the destination while obeying strict rules that govern each step. Brace yourself for an extraordinary journey through a maze of complexity, where only the sharpest minds can prevail!
Grid Representation:
The grid is a rectangular matrix consisting of non-negative integers representing the cost of moving to a specific cell. Each cell in the grid corresponds to a position in the path, and the value of the cell represents the cost associated with taking a step to that position.
Rules:
You start at a designated starting point (S) located at the top-left cell (0,0) of the grid.
The destination (D) is located at the bottom-right cell of the grid.
You can only move horizontally or vertically (not diagonally) to adjacent cells.
Each step has a certain cost associated with it, which varies depending on the position and direction.
The cost of each step is represented by an integer value that is a function of the current coordinates and direction.
You must minimize the total cost of the path while obeying all rules.
Test Cases:
Test Case 1:
Grid:
[[0, 5, 4, 3],
[1, 0, 0, 0],
[2, 6, 7, 0]]
Expected Output: The shortest path is S -> 5 -> 4 -> 3 -> D with a total cost of 5+4+3+0 = 12.
Test Case 2:
Grid:
[[0, 2, 3, 4],
[5, 0, 0, 0],
[6, 7, 8, 0]]
Expected Output: The shortest path is S -> 2 -> 3 -> 4 -> D with a total cost of 2+3+4+0 = 9.
Test Case 3:
Grid:
[[0, 1, 2, 3],
[6, 0, 4, 0],
[5, 9, 8, 0]]
Expected Output: The shortest path is S -> 1 -> 2 -> 3 -> D with a total cost of 1+2+3+0 = 6.
def kimite(grid):
rows = len(grid)
cols = len(grid[0])
# Helper function to calculate the cost of a step based on current coordinates and direction
def get_step_cost(x, y, direction):
if direction == "right" and x + 1 < cols:
return grid[y][x + 1]
elif direction == "down" and y + 1 < rows:
return grid[y + 1][x]
else:
return float('inf') # Return a very high cost if the step is not allowed
# Initialize a 2D list to keep track of the minimum cost to reach each cell
min_costs = [[float('inf')] * cols for _ in range(rows)]
min_costs[0][0] = grid[0][0]
# Traverse the grid to find the minimum cost path
for y in range(rows):
for x in range(cols):
# Check rightward move
right_cost = min_costs[y][x] + get_step_cost(x, y, "right")
if x + 1 < cols and right_cost < min_costs[y][x + 1]:
min_costs[y][x + 1] = right_cost
# Check downward move
down_cost = min_costs[y][x] + get_step_cost(x, y, "down")
if y + 1 < rows and down_cost < min_costs[y + 1][x]:
min_costs[y + 1][x] = down_cost
# The minimum cost to reach the destination is stored at the bottom-right cell
destination_cost = min_costs[rows - 1][cols - 1]
return destination_cost if destination_cost != float('inf') else -1
# Test cases
grid1 = [[0, 5, 4, 3],
[1, 0, 0, 0],
[2, 6, 7, 0]]
print(kimite(grid1)) # Output: 12
grid2 = [[0, 2, 3, 4],
[5, 0, 0, 0],
[6, 7, 8, 0]]
print(kimite(grid2)) # Output: 9
grid3 = [[0, 1, 2, 3],
[6, 0, 4, 0],
[5, 9, 8, 0]]
print(kimite(grid3)) # Output: 6import codewars_test as test
# TODO Write tests
import solution # Replace 'solution' with the actual name of your Python file
# test.assert_equals(actual, expected, [optional] message)
@test.describe("The Perplexing Path Puzzle")
def test_group():
@test.it("Test Case 1")
def test_case1():
grid = [[0, 5, 4, 3],
[1, 0, 0, 0],
[2, 6, 7, 0]]
test.assert_equals(solution.kimite(grid), 1, "Failed Test Case 1")
@test.it("Test Case 2")
def test_case2():
grid = [[0, 2, 3, 4],
[5, 0, 0, 0],
[6, 7, 8, 0]]
test.assert_equals(solution.kimite(grid), 2, "Failed Test Case 2")
@test.it("Test Case 3")
def test_case3():
grid = [[0, 1, 2, 3],
[6, 0, 4, 0],
[5, 9, 8, 0]]
test.assert_equals(solution.kimite(grid), 5, "Failed Test Case 3")