from __future__ import annotations

import bisect

import collections

import collections.abc

import functools

import heapq

import operator

import os.path

import random

from itertools import chain, combinations

from statistics import mean

import numpy as np

def sequence(iterable):

"""Converts iterable to sequence, if it is not already one."""

return iterable if isinstance(iterable, collections.abc.Sequence) else tuple([iterable])

def remove_all(item, seq):

return [x for x in seq if x != item]

def unique(seq):

"""Remove duplicate elements from seq. Assumes hashable elements."""

return list(set(seq))

def count(seq):

"""Count the number of items in sequence that are interpreted as true."""

return sum(map(bool, seq))

def multimap(items):

return dict(result)

def multimap_items(mmap):

yield key, val

def product(numbers):

return result

def first(iterable, default=None):

"""Return the first element of an iterable; or default."""

return next(iter(iterable), default)

def is_in(elt, seq):

"""Similar to (elt in seq), but compares with 'is', not '=='."""

return any(x is elt for x in seq)

def mode(data):

"""Return the most common data item. If there are ties, return any one of them."""

[(item, count)] = collections.Counter(data).most_common(1)

return item

def power_set(iterable):

"""power_set([1,2,3]) --> (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"""

s = list(iterable)

return list(chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)))[1:]

def extend(s, var, val):

"""Copy dict s and extend it by setting var to val; return copy."""

return {**s, var: val}

def flatten(seqs):

"""Flatten a sequence of sequences into a single flat list."""

return sum(seqs, [])

identity = lambda x: x

def argmin_random_tie(seq, key=identity):

"""Return a minimum element of seq; break ties at random."""

return min(shuffled(seq), key=key)

def argmax_random_tie(seq, key=identity):

"""Return an element with highest fn(seq[i]) score; break ties at random."""

return max(shuffled(seq), key=key)

def shuffled(iterable):

return items

def histogram(values, mode=0, bin_function=None):

return sorted(bins.items())

def dot_product(x, y):

"""Return the sum of the element-wise product of vectors x and y."""

return sum(_x * _y for _x, _y in zip(x, y))

def element_wise_product(x, y):

"""Return vector as an element-wise product of vectors x and y."""

assert len(x) == len(y)

return np.multiply(x, y)

def matrix_multiplication(x, *y):

return result

def vector_add(a, b):

"""Component-wise addition of two vectors."""

return tuple(map(operator.add, a, b))

def scalar_vector_product(x, y):

"""Return vector as a product of a scalar and a vector"""

return np.multiply(x, y)

def probability(p: float) -> bool:

"""Return true with probability p."""

return p > random.uniform(0.0, 1.0)

def weighted_sample_with_replacement(n, seq, weights):

return [sample() for _ in range(n)]

def weighted_sampler(seq, weights):

return lambda: seq[bisect.bisect(totals, random.uniform(0, totals[-1]))]

def weighted_choice(choices):

upto += w

def rounder(numbers, d=4):

return constructor(rounder(n, d) for n in numbers)

def num_or_str(x: str) -> int | float | str: # TODO: rename as `atom`

return str(x).strip()

def euclidean_distance(x, y) -> float:

"""Return the Euclidean (L2) distance between vectors x and y."""

return np.sqrt(sum((_x - _y) ** 2 for _x, _y in zip(x, y)))

def manhattan_distance(x, y) -> float:

"""Return the Manhattan (L1) distance between vectors x and y."""

return sum(abs(_x - _y) for _x, _y in zip(x, y))

def hamming_distance(x, y) -> int:

"""Return the number of positions at which vectors x and y differ."""

return sum(_x != _y for _x, _y in zip(x, y))

def cross_entropy_loss(x, y) -> float:

"""Return the mean binary cross-entropy loss between targets x and predictions y."""

return (-1.0 / len(x)) * sum(_x * np.log(_y) + (1 - _x) * np.log(1 - _y) for _x, _y in zip(x, y))

def mean_squared_error_loss(x, y) -> float:

"""Return the mean squared error loss between vectors x and y."""

return (1.0 / len(x)) * sum((_x - _y) ** 2 for _x, _y in zip(x, y))

def rms_error(x, y) -> float:

"""Return the root-mean-square error between vectors x and y."""

return np.sqrt(ms_error(x, y))

def ms_error(x, y) -> float:

"""Return the mean of the squared differences between vectors x and y."""

return mean((_x - _y) ** 2 for _x, _y in zip(x, y))

def mean_error(x, y) -> float:

"""Return the mean of the absolute differences between vectors x and y."""

return mean(abs(_x - _y) for _x, _y in zip(x, y))

def mean_boolean_error(x, y) -> float:

"""Return the fraction of positions at which vectors x and y differ."""

return mean(_x != _y for _x, _y in zip(x, y))

def normalize(dist):

return [(n / total) for n in dist]

def random_weights(min_value: float, max_value: float, num_weights: int) -> list:

"""Return a list of num_weights random floats drawn uniformly from [min_value, max_value]."""

return [random.uniform(min_value, max_value) for _ in range(num_weights)]

def sigmoid(x):

"""Return activation value of x with sigmoid function."""

return 1 / (1 + np.exp(-x))

def sigmoid_derivative(value):

"""Return the derivative of the sigmoid, given its already-computed output value."""

return value * (1 - value)

def elu(x: float, alpha: float = 0.01) -> float:

"""Return the Exponential Linear Unit activation of x."""

return x if x > 0 else alpha * (np.exp(x) - 1)

def elu_derivative(value: float, alpha: float = 0.01) -> float:

"""Return the derivative of the ELU activation, given its output value."""

return 1 if value > 0 else alpha * np.exp(value)

def tanh(x):

"""Return the hyperbolic tangent activation of x."""

return np.tanh(x)

def tanh_derivative(value):

"""Return the derivative of tanh, given its already-computed output value."""

return 1 - (value ** 2)

def leaky_relu(x: float, alpha: float = 0.01) -> float:

"""Return the Leaky ReLU activation of x (slope alpha for negative inputs)."""

return x if x > 0 else alpha * x

def leaky_relu_derivative(value: float, alpha: float = 0.01) -> float:

"""Return the derivative of the Leaky ReLU activation, given its output value."""

return 1 if value > 0 else alpha

def relu(x: float) -> float:

"""Return the Rectified Linear Unit activation of x, i.e. max(0, x)."""

return max(0, x)

def relu_derivative(value: float) -> int:

"""Return the derivative of the ReLU activation, given its output value."""

return 1 if value > 0 else 0

def step(x: float) -> int:

"""Return activation value of x with sign function"""

return 1 if x >= 0 else 0

def gaussian(mean: float, st_dev: float, x: float) -> float:

"""Given the mean and standard deviation of a distribution, it returns the probability of x."""

return 1 / (np.sqrt(2 * np.pi) * st_dev) * np.e ** (-0.5 * (float(x - mean) / st_dev) ** 2)

def linear_kernel(x, y=None):

return np.dot(x, y.T)

def polynomial_kernel(x, y=None, degree=2.0):

return (1.0 + np.dot(x, y.T)) ** degree

def rbf_kernel(x, y=None, gamma=None):

np.sum(x * x, axis=1).reshape((-1, 1)) + np.sum(y * y, axis=1).reshape((1, -1))))

orientations = EAST, NORTH, WEST, SOUTH = [(1, 0), (0, 1), (-1, 0), (0, -1)]

turns = LEFT, RIGHT = (+1, -1)

def turn_heading(heading, inc, headings=orientations):

"""Return the heading reached by turning inc steps around the list of headings."""

return headings[(headings.index(heading) + inc) % len(headings)]

def turn_right(heading):

"""Return the heading obtained by turning right (clockwise) from heading."""

return turn_heading(heading, RIGHT)

def turn_left(heading):

"""Return the heading obtained by turning left (counter-clockwise) from heading."""

return turn_heading(heading, LEFT)

def distance(a, b):

return np.hypot((xA - xB), (yA - yB))

def distance_squared(a, b):

return (xA - xB) ** 2 + (yA - yB) ** 2

class injection:

globals().update(self.old)

def memoize(fn, slot=None, maxsize=32):

return memoized_fn

def name(obj):

str(obj))

def isnumber(x):

"""Is x a number?"""

return hasattr(x, '__int__')

def issequence(x):

"""Is x a sequence?"""

return isinstance(x, collections.abc.Sequence)

def print_table(table, header=None, sep=' ', numfmt='{}'):

print(sep.join(getattr(str(x), j)(size) for (j, size, x) in zip(justs, sizes, row)))

def open_data(name, mode='r'):

return open(aima_file, mode=mode)

def failure_test(algorithm, tests):

return mean(int(algorithm(x) != y) for x, y in tests)

class Expr:

return '(' + opp.join(args) + ')'

Number = (int, float, complex)

Expression = (Expr, Number)

def Symbol(name):

"""A Symbol is just an Expr with no args."""

return Expr(name)

def symbols(names):

"""Return a tuple of Symbols; names is a comma/whitespace delimited str."""

return tuple(Symbol(name) for name in names.replace(',', ' ').split())

def subexpressions(x):

yield from subexpressions(arg)

def arity(expression):

return 0

class PartialExpr:

return "PartialExpr('{}', {})".format(self.op, self.lhs)

def expr(x):

return eval(expr_handle_infix_ops(x), defaultkeydict(Symbol)) if isinstance(x, str) else x

infix_ops = '==> <== <=>'.split()

def expr_handle_infix_ops(x):

return x

class defaultkeydict(collections.defaultdict):

return result

class hashabledict(dict):

return 1

class PriorityQueue:

heapq.heapify(self.heap)

class Bool(int):

"""Just like `bool`, except values display as 'T' and 'F' instead of 'True' and 'False'."""

__str__ = __repr__ = lambda self: 'T' if self else 'F'

T = Bool(True)

F = Bool(False)

def gaussian_kernel(size=3):

"""Return a length-size 1D Gaussian kernel centred at the middle (fixed st_dev 0.1)."""

return [gaussian((size - 1) / 2, 0.1, x) for x in range(size)]

def gaussian_kernel_1D(size=3, sigma=0.5):

"""Return a length-size 1D Gaussian kernel centred at the middle with st_dev sigma."""

return [gaussian((size - 1) / 2, sigma, x) for x in range(size)]

def gaussian_kernel_2D(size=3, sigma=0.5):

return g / g.sum()

def conv1D(x, k):

"""1D convolution. x: input vector; K: kernel vector."""

return np.convolve(x, k, mode='same')

def map_vector(f, x):

"""Apply function f to iterable x."""

return [map_vector(f, _x) for _x in x] if hasattr(x, '__iter__') else list(map(f, [x]))[0]

class MCT_Node:

self.actions = None

def ucb(n, C=1.4):

return np.inf if n.N == 0 else n.U / n.N + C * np.sqrt(np.log(n.parent.N) / n.N)