This is Crossing river code

Question

Story

Niñez friends from Kakao Elementary School meet a stream with stepping stones on an autumn picnic with Ms. Ryan and are about to cross over to the other side. Ms. Ryan made the following rules so that Niñez and his friends can safely cross the river:

• Stepping stones are placed in a row, and the number of times a kid may step on a stone is written on each stone.
• The number on the stone decreases by one each time a kid steps on them.
• When the number of stepping stones reaches 0, you can no longer step on them.
• A kid can jump, skipping several stones. The maximum number of stones that a kid may skip is given as a parameter k.
• If a kid jumps, you always jump to the nearest stepping stone that isn't 0.

The friends of Niñez are on the left side of the stream, and they must arrive across the right side of the stream to be counted as crossing the stepping stone.

How many kids can cross the river, given an array of initial values on the stones and the parameter k?

Constraints

• The number of Ninez friends who must cross the stepping stone is considered to be unlimited.
• The stones array has a size of at least 1 and has a maximum length of 200,000.
• The initial value of each element in the stones array is a natural number between 1 and 200,000,000.
• k is a natural number greater than or equal to 1 and less than or equal to the length of the stones.

Code review question

How should i revise my code? this is Kakao intern code test. I used loop to change stone numbers when stepped and repeat many times . It returns how many people could cross the river.

Original challenge (in Korean)

Example

stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
k=3

After the first kid crosses, the stones have the following values:

stones = [1, 3, 4, 2, 1, 0, 3, 1, 4, 0]

The second kid makes it, making two jumps:

stones = [0, 2, 3, 1, 0, 0, 2, 0, 3, 0]

The third kid makes it, making four jumps:

stones = [0, 1, 2, 0, 0, 0, 1, 0, 2, 0]

Now it takes a jump of 4 stones to get to the other side, which is larger than k = 3. So the answer for this input is three kids, or simply 3.

def solution(stones, k):
    num=len(stones)
    answer=0
    for count in range(max(stones)):
        stat=-1
        for i in range(num):
            if stat==i-1:
                if stones[i]==0:
                    for j in range(i+1,num):
                        if stones[j]==0:
                            if j-stat>=k:
                                return answer
                            else:
                                pass
                        elif stones[j]!=0:
                            stat=j
                            stones[j]-=1
                            break
                elif stones[i]!=0:
                    stat=i
                    stones[i]-=1
        if stat+k>=num:
            answer+=1
        elif stat+k<num:
            return answer
    return answer

Answer 1

Try to avoid nested if and for loops

The structure of your code is a bunch of nested for and if-elif-else statements. Try to find a way to compact those by restructuring your code or logic. Some examples:

No need to use elif if else suffices.

if stones[i]==0:
    # code
elif stones[i]!=0:
    # more code

Can be rewritten as:

if stones[i]==0:
    # code
else:  # you can place a comment here like: stones[i]!=0 
    # more code

Combine if statements with and or or:

if stat==i-1:
    if stones[i]==0:

Can be rewritten as:

if stat==i-1 and stones[i]==0:

No need to state and else if it does nothing:

else:
    pass

Can be omitted.

Try to use Python code style PEP8 and meaningfull variable naming

See PEP8. Some examples in your code that can be improved for consistent readability by other Pythonistas:

Use spaces around operators and comparisons. These (unrelated) lines:

num=len(stones)
range(i+1,num)
if j-stat>=k:
    pass

Becomes:

num = len(stones)  # spaces around '='
range(i+1, num)    # space after ',' in function arguments
if j - stat >= k:  # spaces around '-' and '>='
    pass

Use meaningfull function and variable names

• solution() -> num_kids_crossing_river()
• answer -> num_kids or simply kids
• i -> current_stone
• k -> max_leap
• Etc.

Use docstrings and comments to clarify your code

Document your code. Place documentation below your function definition (a "docstring") like this:

def num_kids_crossing_river(stones, max_leap)
""" Return the number of kids that can pass the array of stones. 
    <<some more text here; like in the text from the exercise>>

    Args:
        stones (list(int)): initial values on the stones.
        max_leap (int): maximum number of stones a kid can jump over/skip.

    Returns:
        int: the number of kids that can cross the river.

Use comments to document what you are doing, as far as it isn't clear from the code itself. Document the algorithm/idea and not the code itself.

For example:

# Maximum number of iterations is the maximum number on the stones
for count in range(max(stones)):
    etc.

Most importantly: rethink the problem

All of the above can be used to improve your code and coding style, but it does not really optimise your code. One important step in coding is to first think about what you are about to code and how to code it.

If you look at the example, you see that the numbers in the stone array decrease, until there are k or more zero's next to eachother.

So an other way to formulate the problem is: how many times can I subtract 1 from an array until I have k or more zero's next to eachother?

Now suppose k = 0 (no jumps). And stones = [5, 6, 7]. You can see/imagine that the number of kids that can pass is 5.

Now suppose k = 1 and the same stones. You can see/imagine that the number of kids that can pass is 6. The 5 becomes 0 first, but you can skip it. Next, the 6 becomes 0.

What we can do, is to iterate over the stones, and check each "window" of k stones. And check the maximum value in that window. After that number of steps, that window is all 0 and the game stops. So we need to find the window that first gets to 0.

So now we can rephrase the problem again, more in mathematical terms: what is the minimum value of the maximum value of all sequential windows of stones with length k?

Illustrated with the example give in the problem statement: k = 3; stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
+-------+                      # maximum = 5 for this window
   +-------+                   # maximum = 5 for this window
      +-------+                # maximum = 5 for this window
         +-------+             # maximum = 3 for this window
            +-------+          # maximum = 4 for this window
               +-------+       # maximum = 4 for this window
                  +-------+    # maximum = 5 for this window
                     +-------+ # maximum = 5 for this window

Now the minimum value of all those maximum values is 3, which is the answer.

You can see that the value of 3 exactly appears in the piece that goes 0 first and where the fourth kid is stuck.

Here, I give you two implementations. One uses basic Python concepts, like your code. The second uses the (intermediate level Python concept) list comprehensions.

def min_max_of_subsection(array, k):
    """ Returns the minimum value of the maximum value of each subsection of length k in array.

    Args:
        array (list): an array of values (can be anything that has an order)
        k (int): length of the sub section

    Returns:
        value from array
    """
    max_subsection = []
    for array_index in range(len(array) - k + 1):
       max_subsection.append(max(array[array_index:array_index + k]))
    return min(max_subsection)


def min_max_of_subsection2(array, k):
    """ Returns the minimum value of the maximum value of each subsection of length k in array.

    Args:
        array (list): an array of values (can be anything that has an order)
        k (int): length of the sub section

    Returns:
        value from array
    """
    return min(max(array[idx:idx+k]) for idx in range(len(array) - k + 1))

print(min_max_of_subsection([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3))
print(min_max_of_subsection2([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3))

Try it online!