Longest chain of element in lisp

user_13078497 0
Viewed 164

Statement: Sind the longest chain of character and return it. Ex: input: '(1 2 2 3 3 3 4 4 4 4 5 6 ) ouput: '(4 4 4 4)

Problem: I can manage to identify all the different groups in the list and compare them but can't get the function to return the right subset list. It only returns the last group analyzed.

code:

(define finalL (list))
(define (sameNum liste) 
  (if (or (null? liste) (null? (cdr liste)))
      ;; true
      '()
      ;; false
      (let ([lcdr (sameNum (cdr liste))]) 
        (if (eqv? (car liste) (car(cdr liste)) )
            ;; true
            (if (= (length liste) 2)
                ;; true
                (cons (car liste) (cons (car(cdr liste)) lcdr)) 
                ;; false
                (if (or (not(eqv? (car(cdr liste)) (car(cdr (cdr liste))) )) (null? (cdr liste)) )
                    (cons (car liste) (cons (car(cdr liste)) lcdr)) ;true
                    (cons (car liste) lcdr))) ; false
             ;; false
            (if (let ((x (length lcdr)) (y (length finalL))) (< x y))
                ;; true
                (crushL finalL lcdr)
                ;; false
                finalL)))))
;; crush L1 and replace by value of L2
(define (crushL L1 L2)
  (if (null? L1)
      ;; true
      (cons L2 L1)
      ;; false
      (crushL (cdr L1) L2)))
scheme lisp
1 Answers

The trick is to keep four things as you walk down the list:

  • the current chain (note: you can build these backwards, since all the elements are the same!);
  • how long it is;
  • the longest chain you've seen;
  • how long that was.

Then you make decisions based on whether the element you are looking at is the same as the first element in the current chain (still building the same chain) or not (starting a new chain) and, if you are still building the same chain, whether that chain is now the longest.

Like this:

(define (longest-chain l)
  (let lc-loop ([tail l]
                [current-length 0]
                [current-chain '()]
                [longest-length 0]
                [longest-chain '()])
    (cond [(null? tail)
           ;; we're done: return the longest chain
           longest-chain]
          [(and (not (null? current-chain))
                (eqv? (first tail) (first current-chain)))
           ;; building on a current chain
           (let ([chain (cons (first tail) current-chain)]
                 [chain-length (+ 1 current-length)])
             (if (> chain-length longest-length)
                 ;; the current chain is now the longest
                 (lc-loop (rest tail)
                          chain-length chain
                          chain-length chain)
                 ;; it's not the longest yet
                 (lc-loop (rest tail)
                          chain-length chain
                          longest-length longest-chain)))]
          [else
           ;; starting a new chain
           (lc-loop (rest tail)
                    1 (list (first tail))
                    longest-length longest-chain)])))

For extra points: if there is more than one longest chain, which one does this function return? How could you change that so it makes the other choice? Or even a random choice!

Note the above version of the function uses named let, which is a standard construct in Scheme. If you don't want to use that you can just turn it into an explicit function:

(define (longest-chain l)
  (define (lc-loop tail
                   current-length current-chain
                   longest-length longest-chain)
    (cond [(null? tail)
           ;; we're done: return the longest chain
           longest-chain]
          [(and (not (null? current-chain))
                (eqv? (first tail) (first current-chain)))
           ;; building on a current chain
           (let ([chain (cons (first tail) current-chain)]
                 [chain-length (+ 1 current-length)])
             (if (> chain-length longest-length)
                 ;; the current chain is now the longest
                 (lc-loop (rest tail)
                          chain-length chain
                          chain-length chain)
                 ;; it's not the longest yet
                 (lc-loop (rest tail)
                          chain-length chain
                          longest-length longest-chain)))]
          [else
           ;; starting a new chain
           (lc-loop (rest tail)
                    1 (list (first tail))
                    longest-length longest-chain)]))
  (lc-loop l 0 '() 0 '()))

This is entirely equivalent to the above version. If you're not happy with internal defines, then you can turn lc-loop into a top-level definition.

Admin1
Related