NZEC on INVCNT with Guile on Spoj

Question

Filtering accross a very long list can run you into the maximum recusion error (specs say up to ten million) Instead of using '(length (filter ...' use a fold

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
            (fold
              (lambda (init next)
                (if (> (car l) next)
                    (+ init 1)
                    init))
              0
              (cdr L)))
         (cdr L)))))

Second though this would be easier to read pulling out that fold into it's own function

(define (inversions-from-car L)
  (fold
     (lambda (init next)
        (if (> (car l) next)
            (+ init 1)
            init))
      0
      (cdr L)))

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
             (inversions-from-car L)     
         (cdr L)))))

This looks like a good problem to play with data structures, because as written, it's n^2 complexity.

I think you can get it down to n(log n)

Say create a sorted tree on the list of value paired with the # of nodes to the left. for this set

'(2 3 8 6 1) -> '(1 2 3 6 8) -> 
(*tree (*entry 3 2 2)
       (*tree (*entry 2 1 1)
              (*tree (*entry 1 0 1)
                     ()
                     ())
              ())
        (*tree (*entry 8 1 1)
               (*tree (*entry 6 0 1)
                      ()
                      ())
               ()))

*tree and *entry are just type-tage *tree should have an entry, a left and a right *entry should have a value, #left, and number)

Start by finding the the FIRST in the orginal list with a zero accumulator

'(2 3 8 6 1)

If the value of the enrty matched to FIRST, add #left to the accumulator

If the value is entry is more than FIRST recurse on the left branch of the tree with accumulator

If the value of the entry is less then FIRST , recurse on the right branch with #left added to the accumulator

If it's a null-tree throw an error

Then you need to update the tree.

If the value of the entry equal to FIRST, mutate the entry to reduce the number by one

If the value is entry is more then FIRST, mutate the entry toreduce #left by one and recurse on the left branch

If the value of the entry is less than first , recurse on the right branch

If it's a null-tree throw an error

You can combine these rules into a single traversal

Additionally add the rule that if #left is 0 and number is zero, then if the right branch is null mutate this tree to the empty-tree else the right-branch.

Here's a rough (untested version of the idea)

(define (rev-sorted-list->count-list L) ;;sort should be resverse of
                                        ;; final desired order
 (let loop ((value (car L)) (count 1) (L (cdr L)) (acc '()))
   (cond ((null? L) '())
         ((= value (car l))
          (loop value (+ 1 count) (cdr L) acc))
         (else 
          (loop (car l) 1 (cdr L) (cons (cons value count) acc))))))

(define (make-tree count c-L)
 (let* ((middle (ceiling (+ 1 count) 2))
        (left-count (- middle 1))
        (right-count (-count middle))
        (left (if (= 0 left-count)
                  null-tree 
                  (make-tree left-count c-L)))
        (entry+right
          (let loop ((index 1) (L c-L))
            (if (= index middle) 
                L
                (loop (+ 1 index) (cdr L)))))
        (entry 
         (make-entry 
           (caar entry+right)
           left-count
           (cdar entry+right))))
    (build-tree 
       entry
       left
       (if (= 0 right-count)
           null-tree
           (make-tree right-count (cdr entry+right))))))     

;;form left branches from starting points
;;;form right from stopping points
;;never mutating c-L or copies

;;if count = 0 then null tree

(define (build-tree entry left right)
  (list '*tree entry left right) 

(define (entry tree)
 (cadr tree)
(define (left-branch tree)
 (caddr tree))
(define (right-branch tree)
 (cadddr tree))

(define null-tree (list '*tree '()))
(define (null-tree? tree)
 (null? (entry tree)))

(define (make-entry value Nleft count)
 (let ((vec (make-vector 3)))
  (begin (vector-set! vec 0 value)
         (vector-set! vec 1 Nleft)
         (vector-set! vec 2 count)
         vec)))

;;might meessage passing function here

(define (entry-value entry)
 (vector-ref entry 0))

(define (entry-Nleft entry)
 (vector-ref entry 1))

(define (entry-Nleft-set! entry int)
 (vector-set! entry 1 int))

(define (entry-count entry)
 (vector-ref entry 2))

(define (entry-count-set! entry int)
 (vector-set! entry 2 int))

(define (inversions! Test-List Search-Tree)
 (let loop ((acc 0) (L Test-list) (T Search-tree))
   (cond ((null? L) acc)
         ((null-tree? T) (error "null tree " 
                                 "in inner loop of inversion!"))
         ((= (car L) (entry-value (entry T)))
          (entry-count-set! (entry T)
                            (- (entry-count (entry T)) 1))
          (if (and (= 0 (entry-count (entry T)))
                   (= 0 (entry-Nleft (entry T))))
               (set-cdr! T (right-branch T))
               'skip)
          (loop (+ acc (entry-Nleft (entry T)))
                (cdr L)
                Search-tree))
         ((< (car L) (entry-value (entry T)))
          (entry-Nleft-set! (entry T)
                            (- (entry-Nleft (entry T)) 1))
          (loop acc L (left-branch T)))
         ((> (car L) (entry-value (entry T)))
          (loop (+ acc (entry-Nleft (entry T)))
                L
                (right-branch T))))))