Python Algorithms: Mastermind Solver, Text Frequency, and Sorting Techniques
Mastermind Game Logic Implementation in Python
This section provides Python functions for implementing the core logic of the Mastermind game, including calculating clues and finding compatible combinations. Note that muertos refers to Black Pegs (exact matches) and heridos refers to White Pegs (correct color, wrong position).
1. Counting Color Occurrences
def occurrences(color: str, comb: str) -> int:
""Counts how many times a specific color appears in a combination""
oc = 0
for l in comb:
if l == color:
oc += 1
return oc
2. Calculating Mastermind Clues (Black and White Pegs)
def get_clues(secret: str, guess: str) -> tuple[int, int]:
assert len(secret) == len(guess)
# Black Pegs (Muertos): Exact matches
muertos = 0
for i in range(len(secret)):
if secret[i] == guess[i]:
muertos += 1
# White Pegs (Heridos): Correct colors in wrong positions
heridos = 0
# Use a set to iterate over unique colors in the secret code
for l in set(secret):
# Calculate total matches for this color in both codes
total_matches = min(occurrences(l, secret), occurrences(l, guess))
heridos += total_matches
# Subtract exact matches (muertos) from total color matches
heridos -= muertos
# Returns (White Pegs, Black Pegs)
return heridos, muertos
3. Checking Combination Compatibility
def is_compatible_history(comb: str, history: dict) -> bool:
""Checks if a combination is compatible with the entire game history""
i = 0
res = True
while i < len(history["guesses"]) and res:
# Compare the clues generated by 'comb' against the recorded clues
res = history["clues"][i] == get_clues(comb, history["guesses"][i])
i += 1
return res
4. Generating the Next Combination
This function iterates through possible combinations lexicographically, assuming colors are represented by characters starting from ‘a’, up to NCOLORS.
def next_comb(comb: str) -> str:
i = len(comb) - 1
res = ""
# Iterate backwards, simulating addition with carry
while i >= 0:
# Check if the current color is the maximum allowed color (NCOLORS is assumed)
if ord(comb[i]) - ord('a') + 1 == NCOLORS:
res = 'a' + res # Reset to 'a' (carry over)
else:
# Increment the color character
aux = chr(ord(comb[i]) + 1)
res = aux + res
break
i -= 1
# Handle the prefix (characters that didn't carry)
res = comb[:i+1] + res
return res
5. Finding the Next Compatible Combination
def next_compatible_comb(current: str, history: dict) -> str:
""Finds the next combination that is consistent with the game history""
current = next_comb(current)
while not is_compatible_history(current, history):
current = next_comb(current)
return current
6. Mastermind Game Simulation
def game(secret: str) -> dict:
""Simulates a Mastermind game using an iterative solving strategy""
# Start with the initial guess (e.g., "aaaa", assuming SIZE is defined)
current = "a" * SIZE
clue = get_clues(secret, current)
hist = {
'guesses': [current],
'clues': [clue]
}
# Loop until the number of Black Pegs (index 1 of clue) equals the code size
while hist["clues"][-1][1] != SIZE:
current = next_compatible_comb(current, hist)
clue = get_clues(secret, current)
hist["guesses"].append(current)
hist["clues"].append(clue)
return hist
Text Frequency Analysis Functions
These functions are designed for basic text processing, including word extraction, custom lowercasing (handling accented characters), and calculating word frequencies.
1. Utility Functions for Character Checking
def is_in(s: str, ltr: str) -> bool:
""Checks if a letter (ltr) is present in a string (s)""
i = 0
while i < len(s) and s[i] != ltr:
i = i + 1
return i < len(s)
def get_word(txt: str, pos: int) -> tuple[str, int]:
""Extracts a word starting from position 'pos', skipping punctuation (PUNCTUATION is assumed)""
i = pos
# Skip leading punctuation
while i < len(txt) and is_in(PUNCTUATION, txt[i]):
i += 1
word = ''
# Collect characters until punctuation is found
while i < len(txt) and not is_in(PUNCTUATION, txt[i]):
word += txt[i]
i += 1
return word, i
2. Custom Lowercasing Function
The lower function ensures proper conversion to lowercase, specifically handling common Spanish accented uppercase letters.
def lower(word: str) -> str:
new = ''
for ltr in word:
if 'A' <= ltr <= 'Z':
# Standard ASCII uppercase to lowercase conversion
ltr = chr(ord('a') + ord(ltr) - ord('A'))
# Handling specific accented characters
elif ltr == 'Á':
ltr = 'á'
elif ltr == 'É':
ltr = 'é'
elif ltr == 'Í':
ltr = 'í'
elif ltr == 'Ó':
ltr = 'ó'
elif ltr == 'Ú':
ltr = 'ú'
elif ltr == 'Ü':
ltr = 'ü'
elif ltr == 'Ñ':
ltr = 'ñ'
new = new + ltr
return new
3. Calculating Word Frequencies
def frequency(text: str) -> dict:
""Calculates the raw frequency count of words in a text""
fr = {}
i = 0
while i < len(text):
word, end_pos = get_word(text, i)
word = lower(word)
if word in fr:
fr[word] += 1
else:
fr[word] = 1
i = end_pos
return fr
def frequency_rel(freq: dict) -> None:
""Converts raw frequencies into relative frequencies (proportions)""
total = 0
# Calculate the total number of words
for count in freq.values():
total += count
# Divide each count by the total
for word in freq.keys():
freq[word] /= total
Sorting Algorithms: Merge and Partition
This section provides implementations for fundamental components of common comparison-based sorting algorithms.
1. Merge Function (Merge Sort Component)
The merge function combines two sorted sub-arrays (from low to mid and mid+1 to high) into a single sorted array using an auxiliary list.
def merge(lst: list, low: int, mid: int, high: int, aux: list) -> None:
i1 = low
i2 = mid + 1
i3 = low
# Merge elements from both halves into aux
while i1 <= mid and i2 <= high:
if lst[i1] < lst[i2]:
aux[i3] = lst[i1]
i1 += 1
else:
aux[i3] = lst[i2]
i2 += 1
i3 += 1
# Copy remaining elements from the first half
while i1 <= mid:
aux[i3] = lst[i1]
i1 += 1
i3 += 1
# Copy remaining elements from the second half
while i2 <= high:
aux[i3] = lst[i2]
i2 += 1
i3 += 1
# Copy sorted elements back to the original list
lst[low:high+1] = aux[low:high+1]
2. Three-Way Partition Function (Quicksort Component)
The partition function rearranges elements around a given pivot, resulting in three sections: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot.
def partition(lst: list, pivot, low: int, high: int) -> tuple[int, int]:
lw = low # Boundary for elements < pivot
bg = high # Boundary for elements > pivot
i = low
while i <= bg:
if lst[i] < pivot:
# Swap current element with element at lw
lst[i], lst[lw] = lst[lw], lst[i]
lw += 1
i += 1
elif lst[i] > pivot:
# Swap current element with element at bg
lst[i], lst[bg] = lst[bg], lst[i]
bg -= 1
# i is not incremented because the swapped element needs checking
else:
# Element equals pivot
i += 1
print(lst)
# Returns the start index of the equal section (lw) and the end index + 1 (bg+1)
return lw, bg + 1