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.
Pages: 1 2
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>