
"""simple docstring"""

from __future__ import annotations

from random import random
from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE_    					=						TypeVar('''KT''')
SCREAMING_SNAKE_CASE_    					=						TypeVar('''VT''')
class      _UpperCAmelCase							(		Generic[KT, VT]							):




      def __init__(							self   ,       lowercase_ = "root"   ,       lowercase_ = None							)						->					List[str]:
          UpperCAmelCase									=					key
          UpperCAmelCase									=					value
          UpperCAmelCase									=					[]




      def __repr__(							self							)						->					str:
          return F"Node({self.key}: {self.value})"




      @property
      def     a_      (							self							)						->					int:
          return len(self.forward							)

class      _UpperCAmelCase							(		Generic[KT, VT]							):




      def __init__(							self   ,       lowercase_ = 0.5   ,       lowercase_ = 1_6							)						->					List[Any]:
          UpperCAmelCase									=					Node[KT, VT]()
          UpperCAmelCase									=					0
          UpperCAmelCase									=					p
          UpperCAmelCase									=					max_level




      def __str__(							self							)						->					str:
          UpperCAmelCase									=					list(self							)

          if len(lowercase_							) == 0:
              return F"SkipList(level={self.level})"

          UpperCAmelCase									=					max((len(str(lowercase_							)							) for item in items)   ,       default=4							)
          UpperCAmelCase									=					max(lowercase_   ,       4							) + 4

          UpperCAmelCase									=					self.head
          UpperCAmelCase									=					[]

          UpperCAmelCase									=					node.forward.copy()
          lines.append(F"[{node.key}]".ljust(lowercase_   ,       '-'							) + '* ' * len(lowercase_							)							)
          lines.append(' ' * label_size + '| ' * len(lowercase_							)							)

          while len(node.forward							) != 0:
              UpperCAmelCase									=					node.forward[0]

              lines.append(
                  F"[{node.key}]".ljust(lowercase_   ,       '-'							)
                  + ' '.join(str(n.key							) if n.key == node.key else '|' for n in forwards							)							)
              lines.append(' ' * label_size + '| ' * len(lowercase_							)							)
              UpperCAmelCase									=					node.forward

          lines.append('None'.ljust(lowercase_							) + '* ' * len(lowercase_							)							)
          return F"SkipList(level={self.level})\n" + "\n".join(lowercase_							)




      def __iter__(							self							)						->					Union[str, Any]:
          UpperCAmelCase									=					self.head

          while len(node.forward							) != 0:
              yield node.forward[0].key
              UpperCAmelCase									=					node.forward[0]




      def     a_      (							self							)						->					int:
          UpperCAmelCase									=					1
          while random() < self.p and level < self.max_level:
              level += 1

          return level




      def     a_      (							self   ,       lowercase_							)						->					tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
          UpperCAmelCase									=					[]

          UpperCAmelCase									=					self.head

          for i in reversed(range(self.level							)							):
              # i < node.level - When node level is lesser than `i` decrement `i`.
              # node.forward[i].key < key - Jumping to node with key value higher
              #                             or equal to searched key would result
              #                             in skipping searched key.
              while i < node.level and node.forward[i].key < key:
                  UpperCAmelCase									=					node.forward[i]
              # Each leftmost node (relative to searched node) will potentially have to
              # be updated.
              update_vector.append(lowercase_							)

          update_vector.reverse()  # Note that we were inserting values in reverse order.

          # len(node.forward) != 0 - If current node doesn't contain any further
          #                          references then searched key is not present.
          # node.forward[0].key == key - Next node key should be equal to search key
          #                              if key is present.
          if len(node.forward							) != 0 and node.forward[0].key == key:
              return node.forward[0], update_vector
          else:
              return None, update_vector




      def     a_      (							self   ,       lowercase_							)						->					Optional[Any]:
          UpperCAmelCase			,							UpperCAmelCase									=					self._locate_node(lowercase_							)

          if node is not None:
              for i, update_node in enumerate(lowercase_							):
                  # Remove or replace all references to removed node.
                  if update_node.level > i and update_node.forward[i].key == key:
                      if node.level > i:
                          UpperCAmelCase									=					node.forward[i]
                      else:
                          UpperCAmelCase									=					update_node.forward[:i]




      def     a_      (							self   ,       lowercase_   ,       lowercase_							)						->					Optional[int]:
          UpperCAmelCase			,							UpperCAmelCase									=					self._locate_node(lowercase_							)
          if node is not None:
              UpperCAmelCase									=					value
          else:
              UpperCAmelCase									=					self.random_level()

              if level > self.level:
                  # After level increase we have to add additional nodes to head.
                  for _ in range(self.level - 1   ,       lowercase_							):
                      update_vector.append(self.head							)
                  UpperCAmelCase									=					level

              UpperCAmelCase									=					Node(lowercase_   ,       lowercase_							)

              for i, update_node in enumerate(update_vector[:level]							):
                  # Change references to pass through new node.
                  if update_node.level > i:
                      new_node.forward.append(update_node.forward[i]							)

                  if update_node.level < i + 1:
                      update_node.forward.append(lowercase_							)
                  else:
                      UpperCAmelCase									=					new_node




      def     a_      (							self   ,       lowercase_							)						->					VT | None:
          UpperCAmelCase			,							UpperCAmelCase									=					self._locate_node(lowercase_							)

          if node is not None:
              return node.value

          return None




def     lowercase__						(					) ->      Tuple:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()
    skip_list.insert('Key1' ,				3 )
    skip_list.insert('Key2' ,				12 )
    skip_list.insert('Key3' ,				41 )
    skip_list.insert('Key4' ,				-19 )

    UpperCAmelCase									=					skip_list.head
    UpperCAmelCase									=					{}
    while node.level != 0:
        UpperCAmelCase									=					node.forward[0]
        UpperCAmelCase									=					node.value

    assert len(lowerCAmelCase ) == 4
    assert all_values["Key1"] == 3
    assert all_values["Key2"] == 12
    assert all_values["Key3"] == 41
    assert all_values["Key4"] == -19




def     lowercase__						(					) ->      Optional[Any]:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()
    skip_list.insert('Key1' ,				10 )
    skip_list.insert('Key1' ,				12 )

    skip_list.insert('Key5' ,				7 )
    skip_list.insert('Key7' ,				10 )
    skip_list.insert('Key10' ,				5 )

    skip_list.insert('Key7' ,				7 )
    skip_list.insert('Key5' ,				5 )
    skip_list.insert('Key10' ,				10 )

    UpperCAmelCase									=					skip_list.head
    UpperCAmelCase									=					{}
    while node.level != 0:
        UpperCAmelCase									=					node.forward[0]
        UpperCAmelCase									=					node.value

    if len(lowerCAmelCase ) != 4:
        print()
    assert len(lowerCAmelCase ) == 4
    assert all_values["Key1"] == 12
    assert all_values["Key7"] == 7
    assert all_values["Key5"] == 5
    assert all_values["Key10"] == 10




def     lowercase__						(					) ->      Tuple:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()
    assert skip_list.find('Some key' ) is None




def     lowercase__						(					) ->      Optional[Any]:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()

    skip_list.insert('Key2' ,				20 )
    assert skip_list.find('Key2' ) == 20

    skip_list.insert('Some Key' ,				10 )
    skip_list.insert('Key2' ,				8 )
    skip_list.insert('V' ,				13 )

    assert skip_list.find('Y' ) is None
    assert skip_list.find('Key2' ) == 8
    assert skip_list.find('Some Key' ) == 10
    assert skip_list.find('V' ) == 13




def     lowercase__						(					) ->      Optional[Any]:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()
    skip_list.delete('Some key' )

    assert len(skip_list.head.forward ) == 0




def     lowercase__						(					) ->      Tuple:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()

    skip_list.insert('Key1' ,				12 )
    skip_list.insert('V' ,				13 )
    skip_list.insert('X' ,				14 )
    skip_list.insert('Key2' ,				15 )

    skip_list.delete('V' )
    skip_list.delete('Key2' )

    assert skip_list.find('V' ) is None
    assert skip_list.find('Key2' ) is None




def     lowercase__						(					) ->      Any:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()

    skip_list.insert('Key1' ,				12 )
    skip_list.insert('V' ,				13 )
    skip_list.insert('X' ,				14 )
    skip_list.insert('Key2' ,				15 )

    skip_list.delete('V' )
    assert skip_list.find('V' ) is None
    assert skip_list.find('X' ) == 14
    assert skip_list.find('Key1' ) == 12
    assert skip_list.find('Key2' ) == 15

    skip_list.delete('X' )
    assert skip_list.find('V' ) is None
    assert skip_list.find('X' ) is None
    assert skip_list.find('Key1' ) == 12
    assert skip_list.find('Key2' ) == 15

    skip_list.delete('Key1' )
    assert skip_list.find('V' ) is None
    assert skip_list.find('X' ) is None
    assert skip_list.find('Key1' ) is None
    assert skip_list.find('Key2' ) == 15

    skip_list.delete('Key2' )
    assert skip_list.find('V' ) is None
    assert skip_list.find('X' ) is None
    assert skip_list.find('Key1' ) is None
    assert skip_list.find('Key2' ) is None




def     lowercase__						(					) ->      int:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()

    skip_list.insert('Key1' ,				12 )
    skip_list.insert('V' ,				13 )
    skip_list.insert('X' ,				142 )
    skip_list.insert('Key2' ,				15 )

    skip_list.delete('X' )

    def traverse_keys(lowerCAmelCase				:					Tuple ):
        yield node.key
        for forward_node in node.forward:
            yield from traverse_keys(lowerCAmelCase )

    assert len(set(traverse_keys(skip_list.head ) ) ) == 4




def     lowercase__						(					) ->      Union[str, Any]:






    """simple docstring"""




    def is_sorted(lowerCAmelCase				:					int ):
        return all(next_item >= item for item, next_item in zip(lowerCAmelCase ,				lst[1:] ) )

    UpperCAmelCase									=					SkipList()
    for i in range(10 ):
        skip_list.insert(lowerCAmelCase ,				lowerCAmelCase )
    assert is_sorted(list(lowerCAmelCase ) )
    skip_list.delete(5 )
    skip_list.delete(8 )
    skip_list.delete(2 )
    assert is_sorted(list(lowerCAmelCase ) )
    skip_list.insert(-12 ,				-12 )
    skip_list.insert(77 ,				77 )
    assert is_sorted(list(lowerCAmelCase ) )




def     lowercase__						(					) ->      Dict:






    """simple docstring"""




    for _ in range(100 ):
        # Repeat test 100 times due to the probabilistic nature of skip list
        # random values == random bugs
        test_insert()
        test_insert_overrides_existing_value()

        test_searching_empty_list_returns_none()
        test_search()

        test_deleting_item_from_empty_list_do_nothing()
        test_deleted_items_are_not_founded_by_find_method()
        test_delete_removes_only_given_key()
        test_delete_doesnt_leave_dead_nodes()

        test_iter_always_yields_sorted_values()




def     lowercase__						(					) ->      List[Any]:






    """simple docstring"""




    UpperCAmelCase									=					SkipList()
    skip_list.insert(2 ,				'2' )
    skip_list.insert(4 ,				'4' )
    skip_list.insert(6 ,				'4' )
    skip_list.insert(4 ,				'5' )
    skip_list.insert(8 ,				'4' )
    skip_list.insert(9 ,				'4' )

    skip_list.delete(4 )

    print(lowerCAmelCase )


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   main()





"""simple docstring"""

import argparse
import datetime




def     lowercase__						(					lowerCAmelCase				:					str ) ->      str:






    """simple docstring"""




    UpperCAmelCase									=					{
        '0': 'Sunday',
        '1': 'Monday',
        '2': 'Tuesday',
        '3': 'Wednesday',
        '4': 'Thursday',
        '5': 'Friday',
        '6': 'Saturday',
    }

    UpperCAmelCase									=					{0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 0}

    # Validate
    if not 0 < len(lowerCAmelCase ) < 11:
        raise ValueError('Must be 10 characters long' )

    # Get month
    UpperCAmelCase									=					int(date_input[0] + date_input[1] )
    # Validate
    if not 0 < m < 13:
        raise ValueError('Month must be between 1 - 12' )

    UpperCAmelCase									=					date_input[2]
    # Validate
    if sep_a not in ["-", "/"]:
        raise ValueError('Date separator must be \'-\' or \'/\'' )

    # Get day
    UpperCAmelCase									=					int(date_input[3] + date_input[4] )
    # Validate
    if not 0 < d < 32:
        raise ValueError('Date must be between 1 - 31' )

    # Get second separator
    UpperCAmelCase									=					date_input[5]
    # Validate
    if sep_a not in ["-", "/"]:
        raise ValueError('Date separator must be \'-\' or \'/\'' )

    # Get year
    UpperCAmelCase									=					int(date_input[6] + date_input[7] + date_input[8] + date_input[9] )
    # Arbitrary year range
    if not 45 < y < 8_500:
        raise ValueError(
            'Year out of range. There has to be some sort of limit...right?' )

    # Get datetime obj for validation
    UpperCAmelCase									=					datetime.date(int(lowerCAmelCase ) ,				int(lowerCAmelCase ) ,				int(lowerCAmelCase ) )

    # Start math
    if m <= 2:
        UpperCAmelCase									=					y - 1
        UpperCAmelCase									=					m + 12
    # maths var
    UpperCAmelCase									=					int(str(lowerCAmelCase )[:2] )
    UpperCAmelCase									=					int(str(lowerCAmelCase )[2:] )
    UpperCAmelCase									=					int(2.6 * m - 5.39 )
    UpperCAmelCase									=					int(c / 4 )
    UpperCAmelCase									=					int(k / 4 )
    UpperCAmelCase									=					int(d + k )
    UpperCAmelCase									=					int(t + u + v + x )
    UpperCAmelCase									=					int(z - (2 * c) )
    UpperCAmelCase									=					round(w % 7 )
    # End math

    # Validate math
    if f != convert_datetime_days[dt_ck.weekday()]:
        raise AssertionError('The date was evaluated incorrectly. Contact developer.' )

    # Response
    UpperCAmelCase									=					F"Your date {date_input}, is a {days[str(lowerCAmelCase )]}!"
    return response


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   SCREAMING_SNAKE_CASE_    					=						argparse.ArgumentParser(
       description=(
           '''Find out what day of the week nearly any date is or was. Enter '''
           '''date as a string in the mm-dd-yyyy or mm/dd/yyyy format'''
       )
   )
   parser.add_argument(
       '''date_input''', type=str, help='''Date as a string (mm-dd-yyyy or mm/dd/yyyy)'''
   )
   SCREAMING_SNAKE_CASE_    					=						parser.parse_args()
   zeller(args.date_input)



