Three In A Row

January 9, 2018

Since the purpose of the exercise is to find three items in a row, we pick up in the middle of the problem with the input already parsed into a list; if you want to work from a file, have a look at the Text File Databases essay:

(define sample-input '(
  ("01/11/2018" . "0003")
  ("01/12/2018" . "0003")
  ("01/13/2018" . "0004")
  ("01/13/2018" . "0003")))

Our strategy is to sort by userid and date, then scan. To make the sort simpler, we “sign” each input record by converting the userid and date to an integer, so the first record in the file becomes 32458130, where 3 is the user id and 2458130 is the julian number of 1/11/2018:

(define (signature x)
  (+ (* (string->number (cdr x)) 10000000)
     (julian (string->number (substring (car x) 6 10))
             (string->number (substring (car x) 0 2))
             (string->number (substring (car x) 3 5)))))

Then the solution looks like this:

(define (three-in-a-row xs)
  (unique =
    (map (lambda (n) (quotient n 10000000))
      (map car
        (filter first-three-in-a-row
          (cdrs
            (unique =
              (sort <
                (map signature xs)))))))))

Working from the bottom up: Map signature signs each input record, sort brings together users by date, unique discards multiple appearances on the same date, cdrs makes a list of each starting point in the sorted list, filter first-three-in-a-row discards records that don’t appear on three successive days, map keeps just the first day, map extracts the userid, and unique keeps only a single instance of each userid. Whew!

We use two auxiliary functions. First-three-in-a-row is #t if the first three integers in a list are in ascending order, or #f otherwise:

(define (first-three-in-a-row xs)
  (and (pair? xs) (pair? (cdr xs)) (pair? (cddr xs))
       (= (+ (car xs) 1) (cadr xs))
       (= (+ (car xs) 2) (caddr xs))))

Cdrs is mis-named, but I can’t think of a better name. Not only does it return a list of all the cdrs of a list, but it also returns the original list:

(define (cdrs xs)
  (do ((ys xs (cdr ys)) (yss (list) (cons (cdr ys) yss)))
      ((null? ys) (cons xs (reverse yss)))))

Running the program tells us that userid 3 appeared on three successive days:

> (three-in-a-row sample-input)
(3)

You can run the program at https://ideone.com/iV61wF.

Advertisements

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: