prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Param switches on faker.password() don't guarantee valid password
  The format switches on `faker.password()` (`special_chars, digits, upper_case, lower_case`) don't always return passwords matching those rules.
  
  This is problematic as when using generated passwords in unit tests, where passwords must conform to validity rules (e.g. "must contain numbers"), tests can randomly fail.
  
  I expected that these switches would guarantee the function returns a conforming password. e.g. `faker.password(digits=True)` always returns a password containing digits, but this is not the case.
  
  
  </issue>
  <code>
  [start of faker/providers/misc/__init__.py]
  1 # coding=utf-8
  2 
  3 from __future__ import unicode_literals
  4 import hashlib
  5 import string
  6 import uuid
  7 
  8 from faker.generator import random
  9 from faker.providers.date_time import Provider as DatetimeProvider
  10 
  11 from .. import BaseProvider
  12 
  13 
  14 class Provider(BaseProvider):
  15     language_codes = ('cn', 'de', 'el', 'en', 'es', 'fr', 'it', 'pt', 'ru')
  16 
  17     @classmethod
  18     def boolean(cls, chance_of_getting_true=50):
  19         return random.randint(1, 100) <= chance_of_getting_true
  20 
  21     @classmethod
  22     def null_boolean(cls):
  23         return {
  24             0: None,
  25             1: True,
  26             -1: False
  27         }[random.randint(-1, 1)]
  28 
  29     @classmethod
  30     def md5(cls, raw_output=False):
  31         """
  32         Calculates the md5 hash of a given string
  33         :example 'cfcd208495d565ef66e7dff9f98764da'
  34         """
  35         res = hashlib.md5(str(random.random()).encode('utf-8'))
  36         if raw_output:
  37             return res.digest()
  38         return res.hexdigest()
  39 
  40     @classmethod
  41     def sha1(cls, raw_output=False):
  42         """
  43         Calculates the sha1 hash of a given string
  44         :example 'b5d86317c2a144cd04d0d7c03b2b02666fafadf2'
  45         """
  46         res = hashlib.sha1(str(random.random()).encode('utf-8'))
  47         if raw_output:
  48             return res.digest()
  49         return res.hexdigest()
  50 
  51     @classmethod
  52     def sha256(cls, raw_output=False):
  53         """
  54         Calculates the sha256 hash of a given string
  55         :example '85086017559ccc40638fcde2fecaf295e0de7ca51b7517b6aebeaaf75b4d4654'
  56         """
  57         res = hashlib.sha256(str(random.random()).encode('utf-8'))
  58         if raw_output:
  59             return res.digest()
  60         return res.hexdigest()
  61 
  62     def locale(self):
  63         return self.language_code() + '_' + self.country_code()
  64 
  65     @classmethod
  66     def country_code(cls):
  67         return cls.random_element(DatetimeProvider.countries)['code']
  68 
  69     @classmethod
  70     def language_code(cls):
  71         return cls.random_element(cls.language_codes)
  72 
  73     @classmethod
  74     def uuid4(cls):
  75         """
  76         Generates a random UUID4 string.
  77         """
  78         return str(uuid.uuid4())
  79 
  80     @classmethod
  81     def password(cls, length=10, special_chars=True, digits=True, upper_case=True, lower_case=True):
  82         """
  83         Generates a random password.
  84         @param length: Integer. Length of a password
  85         @param special_chars: Boolean. Whether to use special characters !@#$%^&*()_+
  86         @param digits: Boolean. Whether to use digits
  87         @param upper_case: Boolean. Whether to use upper letters
  88         @param lower_case: Boolean. Whether to use lower letters
  89         @return: String. Random password
  90         """
  91         chars = ""
  92         if special_chars:
  93             chars += "!@#$%^&*()_+"
  94         if digits:
  95             chars += string.digits
  96         if upper_case:
  97             chars += string.ascii_uppercase
  98         if lower_case:
  99             chars += string.ascii_lowercase
  100         return ''.join(random.choice(chars) for x in range(length))
  101
  [end of faker/providers/misc/__init__.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/faker/providers/misc/__init__.py b/faker/providers/misc/__init__.py
  --- a/faker/providers/misc/__init__.py
  +++ b/faker/providers/misc/__init__.py
  @@ -88,13 +88,33 @@
           @param lower_case: Boolean. Whether to use lower letters
           @return: String. Random password
           """
  -        chars = ""
  +        choices = ""
  +        required_tokens = []
           if special_chars:
  -            chars += "!@#$%^&*()_+"
  +            required_tokens.append(random.choice("!@#$%^&*()_+"))
  +            choices += "!@#$%^&*()_+"
           if digits:
  -            chars += string.digits
  +            required_tokens.append(random.choice(string.digits))
  +            choices += string.digits
           if upper_case:
  -            chars += string.ascii_uppercase
  +            required_tokens.append(random.choice(string.ascii_uppercase))
  +            choices += string.ascii_uppercase
           if lower_case:
  -            chars += string.ascii_lowercase
  -        return ''.join(random.choice(chars) for x in range(length))
  +            required_tokens.append(random.choice(string.ascii_lowercase))
  +            choices += string.ascii_lowercase
  +
  +        assert len(required_tokens) <= length, "Required length is shorter than required characters"
  +
  +        # Generate a first version of the password
  +        chars = [random.choice(choices) for x in range(length)]
  +
  +        # Pick some unique locations
  +        random_indexes = set()
  +        while len(random_indexes) < len(required_tokens):
  +            random_indexes.add(random.randint(0, len(chars) - 1))
  +
  +        # Replace them with the required characters
  +        for i, index in enumerate(random_indexes):
  +            chars[index] = required_tokens[i]
  +
  +        return ''.join(chars)
  
verification_info: {"golden_diff": "diff --git a/faker/providers/misc/__init__.py b/faker/providers/misc/__init__.py\n--- a/faker/providers/misc/__init__.py\n+++ b/faker/providers/misc/__init__.py\n@@ -88,13 +88,33 @@\n         @param lower_case: Boolean. Whether to use lower letters\n         @return: String. Random password\n         \"\"\"\n-        chars = \"\"\n+        choices = \"\"\n+        required_tokens = []\n         if special_chars:\n-            chars += \"!@#$%^&*()_+\"\n+            required_tokens.append(random.choice(\"!@#$%^&*()_+\"))\n+            choices += \"!@#$%^&*()_+\"\n         if digits:\n-            chars += string.digits\n+            required_tokens.append(random.choice(string.digits))\n+            choices += string.digits\n         if upper_case:\n-            chars += string.ascii_uppercase\n+            required_tokens.append(random.choice(string.ascii_uppercase))\n+            choices += string.ascii_uppercase\n         if lower_case:\n-            chars += string.ascii_lowercase\n-        return ''.join(random.choice(chars) for x in range(length))\n+            required_tokens.append(random.choice(string.ascii_lowercase))\n+            choices += string.ascii_lowercase\n+\n+        assert len(required_tokens) <= length, \"Required length is shorter than required characters\"\n+\n+        # Generate a first version of the password\n+        chars = [random.choice(choices) for x in range(length)]\n+\n+        # Pick some unique locations\n+        random_indexes = set()\n+        while len(random_indexes) < len(required_tokens):\n+            random_indexes.add(random.randint(0, len(chars) - 1))\n+\n+        # Replace them with the required characters\n+        for i, index in enumerate(random_indexes):\n+            chars[index] = required_tokens[i]\n+\n+        return ''.join(chars)\n", "issue": "Param switches on faker.password() don't guarantee valid password\nThe format switches on `faker.password()` (`special_chars, digits, upper_case, lower_case`) don't always return passwords matching those rules.\n\nThis is problematic as when using generated passwords in unit tests, where passwords must conform to validity rules (e.g. \"must contain numbers\"), tests can randomly fail.\n\nI expected that these switches would guarantee the function returns a conforming password. e.g. `faker.password(digits=True)` always returns a password containing digits, but this is not the case.\n\n", "before_files": [{"content": "# coding=utf-8\n\nfrom __future__ import unicode_literals\nimport hashlib\nimport string\nimport uuid\n\nfrom faker.generator import random\nfrom faker.providers.date_time import Provider as DatetimeProvider\n\nfrom .. import BaseProvider\n\n\nclass Provider(BaseProvider):\n    language_codes = ('cn', 'de', 'el', 'en', 'es', 'fr', 'it', 'pt', 'ru')\n\n    @classmethod\n    def boolean(cls, chance_of_getting_true=50):\n        return random.randint(1, 100) <= chance_of_getting_true\n\n    @classmethod\n    def null_boolean(cls):\n        return {\n            0: None,\n            1: True,\n            -1: False\n        }[random.randint(-1, 1)]\n\n    @classmethod\n    def md5(cls, raw_output=False):\n        \"\"\"\n        Calculates the md5 hash of a given string\n        :example 'cfcd208495d565ef66e7dff9f98764da'\n        \"\"\"\n        res = hashlib.md5(str(random.random()).encode('utf-8'))\n        if raw_output:\n            return res.digest()\n        return res.hexdigest()\n\n    @classmethod\n    def sha1(cls, raw_output=False):\n        \"\"\"\n        Calculates the sha1 hash of a given string\n        :example 'b5d86317c2a144cd04d0d7c03b2b02666fafadf2'\n        \"\"\"\n        res = hashlib.sha1(str(random.random()).encode('utf-8'))\n        if raw_output:\n            return res.digest()\n        return res.hexdigest()\n\n    @classmethod\n    def sha256(cls, raw_output=False):\n        \"\"\"\n        Calculates the sha256 hash of a given string\n        :example '85086017559ccc40638fcde2fecaf295e0de7ca51b7517b6aebeaaf75b4d4654'\n        \"\"\"\n        res = hashlib.sha256(str(random.random()).encode('utf-8'))\n        if raw_output:\n            return res.digest()\n        return res.hexdigest()\n\n    def locale(self):\n        return self.language_code() + '_' + self.country_code()\n\n    @classmethod\n    def country_code(cls):\n        return cls.random_element(DatetimeProvider.countries)['code']\n\n    @classmethod\n    def language_code(cls):\n        return cls.random_element(cls.language_codes)\n\n    @classmethod\n    def uuid4(cls):\n        \"\"\"\n        Generates a random UUID4 string.\n        \"\"\"\n        return str(uuid.uuid4())\n\n    @classmethod\n    def password(cls, length=10, special_chars=True, digits=True, upper_case=True, lower_case=True):\n        \"\"\"\n        Generates a random password.\n        @param length: Integer. Length of a password\n        @param special_chars: Boolean. Whether to use special characters !@#$%^&*()_+\n        @param digits: Boolean. Whether to use digits\n        @param upper_case: Boolean. Whether to use upper letters\n        @param lower_case: Boolean. Whether to use lower letters\n        @return: String. Random password\n        \"\"\"\n        chars = \"\"\n        if special_chars:\n            chars += \"!@#$%^&*()_+\"\n        if digits:\n            chars += string.digits\n        if upper_case:\n            chars += string.ascii_uppercase\n        if lower_case:\n            chars += string.ascii_lowercase\n        return ''.join(random.choice(chars) for x in range(length))\n", "path": "faker/providers/misc/__init__.py"}]}