Camel Case to Snake Case

Code brought over from other languages is full of names like parseHTTPResponse and XMLHttpRequest. Write camel_to_snake(name) that converts a camel case or Pascal case name to snake case: lowercase words joined by underscores.

The hard part is deciding where one word ends and the next begins. A capital letter starts a new word when:

• the character before it is a lowercase letter or a digit (userId, top10List), or
• the character before it is a capital too and the character after it is a lowercase letter. This is where an acronym ends and a new word begins: in HTTPResponse the R starts Response.

Digits never start a word: they stay with the word before them. The first character never gets an underscore in front of it.

Examples

camel_to_snake("parseHTTPResponse")  # returns 'parse_http_response'
camel_to_snake("userId")             # returns 'user_id'
camel_to_snake("PascalCase")         # returns 'pascal_case'
camel_to_snake("XMLHttpRequest")     # returns 'xml_http_request'

Constraints

• 1 <= len(name) <= 100
• name contains only the letters a to z and A to Z and the digits 0 to 9, and starts with a letter