[racket] Is there a better way to do this in Racket?

From: Danny Yoo (dyoo at hashcollision.org)
Date: Sun May 13 17:34:19 EDT 2012

On Sun, May 13, 2012 at 4:47 PM, Harry Spier <vasishtha.spier at gmail.com> wrote:
> Is there a better way to do this iin Racket (shorter, clearer, more readable)?

The problem "feels" like a state machine problem, in that we can
imagine a machine in either one of two states: we're searching for the
start of a sequence of ones, or looking for the end of a sequence of
ones.  We can represent being in a state via function call.  The
following code is one way to do so:


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
#lang racket
(require rackunit)


;; Returns the ranges where 1's appear.
;;
#| Design: we'll do this with a state machine approach.

         +---+
         |   v
  -> scanning-for-start ------> scanning-for-end
             ^                        |
             +------------------------+

We start scanning-for-start, and bound between that function and
scanning for end.
|#


;; list-of-ranges-of-ones: (vectorof number) -> (listof (list number number))
(define (list-of-ranges-of-ones nums)


  ;; scanning-for-start: number -> (listof (list number number))
  (define (scanning-for-start i)
    (cond
      [(= i (vector-length nums))
       '()]
      [(= 1 (vector-ref nums i))
       (scanning-for-end i (add1 i))]
      [else
       (scanning-for-start (add1 i))]))

  ;; scanning-for-end: number -> (listof (list number number))
  (define (scanning-for-end start i)
    (cond
      [(= i (vector-length nums))
       (list (list start (sub1 i)))]
      [(= 1 (vector-ref nums i))
       (scanning-for-end start (add1 i))]
      [else
       (cons (list start (sub1 i))
             (scanning-for-start (add1 i)))]))

  (scanning-for-start 0))


(check-equal? (list-of-ranges-of-ones #(0))
              '())
(check-equal? (list-of-ranges-of-ones #(0 0))
              '())
(check-equal? (list-of-ranges-of-ones #(0 0 0))
              '())
(check-equal? (list-of-ranges-of-ones #(1))
              '((0 0)))
(check-equal? (list-of-ranges-of-ones #(1 1))
              '((0 1)))
(check-equal? (list-of-ranges-of-ones #(1 1 1))
              '((0 2)))
(check-equal? (list-of-ranges-of-ones #(1 1 1 0))
              '((0 2)))
(check-equal? (list-of-ranges-of-ones #(0 1 1 1))
              '((1 3)))
(check-equal? (list-of-ranges-of-ones #(0 1 1 1 0))
              '((1 3)))
(check-equal? (list-of-ranges-of-ones #( 0 1 1 1 0 0 0 1 1 1 0))
              '((1 3) (7 9)))
(check-equal? (list-of-ranges-of-ones #( 1 1 1 1 0 0 0 1 1 1 1))
              '((0 3) (7 10)))
(check-equal? (list-of-ranges-of-ones #( 0 1 0 1 0 1 0 1 0 1 0))
              '((1 1) (3 3) (5 5) (7 7) (9 9)))

Posted on the users mailing list.