19
\$\begingroup\$

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!

\$\endgroup\$
10
  • 2
    \$\begingroup\$ Could you clarify the exact problem definition? Does your code need to return the next increment for one given plate? Does it need to return all the increments? Or does it simply need to return all possible plates without input? \$\endgroup\$ Aug 19, 2021 at 14:07
  • 9
    \$\begingroup\$ Obligatory oneliner perl -E 'for $w ("AAA".."ZZZ") { printf "$w%04d\n", $_ for 1..9999 }' \$\endgroup\$
    – pipe
    Aug 19, 2021 at 19:31
  • 1
    \$\begingroup\$ @marcovtwout The code needs to generate ALL plates from AAA0001 to ZZZ9999. What you see in the question is my 99% of the code, where the magic happens. Everything else not here is just a simple loop getting whatever comes out from getIncrementedPlate() and passing it back to setPlate() for the next plate. This is the base of the idea the way I implemented. But in the back, there is a loop where it starts with setPlate(AAA0001) + getIncrementedPlate() alllll the way to if getIncrementedPlate() == ZZZ9999, stop. \$\endgroup\$
    – vianna77
    Aug 19, 2021 at 21:24
  • 1
    \$\begingroup\$ I also want to annoyingly suggest a one-line solution, in Ruby: ("AAA".."ZZZ").to_a.product(("0001".."9999").to_a).map(&:join) \$\endgroup\$ Aug 20, 2021 at 14:35
  • 2
    \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$
    – pacmaninbw
    Aug 21, 2021 at 15:37

8 Answers 8

42
\$\begingroup\$

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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Just as a comment, when I first wrote the draft of my code, it looked like yours solution above. Then I realized that when char b is increased by 1, char c needs to go back to 'A' or you will miss all the ABA, ABB, ABC... and so on. Same thing for when char a is increased... char b and char c needs to go back to A or else you will miss a bazilion of plates, like BAA, BAB.... The way you suggested locks the rightmost char into Z every time you reach Z for that char. \$\endgroup\$
    – vianna77
    Aug 19, 2021 at 21:30
  • 24
    \$\begingroup\$ @vianna77 I think you have a fundamental misunderstanding of how loops work. Each inner loop will restart when its parent loop increments. I suggest you try to code above with just the first two characters and watch how it creates all combinations from AA to ZZ. \$\endgroup\$
    – Turksarama
    Aug 19, 2021 at 22:40
  • 1
    \$\begingroup\$ @Turksarama thanks for pointed that out! :) It was great in more than one way. First, to remind me that I have to rest... I really could use some vacation. Also a good way to make me humble... when inner loops are such a challenging problem to solve, I really have to calm down :D \$\endgroup\$
    – vianna77
    Aug 19, 2021 at 22:53
  • 4
    \$\begingroup\$ @vianna77 if it helps at all, you have almost the exact right attitude to improve quickly - you're gonna make it. \$\endgroup\$ Aug 20, 2021 at 13:10
  • 1
    \$\begingroup\$ @vianna77: I thought more about the nested loop issue you faced, and you were not "fully" wrong. There are 2 kinds of nested loops: the rectangular kind (independent variables: outer from 0 to X and inner from 0 to Y) and the triangular kind (independent variables: outer from 0 to X and inner from outer to Y). Your comment makes me think your brain "locked in" on the triangular kind, and when that happens it's really hard to notice because your eyes glaze over the data as the brain goes "I know what I'm doing, move along". \$\endgroup\$ Aug 21, 2021 at 9:49
15
\$\begingroup\$

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.)

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Shouldn't your next throw a NoSuchElementException in case has_next is false after the if? \$\endgroup\$ Aug 19, 2021 at 15:41
  • \$\begingroup\$ @YanickSalzmann Good catch. I'll update when I'm at a computer. \$\endgroup\$
    – AJNeufeld
    Aug 19, 2021 at 15:52
  • \$\begingroup\$ To make it more general you could keep the sum of the digits, and at the end of the loop over the plate, if it’s still 0, you know you need to set the last digit to 1. \$\endgroup\$
    – Tim
    Aug 19, 2021 at 20:19
  • \$\begingroup\$ @AJNeufeld Responding to "Why are you using strings to store single characters?" When I received the values, it was a String with 3 chars and, as stated in the question, I was coding against time. First solution is pretty much permanent, like all "temporary solutions" in the world. Now I have time to think, so I'm improving the code. I will test your code this weekend, but the main issue is that working around the "reset middle and rightmost back to A" really boggled my mind because a bunch of plates went missing... and that plus skipping 0000 is a big part of the problem to solve. \$\endgroup\$
    – vianna77
    Aug 19, 2021 at 21:49
  • 6
    \$\begingroup\$ "You are using a sledge-hammer to crack a peanut." - so here's a much prettier sledge-hammer? \$\endgroup\$
    – AakashM
    Aug 20, 2021 at 9:41
12
\$\begingroup\$

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++);
  }
}
\$\endgroup\$
9
\$\begingroup\$

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).
\$\endgroup\$
1
  • \$\begingroup\$ Thanks... I was thinking about splitting the problem into 2. One part to deal with the letters and one to deal with the numbers. Many people suggested Iterator. Maybe just get the letters and append it to the current index that goes from 1 (formatted to 0001) to 9999? \$\endgroup\$
    – vianna77
    Aug 19, 2021 at 21:54
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ String.format("%s%04d", number, string); I'm certain you've got the arguments backwards (although to be fair, you did say "something like this", so I guess having the arguments in the correct order is technically something like it). \$\endgroup\$
    – AJNeufeld
    Aug 19, 2021 at 15:32
  • \$\begingroup\$ Oops :) I'll correct \$\endgroup\$
    – Joeblade
    Aug 25, 2021 at 9:51
4
\$\begingroup\$

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):

enter image description here

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();
\$\endgroup\$
10
  • \$\begingroup\$ The only issue I see with this approach is you are making the "skip 0000" requirement be part of the Clock's client code. Still, great explanation! \$\endgroup\$ Aug 19, 2021 at 12:27
  • \$\begingroup\$ @m-alorda: I assume must be misunderstanding your comment, because the skip logic is specifically not part of the clock logic, it is up to the consumer of the clock to decide to not do anything with the "0000" values that are being generated by the clock just like any other value. \$\endgroup\$
    – Flater
    Aug 19, 2021 at 16:35
  • 1
    \$\begingroup\$ my bad, I actually meant the requirement was NOT part of the Clock. From the stated problem, I believe it should be \$\endgroup\$ Aug 19, 2021 at 16:58
  • 2
    \$\begingroup\$ We can handle that by treating the four numeric positions as a single "digit", and giving them a custom class with a maxValue of 9998 and a PrintValue that adds 1 to that value before formatting it into four string digits. \$\endgroup\$ Aug 19, 2021 at 21:29
  • \$\begingroup\$ Why not use a loop to create the digits? \$\endgroup\$ Aug 20, 2021 at 1:10
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I think this approach is the most efficient. I would argue that you only need a single set of loops. If you need to increment and you are at Z reset to A, 9 resets to 0. And the check for 0000 could be outside the increment and just increment again...just my opinion. \$\endgroup\$
    – rtaft
    Aug 19, 2021 at 13:07
  • \$\begingroup\$ This would be stronger if you made an observation about the original code, as of course that is the actual requirement. We are reviewing the OP's code, not just writing our own. I.e. your explanation isn't a code review; it doesn't explain why your code is better than the OP's code. \$\endgroup\$
    – mdfst13
    Aug 19, 2021 at 14:09
0
\$\begingroup\$

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
        }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.