Created
November 7, 2023 22:35
-
-
Save heyajulia/b54a476be8eab73209afca67b194f07d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Given a string, return the shortest "unambiguous abbreviation" of that string. | |
Assume that your input string is a non-empty string consisting of lowercase letters (a-z) and spaces. | |
Example: | |
UnambiguousAbbreviation("peter piper picked a peck of pickled peppers") = "pet pip picke a pec o pi p" | |
Initially, the word bank looks like: | |
B = ("peter", "piper", "picked", "a", "peck", "of", "pickled", "peppers") | |
To type "peter", you'd need to type "pet" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = ("piper", "picked", "a", "peck", "of", "pickled", "peppers") | |
To type "piper", you'd need to type "pip" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = ("picked", "a", "peck", "of", "pickled", "peppers") | |
To type "picked", you'd need to type "picke" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = ("a", "peck", "of", "pickled", "peppers") | |
To type "a", you'd need to type "a" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = ("peck", "of", "pickled", "peppers") | |
To type "peck", you'd need to type "pec" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = ("of", "pickled", "peppers") | |
To type "of", you'd need to type "o" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = ("pickled", "peppers") | |
To type "pickled", you'd need to type "pi" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = ("peppers") | |
To type "peppers", you'd need to type "p" as that's the shortest unambiguous abbreviation. The word bank now looks like: | |
B = () | |
The word bank is now empty, so we're done. The shortest unambiguous abbreviation of the input string is thus: | |
"pet pip picke a pec o pi p" | |
Thus, implement a function like: | |
def UnambiguousAbbreviation(bank: list[str]) -> str: | |
... | |
...in the programming language of your choice. |
I ended up writing your `unambiguous-abbreviations` sub as a one-liner...
Like so:sub unambiguous-abbreviations(+w) {
w.map({ .&{ [\~] .comb }.first({ w.grep(*.begins-with($_)).uniq.elems == 1 }) or $_ })
}
The .&{ [\~] .comb }
gets all the prefixes of $_
;
The .first({ w.grep(*.begins-with($_)).uniq.elems == 1 })
is the smallest unambiguous prefix (or Nil, in case there isn't one and you need the full word... hence the or $_
part in the end
@massa Awesome! 🤩 I love how versatile Raku is.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
My original solution in Raku (hidden to prevent spoilers)
Updated solution (fixes the duplicate word/
raku raku
bug)Updated solution (fixes duplicate prefix/
lovely love
bug)Property-based testing
I realized that, given a string
S
and its unambiguous abbreviationA
, two things should always hold:A
contains as many words asS
, andA
is a prefix of the corresponding word inS
.So, naturally, I built a quick-n-dirty proptest """framework""":
It identified problems with my first two attempts fairly quickly, but it hasn't identified any problems with the latest version.