# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3.10.1 64-bit
#     language: python
#     name: python3
# ---

# +
# Question: Minimize the maximum distance to reach all required places.
# In other words, choose a block such that distance of all places is minimum from there
# Example: consider block at index 3, min distance to reach gym is 1,
# for school is 0, and for store is 1. Thus, the maximum you have to travel to reach
# any of the places is 1.
# Write code to find such a block

# +
blocks = [
    {
        "gym": False,
        "school": True,
        "store": False,
    },
    {
        "gym": True,
        "school": False,
        "store": False,
    },
    {
        "gym": True,
        "school": True,
        "store": False,
    },
    {
        "gym": False,
        "school": True,
        "store": False,
    },
    {
        "gym": False,
        "school": True,
        "store": True,
    },
]

# list of required places to consider
reqs = ["gym", "school"]

# +
# a dictionary to store max of min distances of any place
distances = {}

# iterating through blocks
for i, block in enumerate(blocks):
    dis_to_place = {}
    
    # iterating through the required places list to check distances
    for place in reqs:
        dist_after = dist_before = current_pos = len(blocks)

        # if place is in current block set distance to 0 and continue
        if block[place]:
            dis_to_place[place] = 0
            continue
        
        # if place is not in current block then look in blocks after and before
        if not block[place]:
            
            # checking blocks after the current block
            for si, sblock in enumerate(blocks[(i+1):]):
                if sblock[place]:
                    dist_after = si+1
                    break

            # checking blocks before the current block if current block is not the first
            if i != 0:
                for si, sblock in enumerate(blocks[(i-1)::-1]):
                    if sblock[place]:
                        dist_before = si+1
                        break
            # selecting the minimum of dist_after and dist_before
            dis_to_place[place] = min((dist_after, dist_before, current_pos))
    
    # selecting the max distance from either place's distances
    distances[i] = max(dis_to_place.values())

print(distances)

# +
# selecting the distance with least max travel
minimized = sorted(distances.items(), key=lambda x: x[1])[0]

print(minimized)

# +
# here block at index 2 has the minimum maximum distance 0
# which is the answer

StarcoderdataJupyterScriptsDedupFiltered