Odometer

August 3, 2018

We begin with a function that increments a character:

(define (next-char c)
  (integer->char (+ (char->integer c) 1)))

Next we have a function that increments a single odometer position, which can be either a letter or digit, and returns both the next letter or digit and an indication if there is a carry:

(define (next1 c)
  (cond ((char=? c #\Z) (values #\A #t))
        ((char=? c #\9) (values #\0 #t))
        (else (values (next-char c) #f))))

Finally we have a function that increments each character, starting from the least significant, until there is no carry:

(define (next str)
  (let loop ((cs (reverse (string->list str))) (xs (list)) (carry? #f))
    (if (null? cs) (list->string (reverse xs))
      (call-with-values
        (lambda () (next1 (car cs)))
        (lambda (x carry?)
          (if carry?  (loop (cdr cs) (cons x xs) #f)
            (list->string  (append (reverse (cdr cs)) (cons x xs)))))))))

Here are some examples:

> (next "123")
"124"
> (next "199")
"200"
> (next "999")
"000"
> (next "ABC")
"ABD"
> (next "FZZ")
"GAA"
> (next "G7TS39")
"G7TS40"

You can run the program at https://ideone.com/vDHSfC.

Advertisements

Pages: 1 2

8 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>
    
  6. mcmillhj said

    Perl6 solution delegating some work to the built-in succ method: https://docs.perl6.org/routine/succ

    #perl6
     
    sub succ(Str $digit where *.chars == 1) {
      my $next = $digit.succ;
      my $has_carry = $next.chars > 1;
    
      return $has_carry, $has_carry ?? $next.substr(1) !! $next;
    }
    
    sub odometer(Str:D $current where * ~~ /^<[a..z A..Z 0..9]>+$/) {
      my @next;
    
      my $should_increment = True;
      my $next_digit = Nil;
      for reverse($current.comb) -> $digit {
        if $should_increment {
          ($should_increment, $next_digit) = succ($digit);
          @next.push: $next_digit;
        } else {
          @next.push: $digit;
        }
      }
    
      join '', reverse @next;
    }
    
    for ["G7TS39", "G7TZ99", "Z9ZZ99"] -> $input {
      say odometer($input);
    }
    # G7TS40
    # G7UA00
    # A0AA00
    
  7. Daniel said

    Here’s a solution in Python that uses numpy functions ravel_multi_index and unravel_index.

    The odometer reading is treated as the subscript for indexing into a higher order array. The subscript index is converted to the index for a corresponding flattened version of the array. This index is incremented, and then converted back to a subscript.

    import numpy as np
    import string
    
    def increment(odometer, x=1):
        digits = np.array([int(c, 36) for c in odometer.upper()])
        bases = np.array([10 if x < 10 else 26 for x in digits])
        digits[bases == 26] -= 10
        idx = np.ravel_multi_index(digits, bases)
        idx += x
        idx %= np.ravel_multi_index(bases - 1, bases) + 1
        digits = np.array(np.unravel_index(idx, bases))
        digits[bases == 26] += 10
        lookup = string.digits + string.ascii_uppercase
        return "".join(lookup[x] for x in digits)
    
    print(increment('G7TS39'))
    print(increment('G7TZ99'))
    print(increment('Z9ZZ99'))
    print(increment('1Z9'))
    

    Output:

    G7TS40
    G7UA00
    A0AA00
    2A0
    
  8. sealfin said

    August 3rd, 2018.c:

    #include <ctype.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef short bool;
    
    #define false 0
    #define true 1
    
    char f_ProcessCharacter( char p_character, bool * const p_incrementCharacter, bool * const p_illegalCharacter )
    {
      *p_illegalCharacter = false;
      if( isdigit( p_character ))
      {
        if( *p_incrementCharacter )
        {
          if( p_character == '9' )
            p_character = '0';
          else
          {
            p_character ++;
            *p_incrementCharacter = false;
          }
        }
      }
      else
        if( isalpha( p_character ))
        {
          p_character = toupper( p_character );
          if( *p_incrementCharacter )
            if( p_character == 'Z' )
              p_character = 'A';
            else
            {
              p_character ++;
              *p_incrementCharacter = false;
            }
        }
        else
          *p_illegalCharacter = true;
      return p_character;
    }
    
    int main( const int argc, const char * const argv[] )
    {
      const size_t index =
      #ifdef LEONARDO
      0
      #else
      1
      #endif
      ;
      bool error_occurred = argc - 1 != index;
    
      #ifndef LEONARDO
      printf( "\n" );
      #endif
      if( !error_occurred )
      {
        char *odometer_reading = ( char* )malloc( sizeof( char ) * ( strlen( argv[ index ] ) + 1 ));
        size_t i = strlen( argv[ index ] );
        bool increment_character = true;
    
        strcpy( odometer_reading, argv[ index ] );
        for( ; ( i > 0 ) && !error_occurred; i -- )
          odometer_reading[ i - 1 ] = f_ProcessCharacter( odometer_reading[ i - 1 ], &increment_character, &error_occurred );
        if( !error_occurred )
          printf( "Incrementing the odometer reading \"%s\" results in the odometer reading \"%s\".\n", argv[ index ], odometer_reading );
        free( odometer_reading );
      }
      if( error_occurred )
        printf( "This program must be passed, via the command line, an odometer reading - viz., a string containing only digits and letters; this program will then increment that odometer reading.\n" );
      #ifndef LEONARDO
      printf( "\n" );
      #endif
      if( !error_occurred )
        exit( EXIT_SUCCESS );
      else
        exit( EXIT_FAILURE );
    }

    The solution is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) on both Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo IDE 3.4.1) and Mac OS X 10.4.11 (the solution compiled using the command line: gcc -c August\ 3rd,\ 2018.c; gcc August\ 3rd,\ 2018.o -o August\ 3rd,\ 2018).

    (I’m just trying to solve the problems posed by this ‘site whilst I try to get a job (and I’ve solved this problem in particular to test my understanding of compiling using the command line – an understanding that might be necessary if I’m to release an executable of my SDL2 joystick interrogator utility, or of my entry for Ludum Dare 5, for the Raspberry Pi); I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

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: