From: Ken Tilton
Subject: At pain of repeating myself, another nooby exercise from "In the Trenches With Kenny"
Date:
Message-ID: <AW54h.405$sf2.12@newsfe12.lga>
Gotta keep the kiddies amused (without turning the damn thing into a
game) so how about some random sound effects every time they do
something good (or bad)? But let's not repeat ourselves, right? Not too
quickly anyway.
First, the test to be passed:
(loop with sequence
with choices ='(four score and seven years ago)
with decent-interval = (floor (length choices) 2)
repeat 100
for word = (without-repeating :test-wr decent-interval choices)
for pos = (position word sequence)
if (and pos (< pos decent-interval))
do (break "too soon for ~a after ~a" word sequence)
else do (push word sequence)(print word))
The idea is that we will repeat ourselves, but let us not do that too
soon, roughly defined as within half the length of the list. And we do
not want to be predictable, so we do want to vary the sequence (not just
create a random circular list and traverse that forever. Not to say that
one cannot use a circular list somewhere in the implementation.
I did it in eighteen lines and again feel like it should be a
three-liner, but I have deadlines to make and it is just a little
utility (TIMSAIASTI). Anyone else want to try? My version in a very deep PS.
kt
ps.
(let ((used-items (make-hash-table)))
(defun without-repeating (key decent-interval all )
(destructuring-bind (this last)
(or (gethash key used-items)
(list nil nil))
(loop with available = (or (set-difference all this)
(prog1 all
(setf last this this nil)
(setf (gethash key used-items)
(list this last))))
with len = (length available)
for r = (random len)
for choice = (nth r available)
unless (and last (position choice last)
(< (+ (length this) (position choice last))
decent-interval))
do (setf (gethash key used-items)
(list (cons choice this) last))
(return choice)))))
k
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Ken Tilton wrote:
> The idea is that we will repeat ourselves, but let us not do that too
> soon, roughly defined as within half the length of the list. And we do
> not want to be predictable, so we do want to vary the sequence (not just
> create a random circular list and traverse that forever. Not to say that
> one cannot use a circular list somewhere in the implementation.
(I think I may have defeated the point of the exercise by reading the
PS, which Google did a poor job of burying....)
Well, I came up with something a little shorter and simpler (12 lines,
no loop) that passed the test by using the entry from used-items to
make "available" via set difference.
Cheers,
Pillsy
;;; And my attempt at the function.
(let ((used-items (make-hash-table)))
(defun without-repeating (key decent-interval all)
(let ((this (gethash key used-items)))
(let ((available (set-difference all this)))
(let ((item (nth (random (length available))
available)))
(setf (gethash key used-items)
(append (if (= (length this) decent-interval)
(cdr this)
this)
(list item)))
item)))))
From: Ken Tilton
Subject: Re: At pain of repeating myself, another nooby exercise from "In the Trenches With Kenny"
Date:
Message-ID: <yYe4h.185$ng.178@newsfe10.lga>
·········@gmail.com wrote:
> Ken Tilton wrote:
>
>
>>The idea is that we will repeat ourselves, but let us not do that too
>>soon, roughly defined as within half the length of the list. And we do
>>not want to be predictable, so we do want to vary the sequence (not just
>>create a random circular list and traverse that forever. Not to say that
>>one cannot use a circular list somewhere in the implementation.
>
>
> (I think I may have defeated the point of the exercise by reading the
> PS, which Google did a poor job of burying....)
>
> Well, I came up with something a little shorter and simpler (12 lines,
> no loop) that passed the test by using the entry from used-items to
> make "available" via set difference.
>
> Cheers,
> Pillsy
>
> ;;; And my attempt at the function.
>
> (let ((used-items (make-hash-table)))
> (defun without-repeating (key decent-interval all)
> (let ((this (gethash key used-items)))
> (let ((available (set-difference all this)))
> (let ((item (nth (random (length available))
> available)))
> (setf (gethash key used-items)
> (append (if (= (length this) decent-interval)
> (cdr this)
> this)
> (list item)))
> item)))))
>
did u run the test? kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Ken Tilton wrote:
> ·········@gmail.com wrote:
> > ;;; And my attempt at the function.
> > (let ((used-items (make-hash-table)))
> > (defun without-repeating (key decent-interval all)
> > (let ((this (gethash key used-items)))
> > (let ((available (set-difference all this)))
> > (let ((item (nth (random (length available))
> > available)))
> > (setf (gethash key used-items)
> > (append (if (= (length this) decent-interval)
> > (cdr this)
> > this)
> > (list item)))
> > item)))))
> did u run the test? kt
I did, and it passed. The output even looked pretty random.
Cheers,
Pillsbury
From: Ken Tilton
Subject: Re: At pain of repeating myself, another nooby exercise from "In the Trenches With Kenny"
Date:
Message-ID: <Eeo4h.13$Yc2.12@newsfe11.lga>
·········@gmail.com wrote:
> Ken Tilton wrote:
>
>>·········@gmail.com wrote:
>
>
>>>;;; And my attempt at the function.
>
>
>>>(let ((used-items (make-hash-table)))
>>> (defun without-repeating (key decent-interval all)
>>> (let ((this (gethash key used-items)))
>>> (let ((available (set-difference all this)))
>>> (let ((item (nth (random (length available))
>>> available)))
>>> (setf (gethash key used-items)
>>> (append (if (= (length this) decent-interval)
>>> (cdr this)
>>> this)
>>> (list item)))
>>> item)))))
>
>
>>did u run the test? kt
>
>
> I did, and it passed. The output even looked pretty random.
Oh, sorry, I just glanced at it and it was so elegant I missed how it
worked. Sweet!
You can use LET*, btw, when you have one binding that depends on a prior
binding.
kenny
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Ken Tilton wrote:
> ·········@gmail.com wrote:
> > I did, and it passed. The output even looked pretty random.
> Oh, sorry, I just glanced at it and it was so elegant I missed how it
> worked. Sweet!
8^)
> You can use LET*, btw, when you have one binding that depends on a prior
> binding.
Cool. It looks much nicer that way.
Cheers, Pillsbury
From: Jan Van lent
Subject: Re: At pain of repeating myself, another nooby exercise from "In the Trenches With Kenny"
Date:
Message-ID: <m2k624sz4z.fsf@sophus.local>
·········@gmail.com writes:
> Ken Tilton wrote:
>
>> The idea is that we will repeat ourselves, but let us not do that too
>> soon, roughly defined as within half the length of the list. And we do
>> not want to be predictable, so we do want to vary the sequence (not just
>> create a random circular list and traverse that forever. Not to say that
>> one cannot use a circular list somewhere in the implementation.
>
> (I think I may have defeated the point of the exercise by reading the
> PS, which Google did a poor job of burying....)
>
> Well, I came up with something a little shorter and simpler (12 lines,
> no loop) that passed the test by using the entry from used-items to
> make "available" via set difference.
>
> Cheers,
> Pillsy
>
> ;;; And my attempt at the function.
>
> (let ((used-items (make-hash-table)))
> (defun without-repeating (key decent-interval all)
> (let ((this (gethash key used-items)))
> (let ((available (set-difference all this)))
> (let ((item (nth (random (length available))
> available)))
> (setf (gethash key used-items)
> (append (if (= (length this) decent-interval)
> (cdr this)
> this)
> (list item)))
> item)))))
This is elegant and general.
The following version might be more efficient (no set-difference). It
bends the rules by assuming that the interval and the sequence stay
the same for a given key. If this is the case you could use
without-repeating-generator directly (as in test-generator).
;; Returns a function that generates an elements from ALL each time it
;; is called. When a certain element is generated it will take at
;; least DECENT-INTERVAL calls before it is generated again.
;;
;; note: order of ALL is important for first few calls, could be fixed
(defun without-repeating-generator (decent-interval all)
(let* ((n (length all))
(v (make-array n :initial-contents all))
(m (- n decent-interval))
(pos 0))
(lambda ()
(let* ((random-pos (mod (+ pos (random m)) n))
(result (aref v random-pos)))
(setf (aref v random-pos) (aref v pos))
(setf (aref v pos) result)
(setf pos (mod (+ pos 1) n))
result))))
;; example of usage of without-repeating-generator
(defun test-generator (nit all)
(let ((next (without-repeating-generator (floor (/ (length all) 2)) all)))
(loop for it from 0 below nit
do (print (funcall next)))))
;; force into interface asked for, assumes that DECENT-INTERVAL and
;; ALL will stay the same for a given KEY
;; allowing DECENT-INTERVAL to vary would be easy
(let ((generators (make-hash-table)))
(defun without-repeating (key decent-interval all)
(let ((generator (gethash key generators nil)))
(if generator (funcall generator)
(let ((generator (without-repeating-generator decent-interval all)))
(setf (gethash key generators) generator)
(funcall generator))))))
jan
From: Ken Tilton
Subject: Re: At pain of repeating myself, another nooby exercise from "In the Trenches With Kenny"
Date:
Message-ID: <YpG4h.6$Rt2.4@newsfe10.lga>
Jan Van lent wrote:
> ·········@gmail.com writes:
>
>
>>Ken Tilton wrote:
>>
>>
>>>The idea is that we will repeat ourselves, but let us not do that too
>>>soon, roughly defined as within half the length of the list. And we do
>>>not want to be predictable, so we do want to vary the sequence (not just
>>>create a random circular list and traverse that forever. Not to say that
>>>one cannot use a circular list somewhere in the implementation.
>>
>>(I think I may have defeated the point of the exercise by reading the
>>PS, which Google did a poor job of burying....)
>>
>>Well, I came up with something a little shorter and simpler (12 lines,
>>no loop) that passed the test by using the entry from used-items to
>>make "available" via set difference.
>>
>>Cheers,
>>Pillsy
>>
>>;;; And my attempt at the function.
>>
>>(let ((used-items (make-hash-table)))
>> (defun without-repeating (key decent-interval all)
>> (let ((this (gethash key used-items)))
>> (let ((available (set-difference all this)))
>> (let ((item (nth (random (length available))
>> available)))
>> (setf (gethash key used-items)
>> (append (if (= (length this) decent-interval)
>> (cdr this)
>> this)
>> (list item)))
>> item)))))
>
>
> This is elegant and general.
>
> The following version might be more efficient (no set-difference). It
> bends the rules by assuming that the interval and the sequence stay
> the same for a given key. If this is the case you could use
> without-repeating-generator directly (as in test-generator).
>
> ;; Returns a function that generates an elements from ALL each time it
> ;; is called. When a certain element is generated it will take at
> ;; least DECENT-INTERVAL calls before it is generated again.
> ;;
> ;; note: order of ALL is important for first few calls, could be fixed
> (defun without-repeating-generator (decent-interval all)
> (let* ((n (length all))
> (v (make-array n :initial-contents all))
> (m (- n decent-interval))
> (pos 0))
> (lambda ()
> (let* ((random-pos (mod (+ pos (random m)) n))
> (result (aref v random-pos)))
> (setf (aref v random-pos) (aref v pos))
> (setf (aref v pos) result)
> (setf pos (mod (+ pos 1) n))
> result))))
Excellent. I felt guilty about the set-difference.
This uses mod to treat an array like a circular list. I am tempted to
attempt the same approach on a real circular list to eliminate all the
arithmetic (albeit run slower), but deadlines loom. :(
kt
ps. The assumption about things not changing was fine. k
>
> ;; example of usage of without-repeating-generator
> (defun test-generator (nit all)
> (let ((next (without-repeating-generator (floor (/ (length all) 2)) all)))
> (loop for it from 0 below nit
> do (print (funcall next)))))
>
> ;; force into interface asked for, assumes that DECENT-INTERVAL and
> ;; ALL will stay the same for a given KEY
> ;; allowing DECENT-INTERVAL to vary would be easy
> (let ((generators (make-hash-table)))
> (defun without-repeating (key decent-interval all)
> (let ((generator (gethash key generators nil)))
> (if generator (funcall generator)
> (let ((generator (without-repeating-generator decent-interval all)))
> (setf (gethash key generators) generator)
> (funcall generator))))))
>
> jan
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
From: Ken Tilton
Subject: Re: At pain of repeating myself, another nooby exercise from "In the Trenches With Kenny"
Date:
Message-ID: <VoK4h.15$8j1.6@newsfe12.lga>
Jan Van lent wrote:
> ;; force into interface asked for, assumes that DECENT-INTERVAL and
> ;; ALL will stay the same for a given KEY
> ;; allowing DECENT-INTERVAL to vary would be easy
> (let ((generators (make-hash-table)))
> (defun without-repeating (key decent-interval all)
> (let ((generator (gethash key generators nil)))
> (if generator (funcall generator)
> (let ((generator (without-repeating-generator decent-interval all)))
> (setf (gethash key generators) generator)
> (funcall generator))))))
OK, I could not resist, working on the circular list version now. Just
noticed the above could avoid duplication with:
(let ((generators (make-hash-table)))
(defun without-repeating (key decent-interval all)
(funcall (or (gethash key generators)
;; setf always returns the value set, so...
(setf (gethash key generators)
(without-repeating-generator decent-interval all))))))
kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
From: Ken Tilton
Subject: Re: At pain of repeating myself, another nooby exercise from "In the Trenches With Kenny"
Date:
Message-ID: <8GK4h.27$z14.13@newsfe08.lga>
Jan Van lent wrote:
> ·········@gmail.com writes:
>
>
>>Ken Tilton wrote:
>>
>>
>>>The idea is that we will repeat ourselves, but let us not do that too
>>>soon, roughly defined as within half the length of the list. And we do
>>>not want to be predictable, so we do want to vary the sequence (not just
>>>create a random circular list and traverse that forever. Not to say that
>>>one cannot use a circular list somewhere in the implementation.
>>
>>(I think I may have defeated the point of the exercise by reading the
>>PS, which Google did a poor job of burying....)
>>
>>Well, I came up with something a little shorter and simpler (12 lines,
>>no loop) that passed the test by using the entry from used-items to
>>make "available" via set difference.
>>
>>Cheers,
>>Pillsy
>>
>>;;; And my attempt at the function.
>>
>>(let ((used-items (make-hash-table)))
>> (defun without-repeating (key decent-interval all)
>> (let ((this (gethash key used-items)))
>> (let ((available (set-difference all this)))
>> (let ((item (nth (random (length available))
>> available)))
>> (setf (gethash key used-items)
>> (append (if (= (length this) decent-interval)
>> (cdr this)
>> this)
>> (list item)))
>> item)))))
>
>
> This is elegant and general.
>
> The following version might be more efficient (no set-difference). It
> bends the rules by assuming that the interval and the sequence stay
> the same for a given key. If this is the case you could use
> without-repeating-generator directly (as in test-generator).
>
> ;; Returns a function that generates an elements from ALL each time it
> ;; is called. When a certain element is generated it will take at
> ;; least DECENT-INTERVAL calls before it is generated again.
> ;;
> ;; note: order of ALL is important for first few calls, could be fixed
> (defun without-repeating-generator (decent-interval all)
> (let* ((n (length all))
> (v (make-array n :initial-contents all))
> (m (- n decent-interval))
> (pos 0))
> (lambda ()
> (let* ((random-pos (mod (+ pos (random m)) n))
> (result (aref v random-pos)))
> (setf (aref v random-pos) (aref v pos))
> (setf (aref v pos) result)
> (setf pos (mod (+ pos 1) n))
> result))))
Not as efficient, but:
(defun without-repeating-generator (decent-interval all)
(let* ((len (length all))
(head (let ((v (copy-list all)))
(nconc v v))))
(lambda ()
(rotatef (car head)
(car (nthcdr (random (- len decent-interval)) head)))
(prog1
(car head)
(setf head (cdr head))))))
Thx for the idea.
kt
>
> ;; example of usage of without-repeating-generator
> (defun test-generator (nit all)
> (let ((next (without-repeating-generator (floor (/ (length all) 2)) all)))
> (loop for it from 0 below nit
> do (print (funcall next)))))
>
> ;; force into interface asked for, assumes that DECENT-INTERVAL and
> ;; ALL will stay the same for a given KEY
> ;; allowing DECENT-INTERVAL to vary would be easy
> (let ((generators (make-hash-table)))
> (defun without-repeating (key decent-interval all)
> (let ((generator (gethash key generators nil)))
> (if generator (funcall generator)
> (let ((generator (without-repeating-generator decent-interval all)))
> (setf (gethash key generators) generator)
> (funcall generator))))))
>
> jan
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Ken Tilton wrote:
> Gotta keep the kiddies amused (without turning the damn thing into a
> game) so how about some random sound effects every time they do
> something good (or bad)? But let's not repeat ourselves, right? Not too
> quickly anyway.
>
> First, the test to be passed:
>
> (loop with sequence
> with choices ='(four score and seven years ago)
> with decent-interval = (floor (length choices) 2)
> repeat 100
> for word = (without-repeating :test-wr decent-interval choices)
> for pos = (position word sequence)
> if (and pos (< pos decent-interval))
> do (break "too soon for ~a after ~a" word sequence)
> else do (push word sequence)(print word))
>
> The idea is that we will repeat ourselves, but let us not do that too
> soon, roughly defined as within half the length of the list. And we do
> not want to be predictable, so we do want to vary the sequence (not just
> create a random circular list and traverse that forever. Not to say that
> one cannot use a circular list somewhere in the implementation.
>
> I did it in eighteen lines and again feel like it should be a
> three-liner, but I have deadlines to make and it is just a little
> utility (TIMSAIASTI). Anyone else want to try? My version in a very deep PS.
>
> kt
...snip...
>
> (let ((used-items (make-hash-table)))
> (defun without-repeating (key decent-interval all )
> (destructuring-bind (this last)
> (or (gethash key used-items)
> (list nil nil))
> (loop with available = (or (set-difference all this)
> (prog1 all
> (setf last this this nil)
> (setf (gethash key used-items)
> (list this last))))
> with len = (length available)
> for r = (random len)
> for choice = (nth r available)
> unless (and last (position choice last)
> (< (+ (length this) (position choice last))
> decent-interval))
> do (setf (gethash key used-items)
> (list (cons choice this) last))
> (return choice)))))
>
here's 12 for the whole thing...
(let* ((n 100)
(sequence '(four score and seven years ago))
(length (length sequence))
(decent-interval (floor length 2))
used)
(loop (when (< n 1) (return))
(let* ((pick (nth (random length) sequence))
(pos (position pick used)))
(unless (and pos (< pos decent-interval))
(print pick)
(push pick used)
(decf n)))))
;nick
> k
>
> --
> Cells: http://common-lisp.net/project/cells/
>
> "I'll say I'm losing my grip, and it feels terrific."
> -- Smiling husband to scowling wife, New Yorker cartoon
Ken Tilton wrote:
> The idea is that we will repeat ourselves, but let us not do that too
> soon, roughly defined as within half the length of the list. And we do
> not want to be predictable, so we do want to vary the sequence (not just
> create a random circular list and traverse that forever. Not to say that
> one cannot use a circular list somewhere in the implementation.
Not that I'm the target audience...
You might prefer using a "generator." (Hope I'm using the term
correctly.) You call a function which returns another function. Then
you keep on calling that returned function, which each time offers you
the next element in the sequence you want.
That would keep you from needing to use keys like :test-wr, as you
currently do.
Tayssir