Issue with Problem 170 (Binary Search in Array)
source link: https://www.codeabbey.com/index/forum_topic/dd47ea4ad5f126a25e55f3d42067e5c6
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Issue with Problem 170 (Binary Search in Array)
Back to General discussions forum
I am having a strange issue with Problem 170 (Binary Search in Array). Whenever I submit my answer, I am getting an error of the form "You are expected to return 5651 country codes!" (replacing 5651 with however many country codes there are supposed to be for that particular set of input data). However, I have checked and I am submitting that exact number of country codes each time. I also am pretty sure I am meeting the time limit (although I would think that would produce a different error message). I am able to find country codes for all of the IPs, and my answer seems to be formatted correctly.
Does anyone know what is going on here?
I will include my code (in Python) for reference. I apologize if there are formatting issues here
I will note that I copied the input data into Notepad, manually removed the first line (which has the number of IP addresses to find country codes for), and then saved it as a text file in the same place I saved my code. I would then run the code and copy the answer string that gets printed out into the answer box in the problem.
ipCodesFile = open("IP Country Codes.txt", 'r')
ipCodesUnsplit = ipCodesFile.read()
ipCodesFile.close()
ipCodes = ipCodesUnsplit.split()
inputDataFile = open("Code Abbey Binary Search in Array Input.txt", 'r')
inputData = inputDataFile.read()
inputDataFile.close()
i = 0
answerString = ""
while i < len(inputData):
ipAddress = ""
while i < len(inputData):
if inputData[i] == "\n":
i += 1
break
else:
ipAddress += inputData[i]
i += 1
ipInteger = int(ipAddress, 36)
leftBound = 0
rightBound = len(ipCodes) // 3
firstCountryStart = int(ipCodes[0], 36)
firstCountryOffset = int(ipCodes[1], 36)
lastCountryStart = int(ipCodes[-3], 36)
lastCountryOffset = int(ipCodes[-2], 36)
if firstCountryStart <= ipInteger <= firstCountryStart + firstCountryOffset:
answerString += ipCodes[2] + " "
elif lastCountryStart <= ipInteger <= lastCountryStart + lastCountryOffset:
answerString += ipCodes[-1] + " "
else:
segmentSize = rightBound - leftBound
#I am ending when segmentSize == 1 because when
# segmentSize == 1 and countryStart <= ipInteger, midpoint = leftBound
# and hence the solution will not iterate further, getting stuck in an
# infinite loop
while segmentSize > 1:
midpoint = (leftBound + rightBound) // 2
countryStart = int(ipCodes[3 * midpoint], 36)
if countryStart <= ipInteger:
nextCountryStart = int(ipCodes[3 * (midpoint + 1)], 36)
if nextCountryStart > ipInteger:
countryOffset = int(ipCodes[3 * midpoint + 1], 36)
if ipInteger <= countryStart + countryOffset:
answerString += ipCodes[3 * midpoint + 2] + " "
else:
answerString += "Unknown "
break
else:
leftBound = midpoint
segmentSize = rightBound - leftBound
else:
rightBound = midpoint
segmentSize = rightBound - leftBound
if segmentSize == 1:
leftCountryStart = int(ipCodes[3 * leftBound], 36)
rightCountryStart = int(ipCodes[3 * rightBound], 36)
if leftCountryStart <= ipInteger:
if rightCountryStart > ipInteger:
leftCountryOffset = int(ipCodes[3 * leftBound + 1], 36)
if ipInteger <= leftCountryStart + leftCountryOffset:
answerString += ipCodes[3 * leftBound + 2] + " "
else:
answerString += "Unknown "
else:
rightCountryOffset = int(ipCodes[3 * rightBound + 1], 36)
if ipInteger <= rightCountryStart + rightCountryOffset:
answerString += ipCodes[3 * rightBound + 2] + " "
else:
answerString += "Unknown "
#I don't think it is possible to end with segmentSize of 0, but just in case
# I will include code for this case
elif segmentSize == 0:
countryStart = int(ipCodes[3 * leftBound], 36)
countryOffset = int(ipCodes[3 * leftBound + 1], 36)
if countryStart <= ipInteger <= countryStart + countryOffset:
answerString += ipCodes[3 * leftBount + 2] + " "
else:
answerString += "Unknown "
print(answerString)
Recommend
-
11
Issue #170 08 Oct 2020 Written by: Bas Broek My last issue. I have had such a great time...
-
7
Find element in slice/array with linear or binary search yourbasic.org/golang Linear search Go doesn’t have an out-of-the-box linear search function for
-
6
85.85.170.170 IP address and other printer badness It seems that anyone who spends enough time around network printers will eventually build up a personal library of technical insanity stories. I've definitely seen my share of ga...
-
12
Instagram Launches Revised Instagram Lite App in 170 Regions After first launching the app in India
-
8
16:47 OKT突破170美元关口 欧易OKEx数据显示，OKT短线上涨，突破170美元关口，现报170.2美元，行情波动较大，请做好风险控制。
-
7
Standard Crypto Raises $170 Million – TrustnodesThe Standard Crypto Flagship Fund LP has raised $169,551,000 according to a filing with the Securities and Exchanges Commission. Adam Goldberg, Managing Member and General Partner of S...
-
19
Tunnel run game WARNING! This tutorial contains explicit math! Viewer discretion advised! The idea of the game is simple: run and jump through the maze avoiding the black areas. What makes it look cool is that th...
-
3
Solve almost every Binary Search ProblemBy Rahul Agarwal 24 July 2021Algorithms are an integral part of data science. While most of us data scientists don’t take a proper algorithms course while studying, they are importan...
-
8
Issue #170 08 Oct 2020 Written by: Bas Broek My last issue. I have had such a great time...
-
5
What is Binary Searching?Binary searching is a type of algorithm that can quickly search through a sorted array of elements. The algorithm works by comparing the search key to the
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK