Topic: [challenge] A35 : Smallest Missing Positive Integer

[JohnK]

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.

[pBe]

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. )

[bruno_vdh]

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]

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.

[pBe]

Can be a little better on limit values...

Code: [Select]

(minMiss '(-2 -1 -5 0)) => nil ; if all numbers are negative or null
l

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]

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

[JohnK]

--->%
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.

[bruno_vdh]

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]

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]

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]

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]

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]

(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]

(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