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

0 Members and 1 Guest are viewing this topic.

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
[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 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

  • Administrator
  • Seagull
  • Posts: 10140
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

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
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.            (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.   )
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 :-D

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

  • Administrator
  • Seagull
  • Posts: 10140
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 »

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
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.
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

  • Administrator
  • Seagull
  • Posts: 10140
Re: [challenge] A33 : Largest Gap Sum
« Reply #13 on: March 17, 2022, 10:44:27 AM »
--->%
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!
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org