At the high level bit, there's not much to complain about and a lot to like. Not so much because the code works (a necessary but non-trivial requirement for this site). But because the logic is sound (sets/hashmaps) and can be described and understood easily without a lot of details in the code. But I might be biased because I've written similar code to so solve somewhat similar problems in the past.
Code reveiew trope: performance
I want to be clear that I don't think performance matters much in this context. Firstly because the context is Emacs and second because it's in eLisp and third because this particular problem probably isn't all that important (even though the larger class of problems is important). If raw performance really mattered the code wouldn't be running in Emacs and even if it were we'd write it in C rather than eLisp.
But I find there is something unsettling about the solution.
Aesthetics/idioms
The eLisp way to implement sets is with lists. Using lists to represent sets is idiomatic. Using hashmaps is unidiomatic. And it feels unidiomatic.
The other issue is that hashmaps aren't idiomatic math. Sets are. Whether we use lists or hashmaps to implement the set abstraction, wrapping the implementation in the language of sets makes it clearer what we are doing.
;; add-to-hashmap (hashmap item) ...
;; becomes
(defun add-element-to-set (set element)
"Insert ELEMENT into SET and return SET."
(puthash element t set)
set)
layering abstractions is even more idiomatic:
(setf 'set-insert (function puthash))
helps the set abstraction permeate deeper into code
(defun add-element-to-set (set element)
"Insert ELEMENT into SET and return SET."
(set-insert element t set) ;;; CHANGED
set)
On the other hand, some people see this idiom as a bug not a feature.
About performance
The reason lists are idiomatic for sets (and many other things in Lisp) is because a lot of the time, lists are good enough. Checking if a string is a panagram inside of Emacs is probably one of those times. Suppose we use the procedure.
;;; PROGRAM ONE
(defun panagram? (sentence)
(let (s (upcase sentence))
(and
(string-match "A" s)
(string-match "B" s)
...
(string-match "Z" s))))
Implementation details aside, this blunt force form is O(n) time and space. Because each letter in the input matters (at least in theory) we can't get better than O(n).
About hashmaps
O(1) time for lookups and insertions makes hashmaps attractive for many implementations. But the O(1) is amortized. Inserting n elements into a hashmap takes O(n) time. Reading each of those n elements also takes O(n) time. Hashmaps are only more efficient when we make many more reads than insertions. But here we have n insertions into and n reads from the hashmap before it gets garbage collected. There's no amortization. Using hashmaps is not a performance optimization.
But hashing is more than hashmaps. So is mapping.
Mapping and Hashing
If we had a wishing well, after we wished for more wishing wells, we might wish for a hash function that hashes our string into the boolean panogram?. Wait a minute, at the high level, that's what the problem is. It's just at the high level, the hash of the input string is a hashmap of characters rather than a simpler data structure that's easier to unpack. Let's be fearless and try writing our own hash function.
Hashing with primes
The first 26 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101. Their product is 1267259750580658434. Pseudo-code for panagram?
### PROGRAM TWO ###
product = 1
primes = array[2 3 5 ...101]
foreach character in string
product = product * primes[downcase(character) - 97]
return product modulo 1267259750580658434 == 0
avoids allocating the hash map, writing to it, and reading from it. Hashing at the level of the string rather than the character is generally simpler. The use of prime factors makes it a little more clever than is ideal. It requires more mental effort to understand than the blunt approach using (and ...) or the use of hashmaps. It might not be worth it. But it might be a step in the right direction
PROGRAM TWO has some useful attributes:
- The reduction is simple. It compresses the string into an easily interpreted value.
- It utilizes the lexographic order inherent in the alphabet to map characters to values in an array.
- It reflects the boundaries of the input domain (26 characters). This is also true for PROGRAM ONE.
- Thinking about the characteristics of the input is a good thing. For example strings of less than 26 characters cannot be panagrams.
Simpler hashing
Using prime factorization is a generic approach that scales all the way out to things like Git source control and https. But like hashmaps, it feels like overkill here. There are simpler ways to record whether or not a character occurs in a string. All we need is one bit...
...but bitwise operations are a bit low level for elisp and emacs, so maybe we simulate them.
### PROGRAM THREE ###
bitmap = [0]
do 25 times
append 0 to bitmap # array length 26 all zeros
foreach character in string
bitmap[downcase(character) - 97] = 1
return reduce(bitmap 0 '#+) == 26
Remarks
What makes this problem potentially interesting is that we have to start thinking about properties of the data. For example, no string less than 26 characters can possibly be a pangram. And not only do we know that most strings are not pangrams we know the most likely ways in which they are not pangrams...such as missing q or z or x.
That means we might come back to PROGRAM ONE and refactor the (and ...) to
;;; PROGRAM FOUR ;;;
(defun panagram? (sentence)
(let (s (upcase sentence))
(and
(string-match "Q" s)
(string-match "Z" s)
...
(string-match "E" s))))
Most ordinary sentences will be rejected by the first string-match and nearly all sentences would be rejected if the first regex was [QZXJ].
To put it another way, if we represent each character as one bit in a bitmap, there are 226-1 bitmaps that are not pangrams and only one that is. Finding pangrams efficiently correlates with rejecting strings quickly.
