Vampire number generator

Question

Inspired by Reddit r/dailyprogrammer

A vampire number v is a number v=xy with an even number n of digits formed by multiplying a pair of n/2-digit numbers (where the digits are taken from the original number in any order) x and y together. Pairs of trailing zeros are not allowed. If v is a vampire number, then x and y are called its "fangs." EDIT FOR CLARITY Vampire numbers were original 2 two-digit number (fangs) that multiplied to form a four digit number. We can extend this concept to an arbitrary number of two digit numbers. For this challenge we'll work with three two-digit numbers (the fangs) to create six digit numbers with the same property - we conserve the digits we have on both sides of the equation.

As always, looking for general feedback over code readability, structure and efficiency. But also I was looking to make the code a bit more flexible.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created on 6/29/2016.
 *
 * Inspired by r/dailyprogrammer
 * https://www.reddit.com/r/dailyprogrammer/comments/3moxid/20150928_challenge_234_easy_vampire_numbers/
 *
 */


public class VampireNumbers {

    /**
     * Calls generate function then displays return value.
     * @param args Not used in this application.
     */
    public static void main(String args[]){
        generate().forEach(System.out::println); // Generates vampires, displays them on screen.
    }

    /**
     * Generates list of vampire numbers. Currently only supports 3 fangs of length 2.
     * @return List of vampires generated along with their fangs.
     */
    private static List<String> generate(){
        ArrayList<String> vampires = new ArrayList<>();
        for (int i = 10; i < 100; i++) {
            String fangOne = String.valueOf(i);
            for (int j = i; j < 100; j++) {
                String fangTwo = String.valueOf(j);
                for (int k = j; k < 100; k++) {
                    String fangThree = String.valueOf(k);
                    String vampire = String.valueOf(i * j * k);
                    if (sortVampire(fangOne + fangTwo + fangThree).equals(sortVampire(vampire))){
                            vampires.add(String.format("%s * %s * %s = %s", fangOne, fangTwo, fangThree, vampire));
                    }
                }
            }
        }
        return vampires;
    }

    /**
     * Used to sort a string of numbers. Helpful when determining if all fangs
     * are within the generated vampire number.
     * @param vampire String of numbers
     * @return The sorted character list of the given string.
     */
    private static List<Character> sortVampire(String vampire){
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < vampire.length(); i++){
            list.add(vampire.charAt(i));
        }
        Collections.sort(list);
        return list;
    }
}

It works as of now but can only generate 3 fangs(of length 2) creating vampire numbers of length 6. Was looking to expand the parameters of the generate function to something like:

private static List<String> generate(int fangLength, int vampireLength)

Also I had a question over this line specifically:

if (sortVampire(fangOne + fangTwo + fangThree).equals(sortVampire(vampire)))

Instead of concatenating all three fangs, would it be worth it to use a StringBuilder in this scenario?

Answer 1

Also I had a question over this line specifically:

if (sortVampire(fangOne + fangTwo + fangThree).equals(sortVampire(vampire)))

Instead of concatenating all three fangs, would it be worth it to use a StringBuilder in this scenario?

Not in this case. The compiler is smart enough to replace the concatenation of the String with the use of a StringBuilder. Using a StringBuilder to create a String from multiple concatenation is typically useful when it is done inside a loop.

For 3 fangs of length 2, your code is straight-forward and will be performant. A couple of notes:

• There is a mathematical property that could be used to further improve performance. For bigger lengths, it can improve considerably the performance.
• To determine whether all of the fangs have the same digits as their product, you are currently creating a list of characters and sorting those lists to test for equality. You could do that in a simpler and faster way without sorting anything.

---

To support arbitrary vampireLength, i.e. an arbitrary count of numbers to multiply to make up the final vampire number, we can resort to a recursive algorithm. For that, we will define a method generate

List<String> generate(int fangLength, int vampireLength, int... previousNumbers)

It takes as input the fangLength (count of digits in each fang), the vampireLength (count of fangs) and the previousVampires (array of all the numbers considered so far). This previousNumbers will be sorted ascendingly by construction. It returns the list of all the solutions.

• The base case is when vampireLength is 0: it means that previousNumbers contains all the numbers to decide whether their product makes a vampire number. In this case, we perform the multiplication of all those numbers and compare the digits together: if they are the same then we can build the String representing the solution and return it in a singleton list; if they are not, we can return an empty list.
• In the recursive case, we need to loop over all the possible numbers. First, the upper bound to consider: with a count of digits fangLength to consider, the upper bound is simply \$10^{\text{fangLength}}\$. Then, the lower bound: if there were no previous numbers then it is 10 (the starting point); else it is the last considered previousNumbers (so the greater). For each of those possible numbers i, we concatenate all the solutions by invoking the generate method again, adding i to the previousNumbers.

A sample code would be:

private static List<String> generate(int fangLength, int vampireLength, int... previousNumbers) {
    if (vampireLength == 0) {
        int product = Arrays.stream(previousNumbers).reduce(1, (a, b) -> a * b);
        if (sameDigits(product, previousNumbers)) {
            String op = Arrays.stream(previousNumbers).mapToObj(String::valueOf).collect(Collectors.joining(" * "));
            return Collections.singletonList(op + " = " + product);
        }
        return Collections.emptyList();
    }
    List<String> list = new ArrayList<>();
    int end = (int) Math.pow(10, fangLength);
    int start = previousNumbers.length == 0 ? 10 : previousNumbers[previousNumbers.length - 1];
    for (int i = start; i < end; i++) {
        int[] currentVampires = Arrays.copyOf(previousNumbers, previousNumbers.length + 1);
        currentVampires[currentVampires.length - 1] = i;
        list.addAll(generate(fangLength, vampireLength - 1, currentVampires));
    }
    return list;
}

private static boolean sameDigits(int target, int... numbers) {
    int[] array = new int[10];
    Arrays.stream(numbers).flatMap(i -> String.valueOf(i).chars()).forEach(c -> array[c - '0']++);
    String.valueOf(target).chars().forEach(c -> array[c - '0']--);
    return Arrays.stream(array).allMatch(i -> i == 0);
}

Some notes in this code:

• It is using the Stream API to make the code more fluent: the product is calculated by reducing over the array of numbers and multiplying each of them together; the String solution is build by joining all the numbers, converted to a String, separated by " * ".
• The sameDigits method was rewritten to implement the simpler algorithm of checking whether the digits are the same.