Topic: [challenge] A33 : Largest Gap Sum

[JohnK]

Given an list of integers, return the largest gap summation between elements of that list.

Here's an illustrative example. Consider the list:

[9, 4, 26, 26, 0, 0, 5, 20, 6, 25, 5]
which, sorted (for human readability), becomes
[0, 0, 4, 5, 5, 6, 9, 20, 25, 26, 26]
we can now see that the largest gap in the list is the gap between 9 and 20.
so: (+ 10 11 12 13 14 15 16 17 18 19) = 145

NOTE:
        - There is no need to sort this array.
        - This can be solved in a single pass over the list.
        - summation can only occur with two or more numbers.

Examples
(largestGapsum '(9 4 26 26 0 0 5 20 6 25 5))
> 145

(largestGapsum '(14 13 7 1 4 12 3 7 7 12 11 5 7))
> 27
; (+ 8 9 10)

(largestGapsum '(3 8 5 5 2 6 14 2 11 4 10 13 8 1 9))
> 0
; because the largest gap is only one number 12 and/or 7.
; and `sum` the addition of two or more numbers.
; (+ 12) and/or (+ 7)

[pBe]

NOTE:
        - There is no need to sort this array. ✓
        - This can be solved in a single pass over the list. ✓
        - summation can only occur with two or more numbers. ✓

First try, not pretty but...

Code - Auto/Visual Lisp: [Select]

1. (defun _largestGapsum (ls / a p l lst _l)
2.   (setq m (apply 'max ls) _l ls )
3.   (while (setq a (Car ls))
4.     (and (not (member a p))(setq p (cons a p))
5.             (while (and              
6.                      (not (member (setq a (1+ a)) _l))
7.                      (< a m)
8.                    )
9.               (setq l (cons a l))
10.             )
11.         )
12.     (cond
13.       ((<= (length l) 1)        )
14.       ((and l (> (length l) (length lst)) (setq lst l)) )
15.        )  
16.     (setq l nil ls (cdr ls))
17.   )
18.   (apply '+ lst)
19.  
20. )

[pBe]

Same logic.. less variables

Code - Auto/Visual Lisp: [Select]

1. (defun _largestGapsum (ls / m lst)
2.   (setq m (apply 'max ls))
3.   (mapcar (function (lambda (n / a l)
4.                       (while (and (not (member (setq n (1+ n)) ls))
5.                                   (< n m)
6.                              )
7.                         (setq l (cons n l))
8.                       )
9.                       (and l
10.                            (> (length l) 1)
11.                            (> (length l) (length lst))
12.                            (setq lst l)
13.                       )
14.                     )
15.           )
16.           ls
17.   )
18.   (apply '+ lst)
19. )

[bruno_vdh]

Hello JohnK,

I hesitated to give an answer, because I am not sure to translate well

Given an list of integers, return the largest gap summation between elements of that list.

So I have a doubt about the expected result
Example:

Code: [Select]

(largestGapsum '(4 8 11)) return 18 or 19?
because (+ 5 6 7) = 18 is the largest interval
and (+ 9 10) = 19 is the largest sum
Otherwise quickly in first approach a code based on the calculation of the largest sum,

Code - Auto/Visual Lisp: [Select]

1. (defun largestGapsum (l / f)
2.   (defun f (a b acc)
3.     (cond ((>= a b) (if (cdr acc) (list acc)))
4.           ((member a l) (f (1+ a) b acc))
5.           ((or (null acc) (= a (1+ (car acc)))) (f (1+ a) b (cons a acc)))
6.           ((cdr acc) (cons acc (f (1+ a) b (list a))))
7.           (T (f (1+ a) b (list a)))
8.     )
9.   )  
10.  
11.  (apply 'max  (mapcar '(lambda (x) (apply '+ x)) (cons '(0) (f (1+ (apply 'min l)) (apply 'max l) nil))))
12. )

[JohnK]

Hello JohnK,

I hesitated to give an answer, because I am not sure to translate well
--->%

Did I make another mistake?

My version returns 19 as well.

Code: [Select]

Command: (largestGapsum '(4 8 11))
19
It looks like you did a good job.

[JohnK]

Not sure if this has been posted yet, but here was mine.

Code - Auto/Visual Lisp: [Select]

1. (defun largestgapsum (lst / cntr min? sum run maxsum)
2.   ;; largestgapsum
3.   ;; This function will sum the missing numbers and return the
4.   ;; maximum total of those gaps.
5.   ;;
6.   ;; Example:
7.   ;; (largestGapsum '(14 13 7 1 4 12 3 7 7 12 11 5 7))
8.   ;; > 27
9.   ;; because : (+ 8 9 10)
10.   (setq cntr (apply 'max lst)
11.         min? (apply 'min lst)
12.         sum 0
13.         run '()
14.         maxsum '())
15.   (while (>= cntr min?)
16.          (if (not (member cntr lst))
17.            (progn
18.              (while (not (member cntr lst))
19.                     (setq run (cons cntr run)
20.                           cntr (1- cntr)))
21.              (setq sum (apply '+ run))
22.              (if (and (> sum maxsum) (> (length run) 1))
23.                (setq maxsum sum)
24.                )
25.              )
26.            )
27.     (setq cntr (1- cntr)
28.           run '())
29.          )
30.   maxsum
31.   )

[bruno_vdh]

My version returns 19 as well.

Code: [Select]

Command: (largestGapsum '(4 8 11))
19It looks like you did a good job.

Yes a chance in 2  , pBe made the other choice...

Code: [Select]

$ (_largestGapsum '(4 8 11))
18

[pBe]

Hang on, was it summation of the largest gap ? Or largest summation of any gap?

So It would be largestsumgap ?

[pBe]

But your honor, the contract said...

....
we can now see that the largest gap in the list is the gap between 9 and 20.
...

I will file my appeal later  then

Code - Auto/Visual Lisp: [Select]

1. (defun _largestSumGap (ls / l m n p lst)
2. (setq m (apply 'max ls))
3.   (Foreach n  ls
4.     (cond
5.       ((member n p))
6.       ((setq p (cons n p))
7.        (while (and (not (member (setq n (1+ n)) ls))
8.                                   (< n m)
9.                              )
10.                         (setq l (cons n l))
11.                       )
12.        (and l (> (length l) 1) (> (setq l (apply '+ l)) lst)
13.            (setq lst l)
14.                 ))
15.               )
16.     (Setq l nil)
17.       )
18.   lst
19. )
20.  

[JohnK]

Complaints can be filed at: https://www.disney.com/

[pBe]

Complaints can be filed at: https://www.disney.com/

Ouch!

[JohnK]

How was this challenge? I know Bruno flipped me on my ear with his Gauss summation formula (which would have made my attempt at this challenge a lot easier) but I thought it was a fun little problem. Thoughts?

[pBe]

How was this challenge? I know Bruno flipped me on my ear with his Gauss summation formula (which would have made my attempt at this challenge a lot easier) but I thought it was a fun little problem. Thoughts?

You roll over too easy JohnK, can't blame you, Bruno's solution is really good.
I had to look that up.  It appears that the bandage-sounding name guy was a child prodigy. I'm not  math person. but it looks a lot of fun.

Indeed the challenges you come up with are really fun to solve.
What about this for the next one? or is it already asked and answered?

['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']
These strings partially overlap each other. If you manually overlapped them you would get:
SGALWDVPSPV

[JohnK]

--->%
What about this for the next one? or is it already asked and answered?

['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']
These strings partially overlap each other. If you manually overlapped them you would get:
SGALWDVPSPV

Added to my list. Thank you for the idea!