ZenulAbidin · September 6, 2024 08:35
diff --git a/ev-guessing.py b/ev-guessing.py
 import matplotlib.pyplot as plt
 import numpy as np
 import random
 from math import log2

 # Define the binary search strategies
 def choose_straight_middle_left(left_incl, right_incl):
    return (left_incl + right_incl) // 2

 def choose_straight_middle_right(left_incl, right_incl):
    return (left_incl + right_incl + 1) // 2

 def choose_right_leaning(left_incl, right_incl):
    search_space_size = right_incl - left_incl + 1
    log_size = int(log2(search_space_size))
    return min(left_incl + 2 ** log_size - 1, right_incl)

 def choose_left_leaning(left_incl, right_incl):
    search_space_size = right_incl - left_incl + 1
    log_size = int(log2(search_space_size))
    return max(left_incl, right_incl - 2 ** log_size + 1)

 # Simulation parameters
 iterations = 100  # number of random targets to test

 # Initialize arrays to hold the number of guesses for each strategy
 straight_middle_left_counts = []
 straight_middle_right_counts = []
 right_leaning_counts = []
 left_leaning_counts = []

 # Simulate for 'iterations' random target numbers
 for _ in range(iterations):
    target = random.randint(1, 100)  # choose a random target number
    left_incl = 1
    right_incl = 100
    
    # Variables to count guesses for each strategy
    straight_middle_left_guess_count = 0
    straight_middle_right_guess_count = 0
    right_leaning_guess_count = 0
    left_leaning_guess_count = 0
    
    # Simulate for straight middle-left strategy
    left, right = left_incl, right_incl
    while left <= right:
        straight_middle_left_guess_count += 1
        guess = choose_straight_middle_left(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Simulate for straight middle-right strategy
    left, right = left_incl, right_incl
    while left <= right:
        straight_middle_right_guess_count += 1
        guess = choose_straight_middle_right(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Simulate for right-leaning strategy
    left, right = left_incl, right_incl
    while left <= right:
        right_leaning_guess_count += 1
        guess = choose_right_leaning(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Simulate for left-leaning strategy
    left, right = left_incl, right_incl
    while left <= right:
        left_leaning_guess_count += 1
        guess = choose_left_leaning(left, right)
        if guess == target:
            break
        elif guess < target:
            left = guess + 1
        else:
            right = guess - 1
    
    # Store the number of guesses for each strategy
    straight_middle_left_counts.append(straight_middle_left_guess_count)
    straight_middle_right_counts.append(straight_middle_right_guess_count)
    right_leaning_counts.append(right_leaning_guess_count)
    left_leaning_counts.append(left_leaning_guess_count)

 # Plotting the results
 iterations_range = np.arange(1, iterations + 1)

 plt.figure(figsize=(10, 6))

 # Plot each strategy's guess counts
 plt.plot(iterations_range, straight_middle_left_counts, label="Middle Left", marker='o')
 plt.plot(iterations_range, straight_middle_right_counts, label="Middle Right", marker='s')
 plt.plot(iterations_range, right_leaning_counts, label="Right-Leaning", marker='^')
 plt.plot(iterations_range, left_leaning_counts, label="Left-Leaning", marker='x')

 # Add labels and title
 plt.xlabel("Iteration (Random Target Number)")
 plt.ylabel("Number of Guesses")
 plt.title("Number of Guesses for Various Binary Search Strategies (Random Targets)")
 plt.legend()

 # Display the plot
 plt.grid(True)
 plt.show()
	import matplotlib.pyplot as plt
	import numpy as np
	import random
	from math import log2

	# Define the binary search strategies
	def choose_straight_middle_left(left_incl, right_incl):
	return (left_incl + right_incl) // 2

	def choose_straight_middle_right(left_incl, right_incl):
	return (left_incl + right_incl + 1) // 2

	def choose_right_leaning(left_incl, right_incl):
	search_space_size = right_incl - left_incl + 1
	log_size = int(log2(search_space_size))
	return min(left_incl + 2 ** log_size - 1, right_incl)

	def choose_left_leaning(left_incl, right_incl):
	search_space_size = right_incl - left_incl + 1
	log_size = int(log2(search_space_size))
	return max(left_incl, right_incl - 2 ** log_size + 1)

	# Simulation parameters
	iterations = 100 # number of random targets to test

	# Initialize arrays to hold the number of guesses for each strategy
	straight_middle_left_counts = []
	straight_middle_right_counts = []
	right_leaning_counts = []
	left_leaning_counts = []

	# Simulate for 'iterations' random target numbers
	for _ in range(iterations):
	target = random.randint(1, 100) # choose a random target number
	left_incl = 1
	right_incl = 100

	# Variables to count guesses for each strategy
	straight_middle_left_guess_count = 0
	straight_middle_right_guess_count = 0
	right_leaning_guess_count = 0
	left_leaning_guess_count = 0

	# Simulate for straight middle-left strategy
	left, right = left_incl, right_incl
	while left <= right:
	straight_middle_left_guess_count += 1
	guess = choose_straight_middle_left(left, right)
	if guess == target:
	break
	elif guess < target:
	left = guess + 1
	else:
	right = guess - 1

	# Simulate for straight middle-right strategy
	left, right = left_incl, right_incl
	while left <= right:
	straight_middle_right_guess_count += 1
	guess = choose_straight_middle_right(left, right)
	if guess == target:
	break
	elif guess < target:
	left = guess + 1
	else:
	right = guess - 1

	# Simulate for right-leaning strategy
	left, right = left_incl, right_incl
	while left <= right:
	right_leaning_guess_count += 1
	guess = choose_right_leaning(left, right)
	if guess == target:
	break
	elif guess < target:
	left = guess + 1
	else:
	right = guess - 1

	# Simulate for left-leaning strategy
	left, right = left_incl, right_incl
	while left <= right:
	left_leaning_guess_count += 1
	guess = choose_left_leaning(left, right)
	if guess == target:
	break
	elif guess < target:
	left = guess + 1
	else:
	right = guess - 1

	# Store the number of guesses for each strategy
	straight_middle_left_counts.append(straight_middle_left_guess_count)
	straight_middle_right_counts.append(straight_middle_right_guess_count)
	right_leaning_counts.append(right_leaning_guess_count)
	left_leaning_counts.append(left_leaning_guess_count)

	# Plotting the results
	iterations_range = np.arange(1, iterations + 1)

	plt.figure(figsize=(10, 6))

	# Plot each strategy's guess counts
	plt.plot(iterations_range, straight_middle_left_counts, label="Middle Left", marker='o')
	plt.plot(iterations_range, straight_middle_right_counts, label="Middle Right", marker='s')
	plt.plot(iterations_range, right_leaning_counts, label="Right-Leaning", marker='^')
	plt.plot(iterations_range, left_leaning_counts, label="Left-Leaning", marker='x')

	# Add labels and title
	plt.xlabel("Iteration (Random Target Number)")
	plt.ylabel("Number of Guesses")
	plt.title("Number of Guesses for Various Binary Search Strategies (Random Targets)")
	plt.legend()

	# Display the plot
	plt.grid(True)
	plt.show()