Problem:


Problem D: Pathological Paths

Professor Pathfinder is a distinguished authority on the structure of hyperlinks in the World
Wide Web. For establishing his hypotheses, he has been developing software agents, which
automatically traverse hyperlinks and analyze the structure of the Web. Today, he has gotten
an intriguing idea to improve his software agents. However, he is very busy and requires help
from good programmers. You are now being asked to be involved in his development team and
to create a small but critical software module of his new type of software agents.

Upon traversal of hyperlinks, Pathfinder’s software agents incrementally generate a map of
visited portions of the Web. So the agents should maintain the list of traversed hyperlinks
and visited web pages. One problem in keeping track of such information is that two or more
different URLs can point to the same web page. For instance, by typing any one of the following
five URLs, your favorite browsers probably bring you to the same web page, which as you may
have visited is the home page of the ACM ICPC Ehime contest.

      http://www.ehime-u.ac.jp/ICPC/
      http://www.ehime-u.ac.jp/ICPC
      http://www.ehime-u.ac.jp/ICPC/../ICPC/
      http://www.ehime-u.ac.jp/ICPC/./
      http://www.ehime-u.ac.jp/ICPC/index.html

Your program should reveal such aliases for Pathfinder’s experiments.

Well, . . . but it were a real challenge and to be perfect you might have to embed rather compli-
cated logic into your program. We are afraid that even excellent programmers like you could
not complete it in five hours. So, we make the problem a little simpler and subtly unrealis-
tic. You should focus on the path parts (i.e. /ICPC/, /ICPC, /ICPC/../ICPC/, /ICPC/./, and
/ICPC/index.html in the above example) of URLs and ignore the scheme parts (e.g. http://),
the server parts (e.g. www.ehime-u.ac.jp), and other optional parts. You should carefully read
the rules described in the sequel since some of them may not be based on the reality of today’s
Web and URLs.

Each path part in this problem is an absolute pathname, which specifies a path from the root
directory to some web page in a hierarchical (tree-shaped) directory structure. A pathname
always starts with a slash (/), representing the root directory, followed by path segments delim-
ited by a slash. For instance, /ICPC/index.html is a pathname with two path segments ICPC and index.html.

All those path segments but the last should be directory names and the last one the name of an
ordinary file where a web page is stored. However, we have one exceptional rule: an ordinary
file name index.html at the end of a pathname may be omitted. For instance, a pathname
/ICPC/index.html can be shortened to /ICPC/, if index.html is an existing ordinary file name.
More precisely, if ICPC is the name of an existing directory just under the root and index.html
is the name of an existing ordinary file just under the /ICPC directory, /ICPC/index.html and
/ICPC/ refer to the same web page. Furthermore, the last slash following the last path segment
can also be omitted. That is, for instance, /ICPC/ can be further shortened to /ICPC. However,
/index.html can only be abbreviated to / (a single slash).

You should pay special attention to path segments consisting of a single period (.) or a double
period (..), both of which are always regarded as directory names. The former represents the
directory itself and the latter represents its parent directory. Therefore, if /ICPC/ refers to some
web page, both /ICPC/./ and /ICPC/../ICPC/ refer to the same page. Also /ICPC2/../ICPC/
refers to the same page if ICPC2 is the name of an existing directory just under the root;
otherwise it does not refer to any web page. Note that the root directory does not have any
parent directory and thus such pathnames as /../ and /ICPC/../../index.html cannot point
to any web page.

Your job in this problem is to write a program that checks whether two given pathnames refer
to existing web pages and, if so, examines whether they are the same.

Input

The input consists of multiple datasets. The first line of each dataset contains two positive
integers N and M, both of which are less than or equal to 100 and are separated by a single
space character.

The rest of the dataset consists of N + 2M lines, each of which contains a syntactically correct
pathname of at most 100 characters. You may assume that each path segment enclosed by two
slashes is of length at least one. In other words, two consecutive slashes cannot occur in any
pathname. Each path segment does not include anything other than alphanumerical characters
(i.e. ‘a’-‘z’, ‘A’-‘Z’, and ‘0’-‘9’) and periods (‘.’).

The first N pathnames enumerate all the web pages (ordinary files). Every existing directory
name occurs at least once in these pathnames. You can assume that these pathnames do not
include any path segments consisting solely of single or double periods and that the last path
segments are ordinary file names. Therefore, you do not have to worry about special rules for
index.html and single/double periods. You can also assume that no two of the N pathnames
point to the same page.

Each of the following M pairs of pathnames is a question: do the two pathnames point to the
same web page? These pathnames may include single or double periods and may be terminated
by a slash. They may include names that do not correspond to existing directories or ordinary
files.

Two zeros in a line indicate the end of the input.

Output

For each dataset, your program should output the M answers to the M questions, each in a
separate line. Each answer should be “yes” if both point to the same web page, “not found”
if at least one of the pathnames does not point to any one of the first N web pages listed in the
input, or “no” otherwise.

Sample Input

5 6
/home/ACM/index.html
/ICPC/index.html
/ICPC/general.html
/ICPC/japanese/index.html
/ICPC/secret/confidential/2005/index.html
/home/ACM/
/home/ICPC/../ACM/
/ICPC/secret/
/ICPC/secret/index.html
/ICPC
/ICPC/../ICPC/index.html
/ICPC
/ICPC/general.html
/ICPC/japanese/.././
/ICPC/japanese/./../
/home/ACM/index.html
/home/ACM/index.html/
1 4
/index.html/index.html
/
/index.html/index.html
/index.html
/index.html/index.html
/..
/index.html/../..
/index.html/
/index.html/index.html/..
0 0

Output for the Sample Input

not found
not found
yes
no
yes
not found
not found
yes
not found
not found



Sample input:
5 6
/home/ACM/index.html
/ICPC/index.html
/ICPC/general.html
/ICPC/japanese/index.html
/ICPC/secret/confidential/2005/index.html
/home/ACM/
/home/ICPC/../ACM/
/ICPC/secret/
/ICPC/secret/index.html
/ICPC
/ICPC/../ICPC/index.html
/ICPC
/ICPC/general.html
/ICPC/japanese/.././
/ICPC/japanese/./../
/home/ACM/index.html
/home/ACM/index.html/
1 4
/index.html/index.html
/
/index.html/index.html
/index.html
/index.html/index.html
/..
/index.html/../..
/index.html/
/index.html/index.html/..
0 0


Sample output:
not found
not found
yes
no
yes
not found
not found
yes
not found
not found

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split() )
TimeStamp = 0
Stamp = "&Stamp&"
while N+M:
    not_found = {}
    Root = {}
    Root[Stamp] = TimeStamp
    TimeStamp+=1
    not_found[Stamp] = TimeStamp
    TimeStamp+=1
    Root["."] = Root
    Root[".."] = not_found 
    for i in range(N):
        url = raw_input()
        content = url.split('/');
        content.pop(0)
        cur = Root
        for x in content:
            if x not in cur:
                cur[x] = {}
                cur[x]['..'] = cur
                cur[x]['.'] = cur[x]
                cur[x][Stamp] = TimeStamp
                TimeStamp+=1
            cur = cur[x]
        cur['.is_file.'] = True
        if content[-1]=='index.html':
            cur['..']['/'] = cur
        cur['..'] = not_found
        cur['.'] = not_found
    for i in range(M):
        url1 = raw_input()
        content = url1.split('/')
        content.pop(0)
        res1 = Root
        for x in content:
            if x == '':
                x = '/'
            if x not in res1:
                res1 = not_found
                break;
            res1 = res1[x]
        if '/' in res1:
            res1 = res1['/']
        #
        url2 = raw_input()
        content = url2.split('/')
        content.pop(0)
        res2 = Root
        for x in content:
            if x == '':
                x = '/'
            if x not in res2:
                res2 = not_found
                break;
            res2 = res2[x]
        if '/' in res2:
            res2 = res2['/']

        if res1 == not_found or res2 == not_found:
            print "not_found"
        elif res1[Stamp] == res2[Stamp]:
            print "yes"
        else:
            print "no"
    N, M = map(int, raw_input().split() )

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split() )
TimeStamp = 0
Stamp = "&Stamp&"
while N+M:
    not_found = {}
    Root = {}
    Root[Stamp] = TimeStamp
    TimeStamp+=1
    not_found[Stamp] = TimeStamp
    TimeStamp+=1
    Root["."] = Root
    Root[".."] = not_found 
    for i in range(N):
        url = raw_input()
        content = url.split('/');
        content.pop(0)
        cur = Root
        for x in content:
            if x not in cur:
                cur[x] = {}
                cur[x]['..'] = cur
                cur[x]['.'] = cur[x]
                cur[x][Stamp] = TimeStamp
                TimeStamp+=1
            cur = cur[x]
        cur['.is_file.'] = True
        if content[-1]=='index.html':
            cur['..']['/'] = cur
        cur['..'] = not_found
        cur['.'] = not_found
    for i in range(M):
        url1 = raw_input()
        content = url1.split('/')
        content.pop(0)
        res1 = Root
        for x in content:
            if x == '':
                x = '/'
            if x not in res1:
                res1 = not_found
                break;
            res1 = res1[x]
        if '/' in res1:
            res1 = res1['/']
        #
        url2 = raw_input()
        content = url2.split('/')
        content.pop(0)
        res2 = Root
        for x in content:
            if x == '':
                x = '/'
            if x not in res2:
                res2 = not_found
                break;
            res2 = res2[x]
        if '/' in res2:
            res2 = res2['/']

        if res1 == not_found or res2 == not_found:
            print "not_found"
        elif '.is_file.' not in res1 or '.is_file.' not in res2:
            print "not_found"
        elif res1[Stamp] == res2[Stamp]:
            print "yes"
        else:
            print "no"
    N, M = map(int, raw_input().split() )

Submission status: Accepted

Solution code:
def check(a):
    path = []
    for direct in a[1:].split("/"):
        if   direct == ".": continue
        elif direct == "" : direct = "/"
        elif direct == "..":
            if len(path) == 0 or max(url.find("/"+"/".join(path)+"/") for url in urls) == -1: return False
            path.pop()
            continue
        path.append(direct)
    url = "/"+"/".join(path)
    while "//" in url: url = url.replace("//","/")
    if url in urls: return url
    url = (url+"/index.html").replace("//","/")
    return url if url in urls else False
    
while 1:
    n,m = map(int,raw_input().split())
    if n == 0: break
    urls = [raw_input() for i in xrange(n)]
    for loop in xrange(m):
        a = check(raw_input())
        b = check(raw_input())
        if not (a and b): print "not found"
        elif a != b: print "no"
        else: print "yes"

Submission status: Accepted

Solution code:
def check(a):
    path = []
    for d in a[1:].split("/"):
        if   d == ".": continue
        elif d == "" : d = "/"
        elif d == "..":
            if len(path) == 0 or max(url.find("/"+"/".join(path)+"/") for url in urls) == -1: return False
            path.pop()
            continue
        path.append(d)
    url = ("/"+"/".join(path)).replace("//","/")
    if url in urls: return url
    url = (url+"/index.html").replace("//","/")
    return url if url in urls else False
    
while 1:
    n,m = map(int,raw_input().split())
    if n == 0: break
    urls = [raw_input() for i in xrange(n)]
    for loop in xrange(m):
        a = check(raw_input())
        b = check(raw_input())
        if not (a and b): print "not found"
        elif a != b: print "no"
        else: print "yes"

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split() )
TimeStamp = 0
Stamp = "&Stamp&"
while N+M:
    not_found = {}
    Root = {}
    Root[Stamp] = TimeStamp
    TimeStamp+=1
    not_found[Stamp] = TimeStamp
    TimeStamp+=1
    Root["."] = Root
    Root[".."] = not_found 
    for i in range(N):
        url = raw_input()
        content = url.split('/');
        content.pop(0)
        cur = Root
        for x in content:
            if x not in cur:
                cur[x] = {}
                cur[x]['..'] = cur
                cur[x]['.'] = cur[x]
                cur[x][Stamp] = TimeStamp
                TimeStamp+=1
            cur = cur[x]
        cur['.is_file.'] = True
        if content[-1]=='index.html':
            cur['..']['/'] = cur
        cur['..'] = not_found
        cur['.'] = not_found
    for i in range(M):
        url1 = raw_input()
        content = url1.split('/')
        content.pop(0)
        res1 = Root
        for x in content:
            if x == '':
                x = '/'
            if x not in res1:
                res1 = not_found
                break;
            res1 = res1[x]
        if '/' in res1:
            res1 = res1['/']
        #
        url2 = raw_input()
        content = url2.split('/')
        content.pop(0)
        res2 = Root
        for x in content:
            if x == '':
                x = '/'
            if x not in res2:
                res2 = not_found
                break;
            res2 = res2[x]
        if '/' in res2:
            res2 = res2['/']

        if res1 == not_found or res2 == not_found:
            print "not found"
        elif '.is_file.' not in res1 or '.is_file.' not in res2:
            print "not found"
        elif res1[Stamp] == res2[Stamp]:
            print "yes"
        else:
            print "no"
    N, M = map(int, raw_input().split() )

Submission status: Accepted

Solution code:
# from urllib.parse import urljoin

def testcase_ends():
    n, m = map(int, input().split())
    if (n, m) == (0, 0):
        return 1

    htmls = set(input() for i in range(n))
    files = set('/')
    for html in htmls:
        sp = html.split('/')
        for i in range(2, len(sp)):
            files.add('/'.join(sp[:i]) + '/')

        files.add(html)

    def find(url):
        has_ts = url.endswith('/')
        url = url.rstrip('/')
        sp = url.split('/')[1:]
        u = ['']
        for i, c in enumerate(sp, 1):
            if c == '..':
                if len(u) == 0: return None  # ???
                u.pop()
            elif c == '.':
                pass
            else:
                u.append(c)

            if ('/'.join(u) + '/') not in files:
                if i < len(sp):
                    return None
        else:
            u = '/'.join(u)

        if u.endswith('/') and (u+'index.html') in files:
            return u+'index.html'

        if (u+'/index.html') in files:
            return u+'/index.html'

        if u in files and not has_ts:
            return u

        return None

    for i in range(m):
        p1 = input()
        p2 = input()

        p1 = find(p1)
        p2 = find(p2)

        if p1 is None or p2 is None:
            print('not found')
        elif p1 == p2:
            print('yes')
        else:
            print('no')

def main():
    while not testcase_ends():
        pass

if __name__ == '__main__':
    main()