The car plate problem: generate from AAA0001 to ZZZ9999 skipping the 0000

Question

I was given the problem (called "car plate problem") to write all the values that go from AAA0001 to ZZZ9999 with the following premises:

1. Create all the possibilities from AAA0001 to ZZZ9999;
2. Skip all the 0000, ie: AAB0000, AAC0000... ZZZ0000.
3. No repetitions. Once a value is "created" or "found", whatever, the value cannot repeat. So, once your code generated the AAA0002, it shouldn't generate the AAA0002 again.

So... I found a solution (posted below). It was "short" and "oh boy" it was weak! But I was coding against time so I had to go with that solution. I recognize the solution lacks creativity, better use of O.O. and probably there is a design pattern to be use here. None I could identify but still, there must be a better way to make it work. Is there a solution with better code quality and (if possible) less processing?

public class PlateIncrement {
private String plate;
public PlateIncrement () {
}

public void setPlate(String thePlate) {
    plate = thePlate;
} 

public String getIncrementedPlate() {
    String finalNumber = "";
    String finalLetters = "";
    String letters = plate.substring(0,3);
    String numbers = plate.substring(3,7);
    letters = letters.toUpperCase();
    if (Integer.parseInt(numbers) != 9999) {
        finalNumber = incrementNumber(numbers);
        finalLetters = letters;
    } else {
        finalLetters = getIncrementedLetters(letters);
        finalNumber = "0001";
    }
    return finalLetters.concat(finalNumber);
}

private String getIncrementedLetters(String letters) {
    String[] splittedLetters =  letters.split("");
    if( !splittedLetters[2].equalsIgnoreCase("Z") ) {
        incrementLetter(splittedLetters, 2);
    } else if( !splittedLetters[1].equalsIgnoreCase("Z") ) {
        incrementLetter(splittedLetters, 1);
        splittedLetters[2] = "A";
    } else if( !splittedLetters[0].equalsIgnoreCase("Z") ) {
        incrementLetter(splittedLetters, 0);
        splittedLetters[2] = "A";
        splittedLetters[1] = "A";
    }
    return String.join("", splittedLetters);
}

private void incrementLetter(String[] splittedLetters, int i) {
    char theChar = splittedLetters[i].charAt(0);
    char incrementedChar = (char) (theChar + 1);
    splittedLetters[i] = String.valueOf(incrementedChar);
}

private String incrementNumber(String numbers) {
    int number = Integer.parseInt(numbers);
    number += 1;
    String value = String.format("%04d", number);
    return value;
}
}

So I pass the value to setPlate(), get the "next plate" from getIncrementedPlate() and that value is passed again to setPlate() to generate the next plate.

It works. But it takes a lifetime (from AAA0001 to AAB0001 takes 49 seconds!), consumes 100% of all the processors and as I mentioned before, lacks quality.

Could anyone point how to improve it or show me a better improved version?

My current idea to improve the code:

1. Change the entity to have 3 chars, each representing each letter. The entity getPlate will concatenate the chars with the numbers when the getPlate is called.
2. This "PlateIncrement" class will be changed to receive the entity instead of the String. When I request the "nextPlate()", it will know how to properly increment the chars from the entity.
3. I will hold all the possible numbers in-memory. It will be 0,32MB for all the numbers, so it will be ultra cheap.

All suggestions for improvement are welcome!

Answer 1

You correctly identified that your algorithm is a bit too complicated, so let's start from scratch.

The problem statement is, at its core, to iterate from AAA0001 to ZZZ9999.

You should note that the license plate is divided in 2 parts:

• The letters, which will iterate from AAA to ZZZ.
• The digits, which will iterate from 0001 to 9999, for each combination of letters.

So, to start with, let's imagine that the requirement is to print the license plates. The simplest answer possible is nested loops:

class LicensePlateEnumerator {
    public static void main(String[] args) {
        for (char a = 'A'; a <= 'Z'; ++a) {
            for (char b = 'A'; b <= 'Z'; ++b) {
                for (char c = 'A'; c <= 'Z'; ++c) {
                    for (int i = 1; i < 10000; ++i) {
                        String plate = String.format("%c%c%c%04d", a, b, c, i);
                        System.out.println(plate);
                    }
                }
            }
        }
    }
}

That is the core algorithm, and it answers the question from an algorithmic perspective.

Now, consuming its output is maybe not that easy, so you should consider some way of:

1. Expressing the output: String? LicensePlate?
2. Passing the output to the caller: Iterator<?>? Stream<?>? Taking a Consumer<?> parameter?

Depending on your own affinities, you may favor some alternatives over others. Or whoever asked the question may.

The key, though, is to first work out the algorithm without worrying about the "packaging". Once you have the algorithm, you have a foundation you can build upon.

Answer 2

You are using a sledge-hammer to crack a peanut.

Consider String[] splittedLetters = letters.split("");. The split() function takes a regular expression, so you are using the entire regular expression engine to split a string into an array of single character strings. You don't need regular expression here; the overhead of regular expressions is huge!

Allow me to repeat: single character strings. Why are you using strings to store single characters? Java has a char primitive type for storing characters. Moreover, there is a cheap function which turns a string into an array of characters: .toCharArray(). If you use that, you'll be dealing with a fraction of the number of heap-allocated objects, which will ease the burden on the garbage collector, plus all other manner of speed improvements.

Reinderien has the right idea. Implement an Iterable class, which can return an Iterator. Furthermore, instead of splitting a string into tiny single character chunks, and reassembling a new plate, you should use a StringBuilder object, which will allow you to efficiently mutate a string-like buffer to create new strings.

---

Improved code:

import java.util.Iterator;

public class Plates implements Iterable<String> {
    
    private final String initial_plate;
    
    public Plates(String first_plate) {
        initial_plate = first_plate;
    }
    
    @Override
    public Iterator<String> iterator() {
        return new PlateIterator(initial_plate);
    }
    
    private static class PlateIterator implements Iterator<String> {
        private final int plate_length;
        private final StringBuilder plate;
        private boolean has_next = true;
        private boolean need_next = false;
        
        PlateIterator(String first_plate) {
            plate_length = first_plate.length();
            plate = new StringBuilder(plate_length);
            plate.append(first_plate);
            has_next = true;
            need_next = false;
        }
    
        private void advance() {
            need_next = false;
            has_next = false;
            for (int i = plate_length - 1; i >= 0; i--) {
                char ch = plate.charAt(i);
                if (ch == '9')
                    plate.setCharAt(i, '0');
                else if (ch == 'Z')
                    plate.setCharAt(i,  'A');
                else {
                    plate.setCharAt(i, (char) (ch + 1));
                    has_next = true;
                    break;
                }
            }
            if (plate.substring(plate_length - 4).equals("0000"))
                plate.setCharAt(plate_length - 1, '1');
        }
    
        @Override
        public boolean hasNext() {
            if (has_next && need_next)
                advance();
            return has_next;
        }
    
        @Override
        public String next() {
            if (need_next)
                advance();
            need_next = true;
            return plate.toString();
        }
    }

    public static void main(String[] args) {
        Plates plates = new Plates("AAA0001");
        for(String plate : plates) {
            // System.out.println(plate);
        }
    }
}

Run time: 5 seconds

---

It may not be obvious, so I'll point out that in the above implementation, the initial license plate letters/numbers controls the pattern of license plates that are generated.

For instance, given "A0", it would generate up to "Z9" (a total of 260 plates). Given "00AAA00" it would generate all the plates up to "99ZZZ99". (The "skip plates ending in 0000" code only functions properly if the license plate pattern ends in 4 digits; you'd have to modify the code to make it more general, if desired.)

Answer 3

There is no need for any OO in this topic, and design patterns are totally out of scope for this. Your program is a little complex and could deserve some simplicity.

I believe that simplicity is always better, and what is simpler in your case than mapping a number to a license plate and simply increase your number to get the next one?

Basically, as everybody discovered, there is a limited amount of license plates within the rules you set: 26 * 26 * 26 * 9999 = 175742424.

The only question is how to go from a simple number to the expected mapped license plate. As usual, there are various way to do so.

I suggest here one such way that will allow with simple loop to generate all of your license plates in logical order of the license plate.

  private static final int MIN_PLATE_SEQUENCE = 0;
  private static final int MAX_PLATE_SEQUENCE = 9999 * 26 * 26 * 26 - 1;

  static String licensePlateForSequence(int sequence) {
    if (sequence < MIN_PLATE_SEQUENCE || sequence > MAX_PLATE_SEQUENCE) {
      throw new IllegalArgumentException("sequence " + sequence + " would generate an invalid plate");
    }
    
    int digits = sequence % 9999 + 1; // digits will always be between 1 and 9999.
    sequence /= 9999;

    char[] letters = new char[3];
    for (int i = 2; i >= 0; i--) {
      letters[i] = (char)('A' + sequence % 26);
      sequence /= 26;
    }
    
    return String.format("%s%04d", new String(letters), digits);
  }

And now, you can have a controller that calls any number with values between MIN_PLACE_SEQUENCE and MAX_PLACE_SEQUENCE (all inclusive), and just retrieve the appropriate license plate:

For instance, you could go for all of them:

  public static void main(String[] args) {
    for (int seq = MIN_PLATE_SEQUENCE; seq <= MAX_PLATE_SEQUENCE; seq++) {
      System.out.println(licensePlateForSequence(seq));
    }
  }

Or you could fetch directly the values around some boundaries, just to check that everything works fine:

  public static void main(String[] args) {
    int[] interestingSequences = {
      0,                       // AAA0001
      9998,                    // AAA9999
      9999,                    // AAB0001
      9999 * 26 - 1,           // AAZ9999
      9999 * 26,               // ABA0001
      9999 * 26 * 26 - 1,      // AZZ9999
      9999 * 26 * 26,          // BAA0001
      9999 * 26 * 26 * 26 - 1, // ZZZ9999
    };
    for (int plateId: interestingSequences) {
      System.out.println(licensePlateForSequence(plateId));
    }
  }

Creating a stream is now extremely easy!

Stream<String> allPlates = IntStream.range(0, MAX_PLATE_SEQUENCE + 1)
    .mapToObj(Main::licensePlateForSequence);

And an iterator isn't really hard as well!

class LicensePlateIterator implements Iterator<String> {
  private int sequence = MIN_PLATE_SEQUENCE;
  @Override public boolean hasNext() {
    return sequence <= MAX_PLATE_SEQUENCE;
  }
  @Override public String next() {
    if (!hasNext()) throw new NoSuchElementException();
    String plate = licensePlateForSequence(sequence);
    sequence++;
    return plate;
    // Or the one-liner
    // return licensePlateForSequence(sequence++);
  }
}

Answer 4

Your problem statement is to create all of the possibilities, not necessarily to support increment from an existing possibility. The difference is very important. It's slow to parse out a position in the license plate space, increment it and format it again.

Instead, consider

• overriding the Iterator interface,
• keeping state on the instance that remembers where in the iteration you are, and
• do the cheap increment (the number suffix) 10,000 times more frequently than the expensive increment (the letter prefix).

Answer 5

I think the first thing I would say is:

the data you keep internally doesn't have to be the same as the data you give out.

In this case you are working on the full String of the car plate and you have to break it apart to increment it. You could just as easily keep it split internally:

int numberPart = 1;
char[] stringPart = { 'A', 'A', 'A' }; 

that would let you change the individual characters directly.

when forming this into the final output you can use something like:

String.format("%s%04d", string, number); 

to generate the final string in 1 go.

keeping the data in an intermediate form makes your code a lot easier to change at a later day. And often this is something you'll do in the future. the format your client expects is not the format it is kept in the database or in code.

this can work even when you get your data delivered using setPlate. when setPlate is called, transform the data into your internal form.

I would also keep track of your starting point. (so if setPlate is called with XXX2345 , I would keep this XXX2345 and let hasNext check if that value will be the value returned. you can do this by letting next return the value (and already computing what will be the next value)

so in pseudocode, please don't use this bad method/variable names if you try this

String startValue;
public void setPlate(String plate) {
    startValue = plate;
    splitIntoParts(plate);
}

String nextValue;
public String next() {
    String result = nextValue;
    nextValue = calculateNext();
    return result;
}

this allows you to have

public boolean hasNext() {
    return !startValue.equals(nextValue);
}

Of course it would work better if you made Plate into a class and use equals on it rather than on the string representation of it but I'm trying to keep each suggestion/option separate from any other suggestions.

Answer 6

I'm no Java dev, so my snippets use C#, but this should be easily translateable and the focus of this answer is on the class design rather than the specific syntax.

Note also that I opted for code that is as readable as possible, rather than tersely efficient. You can squeeze some more performance out of this by refactoring, but the main goal of this answer was to showcase the idea behind the design.

---

"Computer" is a word meaning "calculator". The reason I'm mentioning this is because computers are fast at math, but (relatively) slow at other things such as text processing. Breaking the calculation down to simpler mathematics will significantly boost processing speed.

Your code is written from your point of view on how words can be broken down in letters and put back together. But this is not the most efficient way to think about it in terms of CPU requirements. If we boil it down to a much more mathematical construct, we will be able to leverage the things that the CPU is very good and efficient at.

Let's look at another way of looking at it, the flip clock (click for animated gif):

How does a flip clock work? Well, the rightmost digit increments. When the rightmost digit cycles back to 0, it tells its neighbor to increment once. The process repeats, and eventually the second-to-last digit will also cycle back to 0, at which point it tells its neighbor (the third from the right digit) to increment.

It's interesting to note here that this doesn't have to use all 10 digits. In a clock, the second-to-last digit only cycles from 0 to 5, because there is no 60th second in a minute.
This means that we can use an arbitrary amount of values in a given digit, for example 26, just like how many letters there are in the alphabet.

The snippet I'll show here is effectively going to rebuild that flip clock in code.

The digit

First, we'll look at an individual digit. We need to define how many values it can cycle across, and we need to tell it who its neighbor is, so that it can tell the neighbor to increment.

Forget about letters. We're only going to use numbers. In the end, we will translate a number value to a given letter character, but only after we've done the calculations.

public abstract class FlipDigit
{
    private readonly int maxValue;
    private readonly FlipDigit neighbor;

    protected int currentValue;

    public FlipDigit(int maxValue, FlipDigit neighbor)
    {
        this.maxValue = maxValue;
        this.neighbor = neighbor;
        this.currentValue = 0;
    }

    public void Increment()
    {
        // Simple +1 increment
        this.currentValue = this.currentValue + 1;

        // If max is reached, cycle back to 0
        if(this.currentValue > this.maxValue)
        {
            this.currentValue = 0;
            
            // If there is a neighbor, increment it.
            if(this.neighbor != null)
                this.neighbor.Increment();
        }
    }

    // Ignore for now
    public abstract string PrintValue();
}

This is really just the code equivalent of how I described how each digit in a flip clock works.

We need to make some subclasses here. The logic works as is, but some digits will need to be printed as numbers, and others as letters. In the above snippet, I already prepared for this by adding the abstract PrintValue method. Our derived classes are only going to implement logic on how to print the correct value. The counting logic itself remains untouched.

public class NumberDigit : FlipDigit
{
    public NumberDigit(FlipDigit neighbor) 
        : base(9, neighbor) 
    {

    }

    public override string PrintValue()
    {
        return this.currentValue.ToString();
    }
}

public class LetterDigit : FlipDigit
{
    private char[] letters = new char[26] { 'A', 'B', 'C', ..., 'Z' };

    public LetterDigit (FlipDigit neighbor) 
        : base(25, neighbor) 
    {

    }

    public override string PrintValue()
    {
        return letters[this.currentValue].ToString();
    }
}

Notice how we've hardcoded the max values (9 for numbers, 25 for letters) in the classes themselves. Maybe you want to change that if you want more custom ranges like that 0-5 digit in a real clock, but for your current case this full range suffices.

The clock

Now, we're going to create a clock, which is effectively a group of connected flip digits. I know that you'll be calling this class LicensePlate, but I'm going to stick with Clock for now to stay close to the analogy.

public class Clock
{
    private List<FlipDigit> digits;
    private FlipDigit lastDigit;

    public Clock()
    {
        this.Digits = new List<FlipDigit>();

        GenerateDigits();
    }

    private void GenerateDigits()
    {
        // Digit 1 is a letter and has no neighbor to the left
        var digit1 = new LetterDigit(null);
        digits.Add(digit1);

        // Digit 2 is a letter and has digit 1 as a neighbor
        var digit2 = new LetterDigit(digit1);
        digits.Add(digit2);

        // And so on...
        var digit3 = new LetterDigit(digit2);
        digits.Add(digit3);

        var digit4 = new NumberDigit(digit3);
        digits.Add(digit4);

        var digit5 = new NumberDigit(digit4);
        digits.Add(digit5);

        var digit6 = new NumberDigit(digit5);
        digits.Add(digit6);

        var digit7 = new NumberDigit(digit6);
        digits.Add(digit7);

        // Digit 7 is also separately kept as a reference
        this.lastDigit = digit7;
    }

    public string GetNext()
    {
        // This will set off a chain of flipping digits when needed
        this.lastDigit.Increment();

        // Now we generate our output based on our list
        var values = this.digits.Select(digit => digit.PrintValue()).ToArray(); 
        var combinedValue = String.Join("", values);

        return combinedValue
    }
}

Using the clock

We've now built a fully working clock. Its usage is very straightforward:

var clock = new Clock();

for(int i = 0; i < 1000000; i++)
{
    var value = clock.GetNext();
    
    if(!value.EndsWith("0000"))
        Console.WriteLine(value);
}

If you want to prevent the entire clock rolling back to its start position, you could throw a custom exception when you've reached the end of the FlipDigit which has no neighbor:

// If there is a neighbor, increment it.
if(this.neighbor != null)
    this.neighbor.Increment();
else
    throw new ClockOutOfRangeException();

Answer 7

In my answer, I will only suggest an efficiency improvement to the iterator:

import java.util.Iterator;
import java.util.NoSuchElementException;

public final class PlateNumberIterable implements Iterable<String> {

    @Override
    public Iterator<String> iterator() {
        return new PlateNumberIterator();
    }

    private static final class PlateNumberIterator implements Iterator<String> {

        private static final int NUMBER_OF_ALL_CANDIDATE_PLATE_NUMBERS = 
                26 * 26 * 26 * 10_000;

        private static final int NUMBER_OF_ALL_SKIPPED_PLATE_NUMBERS = 
                26 * 26 * 26;

        private static final int NUMBER_OF_TOTAL_LEGAL_PLATE_NUMBERS = 
                NUMBER_OF_ALL_CANDIDATE_PLATE_NUMBERS - 
                NUMBER_OF_ALL_SKIPPED_PLATE_NUMBERS; 

        private int numberOfIteratedPlates = 0;

        private final char[] chars = 
                new char[]{ 'A', 'A', 'A', '0', '0', '0', '1' };

        @Override
        public boolean hasNext() {
            return numberOfIteratedPlates < NUMBER_OF_TOTAL_LEGAL_PLATE_NUMBERS;
        }

        @Override
        public String next() {
            if (!hasNext()) {
                throw new NoSuchElementException("Iterator exhausted.");
            }

            numberOfIteratedPlates++;
            String result = new String(chars);
            incrementPlateNumber();
            return result;
        }

        private void incrementPlateNumber() {
            for (int i = 6; i >= 3; i--) {
                if (chars[i] < '9') {
                    chars[i]++;

                    for (int j = i + 1; j < 7; j++) {
                        chars[j] = '0';
                    }

                    return;
                }
            }

            chars[3] =
            chars[4] =
            chars[5] = '0';
            chars[6] = '1';

            for (int i = 2; i >= 0; i--) {
                if (chars[i] < 'Z') {
                    chars[i]++;

                    for (int j = i + 1; j < 3; j++) {
                        chars[j] = 'A';
                    }

                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        int coderoddePlates = 0;
        long start = System.currentTimeMillis();

        for (String plateNumber : new PlateNumberIterable()) {
            coderoddePlates++;
        }

        long end = System.currentTimeMillis();

        System.out.println("coderodde iterable computation time: " + 
                (end - start) + " ms.");

        int AJNeufeldPlates = 0;
        start = System.currentTimeMillis();

        for (String plateNumber : new Plates("AAA0001")) {
            AJNeufeldPlates++;
        }

        end = System.currentTimeMillis();

        System.out.println("AJNeufeld iterable computation time: " +
                (end - start) + " ms.");

        System.out.println("coderodde iterable produced " + coderoddePlates +
                " plates.");

        System.out.println("AJNeufeld iterable produced " + AJNeufeldPlates +
                " plates.");
    }
}

(See this gist for the entire comparison program.)

The performance figures are something like that:

coderodde iterable computation time: 1513 ms.
AJNeufeld iterable computation time: 5086 ms.
coderodde iterable produced 175742424 plates.
AJNeufeld iterable produced 175742424 plates.

The idea is to increment the rightmost character. If it’s already at its maximum value, set it to the minimum value and proceed to the character one step to the left from it. If the new character may be incremented, do that and halt. In case that 2nd character is at its maximum, keep going until a new valid plate number is found. Of course, we need to exclude from consideration every plate number ending in 4 zeros.

Answer 8

We know that there are 9999*26**3 possible license plates, so one strategy would be to just generate that many integers, and then translate each integer to a license plate. I don't work with Java much, so there are likely syntax errors, but this should give the gist of it:

private int num_plates = 9999*26**3;
for (int i = 0; i < num_plates; i++) {
        int digits = i%9999+1;
        int remain = (i-digits)/9999;
        int char_n1 = remain%26;
        remain = (remain-char_n1)/26;
        int char_n2 = remain%26;
        int char_n3 = (remain-char_n2)/26;
        String letters = String.fromCharCode(65+char_1, 65+char_n2, 65+char_n3);
        String plate = letters.concat(digits.to_string);
        //output plate to console or store in array
        }