list challenge

[Moshe-A]

Hi experts,

say i have this sorted list:

'(0 1 4 5 9)

looking for an efficient function to return:

'(0 1 nil nil 4 5 nil nil nil 9)

e.g add a 'nil' as a placeholder for any missing number.

thanks in advance

Moshe

[john.kaulB9QW2]

Very quickly! Here are several versions that should work.

;;;;;
;; use a recursive process (simplest)
(defun fill (lst)
  (defun range (cntr lst)
    (if	lst
      (if (= cntr (car lst))
	(cons (car lst) (range (1+ cntr) (cdr lst)))
	(cons nil (range (1+ cntr) lst)))) )
  (if lst (range (car lst) lst))
)

;;;;;
;; use a recursive-iterative process
(defun fill-ri (cntr lst sofar)
    (if	lst
      (if (= cntr (car lst))
        (fill-ri (1+ cntr) (cdr lst) (cons (car lst) sofar))
        (fill-ri (1+ cntr) lst (cons nil sofar)))
      (reverse sofar)) )

;; create a wrapper function
(defun fill-wrapper (lst)
  ;; we can safely preload the lists for faster processing
  (fill-ri (1+ (car lst)) (cdr lst) (list (car lst))))

(fill-wrapper '(1 2 5 9))

;;;;;
;; AND/OR

; allow for alternate sorting. (most flexible)
(defun fill-ri (cntr lst sofar)
    (if	lst
      (if (= cntr (car lst))
        (fill-ri (proc cntr) (cdr lst) (cons (car lst) sofar))
        (fill-ri (proc cntr) lst (cons nil sofar)))
      (reverse sofar)) )

;; create a wrapper
(defun fill-wrapper (proc lst)
  (fill-ri (proc (car lst)) (cdr lst) (list (car lst))))

(defun fill (lst)
  (fill-wrapper
    ;; increment
     (lambda (x) (1+ x))
     lst))

(fill '(-3 1 2 5 9))

;;;;;
;; OR
;; defined separately
(set 'plus (lambda (x) (1+ x)))
(set 'minus (lambda (x) (1- x)))
;... you get the idea.

[Sea-Haven]

You should acknowledge that these are from The Swamp, the task was seriously increased. Are you the author ?

[challenge] A24 : Add missing values to a list sequence (theswamp.org)

[hak_vz]

--

[john.kaulB9QW2]

Of course I'm the author! And I'm the one that increased the difficulty on the task.

[Kent1Cooper]

---

@john.kaulB9QW2 wrote:

.... I'm the one that increased the difficulty on the task.

---

.... and said there:
".... The OP said the list was sorted so we can disregard or totally ignore the "always in order question" ... But ... what about reverse order?
Questions to consider:
(fill '(1 2 3 9 8 6))

> 1 2 3 nil nil nil nil nil 9 8 nil 6)
...."

That increases the difficulty, but it's self-contradictory, if what you mean is that we can ignore that question because it will always be sorted, and then you proceed to suggest a list that is not sorted.

Also, I'm having an even harder time imagining any possible use for something like that, than for the result with a sorted list.  But we haven't heard anything from the OP about what they want it for, so it's hard to say whether such a variant could be usable for anything.

[john.kaulB9QW2]

Increasing the difficulty was exactly the point. As the request stood it was not enough fun.

As far as placing 'nil' in-between, I do not see the need but the OP must.

As far as "list sorting" goes, sorting does not always mean smallest to greatest so it is NOT contradictory.

Example:
Here is a sorted list.
(84 104 101 32 110 117 109 98 101 114 32 115 101 118 101 110)

What would happen if you change the order?

hint:
(mapcar 'chr '(84 104 101 32 110 117 109 98 101 114 32 115 101 118 101 110))

The point being, in cases like this lists should be treated as that. In essence I question the need for sorting itself; programs should be able to chew up data and ignore the things it doesn't care about.

For example: parsing a string.
To parse a string you look for tokens, you chunk up bits at a time looking for a pattern. Spaces--more often then not--are not really part of that pattern so should I remove all the 32's from the list above before I process it (looking for a number string). No, that would take up far too much processing power on a large list/string. It's far more efficient to write your list processing widget to just ignore them and anything else you don't care about.

[Kent1Cooper]

---

@john.kaulB9QW2 wrote:

....

As far as "list sorting" goes, sorting does not always mean smallest to greatest so it is NOT contradictory.

....

---

I truly think that at least in the context of AutoCAD, and especially when the list is of numbers, virtually all Users would consider "sorting" to be either smallest to largest or vice versa.  Your example may be an "ordered" list, but I would not consider it "sorted."  Note that every single example in the AutoLisp Reference entries for both the (vl-sort) and (vl-sort-i) functions involves either a (<) or a (>) function.

[john.kaulB9QW2]

Okay. So what's your point? I don't mean to sound harsh I am merely asking why does it matter if I want to code a solution up that doesn't (re)sort a list?

Stated another way: Efficiency is also a subjective term but I think we can still agree that sorting is a greatly inefficient task. But sorting aside (I honestly do not care about the sorting other then to make this a bit more fun). But as I said before, if we take the OP at their word the list is pre-sorted (so sorting is not necessary to complete this task). And, unless I'm mistaken this bit of code (out of all the code posted so far) would be the most efficient method for supplying the answer the OP wanted. I'm not trying to bait anyone, just saying this could be a fun little task (albeit "useless" in my opinion). So I hope someone codes up something truly amazing and crushes this code!

(defun fill-ri (cntr lst sofar)
  (if lst
      (if (= cntr (car lst))
        (fill-ri (1+ cntr) (cdr lst) (cons (car lst) sofar))
        (fill-ri (1+ cntr) lst (cons nil sofar)))
      (reverse sofar)) )

(defun fill-wrapper (lst)
  (fill-ri (1+ (car lst)) (cdr lst) (list (car lst))))

(fill-wrapper '(1 4 5 9)

[pbejse]

---

@Moshe-A wrote:

Hi experts,say i have this sorted list: '(0 1 4 5 9) ---> '(0 1 nil nil 4 5 nil nil nil 9)

e.g add a 'nil' as a placeholder for any missing number

---

Just to put something on the table vl-sort, apply, append, mapcar, lambda,cond, while, member, cons, length, reverse, last 

(defun Nullified23 (l)
  (apply 'append
	 (mapcar '(lambda (n / lst)
		    (cond
		      ((= n (last l)) (list (last l)))
		      ((while (not (member (setq n (1+ n)) l))
			 (setq lst (cons nil lst))
		       )
		       (cons (- n (1+ (length lst))) (reverse lst))
		      )
		      ((list (1- n)))
		    )
		  )
		 (setq l (Vl-sort l '<))
	 )
  )
)

🤖

[john.uhden]

In keeping with the desire for a descriptively named function, I offer the following (without comprehending any need for it other than to respond to a challenge and because I am recursively challenged)...

(defun @Anonymous_in_gaps_between_integers_with_nil_that_are_in_any_order (old / new)
  (setq new (list (car old)))
  (while (> (length old) 1)
    (repeat (1- (abs (- (cadr old)(car old))))
      (setq new (cons nil new))
    )
    (setq old (cdr old) new (cons (car old) new))
  )
  (reverse new)
)

I recommend that if you really intend to use such a function that you give it a shorter name.

[john.kaulB9QW2]

That should be very efficient! Great submission.

There are about a dozen entries at TheSwamp so I guess I'll just modify my above solution to not duplicate someone else's concept/code. However, modifying my example above to work with a sorted an "out of order" *sigh* list would make it very inefficient.

We can compare submissions if we get enough people to participate. We can use the output from this for our list (almost straight from the help docs).

(vl-sort-i
  '(a d c b a b b c a q a)
  '(lambda (s1 s2)
     (< (vl-symbol-name s1) (vl-symbol-name s2))
   )
)

I will mod my example above to work with this list.

[john.uhden]

;; Somehow, I think it would be more useful to fill in the gaps with the missing numbers:
(defun @Anonymous_in_gaps_between_integers_that_are_in_original_order (old / a b +- new)
  (setq new (list (car old)))
  (while (> (length old) 1)
    (setq a (car old) b (cadr old) +- (if (minusp (- b a)) - +))
    (repeat (1- (abs (- b a)))
      (setq a (+- a 1) new (cons a new))
    )
    (setq old (cdr old) new (cons (car old) new))
  )
  (reverse new)
)
(setq fill_o @Anonymous_in_gaps_between_integers_that_are_in_original_order)

;; But then, if you want them sorted in ascending order:
(defun @Anonymous_in_gaps_between_integers_into_a_sorted_order (old / i new)
  (setq i (apply 'min old))
  (repeat (1+ (- (apply 'max old) i))
    (setq new (cons i new) i (1+ i))
  )
  (reverse new)
)
(setq fill_s @Anonymous_in_gaps_between_integers_into_a_sorted_order)

[john.uhden]

@john.kaulB9QW2 

In what way would you put that to use?

IOW, what's the purpose?

I still don't understand @Moshe-A 's purpose, unless he just doesn't like gaps.

[john.kaulB9QW2]

Here is my recursive-iterative approach, I posted earlier, revised to work with `out-of-order` lists. NOTE: this will be a very inefficient method for this problem. I did a benchmark and this approach is about 2 - 1.5 times slower then the other methods posted, like john.uhden posted here and some of the other methods posted on TheSwamp. This was a fun little challenge for me, I hope others got some enjoyment. Thank you for the challenge.

(defun fill-ri (cntr lst proc sofar)
  (if lst
      (if (= cntr (car lst))
        (fill-ri cntr (cdr lst) proc sofar)
        (fill-ri (proc cntr) lst proc (cons nil sofar)))
      (reverse sofar)) )

(defun fill-wrapper (lst sofar)
  (set 'proc
         (cond
           ((< (cadr lst) (car lst))
            (lambda (x) (1- x)))
           (T
	    (lambda (x) (1+ x)))))
  (if (cdr lst)
    (fill-wrapper
      (cdr lst)
      (cons (fill-ri (car lst) (list (car lst) (cadr lst)) proc (list (car lst))) sofar))
    (apply 'append (reverse (cons lst sofar)))) )

(defun fill2 (lst)
    (fill-wrapper lst '()) )

[john.uhden]

John,

Please accept my apologies for my first response.  One should not treat a "newcomer" that way.

You will surely add some of my favorite thing to this forum... FUN.

[zylistc]

(setq in (list -3 1 5 8 12));or (setq in (list 1 5 8 -3 12))

(setq lst nil)
(repeat (1+ (- (apply 'max in) (setq n (apply 'min in))))
	(setq lst (cons n lst))
	(setq n (1+ n))
)
(reverse
	(mapcar
		(function
			(lambda (x)
				(if (vl-position x in)
					x
					nil
				)
			)
		)
		lst
	)
)

[john.uhden]

@zylistc 

Albeit you should have copied your code into the code pane </>,

It appears to work just fine.  Nice!