# COSC/MATH 201 - Module 9.5: Random Walk
# Each step moves one unit east/west AND one unit north/south.
# The two directions are chosen by independent fair coin flips.

# A tiny linear congruential generator (LCG) for illustration.
# Each new value is (3 * previous value + 14) %% 10.
a <- 3
b <- 14
m <- 10
seed <- 5

lcg_values <- numeric(6)
lcg_values[1] <- seed
for (i in 2:length(lcg_values)) {
  lcg_values[i] <- (a * lcg_values[i - 1] + b) %% m
}

data.frame(value = lcg_values, between_0_and_1 = lcg_values / m)
# The first new value, 9, could make a choice: 9 / 10 < 0.5 is FALSE.
# This tiny sequence repeats quickly; use R's runif() for the walk below.

set.seed(205)
number_of_steps <- 25

# There are 26 positions: the origin plus one after each step.
x <- numeric(number_of_steps + 1)
y <- numeric(number_of_steps + 1)
x[1] <- 0
y[1] <- 0

for (i in 2:length(x)) {
  if (runif(1) < 0.5) {
    x[i] <- x[i - 1] + 1
  } else {
    x[i] <- x[i - 1] - 1
  }

  if (runif(1) < 0.5) {
    y[i] <- y[i - 1] + 1
  } else {
    y[i] <- y[i - 1] - 1
  }
}

head(data.frame(step = 0:number_of_steps, x, y))

plot(x, y, type = "o", pch = 16, cex = 0.5, asp = 1,
     col = "steelblue", xlab = "East-west position",
     ylab = "North-south position", main = "One 25-step random walk")
points(x[1], y[1], pch = 16, cex = 1.5, col = "darkgreen")
points(x[length(x)], y[length(y)], pch = 16, cex = 1.5,
       col = "firebrick")
legend("topright", c("Start", "Finish"),
       col = c("darkgreen", "firebrick"), pch = 16, bty = "n")

# Distance traveled along the path is fixed; displacement is not.
path_length <- number_of_steps * sqrt(2)
displacement <- sqrt(x[length(x)]^2 + y[length(y)]^2)
data.frame(path_length, displacement,
           final_x = x[length(x)], final_y = y[length(y)])

# Repeat the walk. We only need the final distance of each run.
set.seed(206)
number_of_runs <- 500
steps_per_walk <- 25
final_distances <- numeric(number_of_runs)

for (run in 1:number_of_runs) {
  x_position <- 0
  y_position <- 0

  for (step in 1:steps_per_walk) {
    if (runif(1) < 0.5) {
      x_position <- x_position + 1
    } else {
      x_position <- x_position - 1
    }

    if (runif(1) < 0.5) {
      y_position <- y_position + 1
    } else {
      y_position <- y_position - 1
    }
  }

  final_distances[run] <- sqrt(x_position^2 + y_position^2)
}

data.frame(
  runs = number_of_runs,
  mean_displacement = mean(final_distances),
  fraction_within_5 = mean(final_distances <= 5)
)

hist(final_distances, breaks = 15, col = "skyblue2",
     main = "Final distances from 500 walks",
     xlab = "Distance from start after 25 steps")
abline(v = 5, col = "firebrick", lwd = 2, lty = 2)

# Optional experiment: change only the east-west test in the repeated
# simulation from < 0.5 to < 0.65, keeping the seed and other settings.