On Sunday, November 24, 2019, I participated in the ASU SoDA Coding Challenge VI. The ASU Software Developer’s Association (SoDA) is a club that is dedicated to teaching aspiring programmers how to solve complex problems that will prepare them for industry. The club runs recruiting events, Hackathons, Interview Prep sessions, and other activities that I have personally found invaluable during my first semester at ASU. I would strongly recommend anyone with a remote interest in computer science to join the club.
The SoDA Coding Challenge had 15 questions which were divided into three categories of three questions based on their respective difficulty levels. The Easy Questions, the Medium Questions, and the Hard Questions were made available to the contestants through Google Forms, and participants would have proctors manually check their code to make sure their programs worked.
Easy Question #4 concerns restoring an internet address from a partial internet address. The question reads:
ASU SoDA Coding Challenge VI Easy Question 4: Internet Address Vasya is an active Internet user. One day he came across an Internet resource he liked, so he wrote its address in the notebook. We know that the address of the written resource has format: <protocol>://<domain>.ru[/<context>] where: <protocol> can equal either "http" (without the quotes) or "ftp" (without the quotes), <domain> is a non-empty string, consisting of lowercase English letters, the /<context> part may not be present. If it is present, then <context> is a non-empty string, consisting of lowercase English letters. If string <context> isn't present in the address, then the additional character "/" isn't written. Thus, the address has either two characters "/" (the ones that go before the domain), or three (an extra one in front of the context). When the boy came home, he found out that the address he wrote in his notebook had no punctuation marks. Vasya must have been in a lot of hurry and didn't write characters ":", "/", ".". Help Vasya to restore the possible address of the recorded Internet resource. Input An array of characters representing a string that Vasya wrote in his notebook It is guaranteed that the given string contains at most 50 letters. It is guaranteed that the given string can be obtained from some correct Internet resource address, described above. Output Print a single line — the address of the Internet resource that Vasya liked. If there are several addresses that meet the problem limitations, you are allowed to print any of them. Test Cases input httpsunrux output http://sun.ru/x input ftphttprururu output ftp://http.ru/ruru Note In the second sample there are two more possible answers: "ftp://httpruru.ru" and "ftp://httpru.ru/ru".
My solution for this question is very bad because I am unfamiliar with regular expressions. Here is my solution:
Solution #1: Brute Force Parsing Approach
We simply check for each part of the address and add the necessary characters. The important parts are that the string must start with either “http” or “ftp”, and there must be the characters “ru” after this prefix with some characters in between. Using Python’s index method, it is easy to parse for these components. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Easy Problem #4
https://docs.google.com/document/d/1E_8BtPkGH5iQSBVOxr_lZpjrS5pToaWtDBS1WEZTxWw/edit
'''
import time
import sys
for x in sys.stdin:
if(x[len(x)-1]=='\n'):
x = x[0:len(x)-1]
myInput = x
def findPossible(concat):
l = len(concat)
s = ""
i = 0
if(l>3 and concat[0:4]=="http"):
s += "http://"
i = 4
elif(l>2 and concat[0:3] == "ftp"):
s += "ftp://"
i = 3
else:
return "None possible: Starting sequence is wrong"
concat = concat[i:]
try:
a = concat.index("ru",1)
except:
return "None possible: ru subsequence not found"
s+=concat[0:a]
s+=".ru"
concat = concat[a+2:]
if(len(concat)>0):
s+="/"
s+=concat
while True:
try:
i = s.index("..")
s = s[0:i]+"."+s[i+2:]
except:
break
return s
start = time.time()
print findPossible(myInput)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
http://sun.ru/x
--- 1.59740447998e-05 seconds ---
for input of myInput = "httpsunrux"
'''
And with that, we’re done. I really need to learn some RegEx, because I know it allows for really easy string parsing in cases such as this problem. I didn’t attempt to optimize my solution seeing as the string is at most 50 characters long.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 