meander fill: initial version

1 files changed, 15 insertions, 0 deletions

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