5
\$\begingroup\$

Challenge at https://www.codewars.com/kata/5629db57620258aa9d000014/train/python

Given two strings s1 and s2, we want to visualize how different the two strings are. We will only take into account the lowercase letters (a to z). First let us count the frequency of each lowercase letters in s1 and s2.

s1 = "A aaaa bb c"

s2 = "& aaa bbb c d"

s1 has 4 'a', 2 'b', 1 'c'

s2 has 3 'a', 3 'b', 1 'c', 1 'd'

So the maximum for 'a' in s1 and s2 is 4 from s1; the maximum for 'b' is 3 from s2. In the following we will not consider letters when the maximum of their occurrences is less than or equal to 1.

We can resume the differences between s1 and s2 in the following string: "1:aaaa/2:bbb" where 1 in 1:aaaa stands for string s1 and aaaa because the maximum for a is 4. In the same manner 2:bbb stands for string s2 and bbb because the maximum for b is 3.

The task is to produce a string in which each lowercase letters of s1 or s2 appears as many times as its maximum if this maximum is strictly greater than 1; these letters will be prefixed by the number of the string where they appear with their maximum value and :. If the maximum is in s1 as well as in s2 the prefix is =:.

In the result, substrings (a substring is for example 2:nnnnn or 1:hhh; it contains the prefix) will be in decreasing order of their length and when they have the same length sorted in ascending lexicographic order (letters and digits - more precisely sorted by codepoint); the different groups will be separated by '/'.

My code

from collections import Counter


def mix(s1, s2):
    def clean_dict(inp: dict | Counter, other: dict | Counter) -> dict:
        return {
            char: amount
            for char, amount in inp.items()
            if amount >= other.get(char, 0) and amount > 1
        }
    
    def format_dict(inp, num):
        return [(num, char * amount) for char, amount in inp.items()]

    s1: str = "".join(char for char in s1 if char.isalpha() and char.islower())
    s2: str = "".join(char for char in s2 if char.isalpha() and char.islower())
    one_count: dict = Counter(s1)
    two_count: dict = Counter(s2)

    one_count = clean_dict(one_count, two_count)
    two_count = clean_dict(two_count, one_count)

    part_one: list[tuple[str, str]] = format_dict(one_count, "1")
    part_two: list[tuple[str, str]] = format_dict(two_count, "2")
    
    mixed: list[tuple[str, str]] = part_one + part_two
    clean_mixed: list[tuple[str, str]] = []

    for item in mixed:
        origin, chars = item
        other = tuple(("1" if origin == "2" else "2", chars))
        if other in mixed:
            if origin == "1":
                clean_mixed.append(tuple(("=", chars)))
        else:
            clean_mixed.append(item)

    no_dupes: list[list[str]] = [sorted(pair)[::-1] for pair in clean_mixed]
    no_dupes = sorted(no_dupes, key=lambda pair: (-len(pair[0]), pair[1], pair[0]), reverse=True)
    return "/".join(":".join(pair[::-1]) for pair in no_dupes[::-1])

I have a few questions - is there a better way of combining the two lists into one with no duplicates? I tried an approach with frozenset but found it very ugly.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

nested functions

Nested functions aren’t doing you any favors in this case. Place them up at top level, please, where they are accessible to other callers, such as unit tests.

doctest

Show us example input and output in the docstring, please. Use “python -m doctest *.py” to verify.

generalize

DRY is sometimes called “the rule of three“. So this code isn’t exactly too repetitive.

Nonetheless, the problem statement trivially generalizes from a pair of input strings to N inputs. Consider solving the general problem, at least as far as pre-processing each input string goes. When faced with N inputs, you will be forced to loop over them. I feel this would result in somewhat cleaner code, even for the 2 input case.

zip

I was a little surprised to not see zip() tuples being fed to max() or some custom helper function.

annotations

Typically you should just be annotating the signatures, please. It's a bit crazy to annotate all those assignments instead. If mypy can't figure out the type of what you assigned, then you probably want to add a --strict switch to it, and more carefully annotate the function(s) being called. The biggest situation where assignment annotations win is when you initialize some empty container, so we can't yet see the type of what it will hold, e.g. words: list[str] = [].


Here is one way of solving it for N inputs.

from collections import Counter
import unittest


def lower(s: str) -> str:
    """
    Filters the input string down to just lowercase letters.

    >>> lower('A aaaa xyz xyz')
    'aaaaxyzxyz'
    """
    return "".join(filter(str.islower, s))


def which(letter: str, biggest: int, *counts: Counter[str]) -> str:
    """Reports which counter has the most of the given letter, typically '1' or '2'."""
    for i, count in enumerate(counts):
        if count.get(letter) == biggest:
            return str(i + 1)
    return "999"


def mix(*strings: str) -> str:
    counts = [Counter(lower(string)) for string in strings]
    ret = []
    for letter in sorted(set("".join(strings))):
        biggest = max((count.get(letter, 0) for count in counts))
        if biggest > 1:
            ret.append(which(letter, biggest, *counts) + ":" + letter * biggest)
    return "/".join(ret)


class LetterCountTest(unittest.TestCase):
    def test_letter_count(self) -> None:
        self.assertEqual("2:eee", mix("ee", "eee"))
        self.assertEqual("1:ee", mix("ee", "fe"))
        self.assertEqual(
            "1:aaaa/3:bbb/3:dd",
            mix("A aaaa bb c", "bb", "& daaa bbb c d"),
        )
\$\endgroup\$
2
  • \$\begingroup\$ sorted(set("".join(strings))) bothers me here, it's a lot of unnecessary work. I'd expect something like sorted(set(itertools.chain.from_iterable(strings))) in general case, but here you already have a list of Counters - chaining them would be even less work (sorted(set(itertools.chain.from_iterable(counts))). And your generic solution seems to ignore the "use =: prefix in case of tie" requirement - this should be at least indicated in the answer. \$\endgroup\$ Commented May 2 at 0:44
  • \$\begingroup\$ @SUTerliakov, I was going for "intuitively obvious". All correct solutions will need to be \$O(N)\$ linear in total size of the strings, anyway. If we see an example implementation with profile measurements from running its test suite, then sure, we can talk about whether one optimization or another is premature or is appropriate for a specific workload. // Oooh, thank you! I missed the =: "tie" case in the Problem Statement, in part because the OP code did not remark upon it. It's slightly harder for N > 2. My bad, good call! \$\endgroup\$
    – J_H
    Commented May 2 at 3:50
2
\$\begingroup\$

Re: your question about a better way of de-deduplicating, a nice way of de-duplicating frequency entries while also removing the need to do entry cleanup via clean_dict (removing frequency entries that have a frequency count greater than 1 but also less than the most frequent count of that letter between the two input strings) is by taking the list comprised of frequency entries from both input strings and sorting it by frequency (descending) and letter (lexicographic ascending), in that order. Then take that sorted list and process it one by one while maintaining a set of "seen letters" to avoid including the above-described entries that would have been removed by clean_dict.

By sorting the entries in this way we know that frequency entries with the same frequency and letter will end up next to each other, and if we start with a stack and process entries one by one, we can efficiently de-duplicate by comparing each current entry with the top of the stack.

Here's an example implementation of this idea:

from collections import Counter


def frequencies(s: str, source: str) -> list[tuple[int, str, str]]:
    counter = Counter(c for c in s if c.islower())
    return [
        (frequency, letter, source)
        for letter, frequency in counter.items()
        if frequency > 1
    ]


def mix_string(letter_frequencies: list[tuple[int, str, str]]) -> str:
    return "/".join(
        f"{source}:{frequency*letter}"
        for frequency, letter, source in letter_frequencies
    )


def mix(s1: str, s2: str) -> str:
    seen_letters = set()
    letter_frequencies = frequencies(s1, "1") + frequencies(s2, "2")
    # sort by
    #   1. frequency (descending)
    #   2. letter (lexicographic ascending -> "a" < "b")
    letter_frequencies.sort(key=lambda x: (-x[0], x[1]))
    if not letter_frequencies:
        return ""
    stack = [letter_frequencies[0]]
    seen_letters.add(letter_frequencies[0][1])
    for frequency, letter, source in letter_frequencies[1:]:
        top = stack[-1]
        if frequency == top[0] and letter == top[1]:
            stack.pop()
            stack.append((frequency, letter, "="))
        elif letter in seen_letters:
            continue
        else:
            stack.append((frequency, letter, source))
            seen_letters.add(letter)
    # sort by
    #   1. frequency (descending)
    #   2. source (lexicographic ascending -> "1" < "2" < "=")
    #   3. letter (lexicographic ascending -> "a" < "b")
    stack.sort(key=lambda x: (-x[0], x[2], x[1]))
    return mix_string(stack)

EDIT: Based on @J_H's suggestion, here's a modified version of the above using a data structure with labeled fields:

from collections import Counter
from dataclasses import dataclass


@dataclass(frozen=True)
class Entry:
    frequency: int
    letter: str
    source: str


def frequencies(s: str, source: str) -> list[Entry]:
    counter = Counter(c for c in s if c.islower())
    return [
        Entry(frequency, letter, source)
        for letter, frequency in counter.items()
        if frequency > 1
    ]


def mix_string(letter_frequencies: list[Entry]) -> str:
    return "/".join(
        f"{entry.source}:{entry.frequency*entry.letter}"
        for entry in letter_frequencies
    )


def mix(s1: str, s2: str) -> str:
    seen_letters = set()
    letter_frequencies = frequencies(s1, "1") + frequencies(s2, "2")
    if not letter_frequencies:
        return ""
    letter_frequencies.sort(key=lambda x: (-x.frequency, x.letter))
    stack = [letter_frequencies[0]]
    seen_letters.add(letter_frequencies[0].letter)
    for entry in letter_frequencies[1:]:
        top = stack[-1]
        if entry.frequency == top.frequency and entry.letter == top.letter:
            stack.pop()
            stack.append(Entry(entry.frequency, entry.letter, "="))
        elif entry.letter in seen_letters:
            continue
        else:
            stack.append(entry)
            seen_letters.add(entry.letter)
    stack.sort(key=lambda x: (-x.frequency, x.source, x.letter))
    return mix_string(stack)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Consider making frequencies() return a list of namedtuple. Then instead of cryptic 0, 1, 2 indices that need clunky comments, the lambdas could talk about x.frequency, x.letter, and x.source. Better still, we could use an attrgetter. \$\endgroup\$
    – J_H
    Commented May 1 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.