The Dungeon game

Question

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path - RIGHT -> RIGHT -> DOWN -> DOWN.

Note -

The knight's health has no upper bound.

Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Here is my solution to this challenge -

# Uses dynamic programming

def calculate_minimum_HP(dungeon):
    """
    :type dungeon: List[List[int]]
    :rtype: int
    """
    if not dungeon or not dungeon[0]:
        return 0
    row, col = len(dungeon), len(dungeon[0])
    dp = [[0] * col for _ in range(row)]
    dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

    for i in range(row - 2, -1, -1):
        dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])

    for j in range(col - 2, -1, -1):
        dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])

    for i in range(row - 2, -1, -1):
        for j in range(col - 2, -1, -1):
            dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))

    return dp[0][0]

Here is my Leetcode result -

So, I would like to know whether I could make my program faster and more efficient.

Leetcode timings are weird. I'll submit the exact same source code twice and go from faster than 10% to 90%. I wouldn't be too concerned with the timing. Is there anything stopping you from reusing the given list for memoization? In practice this would be a bad idea but for leetcode it would help — Mitchel Paulin, Jun 5 at 13:16
@MitchelPaulin - Well, if the timing was really my concern, then what would be a good (and reliable) way of timing my program? — Justin, Jun 5 at 13:19
There is no good way to time a program. Ideally you would run it on a clean OS with no other processes but this isn't realistic (hardware differences, dameons, what compiler flags you're using all change things). That is why we have big-Oh because in practice timing is unreliable — Mitchel Paulin, Jun 5 at 13:20
@MitchelPaulin - So which methods of timing would you suggest for my program? What about Python's timeit function? — Justin, Jun 5 at 13:22
I think you're missing my point, system time is an unreliable metric and should not be used for the "goodness" of a leetcode solution. If you want to time it an python library would be fine — Mitchel Paulin, Jun 5 at 13:23

Peilonrayz · Accepted Answer · 2019-06-05 17:47:27Z

Potential Drawbacks of Results

As highlighted by @Mitchel Paulin LeetCode's performance test aren't reliable. I wrote my own answer and got a range of timings from 44ms in >96.53% bracket, but the same code got 56ms in the >46.94% bracket. This means it's also testing the performance of other things whilst testing my code.

This can happen on your machine too. If you're executing a high performance operation whilst trying to time your code your results are going to be useless. But this doesn't mean that you have to have a 'performance testing machine' with nothing running on it to get fairly accurate results. Currently with two web browsers with ~950 tabs open, an IDE, two different notepad software, Spotify and an email client on Windows. I normally get accurate results.

There are times when you see abnormal results in the graphs. I've noticed that sometimes when Spotify changes song you can see additional error bars. But these can just be ignored. The occasional time the entire graph is just useless; but these are rare, easily identifiable and just requires running the timers again.

How to time performance

The simplest way is to just use timeit, however it's hard to see trends with this. Instead I created and use graphtimer to create graphs. The benefit to graphs is they're visual and easier to understand then a bunch of numbers.

Normally programming challenges give you a couple of integers to test against. So setting up timers for, say, a prime sieve is easier than what we have here. And so before we start checking the performance of your code we need to create a function that converts a single number to the arguments we want. I'll provide the function I used to do this. As for this it's fairly complex. I set the entire size of the dungeon to the passed size, and then randomly created the dungeon from this.

After this when testing you need to test each change one at a time. This is because you may make two changes where one of the changes improves performance, but the other reduces performance. This can lead to you not getting maximum performance as you've thrown away an idea that improves performance.

I don't like the way you're building range. And so have some ideas to change it:

Change to use reversed(range(row -1)).
Near the beginning of the function create a variable that holds the rages.
Same as (2) but cast the range to a list.

This shows:

Precomputing the range and not casting is the fastest.
Using reverse is slower than your code.
Precomputing the range and casting is slower for less than three items, but then becomes faster.

Code Review

Change mutations to be in-place. Don't make dp.
Remove the guard statement.

In my solution I used min rather than max causing my final line to be slower. So don't swap these.
Change formatting of your min, and your list indexing so it's easier to read them.

All this gets:

def solution_justin_no_guard(dungeon):
    dungeon[-1][-1] = max(1, 1 - dungeon[-1][-1])

    row, col = len(dungeon), len(dungeon[0])
    rows = range(row - 2, -1, -1)
    cols = range(col - 2, -1, -1)

    for i in rows:
        dungeon[i][-1] = max(1, dungeon[i + 1][-1] - dungeon[i][-1])

    for j in cols:
        dungeon[-1][j] = max(1, dungeon[-1][j + 1] - dungeon[-1][j])

    for i in rows:
        for j in cols:
            dungeon[i][j] = min(
                max(1, dungeon[i][j + 1] - dungeon[i][j]),
                max(1, dungeon[i + 1][j] - dungeon[i][j])
            )

    return dungeon[0][0]

Graphs

You need to install numpy, matplotlib and graphtimer from pypi to be able to run the following. Produces the above three graphs.

import random
import copy

import numpy as np
import matplotlib.pyplot as plt
from graphtimer import Plotter, MultiTimer


def solution_justin(dungeon):
    if not dungeon or not dungeon[0]:
        return 0
    row, col = len(dungeon), len(dungeon[0])
    dp = [[0] * col for _ in range(row)]
    dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

    for i in range(row - 2, -1, -1):
        dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])

    for j in range(col - 2, -1, -1):
        dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])

    for i in range(row - 2, -1, -1):
        for j in range(col - 2, -1, -1):
            dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))

    return dp[0][0]


def solution_justin_reverse(dungeon):
    if not dungeon or not dungeon[0]:
        return 0
    row, col = len(dungeon), len(dungeon[0])
    dp = [[0] * col for _ in range(row)]
    dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

    for i in reversed(range(row - 1)):
        dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])

    for j in reversed(range(col - 1)):
        dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])

    for i in reversed(range(row - 1)):
        for j in reversed(range(col - 1)):
            dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))

    return dp[0][0]


def solution_justin_pre_computed(dungeon):
    if not dungeon or not dungeon[0]:
        return 0
    row, col = len(dungeon), len(dungeon[0])
    dp = [[0] * col for _ in range(row)]
    dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

    rows = range(row - 2, -1, -1)
    cols = range(col - 2, -1, -1)

    for i in rows:
        dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])

    for j in cols:
        dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])

    for i in rows:
        for j in cols:
            dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))

    return dp[0][0]


def solution_justin_pre_computed_list(dungeon):
    if not dungeon or not dungeon[0]:
        return 0
    row, col = len(dungeon), len(dungeon[0])
    dp = [[0] * col for _ in range(row)]
    dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

    rows = list(range(row - 2, -1, -1))
    cols = list(range(col - 2, -1, -1))

    for i in rows:
        dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])

    for j in cols:
        dp[-1][j] = max(1, dp[-1][j + 1] - dungeon[-1][j])

    for i in rows:
        for j in cols:
            dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]))

    return dp[0][0]


def solution_justin_inplace(dungeon):
    if not dungeon or not dungeon[0]:
        return 0
    row, col = len(dungeon), len(dungeon[0])
    dungeon[-1][-1] = max(1, 1 - dungeon[-1][-1])

    rows = range(row - 2, -1, -1)
    cols = range(col - 2, -1, -1)

    for i in rows:
        dungeon[i][-1] = max(1, dungeon[i + 1][-1] - dungeon[i][-1])

    for j in cols:
        dungeon[-1][j] = max(1, dungeon[-1][j + 1] - dungeon[-1][j])

    for i in rows:
        for j in cols:
            dungeon[i][j] = min(
                max(1, dungeon[i][j + 1] - dungeon[i][j]),
                max(1, dungeon[i + 1][j] - dungeon[i][j])
            )

    return dungeon[0][0]


def solution_justin_no_guard(dungeon):
    dungeon[-1][-1] = max(1, 1 - dungeon[-1][-1])

    row, col = len(dungeon), len(dungeon[0])
    rows = range(row - 2, -1, -1)
    cols = range(col - 2, -1, -1)

    for i in rows:
        dungeon[i][-1] = max(1, dungeon[i + 1][-1] - dungeon[i][-1])

    for j in cols:
        dungeon[-1][j] = max(1, dungeon[-1][j + 1] - dungeon[-1][j])

    for i in rows:
        for j in cols:
            dungeon[i][j] = min(
                max(1, dungeon[i][j + 1] - dungeon[i][j]),
                max(1, dungeon[i + 1][j] - dungeon[i][j])
            )

    return dungeon[0][0]


def solution_peilonrayz(dungeon):
    dungeon[-1][-1] = min(dungeon[-1][-1], 0)
    row = len(dungeon)
    col = len(dungeon[0])
    rows = range(row - 2, -1, -1)
    cols = range(col - 2, -1, -1)

    for i in rows:
        dungeon[i][-1] = min(dungeon[i][-1] + dungeon[i + 1][-1], 0)

    for i in cols:
        dungeon[-1][i] = min(dungeon[-1][i] + dungeon[-1][i + 1], 0)

    for y in rows:
        for x in cols:
            dungeon[y][x] = max(
                min(dungeon[y][x] + dungeon[y + 1][x], 0),
                min(dungeon[y][x] + dungeon[y][x + 1], 0)
            )

    return abs(min(dungeon[0][0], 0)) + 1


memoize = {}


def create_arg(size, *, _i):
    size = int(size)
    key = size, _i
    if key in memoize:
        return copy.deepcopy(memoize[key])
    divisors = [
        (i, size // i)
        for i in range(1, int(size ** 0.5) + 1)
        if size % i == 0
    ]
    if len(divisors) > 1:
        divisors = divisors[1:]
    y_size, x_size = random.choice(divisors)
    output = [[None] * x_size for _ in range(y_size)]
    for i in range(size):
        y, x = divmod(i, x_size)
        output[y][x] = random.randint(-100, 100)
    memoize[key] = output
    return output


def main():
    fig, axs = plt.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    (
        Plotter(MultiTimer([
            solution_justin,
            solution_justin_reverse,
            solution_justin_pre_computed,
            solution_justin_pre_computed_list,
        ]))
            .repeat(10, 1, np.logspace(0, 2), args_conv=create_arg)
            .min()
            .plot(axs, title='Comparison of Loop Changes', x_label='dungeon size')
    )
    fig.show()

    fig, axs = plt.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    (
        Plotter(MultiTimer([
            solution_justin_pre_computed,
            solution_justin_inplace,
            solution_justin_no_guard,
            solution_peilonrayz,
        ]))
            .repeat(10, 1, np.logspace(0, 2), args_conv=create_arg)
            .min()
            .plot(axs, title='Code Review Changes', x_label='dungeon size')
    )
    fig.show()

    fig, axs = plt.subplots()
    axs.set_yscale('log')
    axs.set_xscale('log')
    (
        Plotter(MultiTimer([
            solution_justin,
            solution_justin_no_guard,
        ]))
            .repeat(10, 1, np.logspace(0, 2), args_conv=create_arg)
            .min()
            .plot(axs, title='Comparison of Original and Final', x_label='dungeon size')
    )
    fig.show()


if __name__ == '__main__':
    main()

Final notes

The graph is a zig-zaged line. This is because the program is faster when there's only one row or column. And it currently only allows this case when the number is prime. It looks like if a list has at least two dimensions then the performance decreases dramatically to the upper line, but doesn't change much between a 20x2 and a 5x8. I can't prove this, as the graph is only 2D not 3D, but the lack of error bars suggest it. If create_arg is changed to always create a 1xn list once then you get the following graph.

@yuri I provided the entire source code under the section "Graphs" and before "Final notes", you'll need to install numpy, matplotlib and graphtimer from PyPI. It doesn't produce the final graph, getting that requires changing create_arg. — Peilonrayz, Jun 5 at 19:18
Sorry didn't read that part, was too distracted by the shiny graphs. — yuri, Jun 5 at 19:19

asked	1 month ago
viewed	86 times
active	1 month ago

Stack Exchange Network

current community

your communities

more stack exchange communities

The Dungeon game

1 Answer 1

Potential Drawbacks of Results

How to time performance

Code Review

Graphs

Final notes

Your Answer

Not the answer you're looking for? Browse other questions tagged python performance python-3.x programming-challenge dynamic-programming or ask your own question.

Hot Network Questions

The Dungeon game

1 Answer 1

Potential Drawbacks of Results

How to time performance

Code Review

Graphs

Final notes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged python performance python-3.x programming-challenge dynamic-programming or ask your own question.

Related

Hot Network Questions