Brute-force ID reversal search

Question

EDIT

The random number generator in this code is a blackbox for a similar algorithm that isn't publishable for privacy concern. The algorithm works in similar way, in that it takes in a seed value and generates number.

Simplifying the question

The corrupted references are from a text file, there are thousands of those reference numbers. I'm tasked to create a program that will take in one reference from the text file, then brute force the algorithm through to find the seed that generated the number.

The generated numbers are in reversed, so just brute forcing will not get you the right number, you will have to reverse the brute number and check if it matches with the reference number, if yes then print the seed number and get the next reference number.

Since the seeds value are from 100 million to 999 million, we have to brute force through those to find the right seed value. it takes 4 minute to brute force a single reference number and I have hundreds of thousands of the numbers to go through. How can I make it super fast?

I tried putting the references in arraylist on first load since it's just 900 million list of reference and then use indexOF, but it gives me outofmemory error.

Product Version: Apache NetBeans IDE 9.0 (Build incubator-netbeans-release-334-on-20180708)

Java: 11.0.1; Java HotSpot(TM) 64-Bit Server VM 11.0.1+13-LTS

Runtime: Java(TM) SE Runtime Environment 11.0.1+13-LTS

System: Mac OS X version 10.13.6 running on x86_64; UTF-8; en_GB (nb)

import java.io.FileNotFoundException;
import java.io.UnsupportedEncodingException;
import java.util.Random;
import java.util.ArrayList;
/**
 *
 * @author HJoe
 */
public class idResolver {

    /**
     * @param args
     * @throws java.io.FileNotFoundException
     * @throws java.io.UnsupportedEncodingException
     */
    public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {
    ArrayList corruptedReferences = new ArrayList();
    Stream<String> lines = Files.lines(Paths.get("/Users/kingamada/Documents/Corrupted References.txt"));
    lines.forEach(l -> {
        corruptedReferences.add(l);
    });
        StringBuilder sb = new StringBuilder();
        int max = 1000000000;
        int min = 100000000;
        long nano_startTime = System.nanoTime();
        long millis_startTime = System.currentTimeMillis();
        for (int i = 0; i < corruptedReferences.size(); i++) {
            long corruptIDNumbers =corruptedReferences.get(i);
            for (int n = min; n < max; n++) {
                Random rand = new Random(n);
                long findID = rand.nextLong();
                sb.append(findID);
                //String reverseID = reverse(String.valueOf(findID));
                findID = Long.valueOf(sb.reverse().toString().substring(0, 9));
                if (findID == corruptIDNumbers) {
                    //System.out.println("Found the ID:  "+n);
                    break;
                }
                sb.setLength(0);

            }
            long nano_endTime = System.nanoTime();
            long millis_endTime = System.currentTimeMillis();

            System.out.println("Time taken in nano seconds: "
                + (nano_endTime - nano_startTime));
            System.out.println("Time taken in milli seconds: "
                + (millis_endTime - millis_startTime));

        }
    }

    public static String reverse(String input) {
        char[] in = input.toCharArray();
        int begin = 0;
        int end = in.length - 1;
        char temp;
        while (end > begin) {
            temp = in[begin];
            in[begin] = in[end];
            in[end] = temp;
            end--;
            begin++;
        }
        return new String(in);
    }

    public static long reverseID(Long idNumber) {
        String s = String.valueOf(idNumber);
        StringBuilder sb = new StringBuilder();
        for (int n = 0; n < s.length(); n++) {
            sb.append(s.charAt((s.length() - n) - 1));
        }
        s = sb.toString();
        long reversedNumber = Long.valueOf(s);
        return reversedNumber;

    }
}

Answer 1

The first and easiest option is to turn your loops inside-out. In your inner loop, you reverse the corrupt numbers. That shouldn't even be done in your main loop - just do it once, making a reversedIDs after initializing your corruptIDNumbers.

Your for (int i = 0; i < 1; i++) doesn't make a lot of sense, and is probably just you manually truncating the program due to the runtime. But it should go away completely. Instead, make a HashSet containing your reversedIDs, and do not iterate over this set. On every randomly generated number, test to see if the generated number is a member of the set.

Another important thing to do, since your brute-force approach is CPU-bound and highly parallelizable, is to multi-thread. Here is a suggested multi-threaded brute-force approach that completes for me in 5 seconds.

You'll of course want to change the number of workers to suit your CPU.

import java.io.FileInputStream;
import java.io.IOException;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;


public class IDResolver implements AutoCloseable {
    // This class is intended to be instantiated. main() is a thin entry point.

    // The set of all IDs as read from the file. Modern RAM capacity will easily
    // fit hundreds of thousands of IDs at once.
    private final Set<Long> ids = new HashSet<>();

    // The number of threads to run. Do not increase this beyond the hyperthread
    // capacity of your CPU or you will see steeply diminishing returns.
    private final int nworkers = 8;

    // The array of all Thread worker objects.
    private final Worker[] workers = new Worker[nworkers];

    // The upper and lower bound of the seed search space.
    private final long seedMin = 100_000_000,
                       seedMax = 1_000_000_000;

    // The constructor; accepts the name of the file containing IDs, one per
    // line.
    public IDResolver(String filename) throws IOException {
        populate(filename);

        // The start of each worker's seed search space; computed incrementally.
        long start = seedMin;

        System.out.println("Workers:");

        // Loop to create each worker and print its summary.
        for (int w = 0; w < nworkers; w++) {
            long end;
            if (w == nworkers-1)
                end = seedMax;
             else
                end = (seedMax - seedMin)*(w + 1)/nworkers + seedMin;

            workers[w] = new Worker(w, w==nworkers-1, start, end);
            System.out.println(workers[w]);
            start = end;
        }
        System.out.println();
    }

    // Populate the ID set from the ID file. Each ID is string-reversed before
    // being added to the set.
    private void populate(String filename) throws IOException {
        try (var stream = new FileInputStream(filename);
             var scanner = new Scanner(stream)) {
             var sb = new StringBuilder();

             while (true) {
                String line;
                try {
                    line = scanner.nextLine();
                } catch (NoSuchElementException e) {
                    break;
                }
                sb.append(line);
                long id = Long.valueOf(sb.reverse().toString());
                ids.add(id);
                sb.setLength(0);
             }
        }
    }

    // Entry point for the program. This program accepts one argument, the ID
    // file name.
    public static void main(String[] args) throws Exception {
        try (var resolver = new IDResolver(args[0])) {
            resolver.resolve();
            resolver.join();
        }
    }

    // Resolve all IDs by starting the worker threads.
    public void resolve() {
        for (Worker w: workers)
            w.start();
    }

    // Wait until all of the worker threads are done.
    public void join() throws InterruptedException {
        for (Worker w: workers)
            w.join();
    }

    // When this class is used as an AutoCloseable within a try-with-resources,
    // and close() is called, cancel the worker threads.
    public void close() throws InterruptedException {
        for (Worker w: workers) {
            w.cancel();
            w.join();
        }
    }

    // This is the "black box" function that needs to be replaced with your own.
    // It accepts a seed and returns an ID.
    private static long transform(long seed) {
        // todo: replace me
        var rand = new Random(seed);
        return rand.nextLong();
    }

    // The worker thread class. This supports all of the methods of Thread,
    // notably start().
    private class Worker extends Thread {
        // This is used to control the frequency of progress updates. Change the
        // 24, increasing it for slower updates.
        final long updateMask = (1L << 24) - 1;

        final int worker; // The worker's ID
        final long start; // The start of this worker's seed range
        long end; // The (exclusive) end of this worker's seed range
        final boolean last; // Whether this is the last worker

        public Worker(int worker, boolean last, long start, long end) {
            this.worker = worker;
            this.last = last;
            this.start = start;
            this.end = end;
        }

        // Used to show a summary of this worker
        @Override
        public String toString() {
            return String.format("ID=%d range %10d - %10d", worker, start, end);
        }

        // Show progress - only used on the last worker
        private void tick(long seed) {
            if (last) {
                System.out.print(String.format(
                    "seed=%,d/%,d %.2f%%\r", seed, end,
                    (seed - start)*100. / (end - start)
                ));
            }
        }

        // The worker thread routine.
        public void run() {
            // Loop through all seeds for this worker.
            for (long seed = start; seed < end; seed++) {
                // The candidate ID, as transformed from the current seed.
                long id = transform(seed);
                // Does this candidate ID exist in the set of all known IDs from
                // the file?
                if (ids.contains(id))
                    // If so, print the seed and the ID that it produced.
                    System.out.println(String.format(
                        "seed=%d id=%d", seed, id));
                // Show progress.
                if ((seed&updateMask) == 0)
                    tick(seed);
            }

            tick(end);
            if (last)
                System.out.println();
        }

        // Cancel this worker by setting its seed range end to zero.
        public void cancel() {
            end = 0;
        }
    }
}

Invocation and output:

$ javac IDResolver.java && time java IDResolver corrupted.txt 
Workers:
ID=0 range  100000000 -  212500000
ID=1 range  212500000 -  325000000
ID=2 range  325000000 -  437500000
ID=3 range  437500000 -  550000000
ID=4 range  550000000 -  662500000
ID=5 range  662500000 -  775000000
ID=6 range  775000000 -  887500000
ID=7 range  887500000 - 1000000000

seed=1,000,000,000/1,000,000,000 100.00%

real    0m4.784s
user    0m36.266s
sys 0m0.308s

Answer 2

A couple of things that might help:

To reverse a number, it is more efficient to use math instead of converting the number to a string first. Something like this should work:

public static long reverseID(Long idNumber){
    Long retVal = 0l;
    while(idNumber > 0){
        retVal = (retVal * 10) + (idNumber % 10);
        input /= 10;
    }
    return retVal;
}

Also you can simplify, and possibly make more efficient, the reverse method by using the StringBuilder.reverse() method:

public static String revString(String input){
    return new StringBuilder(input).reverse().toString();
}