We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Doctests failing maths/bailey_borwein_plouffe.py
Doctests are failing in https://github.com/TheAlgorithms/Python/blob/master/maths/bailey_borwein_plouffe.py

```
________ [doctest] maths.bailey_borwein_plouffe.bailey_borwein_plouffe _________
021     ValueError: Digit position must be a positive integer
022     >>> bailey_borwein_plouffe(0)
023     Traceback (most recent call last):
024       ...
025     ValueError: Digit position must be a positive integer
026     >>> bailey_borwein_plouffe(1.7)
027     Traceback (most recent call last):
028       ...
029     ValueError: Digit position must be a positive integer
030     >>> bailey_borwein_plouffe(2, -10)
Differences (unified diff with -expected +actual):
    @@ -1,3 +1,8 @@
     Traceback (most recent call last):
    -  ...
    -ValueError: Precision must be a nonnegative integer
    +  File "/opt/python/3.8.1/lib/python3.8/doctest.py", line 1329, in __run
    +    exec(compile(example.source, filename, "single",
    +  File "<doctest maths.bailey_borwein_plouffe.bailey_borwein_plouffe[5]>", line 1, in <module>
    +    bailey_borwein_plouffe(2, -10)
    +  File "/home/travis/build/TheAlgorithms/Python/maths/bailey_borwein_plouffe.py", line 42, in bailey_borwein_plouffe
    +    raise ValueError("Please input a nonnegative integer for the precision")
    +ValueError: Please input a nonnegative integer for the precision
```
Source: https://travis-ci.com/github/TheAlgorithms/Python/builds/166844585

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `data_structures/linked_list/singly_linked_list.py`
Content:
```
1 class Node:  # create a Node
2     def __init__(self, data):
3         self.data = data  # given data
4         self.next = None  # given next to None
5 
6     def __repr__(self):  # string representation of a Node
7         return f"Node({self.data})"
8 
9 
10 class LinkedList:
11     def __init__(self):
12         self.head = None  # initialize head to None
13 
14     def insert_tail(self, data) -> None:
15         if self.head is None:
16             self.insert_head(data)  # if this is first node, call insert_head
17         else:
18             temp = self.head
19             while temp.next:  # traverse to last node
20                 temp = temp.next
21             temp.next = Node(data)  # create node & link to tail
22 
23     def insert_head(self, data) -> None:
24         new_node = Node(data)  # create a new node
25         if self.head:
26             new_node.next = self.head  # link new_node to head
27         self.head = new_node  # make NewNode as head
28 
29     def print_list(self) -> None:  # print every node data
30         temp = self.head
31         while temp:
32             print(temp.data)
33             temp = temp.next
34 
35     def delete_head(self):  # delete from head
36         temp = self.head
37         if self.head:
38             self.head = self.head.next
39             temp.next = None
40         return temp
41 
42     def delete_tail(self):  # delete from tail
43         temp = self.head
44         if self.head:
45             if self.head.next is None:  # if head is the only Node in the Linked List
46                 self.head = None
47             else:
48                 while temp.next.next:  # find the 2nd last element
49                     temp = temp.next
50                 # (2nd last element).next = None and temp = last element
51                 temp.next, temp = None, temp.next
52         return temp
53 
54     def is_empty(self) -> bool:
55         return self.head is None  # return True if head is none
56 
57     def reverse(self):
58         prev = None
59         current = self.head
60 
61         while current:
62             # Store the current node's next node.
63             next_node = current.next
64             # Make the current node's next point backwards
65             current.next = prev
66             # Make the previous node be the current node
67             prev = current
68             # Make the current node the next node (to progress iteration)
69             current = next_node
70         # Return prev in order to put the head at the end
71         self.head = prev
72 
73     def __repr__(self):  # String representation/visualization of a Linked Lists
74         current = self.head
75         string_repr = ""
76         while current:
77             string_repr += f"{current} --> "
78             current = current.next
79         # END represents end of the LinkedList
80         return string_repr + "END"
81 
82     # Indexing Support. Used to get a node at particular position
83     def __getitem__(self, index):
84         current = self.head
85 
86         # If LinkedList is empty
87         if current is None:
88             raise IndexError("The Linked List is empty")
89 
90         # Move Forward 'index' times
91         for _ in range(index):
92             # If the LinkedList ends before reaching specified node
93             if current.next is None:
94                 raise IndexError("Index out of range.")
95             current = current.next
96         return current
97 
98     # Used to change the data of a particular node
99     def __setitem__(self, index, data):
100         current = self.head
101         # If list is empty
102         if current is None:
103             raise IndexError("The Linked List is empty")
104         for i in range(index):
105             if current.next is None:
106                 raise IndexError("Index out of range.")
107             current = current.next
108         current.data = data
109        
110     def __len__(self):
111         """
112         Return length of linked list i.e. number of nodes
113         >>> linked_list = LinkedList()
114         >>> len(linked_list)
115         0
116         >>> linked_list.insert_tail("head")
117         >>> len(linked_list)
118         1
119         >>> linked_list.insert_head("head")
120         >>> len(linked_list)
121         2
122         >>> _ = linked_list.delete_tail()
123         >>> len(linked_list)
124         1
125         >>> _ = linked_list.delete_head()
126         >>> len(linked_list)
127         0
128         """
129         if not self.head:
130             return 0
131 
132         count = 0
133         cur_node = self.head
134         while cur_node.next:
135             count += 1
136             cur_node = cur_node.next
137         return count + 1
138 
139 
140 def main():
141     A = LinkedList()
142     A.insert_head(input("Inserting 1st at head ").strip())
143     A.insert_head(input("Inserting 2nd at head ").strip())
144     print("\nPrint list:")
145     A.print_list()
146     A.insert_tail(input("\nInserting 1st at tail ").strip())
147     A.insert_tail(input("Inserting 2nd at tail ").strip())
148     print("\nPrint list:")
149     A.print_list()
150     print("\nDelete head")
151     A.delete_head()
152     print("Delete tail")
153     A.delete_tail()
154     print("\nPrint list:")
155     A.print_list()
156     print("\nReverse linked list")
157     A.reverse()
158     print("\nPrint list:")
159     A.print_list()
160     print("\nString representation of linked list:")
161     print(A)
162     print("\nReading/changing Node data using indexing:")
163     print(f"Element at Position 1: {A[1]}")
164     A[1] = input("Enter New Value: ").strip()
165     print("New list:")
166     print(A)
167     print(f"length of A is : {len(A)}")
168 
169 
170 if __name__ == "__main__":
171     main()
172
```

Path: `maths/bailey_borwein_plouffe.py`
Content:
```
1 def bailey_borwein_plouffe(digit_position: int, precision: int = 1000) -> str:
2     """
3     Implement a popular pi-digit-extraction algorithm known as the 
4     Bailey-Borwein-Plouffe (BBP) formula to calculate the nth hex digit of pi.
5     Wikipedia page:
6     https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula
7     @param digit_position: a positive integer representing the position of the digit to extract. 
8     The digit immediately after the decimal point is located at position 1.
9     @param precision: number of terms in the second summation to calculate.
10     A higher number reduces the chance of an error but increases the runtime.
11     @return: a hexadecimal digit representing the digit at the nth position
12     in pi's decimal expansion.
13     
14     >>> "".join(bailey_borwein_plouffe(i) for i in range(1, 11))
15     '243f6a8885'
16     >>> bailey_borwein_plouffe(5, 10000)
17     '6'
18     >>> bailey_borwein_plouffe(-10)
19     Traceback (most recent call last):
20       ...
21     ValueError: Digit position must be a positive integer
22     >>> bailey_borwein_plouffe(0)
23     Traceback (most recent call last):
24       ...
25     ValueError: Digit position must be a positive integer
26     >>> bailey_borwein_plouffe(1.7)
27     Traceback (most recent call last):
28       ...
29     ValueError: Digit position must be a positive integer
30     >>> bailey_borwein_plouffe(2, -10)
31     Traceback (most recent call last):
32       ...
33     ValueError: Precision must be a nonnegative integer
34     >>> bailey_borwein_plouffe(2, 1.6)
35     Traceback (most recent call last):
36       ...
37     ValueError: Precision must be a nonnegative integer
38     """
39     if (not isinstance(digit_position, int)) or (digit_position <= 0):
40         raise ValueError("Digit position must be a positive integer")
41     elif (not isinstance(precision, int)) or (precision < 0):
42         raise ValueError("Please input a nonnegative integer for the precision")
43 
44     # compute an approximation of (16 ** (n - 1)) * pi whose fractional part is mostly accurate
45     sum_result = (
46         4 * _subsum(digit_position, 1, precision)
47         - 2 * _subsum(digit_position, 4, precision)
48         - _subsum(digit_position, 5, precision)
49         - _subsum(digit_position, 6, precision)
50     )
51 
52     # return the first hex digit of the fractional part of the result
53     return hex(int((sum_result % 1) * 16))[2:]
54 
55 
56 def _subsum(
57     digit_pos_to_extract: int, denominator_addend: int, precision: int
58 ) -> float:
59     # only care about first digit of fractional part; don't need decimal
60     """
61     Private helper function to implement the summation
62     functionality. 
63     @param digit_pos_to_extract: digit position to extract
64     @param denominator_addend: added to denominator of fractions in the formula
65     @param precision: same as precision in main function
66     @return: floating-point number whose integer part is not important 
67     """
68     sum = 0.0
69     for sum_index in range(digit_pos_to_extract + precision):
70         denominator = 8 * sum_index + denominator_addend
71         exponential_term = 0.0
72         if sum_index < digit_pos_to_extract:
73             # if the exponential term is an integer and we mod it by the denominator before
74             # dividing, only the integer part of the sum will change; the fractional part will not
75             exponential_term = pow(
76                 16, digit_pos_to_extract - 1 - sum_index, denominator
77             )
78         else:
79             exponential_term = pow(16, digit_pos_to_extract - 1 - sum_index)
80         sum += exponential_term / denominator
81     return sum
82 
83 
84 if __name__ == "__main__":
85     import doctest
86 
87     doctest.testmod()
88
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/data_structures/linked_list/singly_linked_list.py b/data_structures/linked_list/singly_linked_list.py
--- a/data_structures/linked_list/singly_linked_list.py
+++ b/data_structures/linked_list/singly_linked_list.py
@@ -106,7 +106,7 @@
                 raise IndexError("Index out of range.")
             current = current.next
         current.data = data
-       
+
     def __len__(self):
         """
         Return length of linked list i.e. number of nodes
diff --git a/maths/bailey_borwein_plouffe.py b/maths/bailey_borwein_plouffe.py
--- a/maths/bailey_borwein_plouffe.py
+++ b/maths/bailey_borwein_plouffe.py
@@ -39,7 +39,7 @@
     if (not isinstance(digit_position, int)) or (digit_position <= 0):
         raise ValueError("Digit position must be a positive integer")
     elif (not isinstance(precision, int)) or (precision < 0):
-        raise ValueError("Please input a nonnegative integer for the precision")
+        raise ValueError("Precision must be a nonnegative integer")
 
     # compute an approximation of (16 ** (n - 1)) * pi whose fractional part is mostly accurate
     sum_result = (

{"golden_diff": "diff --git a/data_structures/linked_list/singly_linked_list.py b/data_structures/linked_list/singly_linked_list.py\n--- a/data_structures/linked_list/singly_linked_list.py\n+++ b/data_structures/linked_list/singly_linked_list.py\n@@ -106,7 +106,7 @@\n                 raise IndexError(\"Index out of range.\")\n             current = current.next\n         current.data = data\n-       \n+\n     def __len__(self):\n         \"\"\"\n         Return length of linked list i.e. number of nodes\ndiff --git a/maths/bailey_borwein_plouffe.py b/maths/bailey_borwein_plouffe.py\n--- a/maths/bailey_borwein_plouffe.py\n+++ b/maths/bailey_borwein_plouffe.py\n@@ -39,7 +39,7 @@\n     if (not isinstance(digit_position, int)) or (digit_position <= 0):\n         raise ValueError(\"Digit position must be a positive integer\")\n     elif (not isinstance(precision, int)) or (precision < 0):\n-        raise ValueError(\"Please input a nonnegative integer for the precision\")\n+        raise ValueError(\"Precision must be a nonnegative integer\")\n \n     # compute an approximation of (16 ** (n - 1)) * pi whose fractional part is mostly accurate\n     sum_result = (\n", "issue": "Doctests failing maths/bailey_borwein_plouffe.py\nDoctests are failing in https://github.com/TheAlgorithms/Python/blob/master/maths/bailey_borwein_plouffe.py\r\n\r\n```\r\n________ [doctest] maths.bailey_borwein_plouffe.bailey_borwein_plouffe _________\r\n021     ValueError: Digit position must be a positive integer\r\n022     >>> bailey_borwein_plouffe(0)\r\n023     Traceback (most recent call last):\r\n024       ...\r\n025     ValueError: Digit position must be a positive integer\r\n026     >>> bailey_borwein_plouffe(1.7)\r\n027     Traceback (most recent call last):\r\n028       ...\r\n029     ValueError: Digit position must be a positive integer\r\n030     >>> bailey_borwein_plouffe(2, -10)\r\nDifferences (unified diff with -expected +actual):\r\n    @@ -1,3 +1,8 @@\r\n     Traceback (most recent call last):\r\n    -  ...\r\n    -ValueError: Precision must be a nonnegative integer\r\n    +  File \"/opt/python/3.8.1/lib/python3.8/doctest.py\", line 1329, in __run\r\n    +    exec(compile(example.source, filename, \"single\",\r\n    +  File \"<doctest maths.bailey_borwein_plouffe.bailey_borwein_plouffe[5]>\", line 1, in <module>\r\n    +    bailey_borwein_plouffe(2, -10)\r\n    +  File \"/home/travis/build/TheAlgorithms/Python/maths/bailey_borwein_plouffe.py\", line 42, in bailey_borwein_plouffe\r\n    +    raise ValueError(\"Please input a nonnegative integer for the precision\")\r\n    +ValueError: Please input a nonnegative integer for the precision\r\n```\r\nSource: https://travis-ci.com/github/TheAlgorithms/Python/builds/166844585\n", "before_files": [{"content": "class Node:  # create a Node\n    def __init__(self, data):\n        self.data = data  # given data\n        self.next = None  # given next to None\n\n    def __repr__(self):  # string representation of a Node\n        return f\"Node({self.data})\"\n\n\nclass LinkedList:\n    def __init__(self):\n        self.head = None  # initialize head to None\n\n    def insert_tail(self, data) -> None:\n        if self.head is None:\n            self.insert_head(data)  # if this is first node, call insert_head\n        else:\n            temp = self.head\n            while temp.next:  # traverse to last node\n                temp = temp.next\n            temp.next = Node(data)  # create node & link to tail\n\n    def insert_head(self, data) -> None:\n        new_node = Node(data)  # create a new node\n        if self.head:\n            new_node.next = self.head  # link new_node to head\n        self.head = new_node  # make NewNode as head\n\n    def print_list(self) -> None:  # print every node data\n        temp = self.head\n        while temp:\n            print(temp.data)\n            temp = temp.next\n\n    def delete_head(self):  # delete from head\n        temp = self.head\n        if self.head:\n            self.head = self.head.next\n            temp.next = None\n        return temp\n\n    def delete_tail(self):  # delete from tail\n        temp = self.head\n        if self.head:\n            if self.head.next is None:  # if head is the only Node in the Linked List\n                self.head = None\n            else:\n                while temp.next.next:  # find the 2nd last element\n                    temp = temp.next\n                # (2nd last element).next = None and temp = last element\n                temp.next, temp = None, temp.next\n        return temp\n\n    def is_empty(self) -> bool:\n        return self.head is None  # return True if head is none\n\n    def reverse(self):\n        prev = None\n        current = self.head\n\n        while current:\n            # Store the current node's next node.\n            next_node = current.next\n            # Make the current node's next point backwards\n            current.next = prev\n            # Make the previous node be the current node\n            prev = current\n            # Make the current node the next node (to progress iteration)\n            current = next_node\n        # Return prev in order to put the head at the end\n        self.head = prev\n\n    def __repr__(self):  # String representation/visualization of a Linked Lists\n        current = self.head\n        string_repr = \"\"\n        while current:\n            string_repr += f\"{current} --> \"\n            current = current.next\n        # END represents end of the LinkedList\n        return string_repr + \"END\"\n\n    # Indexing Support. Used to get a node at particular position\n    def __getitem__(self, index):\n        current = self.head\n\n        # If LinkedList is empty\n        if current is None:\n            raise IndexError(\"The Linked List is empty\")\n\n        # Move Forward 'index' times\n        for _ in range(index):\n            # If the LinkedList ends before reaching specified node\n            if current.next is None:\n                raise IndexError(\"Index out of range.\")\n            current = current.next\n        return current\n\n    # Used to change the data of a particular node\n    def __setitem__(self, index, data):\n        current = self.head\n        # If list is empty\n        if current is None:\n            raise IndexError(\"The Linked List is empty\")\n        for i in range(index):\n            if current.next is None:\n                raise IndexError(\"Index out of range.\")\n            current = current.next\n        current.data = data\n       \n    def __len__(self):\n        \"\"\"\n        Return length of linked list i.e. number of nodes\n        >>> linked_list = LinkedList()\n        >>> len(linked_list)\n        0\n        >>> linked_list.insert_tail(\"head\")\n        >>> len(linked_list)\n        1\n        >>> linked_list.insert_head(\"head\")\n        >>> len(linked_list)\n        2\n        >>> _ = linked_list.delete_tail()\n        >>> len(linked_list)\n        1\n        >>> _ = linked_list.delete_head()\n        >>> len(linked_list)\n        0\n        \"\"\"\n        if not self.head:\n            return 0\n\n        count = 0\n        cur_node = self.head\n        while cur_node.next:\n            count += 1\n            cur_node = cur_node.next\n        return count + 1\n\n\ndef main():\n    A = LinkedList()\n    A.insert_head(input(\"Inserting 1st at head \").strip())\n    A.insert_head(input(\"Inserting 2nd at head \").strip())\n    print(\"\\nPrint list:\")\n    A.print_list()\n    A.insert_tail(input(\"\\nInserting 1st at tail \").strip())\n    A.insert_tail(input(\"Inserting 2nd at tail \").strip())\n    print(\"\\nPrint list:\")\n    A.print_list()\n    print(\"\\nDelete head\")\n    A.delete_head()\n    print(\"Delete tail\")\n    A.delete_tail()\n    print(\"\\nPrint list:\")\n    A.print_list()\n    print(\"\\nReverse linked list\")\n    A.reverse()\n    print(\"\\nPrint list:\")\n    A.print_list()\n    print(\"\\nString representation of linked list:\")\n    print(A)\n    print(\"\\nReading/changing Node data using indexing:\")\n    print(f\"Element at Position 1: {A[1]}\")\n    A[1] = input(\"Enter New Value: \").strip()\n    print(\"New list:\")\n    print(A)\n    print(f\"length of A is : {len(A)}\")\n\n\nif __name__ == \"__main__\":\n    main()\n", "path": "data_structures/linked_list/singly_linked_list.py"}, {"content": "def bailey_borwein_plouffe(digit_position: int, precision: int = 1000) -> str:\n    \"\"\"\n    Implement a popular pi-digit-extraction algorithm known as the \n    Bailey-Borwein-Plouffe (BBP) formula to calculate the nth hex digit of pi.\n    Wikipedia page:\n    https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula\n    @param digit_position: a positive integer representing the position of the digit to extract. \n    The digit immediately after the decimal point is located at position 1.\n    @param precision: number of terms in the second summation to calculate.\n    A higher number reduces the chance of an error but increases the runtime.\n    @return: a hexadecimal digit representing the digit at the nth position\n    in pi's decimal expansion.\n    \n    >>> \"\".join(bailey_borwein_plouffe(i) for i in range(1, 11))\n    '243f6a8885'\n    >>> bailey_borwein_plouffe(5, 10000)\n    '6'\n    >>> bailey_borwein_plouffe(-10)\n    Traceback (most recent call last):\n      ...\n    ValueError: Digit position must be a positive integer\n    >>> bailey_borwein_plouffe(0)\n    Traceback (most recent call last):\n      ...\n    ValueError: Digit position must be a positive integer\n    >>> bailey_borwein_plouffe(1.7)\n    Traceback (most recent call last):\n      ...\n    ValueError: Digit position must be a positive integer\n    >>> bailey_borwein_plouffe(2, -10)\n    Traceback (most recent call last):\n      ...\n    ValueError: Precision must be a nonnegative integer\n    >>> bailey_borwein_plouffe(2, 1.6)\n    Traceback (most recent call last):\n      ...\n    ValueError: Precision must be a nonnegative integer\n    \"\"\"\n    if (not isinstance(digit_position, int)) or (digit_position <= 0):\n        raise ValueError(\"Digit position must be a positive integer\")\n    elif (not isinstance(precision, int)) or (precision < 0):\n        raise ValueError(\"Please input a nonnegative integer for the precision\")\n\n    # compute an approximation of (16 ** (n - 1)) * pi whose fractional part is mostly accurate\n    sum_result = (\n        4 * _subsum(digit_position, 1, precision)\n        - 2 * _subsum(digit_position, 4, precision)\n        - _subsum(digit_position, 5, precision)\n        - _subsum(digit_position, 6, precision)\n    )\n\n    # return the first hex digit of the fractional part of the result\n    return hex(int((sum_result % 1) * 16))[2:]\n\n\ndef _subsum(\n    digit_pos_to_extract: int, denominator_addend: int, precision: int\n) -> float:\n    # only care about first digit of fractional part; don't need decimal\n    \"\"\"\n    Private helper function to implement the summation\n    functionality. \n    @param digit_pos_to_extract: digit position to extract\n    @param denominator_addend: added to denominator of fractions in the formula\n    @param precision: same as precision in main function\n    @return: floating-point number whose integer part is not important \n    \"\"\"\n    sum = 0.0\n    for sum_index in range(digit_pos_to_extract + precision):\n        denominator = 8 * sum_index + denominator_addend\n        exponential_term = 0.0\n        if sum_index < digit_pos_to_extract:\n            # if the exponential term is an integer and we mod it by the denominator before\n            # dividing, only the integer part of the sum will change; the fractional part will not\n            exponential_term = pow(\n                16, digit_pos_to_extract - 1 - sum_index, denominator\n            )\n        else:\n            exponential_term = pow(16, digit_pos_to_extract - 1 - sum_index)\n        sum += exponential_term / denominator\n    return sum\n\n\nif __name__ == \"__main__\":\n    import doctest\n\n    doctest.testmod()\n", "path": "maths/bailey_borwein_plouffe.py"}], "after_files": [{"content": "class Node:  # create a Node\n    def __init__(self, data):\n        self.data = data  # given data\n        self.next = None  # given next to None\n\n    def __repr__(self):  # string representation of a Node\n        return f\"Node({self.data})\"\n\n\nclass LinkedList:\n    def __init__(self):\n        self.head = None  # initialize head to None\n\n    def insert_tail(self, data) -> None:\n        if self.head is None:\n            self.insert_head(data)  # if this is first node, call insert_head\n        else:\n            temp = self.head\n            while temp.next:  # traverse to last node\n                temp = temp.next\n            temp.next = Node(data)  # create node & link to tail\n\n    def insert_head(self, data) -> None:\n        new_node = Node(data)  # create a new node\n        if self.head:\n            new_node.next = self.head  # link new_node to head\n        self.head = new_node  # make NewNode as head\n\n    def print_list(self) -> None:  # print every node data\n        temp = self.head\n        while temp:\n            print(temp.data)\n            temp = temp.next\n\n    def delete_head(self):  # delete from head\n        temp = self.head\n        if self.head:\n            self.head = self.head.next\n            temp.next = None\n        return temp\n\n    def delete_tail(self):  # delete from tail\n        temp = self.head\n        if self.head:\n            if self.head.next is None:  # if head is the only Node in the Linked List\n                self.head = None\n            else:\n                while temp.next.next:  # find the 2nd last element\n                    temp = temp.next\n                # (2nd last element).next = None and temp = last element\n                temp.next, temp = None, temp.next\n        return temp\n\n    def is_empty(self) -> bool:\n        return self.head is None  # return True if head is none\n\n    def reverse(self):\n        prev = None\n        current = self.head\n\n        while current:\n            # Store the current node's next node.\n            next_node = current.next\n            # Make the current node's next point backwards\n            current.next = prev\n            # Make the previous node be the current node\n            prev = current\n            # Make the current node the next node (to progress iteration)\n            current = next_node\n        # Return prev in order to put the head at the end\n        self.head = prev\n\n    def __repr__(self):  # String representation/visualization of a Linked Lists\n        current = self.head\n        string_repr = \"\"\n        while current:\n            string_repr += f\"{current} --> \"\n            current = current.next\n        # END represents end of the LinkedList\n        return string_repr + \"END\"\n\n    # Indexing Support. Used to get a node at particular position\n    def __getitem__(self, index):\n        current = self.head\n\n        # If LinkedList is empty\n        if current is None:\n            raise IndexError(\"The Linked List is empty\")\n\n        # Move Forward 'index' times\n        for _ in range(index):\n            # If the LinkedList ends before reaching specified node\n            if current.next is None:\n                raise IndexError(\"Index out of range.\")\n            current = current.next\n        return current\n\n    # Used to change the data of a particular node\n    def __setitem__(self, index, data):\n        current = self.head\n        # If list is empty\n        if current is None:\n            raise IndexError(\"The Linked List is empty\")\n        for i in range(index):\n            if current.next is None:\n                raise IndexError(\"Index out of range.\")\n            current = current.next\n        current.data = data\n\n    def __len__(self):\n        \"\"\"\n        Return length of linked list i.e. number of nodes\n        >>> linked_list = LinkedList()\n        >>> len(linked_list)\n        0\n        >>> linked_list.insert_tail(\"head\")\n        >>> len(linked_list)\n        1\n        >>> linked_list.insert_head(\"head\")\n        >>> len(linked_list)\n        2\n        >>> _ = linked_list.delete_tail()\n        >>> len(linked_list)\n        1\n        >>> _ = linked_list.delete_head()\n        >>> len(linked_list)\n        0\n        \"\"\"\n        if not self.head:\n            return 0\n\n        count = 0\n        cur_node = self.head\n        while cur_node.next:\n            count += 1\n            cur_node = cur_node.next\n        return count + 1\n\n\ndef main():\n    A = LinkedList()\n    A.insert_head(input(\"Inserting 1st at head \").strip())\n    A.insert_head(input(\"Inserting 2nd at head \").strip())\n    print(\"\\nPrint list:\")\n    A.print_list()\n    A.insert_tail(input(\"\\nInserting 1st at tail \").strip())\n    A.insert_tail(input(\"Inserting 2nd at tail \").strip())\n    print(\"\\nPrint list:\")\n    A.print_list()\n    print(\"\\nDelete head\")\n    A.delete_head()\n    print(\"Delete tail\")\n    A.delete_tail()\n    print(\"\\nPrint list:\")\n    A.print_list()\n    print(\"\\nReverse linked list\")\n    A.reverse()\n    print(\"\\nPrint list:\")\n    A.print_list()\n    print(\"\\nString representation of linked list:\")\n    print(A)\n    print(\"\\nReading/changing Node data using indexing:\")\n    print(f\"Element at Position 1: {A[1]}\")\n    A[1] = input(\"Enter New Value: \").strip()\n    print(\"New list:\")\n    print(A)\n    print(f\"length of A is : {len(A)}\")\n\n\nif __name__ == \"__main__\":\n    main()\n", "path": "data_structures/linked_list/singly_linked_list.py"}, {"content": "def bailey_borwein_plouffe(digit_position: int, precision: int = 1000) -> str:\n    \"\"\"\n    Implement a popular pi-digit-extraction algorithm known as the \n    Bailey-Borwein-Plouffe (BBP) formula to calculate the nth hex digit of pi.\n    Wikipedia page:\n    https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula\n    @param digit_position: a positive integer representing the position of the digit to extract. \n    The digit immediately after the decimal point is located at position 1.\n    @param precision: number of terms in the second summation to calculate.\n    A higher number reduces the chance of an error but increases the runtime.\n    @return: a hexadecimal digit representing the digit at the nth position\n    in pi's decimal expansion.\n    \n    >>> \"\".join(bailey_borwein_plouffe(i) for i in range(1, 11))\n    '243f6a8885'\n    >>> bailey_borwein_plouffe(5, 10000)\n    '6'\n    >>> bailey_borwein_plouffe(-10)\n    Traceback (most recent call last):\n      ...\n    ValueError: Digit position must be a positive integer\n    >>> bailey_borwein_plouffe(0)\n    Traceback (most recent call last):\n      ...\n    ValueError: Digit position must be a positive integer\n    >>> bailey_borwein_plouffe(1.7)\n    Traceback (most recent call last):\n      ...\n    ValueError: Digit position must be a positive integer\n    >>> bailey_borwein_plouffe(2, -10)\n    Traceback (most recent call last):\n      ...\n    ValueError: Precision must be a nonnegative integer\n    >>> bailey_borwein_plouffe(2, 1.6)\n    Traceback (most recent call last):\n      ...\n    ValueError: Precision must be a nonnegative integer\n    \"\"\"\n    if (not isinstance(digit_position, int)) or (digit_position <= 0):\n        raise ValueError(\"Digit position must be a positive integer\")\n    elif (not isinstance(precision, int)) or (precision < 0):\n        raise ValueError(\"Precision must be a nonnegative integer\")\n\n    # compute an approximation of (16 ** (n - 1)) * pi whose fractional part is mostly accurate\n    sum_result = (\n        4 * _subsum(digit_position, 1, precision)\n        - 2 * _subsum(digit_position, 4, precision)\n        - _subsum(digit_position, 5, precision)\n        - _subsum(digit_position, 6, precision)\n    )\n\n    # return the first hex digit of the fractional part of the result\n    return hex(int((sum_result % 1) * 16))[2:]\n\n\ndef _subsum(\n    digit_pos_to_extract: int, denominator_addend: int, precision: int\n) -> float:\n    # only care about first digit of fractional part; don't need decimal\n    \"\"\"\n    Private helper function to implement the summation\n    functionality. \n    @param digit_pos_to_extract: digit position to extract\n    @param denominator_addend: added to denominator of fractions in the formula\n    @param precision: same as precision in main function\n    @return: floating-point number whose integer part is not important \n    \"\"\"\n    sum = 0.0\n    for sum_index in range(digit_pos_to_extract + precision):\n        denominator = 8 * sum_index + denominator_addend\n        exponential_term = 0.0\n        if sum_index < digit_pos_to_extract:\n            # if the exponential term is an integer and we mod it by the denominator before\n            # dividing, only the integer part of the sum will change; the fractional part will not\n            exponential_term = pow(\n                16, digit_pos_to_extract - 1 - sum_index, denominator\n            )\n        else:\n            exponential_term = pow(16, digit_pos_to_extract - 1 - sum_index)\n        sum += exponential_term / denominator\n    return sum\n\n\nif __name__ == \"__main__\":\n    import doctest\n\n    doctest.testmod()\n", "path": "maths/bailey_borwein_plouffe.py"}]}