Python: How to increment a special-purpose string?

Question

Consider a special-purpose string of length 8, say "A00000XY". The string has following restrictions.

Length = 8.
Last two chars have special meaning and should remain as it is.
A-Z and 0-9 are only valid characters. Thus the regular expression "^[A-Z0-9]{6}XY$" defines the string.

How can I implement a function, say increment, that when called increments the string by one. Thus subsequent calls should look like following:

>>> A = "A00000XY"
>>> print increment(A)
"A00000XY"
>>> print increment(A)
"A00001XY"
>>> print increment(A)
"A00002XY"
...
>>> print increment(A)
"A00009XY"
>>> print increment(A)
"A0000AXY"
>>> print increment(A)
"A0000BXY"
...
>>> print increment(A)
"A0000YXY"
>>> print increment(A)
"A0000ZXY"
>>> print increment(A)
"A00010XY"
>>> print increment(A)
"A00011XY"
...
>>> print increment(A)
"ZZZZZZXY"

Some hints: use `ord` and `chr`. Checkout the ASCII table for digits (48-57) and uppercase letters (65-90). Have a list of those to increment over. Do it for each digit from right to left as you increment with numbers. Increment the neighbor if there was overflow from the right. Play around now to see how far you can get, and come back with some concrete questions when you put in more effort. — bosnjak, Feb 24 '17 at 20:16
```How can I implement a function,...?``` - work your way through [The Tutorial](https://docs.python.org/3/tutorial/index.html) - eventually you will get a handle on the tools that are available and you will start to get Ideas - try some of those ideas out. — wwii, Feb 24 '17 at 20:18
Do you really need to increment a particular string, or you need an algorithm that iterates over all such strings in order? In the former case you can try `itertools.product`. — Ilya V. Schurov, Feb 24 '17 at 20:21
You can use a [numeral system](https://en.wikipedia.org/wiki/Numeral_system#Positional_systems_in_detail) with base 36 to convert the string into a number and back. — , Feb 24 '17 at 20:35

avysk · Accepted Answer · 2017-02-24T20:59:26.417

2

digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def digit_helper(num):
    while num > 0:
        yield digits[num % 36]
        num = num / 36

def increment(string):
    incremented = int(string[:-2], base=36) + 1
    return "".join(reversed(list(digit_helper(incremented)))) + "XY"

Temptation was too high. However, not very suitable as homework answer, I'm afraid :D

Update: it's Python 2. In Python 3 division should be num // 36.

edited Feb 24 '17 at 20:59

answered Feb 24 '17 at 20:37

avysk

1,973
12
18

`num / 36` is a floating-point division. You probably meant the integer-divisor `//`. – Feb 24 '17 at 20:54
@Paul Nope, I was just writing Python 2. `num / 36` is integer division in Python 2. – avysk Feb 24 '17 at 20:55
1

Well, I guess I'm just too much used to Python3 :D. Either way, you should clarify this in the answer. Nice answer apart from that – Feb 24 '17 at 20:58
The answer is almost correct with exception of two issues. 1. Handling for ZZZZZZXY. It should wrap around and return 000000XY. 2. 000000XY isn't handled properly to return 000001XY. It instead returns 1XY. Fixing the two in my reply. I still accept this reply as best reply. – Subhajit Kundu Mar 30 '17 at 08:56

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

So what you really want is a base 36 number. You will need to build a class that works similar to how hex to decimal and decimal to hex conversions work. With your 8 character limit, you have values from 0 to 36^8 - 1 values, or 2821109907455. 9223372036854775807 is the max integer in python , so the good news is that you can represent your value as an integer.

To convert from your string value to the integer:

intValue = 0
Loop through each of the first eight characters in the string.
Pass the character to a function that returns an integer equivalent between 0 and 35. We'll call this charValue
intValue += intValue*36 + charValue

To convert from the integer to your string value:

stringValue = specialCharacters
curDigit = intValue % 36
intValue = intValue / 36
find string equivalent of intValue (0 to Z)
Append to front of stringValue
Repeat until intValue < 36. Any remaining characters would be 0

Obviously you would build the increment and decrement methods as well.

score 0 · Answer 3 · answered Mar 30 '17 at 09:03

Inspired from @avysk response.

The @avysk reply has two issues.

Handling for ZZZZZZXY. It should wrap around and return 000000XY. It shouldn't overflow. However I missed covering this part in my question itself.
000000XY isn't handled properly to return 000001XY. It instead returns 1XY.

Fixing these issue in following code that borrows most from @avysk's response.

digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def digit_helper(num):
  while num > 0:
    yield Tape.digits[num % 36]
    num = num / 36


# This function, using the utility digit_helper, increments the string by 1.
# It produces string in following order:
#     "A00000XY", "A00000XY", "A00001XY", "A00002XY", ...,
#     "A00009XY", "A0000AXY", "A0000BXY", ...,
#     "A0000YXY", "A0000ZXY", "A00010XY", "A00011XY", ...,
#     "ZZZZZZXY", "000000XY", "000001XY", ...
# Logic:
# 1. Strip the string of last two chars.
# 2. Convert to base 36 equivalent integer and increment by one.
# 3. Convert back to Base 36 representation of incremented value.
#   3.1. [0:6] handles the overflow. Overflow happens after "ZZZZZZXY" and produces "1000000XY".
#   3.2. [::-1] reverses the string.
#   3.3. zfill(6) handles underflow, like converting integer 1 to "000001XY".
def increment(string):
  incremented = int(string[:-2], base=36) + 1
  return "".join(Tape.digit_helper(incremented))[0:6][::-1].zfill(6) + string[-2:]

Python: How to increment a special-purpose string?

3 Answers3