Here is a quick and dirty (and slow!) Python solution. I will later translate it to Golang, but I doubt it will become any faster since it already uses dictionaries (hashmaps). What slows it down is probably iterating through each coordinate individually.
withopen('input')asf:data=f.readlines()defcalculate_distance(p1,p2):x1,y1=p1x2,y2=p2returnabs(x1-x2)+abs(y1-y2)# Find the outer border:
P=set()# Contains the points
outer_top,outer_bottom=-1,1000outer_left,outer_right=1000,-1fordindata:y,x=map(int,d[:-1].split(','))P.add((x,y))outer_top=max(outer_top,y)outer_bottom=min(outer_bottom,y)outer_left=min(outer_left,x)outer_right=max(outer_right,x)# Map coordinates to closest points and count:
count_P={}# Counts for each point number of assigned unique closest coordinates
canvas={}# Contains total distance to all points for coordinates
foryinrange(outer_bottom,outer_top+1):forxinrange(outer_left,outer_right+1):canvas[(x,y)]=0min_dist=float('inf')forpinP:dist=calculate_distance((x,y),p)canvas[(x,y)]+=distifdist==min_dist:min_p=Noneelifdist<min_dist:min_p=pmin_dist=distifmin_p:count_P[min_p]=count_P.get(min_p,0)+1ifyin(outer_top,outer_bottom) \
orxin(outer_left,outer_right):# Mark point as having infinite area to not count
count_P[min_p]=float('-inf')# Part 1:
print('Part 1:')print('Point with largest area: {}'.format(max(count_P,key=count_P.get)))print('The area is: {}\n'.format(max(count_P.values())))# Part 2:
region=[]forp,dincanvas.items():ifd<10000:region.append(p)print('Part 2:')print('Size of region: {}'.format(len(region)))
fromcollectionsimportdefaultdictfromcollectionsimportCounterfromitertoolsimportproductimportnumpyasnpfromscipy.spatialimportKDTreewithopen("input.txt")asf:coords=[(int(x.split(",")[0]),int(x.split(",")[1]))forxinf]xs,ys=[xforx,yincoords],[yforx,yincoords]# Part 1
t=KDTree(coords)d=defaultdict(int)edge=set()fori,jinproduct(range(max(xs)),range(max(ys))):points,dists=t.query((i,j),k=2,p=1)ifi==0orj==0ori==max(xs)-1orj==max(ys)-1:edge.add(int(dists[0]))ifpoints[0]!=points[1]:d[(i,j)]=dists[0]forp,areainCounter(d.values()).most_common():ifpnotinedge:print(area)break# Part 2
defdist(x,y):returnsum(abs(x-a)+abs(y-b)fora,bincoords)print(sum(1fori,jinproduct(range(max(xs)),range(max(ys)))ifdist(i,j)<10000))
Here is the Golang code. Even though it uses the exact same algorithm, it runs surprisingly faster!
packagemainimport("bufio""fmt""math""os""strconv""strings")typecoordstruct{xintyint}// readLines reads a whole file into memory// and returns a slice of its lines.funcreadLines(pathstring)([]string,error){file,err:=os.Open(path)iferr!=nil{returnnil,err}deferfile.Close()varlines[]stringscanner:=bufio.NewScanner(file)forscanner.Scan(){lines=append(lines,scanner.Text())}returnlines,scanner.Err()}funcabs(xint)int{ifx<0{return-x}returnx}funcmax(a,bint)int{ifa<b{returnb}returna}funcmin(a,bint)int{returnmax(-a,-b)}funccalculateDistance(p1,p2coord)int{returnabs(p1.x-p2.x)+abs(p1.y-p2.y)}funcmakeCoord(dstring)coord{c:=strings.Split(d,", ")x,_:=strconv.Atoi(c[1])y,_:=strconv.Atoi(c[0])returncoord{x:x,y:y}}funcmain(){data,err:=readLines("input")iferr!=nil{panic(err)}// Find the outer border:varouterTop,outerBottom,outerLeft,outerRightintouterBottom=math.MaxInt32outerLeft=math.MaxInt32P:=[]coord{}for_,d:=rangedata{c:=makeCoord(d)P=append(P,c)outerTop=max(outerTop,c.y)outerBottom=min(outerBottom,c.y)outerLeft=min(outerLeft,c.x)outerRight=max(outerRight,c.x)}// Map coordinates to closest points and count:countP:=map[coord]int{}canvas:=map[coord]int{}fory:=outerBottom;y<=outerTop;y++{forx:=outerLeft;x<=outerRight;x++{c:=coord{x:x,y:y}canvas[c]=0minDist:=math.MaxInt32varminPcoordfor_,p:=rangeP{dist:=calculateDistance(c,p)canvas[c]+=distifdist==minDist{minP=coord{x:math.MinInt32,y:math.MinInt32}}elseifdist<minDist{minP=pminDist=dist}}ifminP.x!=math.MinInt32&&minP.y!=math.MinInt32{ifcountP[minP]!=math.MinInt32{countP[minP]=countP[minP]+1}ify==outerTop||y==outerBottom||x==outerLeft||x==outerRight{countP[minP]=math.MinInt32}}}}// Part 1:fmt.Println("Part 1:")maxi:=math.MinInt32varmaxiPcoordfork,v:=rangecountP{ifv>maxi{maxi=vmaxiP=k}}fmt.Printf("Point with largest area: %v\n",maxiP)fmt.Printf("The area is: %v\n",maxi)// Part 2:fmt.Println("\nPart 2:")varregion[]coordforp,d:=rangecanvas{ifd<10000{region=append(region,p)}}fmt.Printf("Size of region: %v\n",len(region))}
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Here is a quick and dirty (and slow!) Python solution. I will later translate it to Golang, but I doubt it will become any faster since it already uses dictionaries (hashmaps). What slows it down is probably iterating through each coordinate individually.
Python using a kd-tree.
Here is the Golang code. Even though it uses the exact same algorithm, it runs surprisingly faster!