Equivalent passwords ACPC 2014

Question

I am preparing for ACM-TCPC (Tunisia). So I started solving problems from past ACM-ACPC versions. But I got stuck in the Problem I from 2014.

The problem consists of finding the number of non-equivalent passwords in list of passwords. Two passwords, A and B, are equivalent if len(A) == len(B) and |A[i] -B[i]| is the same for i in [0..len(A)] (len is the length of the password and |x| is the absolute value of x).

Examples:

Input:

000
111
222

Output:

1

Input:

1111
123
214
2222

Output:

2

Input

43434
54545
45454

Output:

2

My code works fine and it solves the Judges I/O, However it takes a plentiful amount of time!

The code I wrote:

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;


public class Password {
    public static void main(String[] args){
        String[] str_tab ;
        HashMap<Integer, Integer> hm = null;
        List<String> l = null;
        try {
            int[] tab = null;
            BufferedReader br = new BufferedReader(new FileReader(new File("./password.in")));
            PrintWriter wr = new PrintWriter("./passwrd.out");
            int T = Integer.parseInt(br.readLine().toString());
            for (int i = 0; i < T; i++) {
                l = new ArrayList<String>();
                int N = Integer.parseInt(br.readLine().toString());
                for (int j = 0; j < N; j++) {
                    l.add(br.readLine().toString());
                }
                wr.println("Case "+(i+1)+": " +solve(l));
            }
            wr.close();

        }catch(Exception e){
            e.printStackTrace();
        }
}
    public static int solve(List<String> l){
        List<String> ls = new ArrayList<String>();
        ls.add(l.get(0));
        int j= 0;
        for (int i = 1; i < l.size(); i++) {
            j = 0;
            while(j<ls.size() && !isEq(l.get(i),ls.get(j))) j++;
            if(j == ls.size()) ls.add(l.get(i));
        }

        return ls.size();
    }
    public static boolean isEq(String p1, String p2){
        if(p1.length() != p2.length()) return false;
        int diff = Math.abs(p1.charAt(0) - p2.charAt(0));
        for (int i = 1; i <p1.length(); i++) {

            if(Math.abs(p1.charAt(i) - p2.charAt(i)) != diff){
                return false;
            }
        }
        return true;
    }
}

Did I get it wrong? Is there advice that could help me improve my code? (performance, organization or anything)

Answer 1

Lint

str_tab, hm, and tab are all unused variables.

In br.readLine().toString(), the .toString() is superfluous, as br.readLine() already returns a string.

In main(), the for (int i = 0; i < T; i++) loop would be better as for (int i = 1; i <= T; i++) so that you can avoid the (i+1).

Instead of catch (Exception e) { e.printStackTrace(); }, you could just declare main(String[] args) throws Exception. But what kind of exception? The code would be clearer if you narrowed it down to throws IOException. (It's also possible to get a NumberFormatException, but for a contest problem, I wouldn't bother handling it.)

Skeleton

I would use the following outline:

public class Password {

    public static class DistinctPasswordCounter {
        public DistinctPasswordCounter(Scanner in) {
            this.in = in;
            this.n = Integer.parseInt(in.nextLine());
            …
        }

        public int count() {
            while (this.n --> 0) {
                …
            }
            return …;
        }
    }

    public static void main(String[] args)
            throws FileNotFoundException, NoSuchElementException {
        try (Scanner in = new Scanner(new File("password.in"));
             PrintWriter out = new PrintWriter("password.out")) {
            int t = Integer.parseInt(in.nextLine());
            for (int i = 1; i <= t; i++) {
                DistinctPasswordCounter counter = new DistinctPasswordCounter(in);
                out.printf("Case %d: %d\n", i, counter.count());
            }
        }
    }
}

Notable improvements:

• password.out would be a more logical filename for the output.
• Use try-with-resources for AutoCloseable resources.
• Using Scanner instead of BufferedReader would let you not have to deal with IOException.
• Passing a Scanner instead of a List<String> lets each test case work on the fly as the input streams in.
• solve() doesn't really "solve". I'd pick a more descriptive name. Here, I've instantiated an object to represent each test case. (I think that a good solution requires more state than I would like to pack into a single function.) If the challenge had not required the program to be named Password, I would have just used DistinctPasswordCounter as the name of the class, and eliminated the inner class.

Strategy

Your solve() compares each password with every previously seen password, which makes it O(N²). It's not surprising that the solution is slow, considering that N is large (up to 10⁵).

Consider a different strategy: when you encounter a password, also note all possible variants of it. For example, if the password 31415 appears, then also register the variants 20304, 20306, 20324, 20326, etc.

How many variants would we be talking about? Given an original password, such as 31415, there would be…

• 31415 itself
• the ±1 variants: $${2 \choose 4}{0 \choose 2}{3 \choose 5}{0 \choose 2}{4 \choose 6}$$ … of which there are 2⁵: 20304, 20306, 20324, 20326, 20504, 20506, 20524, 20526, 22304, 22306, 22324, 22326, 22504, 22506, 22524, 22526, 40304, 40306, 40324, 40326, 40504, 40506, 40524, 40526, 42304, 42306, 42324, 42326, 42504, 42506, 42524, 42526.
• the ±2 variants: $${1 \choose 5}\left(3\right){2 \choose 6}\left(3\right){3 \choose 7}$$ … of which there are 2³: 13233, 13237, 13633, 13637, 53233, 53237, 53633, 53637.
• the ±3 variants: $${0 \choose 6}\left(4\right){1 \choose 7}\left(4\right){2 \choose 8}$$ … of which there are 2³: 04142, 04148, 04742, 04748, 64142, 64148, 64742, 64748.
• the ±4 variants: $$\left(7\right)\left(5\right){0 \choose 8}\left(5\right){1 \choose 9}$$ … of which there are 2²: 75051, 75059, 75851, 75859.
• the ±5 variants: $$\left(8\right)\left(6\right)\left(9\right)\left(6\right)\left(0\right)$$ … of which there is 1: 86960.

In the worst case, a password like 44444 or 55555 would generate 1+32+32+32+32+1 = 130 entries. If you stick them all in a HashSet with O(1) insertion and lookup time, then the solution would be O(130 N), which is much better than O(N²) for N ≫ 130.

In practice, there will probably be much fewer than 130 variants. For example, 31415 has just 54 variants. Passwords that are shorter or that have a wide distribution of digits would have fewer variants. Passwords that are equivalent to another password would generate no variants at all. (For large N, the proportion of passwords that are equivalent to an existing password should rise dramatically due to the Birthday Paradox.)

Suggested solution

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.HashSet;
import java.util.NoSuchElementException;

public class Password {

    public static class DistinctPasswordCounter {
        private final Scanner in;
        private final HashSet<String> seenPasswords;
        private int n, distinctCount;

        public DistinctPasswordCounter(Scanner in) {
            this.in = in;
            this.n = Integer.parseInt(in.nextLine());

            // 100 is a rough estimate of the number of variants
            // per password, based on (5 * Math.pow(2, maxLength)).
            // For very large n, it could probably be tuned lower
            // due to the Birthday Paradox.
            this.seenPasswords = new HashSet<>(100 * this.n);
        }

        public int count() {
            while (this.n --> 0) {
                String password = this.in.nextLine();
                if (this.seenPasswords.add(password)) {
                    // No variant of this password has been seen before
                    this.distinctCount++;
                    int variants = this.addVariants(password);
                    // System.err.printf("%3d variants of %s\n", variants + 1, password);
                }
            }
            return this.distinctCount;
        }

        private int addVariants(String password) {
            int diff = 0, variants = 0, v;
            while (0 < (v = this.addVariants(password, ++diff, 0))) {
                variants += v;
            }
            return variants;
        }

        private int addVariants(String password, int diff, int pos) {
            if (pos >= password.length()) {
                this.seenPasswords.add(password);
                return 1;
            }
            char c1 = (char)(password.charAt(pos) - diff),
                 c2 = (char)(password.charAt(pos) + diff);
            String head = password.substring(0, pos),
                   tail = password.substring(pos + 1);
            return (c1 < '0' ? 0 : this.addVariants(head + c1 + tail, diff, pos + 1)) +
                   (c2 > '9' ? 0 : this.addVariants(head + c2 + tail, diff, pos + 1));
        }
    }

    public static void main(String[] args)
            throws FileNotFoundException, NoSuchElementException {
        try (Scanner in = new Scanner(new File("password.in"));
             PrintWriter out = new PrintWriter("password.out")) {
            int t = Integer.parseInt(in.nextLine());
            for (int i = 1; i <= t; i++) {
                DistinctPasswordCounter counter = new DistinctPasswordCounter(in);
                out.printf("Case %d: %d\n", i, counter.count());
            }
        }
    }
}