1"""Chapter 1 practice: a tiny in-memory URL shortener (Level 3 Build) and the
2random-code collision bug (Level 4 Debug). Run: python3 ch01_url_shortener.py"""
3import random
4import string
5
6ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase # 62 characters
7
8
9def to_base62(n):
10 if n == 0:
11 return ALPHABET[0]
12 out = []
13 while n > 0:
14 n, r = divmod(n, 62)
15 out.append(ALPHABET[r])
16 return "".join(reversed(out))
17
18
19class Shortener:
20 """Counter-based shortener: every new link gets the next number, written in base62."""
21
22 def __init__(self, base_url="https://sho.rt/"):
23 self.base_url = base_url
24 self.next_id = 1
25 self.code_to_url = {}
26 self.url_to_code = {} # so the same long URL gets the same short code
27
28 def shorten(self, long_url):
29 if not long_url.startswith(("http://", "https://")):
30 raise ValueError("not a valid URL")
31 if long_url in self.url_to_code:
32 return self.base_url + self.url_to_code[long_url]
33 code = to_base62(self.next_id)
34 self.next_id += 1
35 self.code_to_url[code] = long_url
36 self.url_to_code[long_url] = code
37 return self.base_url + code
38
39 def resolve(self, code):
40 return self.code_to_url.get(code) # None means "404 Not Found"
41
42
43# ---- Level 4: the buggy version ------------------------------------------------
44
45class BuggyShortener:
46 """Picks a random code and never checks whether it's already taken."""
47
48 def __init__(self, code_length=6, seed=None):
49 self.code_length = code_length
50 self.rng = random.Random(seed)
51 self.code_to_url = {}
52
53 def shorten(self, long_url):
54 code = "".join(self.rng.choice(ALPHABET) for _ in range(self.code_length))
55 self.code_to_url[code] = long_url # BUG: silently overwrites an existing code
56 return code
57
58
59class FixedShortener(BuggyShortener):
60 def shorten(self, long_url):
61 while True:
62 code = "".join(self.rng.choice(ALPHABET) for _ in range(self.code_length))
63 if code not in self.code_to_url: # fix: only use a code nobody has
64 self.code_to_url[code] = long_url
65 return code
66
67
68def run_checks():
69 s = Shortener()
70
71 # 1. Shorten then resolve returns the original URL.
72 short = s.shorten("https://example.com/a/very/long/page?id=42")
73 code = short.rsplit("/", 1)[1]
74 assert s.resolve(code) == "https://example.com/a/very/long/page?id=42"
75
76 # 2. The same long URL gets the same code.
77 assert s.shorten("https://example.com/a/very/long/page?id=42") == short
78
79 # 3. Different URLs get different codes.
80 other = s.shorten("https://example.com/other")
81 assert other != short
82
83 # 4. An unknown code returns None (404).
84 assert s.resolve("zzzzzz") is None
85
86 # 5. Invalid input is rejected.
87 try:
88 s.shorten("not a url")
89 raise AssertionError("should have rejected")
90 except ValueError:
91 pass
92
93 # 6. Base62 lengths: 6 characters cover 62**6 = 56.8 billion codes.
94 assert to_base62(62**6 - 1) == "ZZZZZZ"
95 assert len(to_base62(62**6)) == 7
96
97 # Level 4: with only 2-character codes (3,844 possible), collisions show up fast.
98 buggy = BuggyShortener(code_length=2, seed=7)
99 urls = [f"https://example.com/{i}" for i in range(500)]
100 for u in urls:
101 buggy.shorten(u)
102 lost = len(urls) - len(buggy.code_to_url)
103 assert lost > 0, "expected the buggy version to lose links"
104
105 fixed = FixedShortener(code_length=2, seed=7)
106 for u in urls:
107 fixed.shorten(u)
108 assert len(fixed.code_to_url) == len(urls)
109
110 print(f"All checks pass. Buggy version lost {lost} of {len(urls)} links; fixed version lost 0.")
111
112
113if __name__ == "__main__":
114 run_checks()