随机游走 & ortools demo

4 files changed, 122 insertions, 0 deletions

diff --git a/prob/__init__.py b/prob/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/prob/__init__.py
diff --git a/prob/random_walk_1d.py b/prob/random_walk_1d.py
new file mode 100644
index 0000000..445db06
--- /dev/null
+++ b/prob/random_walk_1d.py
@@ -0,0 +1,22 @@
+
+import random
+import matplotlib.pyplot as plt
+from collections import Counter
+import pandas as pd
+
+
+def random_walk(N):
+    x = 0
+    for i in range(N):
+        dx = random.choice([1, -1])
+        x += dx
+    return x
+
+
+if __name__ == '__main__':
+    n_samples = 50000
+    final_x = []
+    for i in range(n_samples):
+        final_x.append(random_walk(100))
+    pd.Series(final_x).value_counts().sort_index().plot(kind='bar')
+    plt.show()
diff --git a/prob/random_walk_demo.py b/prob/random_walk_demo.py
new file mode 100644
index 0000000..6212528
--- /dev/null
+++ b/prob/random_walk_demo.py
@@ -0,0 +1,48 @@
+
+import random
+
+
+def random_walk(N):
+    x, y = 0, 0
+    choices = ['N', 'S', 'E', 'W']
+    for i in range(N):
+        step = random.choice(choices)
+        if step == 'N':
+            y += 1
+        elif step == 'S':
+            y -= 1
+        elif step == 'E':
+            x += 1
+        else:
+            x -= 1
+    return x, y
+
+
+def random_walk_2(N):
+    x, y = 0, 0
+    for i in range(N):
+        dx, dy = random.choice([[0, 1], [0, -1], [1, 0], [-1, 0]])
+        x += dx
+        y += dy
+    return x, y
+
+
+def distance_from_home(x, y):
+    return abs(x) + abs(y)
+
+
+if __name__ == '__main__':
+    # for i in range(25):
+    #     x, y = random_walk_2(10)
+    #     print(f'x = {x}, y = {y}, distance from home: {distance_from_home(x, y)}')
+
+    number_of_walks = 50000
+    for walk_length in range(1, 31):
+        no_transport = 0
+        for i in range(number_of_walks):
+            x, y = random_walk(walk_length)
+            dist = distance_from_home(x, y)
+            if dist <= 5:
+                no_transport += 1
+        no_transport_percentage = float(no_transport)/number_of_walks
+        print(f'walk_length: {walk_length}, no_transport_percentage: {no_transport_percentage}')
diff --git a/prob/random_walk_oo.py b/prob/random_walk_oo.py
new file mode 100644
index 0000000..ce1baf5
--- /dev/null
+++ b/prob/random_walk_oo.py
@@ -0,0 +1,52 @@
+
+import random
+
+
+class Location(object):
+
+    def __init__(self, x, y):
+        self.x = x
+        self.y = y
+
+    def move(self, dx, dy):
+        return Location(self.x + dx, self.y + dy)
+
+    def get_x(self):
+        return self.x
+
+    def get_y(self):
+        return self.y
+
+    def euclidean_distance_from(self, other):
+        x_dist = self.x - other.get_x()
+        y_dist = self.y - other.get_y()
+        return (x_dist ** 2 + y_dist **2)**0.5
+
+    def manhattan_distance_from(self, other):
+        x_dist = self.x - other.get_x()
+        y_dist = self.y - other.get_y()
+        return abs(x_dist) + abs(y_dist)
+
+    def __str__(self):
+        return f'<{self.x}, {self.y}>'
+
+
+class Drunk(object):
+    def __init__(self, name=None):
+        self.name = name
+
+    def __str__(self):
+        if self.name is not None:
+            return self.name
+        return 'Anonymous'
+
+
+def usual_take_step():
+    return random.choice([[-1, 0], [1, 0], [0, -1], [0, 1]])
+
+
+def north_take_step():
+    step_choices = [(0.0, 1.1), (0.0, -0.9), (1.0, 0.0), (-1.0, 0.0)]
+    return random.choice(step_choices)
+
+