2

I want to learn Elisp so I'm trying to solve perl6 weekly challenges. There is one on the week 48:

Survivor

There are 50 people standing in a circle in position 1 to 50. The person standing at position 1 has a sword. He kills the next person i.e. standing at position 2 and pass on the sword to the immediate next i.e. person standing at position 3. Now the person at position 3 does the same and it goes on until only one survives.

Write a script to find out the survivor.

I want to implement it using rings and see how the sequence is descending, but it seems that when it has two elements it is not working properly, or probably I do not get the point:

ELISP> (setf r (ring-convert-sequence-to-ring (number-sequence 1 5)))
(0 5 .
   [5 4 3 2 1])

ELISP> (princ-list (ring-remove r 1) r)
2(0 4 . [5 4 3 1 nil])

"
"
ELISP> (princ-list (ring-remove r 2) r)
4(0 3 . [5 3 1 nil nil])

"
"
ELISP> (princ-list (ring-remove r 3) r)
1(0 2 . [5 3 nil nil nil])

"
"
ELISP> (princ-list (ring-remove r 4) r)
3(0 1 . [5 nil nil nil nil])

"
"

Maybe at the end of each loop I need to change it but working in another way I get:

ELISP> (setf r (ring-convert-sequence-to-ring (number-sequence 5 1 -1)))
(0 5 .
   [1 2 3 4 5])

ELISP> (princ-list (setf (car r) 1) (ring-remove r) (ring-resize r 4) r)
120(0 4 . [3 4 5 1])

"
"
ELISP> (princ-list (setf (car r) 1) (ring-remove r) (ring-resize r 3) r)
140(0 3 . [5 1 3])

"
"
ELISP> (princ-list (setf (car r) 1) (ring-remove r) (ring-resize r 2) r)
110(0 2 . [3 5])

"
"
ELISP> (princ-list (setf (car r) 1) (ring-remove r) (ring-resize r 1) r)
150(0 1 . [nil])

"

"

But I do not understand the last step.

So firstly I want to know how ring works, and are there circular linked lists in EmacsLisp?

Or maybe I need to focus on the recursive solution of the problem, and not work with circular linked lists.

4

I want to implement it using rings and see how the sequence is descending, but it seems that when it has two elements it is not working properly, or probably I do not get the point

It seems to be working as expected in your example. The key thing to note about rings is that they are modulo-indexed, i.e. if you have the ring (3 5) (from newest element to oldest) and try to remove the element at index 4, then you will be left with the ring (5), as the index 4 modulo the length of the ring 2 is 0, which corresponds to the newest element, which in this case is 3.

But I do not understand the last step.

The last step should make more sense if you read the docstring of ring-resize:

ring-resize is a compiled Lisp function in `ring.el'.

(ring-resize RING SIZE)

Set the size of RING to SIZE.
If the new size is smaller, then the oldest items in the ring are
discarded.

Before calling ring-resize, you have the ring (1 1 . [nil 3]) with size 2, length 1, and oldest element 3 at index 1.

Resizing to 1 means getting rid of the oldest element 3, leaving you with the ring (nil).

The reason this is not a bug in the ring.el package is because you are manually changing the "head" (i.e. the index of the oldest element). The ring structure wouldn't have reached the state (1 1 . [nil 3]) if you used its public API. As Tobias notes, the ring structure itself is an internal implementation detail and not to be relied on externally.

are there circular linked lists in EmacsLisp

Yes, see (elisp) Cons Cells. For example:

(let ((l (list 1 2)))
  (nth 2 l)   ; => nil
  (nconc l l) ; Loop back to the start
  (nth 2 l))  ; => 1

Or maybe I need to focus on the recursive solution of the problem, and not work with circular linked lists.

Actually, I think circular lists are probably the simplest and most efficient solution to this problem in Elisp.

Here's a sample circular solution:

(defun my-survivor-circular (first last)
  "Solve the Survivor puzzle for numbers FIRST through LAST.
Return the single surviving number.
Implemented using a circular list."
  (let ((circle (number-sequence first last)))
    ;; Make circle circular
    (nconc circle circle)
    ;; Kill next person so long as they are not us
    (while (not (eq circle (cdr circle)))
      (setcdr circle (cddr circle))
      ;; Pass sword to next survivor
      (pop circle))
    ;; Return single survivor
    (or (car circle) first)))

(my-survivor-circular 1  0) ; =>  1
(my-survivor-circular 1  1) ; =>  1
(my-survivor-circular 1  2) ; =>  1
(my-survivor-circular 1  3) ; =>  3
(my-survivor-circular 1  4) ; =>  1
(my-survivor-circular 1  5) ; =>  3
(my-survivor-circular 1 50) ; => 37

Here's the same idea but without using circular lists:

(defun my-survivor-proper (first last)
  "Solve the Survivor puzzle for numbers FIRST through LAST.
Return the single surviving number.
Implemented using a proper list."
  (let* ((circle (number-sequence first last))
         (sword  circle))
    ;; As long as there is more than one survivor
    (while (cdr circle)
      ;; Kill next person or one at beginning
      (if (cdr sword)
          (setcdr sword (cddr sword))
        (pop circle))
      ;; Pass sword to next survivor or wrap around to beginning
      (setq sword (or (cdr sword) circle)))
    ;; Return single survivor
    (or (car circle) first)))

(my-survivor-proper 1  0) ; =>  1
(my-survivor-proper 1  1) ; =>  1
(my-survivor-proper 1  2) ; =>  1
(my-survivor-proper 1  3) ; =>  3
(my-survivor-proper 1  4) ; =>  1
(my-survivor-proper 1  5) ; =>  3
(my-survivor-proper 1 50) ; => 37

And finally here's a sample solution using rings:

(defun my-survivor-ring (first last)
  "Solve the Survivor puzzle for numbers FIRST through LAST.
Return the single surviving number.
Implemented using a ring."
  (let ((ring  (ring-convert-sequence-to-ring (number-sequence first last)))
        (sword first))
    (while (> (ring-length ring) 1)
      (let* ((kill (ring-next ring sword))
             (next (ring-next ring kill)))
        (ring-remove ring (ring-member ring kill))
        (setq sword next)))
    (if (ring-empty-p ring) first sword)))

(my-survivor-ring 1  0) ; =>  1
(my-survivor-ring 1  1) ; =>  1
(my-survivor-ring 1  2) ; =>  1
(my-survivor-ring 1  3) ; =>  3
(my-survivor-ring 1  4) ; =>  1
(my-survivor-ring 1  5) ; =>  3
(my-survivor-ring 1 50) ; => 37

As you can see, the ring does not lend itself as neatly or as efficiently to this problem as a circular list. I think this is because a ring's circularity is inherent in its index, rather than its data, and perhaps because Emacs' ring API could be enriched.

|improve this answer|||||
  • really great explained, working with circular lists in Elisp – anquegi Feb 19 at 15:24
3

Don't look at the innards of the ring. That is an implementation detail. Look at the results of the interface functions.

You can see what's in the ring with ring-elements. The list indexes of that list are also the indexes of the elements in the ring.

(let ((r (ring-convert-sequence-to-ring (number-sequence 1 5))))
  (ring-elements r))

(1 2 3 4 5)

Let us remove element 1 and look at the resulting list:

(let ((r (ring-convert-sequence-to-ring (number-sequence 1 5))))
  (ring-remove r 1)
  (ring-elements r))

(1 3 4 5)

The element 2 is removed.

If we reference the new element at index 1 we get 3:

(let ((r (ring-convert-sequence-to-ring (number-sequence 1 5))))
  (ring-remove r 1)
  (ring-ref r 1))

3

So the solution of the task at hand is:

;; (org-src-debug)
(let ((r (ring-convert-sequence-to-ring (number-sequence 1 50)))
      l)
  (setf i 0)
  (while (> (setq l (ring-length r)) 1)
    (ring-remove r (setq i (mod (1+ i) l))))
  (ring-ref r 0))

37

i kills its current successor with index (mod (1+ i) l)) where l is the current length of the ring. The successor of the killed takes the place of the killed (we let do that the ring).

|improve this answer|||||
  • 1
    There is a bug in your ring solution when incrementing the index past the length of the ring; the correct answer should be 37. The bug should become clearer if you test it on a circle with numbers 1 through 5, where the correct answer should be 3 instead of 5. – Basil Feb 19 at 14:20
  • 1
    Yes, if i becomes equal to the length of the ring i is incremented but the length is decremented simultaneously. I end up at the second element instead of the first. That's the problem. – Tobias Feb 19 at 14:59
  • @Basil Corrected. – Tobias Feb 19 at 15:10
  • Thanks for your effort in this question, I really learned a lot from your answers – anquegi Feb 19 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.