From ba835b4f5e33f404b7bed9369a1b425a67b312c5 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Mon, 16 Jan 2023 14:27:06 -0500 Subject: meander fill: initial version --- lib/utils/list.py | 15 +++++++++++++++ 1 file changed, 15 insertions(+) create mode 100644 lib/utils/list.py (limited to 'lib/utils/list.py') diff --git a/lib/utils/list.py b/lib/utils/list.py new file mode 100644 index 00000000..2bfe2cd7 --- /dev/null +++ b/lib/utils/list.py @@ -0,0 +1,15 @@ +from random import randrange + + +def poprandom(sequence): + index = randrange(len(sequence)) + item = sequence[index] + + # It's O(1) to pop the last item, and O(n) to pop any other item. So we'll + # always pop the last item and put it in the slot vacated by the item we're + # popping. + last_item = sequence.pop() + if index < len(sequence): + sequence[index] = last_item + + return item -- cgit v1.2.3 From 847e133f97d570e2967dfa7dcfc16a212dc2bbbc Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Tue, 17 Jan 2023 21:44:23 -0500 Subject: meander fill: more work --- lib/utils/list.py | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'lib/utils/list.py') diff --git a/lib/utils/list.py b/lib/utils/list.py index 2bfe2cd7..efa3969e 100644 --- a/lib/utils/list.py +++ b/lib/utils/list.py @@ -1,8 +1,16 @@ -from random import randrange +import random -def poprandom(sequence): - index = randrange(len(sequence)) +def _uniform_rng(): + while True: + yield random.uniform(0, 1) + + +_rng = _uniform_rng() + + +def poprandom(sequence, rng=_rng): + index = int(round(next(rng) * (len(sequence) - 1))) item = sequence[index] # It's O(1) to pop the last item, and O(n) to pop any other item. So we'll -- cgit v1.2.3