Return to Answer

• 558
• 3
• 15

• 558
• 3
• 15

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
 +-------+ # maximum = 5
 +-------+ # maximum = 5
 +-------+ # maximum = 3
 +-------+ # maximum = 4
 +-------+ # maximum = 4
 +-------+ # maximum = 5
 +-------+ # maximum = 5

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!