Odometer

August 3, 2018

Today’s exercise is an Amazon interview question:

An odometer variously uses letters and digits in its reading; for instance, an odometer might have a reading of G7TS39. Incrementing the odometer means adding 1 to a digit or increasing to the next letter to the next letter, with a carry to the next column when appropriate. Thus, G7TS39 increments to G7TS40 and G7TZ99 increments to G7UA00. As a special case, the odometer never increases in size, but rolls over, so the next odometer reading after Z9ZZ99 is A0AA00. An odometer position that initially contains a digit always contains a digit, and an odometer position that initially contains a letter always contains a letter, so 1Z9 increments to 2A0.

Your task is to write a program to increment an odometer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

5 Responses to “Odometer”

  1. Paul said

    In Python.

    from string import ascii_uppercase, digits
    
    SUCC = {a: b for a, b in zip(ascii_uppercase, ascii_uppercase[1:] + "A")}
    SUCC.update({a: b for a, b in zip(digits, digits[1:] + "0")})
    
    def odo_inc(data):
        datalist = list(data)
        for j, c in reversed(list(enumerate(datalist))):
            datalist[j] = succ = SUCC[c]
            if succ not in "0A":
                break
        return "".join(datalist)
        
    print(odo_inc("1Z9"))     # -> "2A0"
    print(odo_inc("Z9ZZ99"))  # -> "A0AA00"
    print(odo_inc("G7TZ99"))  # -> "G7UA00"
    
  2. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(int argc, char* argv[]) {
        if (argc != 2) {
            fprintf(stderr, "Usage: %s STR\n", argv[0]);
            return EXIT_FAILURE;
        }
        size_t n = strlen(argv[1]);
        int carry = 1;
        for (int i = n - 1; i >= 0; --i) {
            if (!carry) break;
            switch(argv[1][i]) {
                case 'z':
                case 'Z':
                    argv[1][i] -= 25;
                    break;
                case '9':
                    argv[1][i] = '0';
                    break;
                default:
                    ++argv[1][i];
                    carry = 0;
                    break;
            }
        }
        printf("%s\n", argv[1]);
        return EXIT_SUCCESS;
    }
    

    Example:

    $ ./odometer G7TS39
    G7TS40
    
    $ ./odometer G7TZ99
    G7UA00
    
    $ ./odometer Z9ZZ99
    A0AA00
    
    $ ./odometer 1Z9
    2A0
    
  3. Mike said

    Python

    Because everything is better with a regular expression. ;-)

    import functools, re
    
    odo = functools.partial(re.sub, '(.)(?=[9Z]*$)', lambda m: '0' if m[1]=='9' else 'A' if m[1]=='Z' else chr(ord(m[1])+1))
    
    

    It works by replacing anything that is followed by nothing but ‘9’s and ‘Z’s. Replace it with a ‘0’ if it was a ‘9’, by an ‘A’ if it was a ‘Z’, or by the next character in sequence otherwise.

  4. Steve said

    @ProgrammingPraxis: Submitted version for Mumps. Haven’t seen it.

  5. Mumps version

    vista@steve-VirtualBox:~/EHR/r$ cat ODOMETER.m 
    ODOMETER ;
             Q
    	 ;
    GO(STR)  ;
             I STR'?1.AN Q STR_" not alphanumeric"
    	 D GO2(.STR,$L(STR),1)
    	 Q STR
    	 ;
    GO2(STR,POS,CARRY) ;
             Q:'POS  ; No more levels to process
    	 S CHAR=$E(STR,POS)
    	 I CARRY D
    	 . I CHAR?1(1"Z",1"9") D  ; Handle end of letters and digits
    	 . . S $E(STR,POS)=$S(CHAR="Z":"A",1:0)
    	 . . S CARRY=1
    	 . E  D
    	 . . S $E(STR,POS)=$C($A(CHAR)+1)
    	 . . S CARRY=0
    	 E  D  ; No more carries
    	 . S CARRY=0
             D GO2(.STR,$S(CARRY:POS-1,1:0),CARRY)
    	 Q 
    
    Examples:
    vista@steve-VirtualBox:~/EHR/r$ gtm
    
    GTM>F I=123,199,999,"ABC","FZZ","G7TS39" W !,I," --> ",$$GO^ODOMETER(I)
    
    123 --> 124
    199 --> 200
    999 --> 000
    ABC --> ABD
    FZZ --> GAA
    G7TS39 --> G7TS40
    GTM>
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: