On Sun, May 13, 2012 at 4:47 PM, Harry Spier <vasishtha.sp...@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)))
____________________
Racket Users list:
http://lists.racket-lang.org/users
