Author Topic: [challenge] A35 : Smallest Missing Positive Integer  (Read 1049 times)

0 Members and 1 Guest are viewing this topic.

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
[challenge] A35 : Smallest Missing Positive Integer
« on: March 17, 2022, 10:27:31 AM »
Given an list of integers, return the smallest positive integer not present in the list.

Here is a illustrative example. Consider the list:

[-2, 6, 4, 5, 7, -1, 7, 1, 3, 6, 6, -2, 9, 10, 2, 2]
After reordering (for your benefit), the list becomes:

[-2, -2, -1, 1, 2, 2, 3, 4, 5, 6, 6, 6, 7, 7, 9, 10]
now we see that the smallest missing positive integer is 8.

Examples
(minMiss '(-2 6 4 5 7 -1 1 3 6 -2 9 10 2 2))
> 8

(minMiss '(5 9 -2 0 1 3 9 3 8 9))
> 2
;; Sorting the list we can see the answer is 2 [-2, 0, 1, 3, 3, 5, 8, 9, 9, 9]

(minMiss '(0 4 4 -1 9 4 5 2 10 7 6 3 10 9))
> 1
;; Sorting the list we can see the answer is 1 [-1, 0, 2, 3, 4, 4, 4, 5, 6, 7, 9, 9, 10, 10]

Note: zero (0) is not considered to be a positive number.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

pBe

  • Bull Frog
  • Posts: 401
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #1 on: March 17, 2022, 12:52:02 PM »
First blood
Code - Auto/Visual Lisp: [Select]
  1. (defun minMiss (l / a)
  2.   (setq a (apply 'min l))
  3.   (while (or (member (setq a (1+ a)) l)
  4.              (< a 1)
  5.          )
  6.         )
  7.   a
  8. )
« Last Edit: March 17, 2022, 12:55:44 PM by pBe »

bruno_vdh

  • Newt
  • Posts: 82
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #2 on: March 17, 2022, 06:13:48 PM »
Hi, my version, in the same spirit as pBe:
Code - Auto/Visual Lisp: [Select]
  1. (defun minMiss (l / x)
  2.   (setq x 0)
  3.   (while (member (setq x (1+ x)) l))
  4.   (if (< x (apply 'max l)) x)
  5. )

Can be a little better on limit values...
Code: [Select]
(minMiss '(-2 -1 -5 0)) => nil ; if all numbers are negative or null
(minMiss '(-2 -1 0 1 2 3)) => nil; if there is no missing number
(minMiss nil) => nil ; if the list is nil

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #3 on: March 17, 2022, 07:49:37 PM »
Mine was also in the same sprit.

Code - Auto/Visual Lisp: [Select]
  1. (defun minMiss (lst / cntr minmiss)
  2.   ;; minMiss
  3.   ;; Returns the smallest positive integer not present in list.
  4.   ;;
  5.   ;; (minMiss '(0 4 4 -1 9 4 5 2 10 7 6 3 10 9))
  6.   ;; > 8
  7.   (setq cntr (apply 'max lst)
  8.         cntr (1- cntr)
  9.         minm 0)
  10.   (while (not (> 1 cntr))
  11.      (if (not (not (member cntr lst)))
  12.           (setq minm cntr)
  13.           )
  14.      (setq cntr (1- cntr))
  15.      )
  16.   minm
  17.   )

I did not think of those possibilities--bruno has mentioned--so I will be revising mine to address those conditions. I will see if I can think of any more conditions and post those so everyone can have fun too.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

pBe

  • Bull Frog
  • Posts: 401
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #4 on: March 17, 2022, 07:59:02 PM »

Can be a little better on limit values...
Code: [Select]
(minMiss '(-2 -1 -5 0)) => nil ; if all numbers are negative or null
l

:D Oddly enough I knew someone will say that BUT again your honor, 1 is the smallest positive integer and not present (also missing) on the list,
IT did not say within range of the numbers present on the list.

Same way if the list are all positive numbers
Code - Auto/Visual Lisp: [Select]
  1. (minMiss_Bvdh '( 45 89 74)) => 1
But then again..
Code - Auto/Visual Lisp: [Select]
  1. (minMiss_pBe '( 45 89 74)) => 46




pBe

  • Bull Frog
  • Posts: 401
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #5 on: March 17, 2022, 08:25:28 PM »

I did not think of those possibilities--bruno has mentioned--so I will be revising mine to address those conditions. I will see if I can think of any more conditions and post those so everyone can have fun too.

I guess there's more appeal piling up :)

Code - Auto/Visual Lisp: [Select]
  1. (defun minMiss (l / a)
  2.   (cond
  3.     ((< (setq m (apply 'max l)) 1) nil)
  4.     ((and
  5.        (setq a (apply 'min l))
  6.        (not (while (or (member (setq a (1+ a)) l)
  7.                        (< a 1)
  8.                    )
  9.             )
  10.        )
  11.        (< a m)
  12.      )
  13.      a
  14.     )
  15.   )
  16. )

Code - Auto/Visual Lisp: [Select]
  1. (minMiss '(-2 6 4 5 7 -1 1 3 6 -2 9 10 2 2))  => 8
  2. (minMiss '(5 9 -2 0 1 3 9 3 8 9))  => 2
  3. (minMiss '(0 4 4 -1 9 4 5 2 10 7 6 3 10 9))  => 1
  4. (minMiss '( 45 89 74)) => 46
  5. (minMiss '(-2 -1 -5 0 2)) => 1

Not within range of the list
Code - Auto/Visual Lisp: [Select]
  1. (minMiss '(-1 -2 1 2 3 4 5 6 7 8))  => nil
  2. (minMiss '(-2 -1 -5 0))  => nil
  3. (minMiss '(-2 -1 0 1 2 3))  => nil
  4. (minMiss nil) => nil
  5. (minMiss '(45 46 47 48)) => nil
« Last Edit: March 17, 2022, 08:31:54 PM by pBe »

JohnK

  • Administrator
  • Seagull
  • Posts: 10140
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #6 on: March 17, 2022, 08:52:10 PM »
--->%
1 is the smallest positive integer and not present (also missing) on the list,
IT did not say within range of the numbers present on the list.

Same way if the list are all positive numbers
Code - Auto/Visual Lisp: [Select]
  1. (minMiss_Bvdh '( 45 89 74)) => 1
But then again..
Code - Auto/Visual Lisp: [Select]
  1. (minMiss_pBe '( 45 89 74)) => 46

Okay, that tosses a wrench into the mix! 1 or 46? ...I think we should consider the lower, positive, bounds of the list to be the floor so then 46 would the proper return. The reasoning is that otherwise 1 would be returned more often than not.

REDO for me in the morning.
TheSwamp.org (serving the CAD community since 2003)

Donate to TheSwamp.org

bruno_vdh

  • Newt
  • Posts: 82
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #7 on: March 18, 2022, 04:38:42 AM »
Same way if the list are all positive numbers
Code - Auto/Visual Lisp: [Select]
  1. (minMiss_Bvdh '( 45 89 74)) => 1
But then again..
Code - Auto/Visual Lisp: [Select]
  1. (minMiss_pBe '( 45 89 74)) => 46

Oops, sorry I missed this one, thanks....
Code - Auto/Visual Lisp: [Select]
  1. (defun minMiss (l / x)
  2.   (if (minusp (setq x (apply 'min l))) (setq x 0))
  3.   (while (member (setq x (1+ x)) l))
  4.   (if (< x (apply 'max l)) x)
  5. )

The error is corrected
Code: [Select]
_$ (minMiss '( 45 89 74))
46

bruno_vdh

  • Newt
  • Posts: 82
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #8 on: March 18, 2022, 06:54:57 AM »
I did not think of those possibilities--bruno has mentioned--so I will be revising mine to address those conditions. I will see if I can think of any more conditions and post those so everyone can have fun too.
John a small thought that I want to share: In general in a code, the game is not to find what we want, but to find within reason what we do not want... ;-)

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1314
  • Marco
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #9 on: March 18, 2022, 04:05:21 PM »
Code: [Select]
(defun MinMiss_a (L / x)
  (if (setq L (cdr (member 0 (vl-sort (cons 0 L) '<))))
    (cond
      ( (and (= 2 (car L))  (cadr L))     1 )
      ( (and (= 1 (car L)) (= 3 (cadr L))) 2 )
      ( T
        (while L
          (if (= (setq x (1+ (car L))) (cadr L))
            (setq L (cdr L))
            (progn (or (cdr L) (setq x nil)) (setq L nil))
          )
        )
        x
      )
    )
  )
)
Edit: I have to fix  (minMiss_a '(2 3))...

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1314
  • Marco
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #10 on: March 18, 2022, 05:10:38 PM »
Maybe this…
Code: [Select]
(defun MinMiss_a2 (L / x f)
  (cond
    ( (and (setq f (member 0 L)) (member 2 L) (not (member 1 L))) 1 )
    ( (setq L (member 0 (vl-sort (cons 0 L) '<)))
      (cond
        ( (and (= 1 (cadr L)) (= 3 (caddr L))) 2 )
        ( T
          (or f (setq L (cdr L)))
          (while L
            (if (= (setq x (1+ (car L))) (cadr L))
              (setq L (cdr L))
              (progn (or (cdr L) (setq x nil)) (setq L nil))
            )
          )
          x
        )
      )
    )
  )
)
Edit 20220321: a little bit better
Code: [Select]
(defun MinMiss_a3 (L / x f)
  (cond
    ( (and (setq f (member 0 L)) (member 2 L) (not (member 1 L))) 1 )
    ( (and L (setq L (member 0 (vl-sort (cons 0 L) '<))))
      (cond
        ( (and (= 1 (cadr L)) (= 3 (caddr L))) 2 )
        ( (or f (setq L (cdr L)))
          (while
            (if (= (setq x (1+ (car L))) (cadr L))
              (setq L (cdr L))
              (if (cdr L) nil (setq x nil))
            )
          )
          x
        )
      )
    )
  )
)

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1314
  • Marco
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #11 on: March 20, 2022, 04:40:37 AM »
Code: [Select]
(setq AList1 '(-2 6 4 5 7 -1 1 3 6 -2 9 10 2 2))
--- Benchmark utility: In memory of Michael Puckett ---
    (MINMISS_A2 ALIST1)......1547 / 1.29 <fastest>
    (MINMISS_JK7 ALIST1).....1765 / 1.13
    (MINMISS_VDH ALIST1).....1844 / 1.08
    (MINMISS_PBE ALIST1).....2000 / 1 <slowest>

(setq AList2 '(84 104 105 115 256 32 105 115 256 32 97  256 32 98 105 103 256 32 108 111 110 103  256 32 116 101 120 116  256 32 115 116 114 105
110 103 32 119 104 105 99 104 32 119 105 -2 6 4 5 7 -1 1 3 6 -2 9 10 2 2 108 108 32 114 101 115 117 108 116 32 105 110 32 97 32 115 109 97 108 108 32 108 105 115 116 32 111
102 32 110 117 109 98 101 114 115 46))
    (MINMISS_VDH ALIST2)......1735 / 26.84 <fastest>
    (MINMISS_A2 ALIST2).......1782 / 26.13
    (MINMISS_PBE ALIST2)......2609 / 17.85
    (MINMISS_JK7 ALIST2).....46563 / 1 <slowest>

apricot125

  • Mosquito
  • Posts: 13
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #12 on: July 11, 2022, 09:33:24 PM »
(defun MinMissInteger (int lst)
  (if (member int lst)
    (MinMissInteger (1+ int) lst)
    int
    ))

(setq lst '(0 4 4 -1 9 4 5 2 10 7 6 3 10 9))
(MinMissInteger 1 lst)
;;; > 1
(setq lst '(-2 6 4 5 7 -1 1 3 6 -2 9 10 2 2))
(MinMissInteger 1 lst)
;;; > 8
(setq lst '(5 9 -2 0 1 3 9 3 8 9))
(MinMissInteger 1 lst)
;;; > 2
(setq lst '(0 4 4 -1 9 4 5 2 10 7 6 3 10 9))
(MinMissInteger 1 lst)
;;; > 1
(MinMissInteger 1 '(45 85 74))
;;; > 1

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1314
  • Marco
Re: [challenge] A35 : Smallest Missing Positive Integer
« Reply #13 on: July 12, 2022, 04:31:13 PM »
(defun MinMissInteger (int lst)
  (if (member int lst)
    (MinMissInteger (1+ int) lst)
    int
    ))

(setq lst '(0 4 4 -1 9 4 5 2 10 7 6 3 10 9))
(MinMissInteger 1 lst)
;;; > 1
(setq lst '(-2 6 4 5 7 -1 1 3 6 -2 9 10 2 2))
(MinMissInteger 1 lst)
;;; > 8
(setq lst '(5 9 -2 0 1 3 9 3 8 9))
(MinMissInteger 1 lst)
;;; > 2
(setq lst '(0 4 4 -1 9 4 5 2 10 7 6 3 10 9))
(MinMissInteger 1 lst)
;;; > 1
(MinMissInteger 1 '(45 85 74))
;;; > 1
(MinMissInteger 1 '(45 85 74));;; > 1