### Author Topic: [challenge] A33 : Largest Gap Sum  (Read 1257 times)

0 Members and 1 Guest are viewing this topic. ##### [challenge] A33 : Largest Gap Sum
« on: March 10, 2022, 10:46:42 AM »
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)
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### pBe

• Bull Frog
• Posts: 401 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #1 on: March 11, 2022, 12:51:13 AM »
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

• Bull Frog
• Posts: 401 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #2 on: March 11, 2022, 01:11:33 AM »
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

• Newt
• Posts: 82 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #3 on: March 11, 2022, 09:19:21 AM »
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 intervaland (+ 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. ) ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #4 on: March 11, 2022, 09:39:28 AM »
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.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #5 on: March 11, 2022, 09:40:39 AM »
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.              (while (not (member cntr lst))
18.                     (setq run (cons cntr run)
19.                           cntr (1- cntr)))
20.              (setq sum (apply '+ run))
21.              (if (and (> sum maxsum) (> (length run) 1))
22.                (setq maxsum sum)
23.                )
24.              )
25.            )
26.     (setq cntr (1- cntr)
27.           run '())
28.          )
29.   maxsum
30.   )
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### bruno_vdh

• Newt
• Posts: 82 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #6 on: March 11, 2022, 09:53:46 AM »
My version returns 19 as well.
Code: [Select]
`Command: (largestGapsum '(4 8 11))19`It 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

• Bull Frog
• Posts: 401 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #7 on: March 11, 2022, 10:38:38 AM »
Hang on, was it summation of the largest gap ? Or largest summation of any gap?

So It would be largestsumgap ?

#### pBe

• Bull Frog
• Posts: 401 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #8 on: March 11, 2022, 01:06:27 PM »
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. ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #9 on: March 11, 2022, 01:21:09 PM »
Complaints can be filed at: https://www.disney.com/
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### pBe

• Bull Frog
• Posts: 401 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #10 on: March 11, 2022, 01:45:18 PM » ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #11 on: March 11, 2022, 02:12:18 PM » 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?
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

#### pBe

• Bull Frog
• Posts: 401 ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #12 on: March 11, 2022, 11:04:33 PM »
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.

['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']
These strings partially overlap each other. If you manually overlapped them you would get:
SGALWDVPSPV ##### Re: [challenge] A33 : Largest Gap Sum
« Reply #13 on: March 17, 2022, 10:44:27 AM »
--->%