Test results - Codility

Tasks Details

hard

1. SheepAndSunshades

Given a set of points on a cartesian plane, find the minimum distance between some pair of them to maximise another metric.

Task Score

100%

Correctness

100%

Performance

100%

There are N sheep relaxing in a field. They are positioned at points with integer coordinates. Each sheep has a square sunshade, so as not to overheat. The sunshade of a sheep standing at position (X, Y) spreads out to a distance of D from (X, Y), covering a square whose middle is at (X, Y) and whose sides are of length 2D. More precisely, it covers a square with vertices in points (X − D, Y − D), (X − D, Y + D), (X + D, Y − D) and (X + D, Y + D). Sheep are in the centres of their sunshades. Sunshades edges are parallel to the coordinate axes.

Every sheep spreads out its sunshade to the same width. No two sunshades can overlap, but their borders can touch.

What is the maximum integer width D to which the sheep can spread out their sunshades?

Write a function:

def solution(X, Y)

that, given two arrays X and Y of length N denoting the positions of the sheep, returns the maximum value of D to which the sheep can spread out their sunshades. There are at least two sheep in the flock, and no two sheep share a point with the same coordinates.

Examples:

1. Given X=[0, 0, 10, 10] and Y=[0, 10, 0, 10],

the function should return 5.

2. Given X=[1, 1, 8] and Y=[1, 6, 0],

the function should return 2.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];

each element of arrays X and Y is an integer within the range [0..100,000];

no two sheep are standing in the same position.

Solution

Programming language used Python

Time spent on task 8 minutes

Notes

not defined yet

Code: 23:26:18 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] X, int[] Y) {
        // write your code in Java SE 8
    }
}

Code: 23:26:52 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(X, Y):
    # write your code in Python 3.6
    pass

Code: 23:26:59 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

def solution(X, Y):
    points = list(zip(X,Y))
    points.sort()
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:27:09 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

def solution(X, Y):
    #
    points = list(zip(X,Y))
    points.sort()
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:27:38 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

def solution(X, Y):
    #best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:28:09 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points that will be used 
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:28:23 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:28:49 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all 
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:28:59 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:29:17 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:29:28 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:29:58 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all o
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:30:16 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:30:46 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:31:00 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:31:30 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is di
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:31:41 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:31:52 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:32:23 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #3rd loop for finding points that have delta X or 
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:32:42 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #3rd loop for finding points that have delta X(and possible Delta Y)
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:32:54 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #3rd loop for finding points with different X that have delta X(and possible Delta Y)
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:33:16 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #3rd loop for finding points with different X that have delta X and Y smaller then minimum
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Code: 23:33:23 UTC, py, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #3rd loop for finding points with different X that have delta X and Y smaller then minimum
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.036 s

▶

example2
Second example test.

✔

0.036 s

▶

example3
Third example test.

✔

0.036 s

Code: 23:33:27 UTC, py, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #3rd loop for finding points with different X that have delta X and Y smaller then minimum
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.036 s

▶

example2
Second example test.

✔

0.040 s

▶

example3
Third example test.

✔

0.036 s

Code: 23:33:30 UTC, py, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

def solution(X, Y):
    #probably best way to unite and sort two arrays
    points = list(zip(X,Y))
    points.sort()
    #creating empty dictonary P and finding distance beetween first two points
    minimum=max((points[1][0]-points[0][0]),abs(points[1][1]-points[0][1]))
    P ={}
    #filling dictonary where is key is X coordinate and value is array with all Y coordinates with same X
    for x in points:
        if x[0] in P: P[x[0]].append(x[1])
        else: P[x[0]] = [x[1]]
    #getting all keys and storing them
    xpoints=list(P.keys())
    #loop that goes through all possible X coordinates. Some values stored in valuable for incresing speed.
    for x in range(0,len(xpoints)):
        ax=xpoints[x]
        ypoints=P[ax]
        #loop for Y coordinates
        for y in range(0,len(ypoints)):
            #finding closest point where is X same and only Y is different
            if (y<len(ypoints)-1) and (ypoints[y+1]-ypoints[y]<minimum): minimum=ypoints[y+1]-ypoints[y]
            ystart=ypoints[y]
            yb1=ypoints[y]-minimum
            yb2=ypoints[y]+minimum
            m=x+1
            #3rd loop for finding points with different X that have delta X and Y smaller then minimum
            while (m<len(xpoints)) and (xpoints[m]-ax<minimum):
                for z in sorted(x for x in P[xpoints[m]] if yb1<x<yb2): 
                    minimum=max(abs(z-ystart), xpoints[m]-ax)
                m +=1
    return(minimum//2)

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*log(N))

expand all Example tests

▶

example1
First example test.

✔

0.036 s

▶

example2
Second example test.

✔

0.036 s

▶

example3
Third example test.

✔

0.036 s

expand all Correctness tests

▶

simple
Simple tests.

✔

0.036 s

▶

small_random
N = 50.

✔

0.036 s

▶

small_line
Points are arranges in a line.

✔

0.036 s

▶

small_grid
Points are arranged in a grid.

✔

0.036 s

0.040 s

▶

small_against_greedy
Tests against random and greedy solutions.

✔

0.036 s

▶

small_square
Points are arranged in a square.

✔

0.036 s

expand all Performance tests

▶

corner_cases
Corner cases.

✔

0.036 s

0.040 s

▶

big_random
N = 100000.

✔

0.604 s

▶

big_line
Points are arranges in a line.

✔

0.272 s

0.116 s

▶

big_grid
Points are arranged in a grid. X3 points

✔

0.040 s

0.340 s

▶

big_against_greedy
Tests against random and greedy solutions.

✔

0.304 s

0.100 s

0.052 s

▶

big_square
Points are arranged in a square.

✔

0.392 s