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.
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"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:
Python
Because everything is better with a regular expression. ;-)
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.
@ProgrammingPraxis: Submitted version for Mumps. Haven’t seen it.
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>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 # A0AA00Here’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:
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 :/ )