Xah's Challenge (Part 2)

Yesterday, I wrote about Xah Lee's programming challenge and gave a solution similar to Lee's own. Today I will give another, possibly simpler, solution. We start with some constants and a couple of helper functions:

(defconst brackets '((?( . ?))
                     (?{ . ?})
                     (?[ . ?])
                     (?“ . ?”)
                     (?‹ . ?›)
                     (?« . ?»)
                     (?【 . ?】)
                     (?〈 . ?〉)
                     (?《 . ?》)
                     (?「 . ?」)
                     (?『 . ?』)))

(defconst not-brackets "^(){}[]“”‹›«»【】〈〉《》「」『』")

(defvar filen nil)

(defun brkt-closes-p (brkt obrkt)
  "Predicate to test if brkt closes obrkt."
  (let ((bpair (assoc obrkt brackets)))
    (and bpair (char-equal brkt (cdr bpair)))))

(defun brkt-open-p (brkt)
  "Predicate to test if brkt is an opening bracket."
  (assoc brkt brackets))

As before, we have a list of the beginning and ending brackets but this time they are given as characters rather than strings. The not-brackets constant will be used in a call to skip-chars-forward. The ^ at the beginning of the string specifies all characters except the brackets.

The brkt-closes-p function is a predicate that tests whether its first argument is the closing bracket for the second argument. It just uses the brackets constant as an alist.

The brkt-open-p function is even simpler. It's a predicate that tests whether its first argument is an opening bracket. That will be true if it's found in a key position of the brackets alist.

As in the first solution, check-file-for-mismatches gets called to check a single file but all the work is done in brkt-match. The check-file-for-mismatches function merely sets up the temporary buffer for the file and calls brkt-match.

(defun check-file-for-mismatches (fpath)
  "Check a file for mismatched brackets."
  (let ((fb (get-buffer-create "*Temp*")))
    (set-buffer fb)
    (insert-file-contents fpath nil nil nil t)
    (goto-char 1)
    (setq filen fpath)
    (brkt-match ?\f)
    (kill-buffer fb)))

The real checking is done in brkt-match:

 1:  (defun brkt-match (obrkt)
 2:    "Match OBRKT with its closing bracket."
 3:    (let ((open-pos (1- (point))))
 4:      (catch 'exit
 5:        (while t
 6:          (skip-chars-forward not-brackets)
 7:          (if (not (eobp))
 8:              (forward-char))
 9:          (cond
10:           ((eobp) (if (not (char-equal ?\f obrkt))
11:                       (print (format "Unclosed %c in %s at %d"
12:                                      obrkt filen open-pos)))
13:            (throw 'exit t))
14:           ((brkt-closes-p (char-before) obrkt) (throw 'exit t))
15:           ((brkt-open-p (char-before)) (brkt-match (char-before)))
16:           (t (print (format "Mismatch in %s at %d" filen (1- (point))))))))))
17:  

The idea is that brkt-match is passed an opening bracket and searches for the closing bracket (the ?\f passed in by check-file-for-mismatches is a special marker indicating the beginning of file—it matches end-of-buffer). Rather than locate the brackets with a regular expression, we find them by skipping over everything else with skip-chars-forward on line 6.

The processing is done in the while loop on lines 5–16. The catch on line 4 is so that we can exit the while if we match the input or reach end-of-buffer. The cond on lines 9–16 makes the checks:

  1. Lines 10–13
    If we are at end-of-buffer and the input was not ?\f then output an error message about an unclosed bracket. In any case, exit the loop and therefore the function.
  2. Line 14
    If the current character closes the input character, exit the loop and function.
  3. Line 15
    If this is an opening bracket, recursively call brkt-match to try to match it.
  4. Line 16
    If the other tests fail then this is a mismatched bracket. Output an error message and keep looking for the closing bracket matching the input.

We can use the exact same do-files from the first solution to drive check-file-for-mismatches so I won't repeat it here.

This solution appears radically different from the first but it isn't really; only the details differ. We use characters instead of strings, skip-chars-forward instead of regular expressions, and recursion instead of an explicit stack but the strategy is the same:

  • Search for the match to an opening bracket
  • If we find another open bracket, save what we've done so far and start over with the new opening bracket
  • When we match an opening bracket, pick up where we left off.

It's an interesting question as to which method is faster. I haven't tested that aspect but I'm pretty sure the second method is faster. It can do simple character compares instead of the more complex string compares and regular expressions have to do at least as much work as skip-chars-forward.

Update: test → tests. Fixed line numbers in text.

This entry was posted in Programming and tagged . Bookmark the permalink.

3 Responses to Xah's Challenge (Part 2)

  1. xah lee says:

    gosh that's fantastic. I'll have to study it. Mind if i grab your code and place on my blog as one of the solution?

    i haven't done any other lisp, but you do common lisp or scheme? It's great because i can learn different things from the lisp family.

    and again thanks for the links. I'll have to return the favor. Give me a few days to go over the code. I'll probably also run speed test since i have lots files to check. PS are you on facebook or g+, twitter?

    • jcs jcs says:

      Sure, feel free to grab the code. I do CL and Scheme, but mostly Scheme. I've done a ton of C code, but lately I've focused on on the Lisp languages, especially Scheme. I also love elisp and how it and Emacs let me fine tune my work flow. I know you feel the same way and I have learned a lot from reading your blog. Thanks for stopping by.

  2. xah lee says:

    btw, i have read many of your blog entries. Very well written! and most are interesting topics to me too. Thanks.

Comments are closed.