forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 1
/
guess-the-word.py
125 lines (116 loc) · 4.25 KB
/
guess-the-word.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
# Time: O(n^2)
# Space: O(n)
# This problem is an interactive problem new to the LeetCode platform.
#
# We are given a word list of unique words, each word is 6 letters long,
# and one word in this list is chosen as secret.
#
# You may call master.guess(word) to guess a word.
# The guessed word should have type string and must be from the original
# list with 6 lowercase letters.
#
# This function returns an integer type,
# representing the number of exact matches (value and position)
# of your guess to the secret word.
# Also, if your guess is not in the given wordlist, it will return -1 instead.
#
# For each test case, you have 10 guesses to guess the word.
# At the end of any number of calls, if you have made 10 or
# less calls to master.guess
# and at least one of these guesses was the secret, you pass the testcase.
#
# Besides the example test case below,
# there will be 5 additional test cases, each with 100 words in the word list.
# The letters of each word in those testcases were chosen independently at
# random from 'a' to 'z',
# such that every word in the given word lists is unique.
#
# Example 1:
# Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]
#
# Explanation:
#
# master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
# master.guess("acckzz") returns 6, because "acckzz" is secret
# and has all 6 matches.
# master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
# master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
# master.guess("abcczz") returns 4, because "abcczz" has 4 matches.
#
# We made 5 calls to master.guess and one of them was the secret,
# so we pass the test case.
# Note: Any solutions that attempt to circumvent the judge will result
# in disqualification.
#
# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master(object):
# def guess(self, word):
# """
# :type word: str
# :rtype int
# """
import collections
import itertools
try:
xrange # Python 2
except NameError:
xrange = range # Python 3
class Solution(object):
def findSecretWord(self, wordlist, master):
"""
:type wordlist: List[Str]
:type master: Master
:rtype: None
"""
def solve(H, possible):
min_max_group, best_guess = possible, None
for guess in possible:
groups = [[] for _ in xrange(7)]
for j in possible:
if j != guess:
groups[H[guess][j]].append(j)
max_group = max(groups, key=len)
if len(max_group) < len(min_max_group):
min_max_group, best_guess = max_group, guess
return best_guess
H = [[sum(a == b for a, b in itertools.izip(wordlist[i], wordlist[j]))
for j in xrange(len(wordlist))]
for i in xrange(len(wordlist))]
possible = range(len(wordlist))
n = 0
while possible and n < 6:
guess = solve(H, possible)
n = master.guess(wordlist[guess])
possible = [j for j in possible if H[guess][j] == n]
# Time: O(n^2)
# Space: O(n)
class Solution2(object):
def findSecretWord(self, wordlist, master):
"""
:type wordlist: List[Str]
:type master: Master
:rtype: None
"""
def solve(H, possible):
min_max_group, best_guess = possible, None
for guess in possible:
groups = [[] for _ in xrange(7)]
for j in possible:
if j != guess:
groups[H[guess][j]].append(j)
max_group = groups[0]
if len(max_group) < len(min_max_group):
min_max_group, best_guess = max_group, guess
return best_guess
H = [[sum(a == b for a, b in itertools.izip(wordlist[i], wordlist[j]))
for j in xrange(len(wordlist))]
for i in xrange(len(wordlist))]
possible = range(len(wordlist))
n = 0
while possible and n < 6:
guess = solve(H, possible)
n = master.guess(wordlist[guess])
possible = [j for j in possible if H[guess][j] == n]