num_of_android_unlock_patterns.cc

/*
* @Author: Fang Zhang <thuzhf@gmail.com>
* @Date:   2016-09-24 16:03:32
*/

#include <iostream>

using namespace std;
using ull = unsigned long long;

int count_one(ull n) {
    int count = 0;
    while (n != 0) {
        ++count;
        n &= n - 1;
    }
    return count;
}

int main() {
    int N; // NxN unlock patterns
    cout << "Input N (corresponding to NxN unlock patterns): ";
    cin >> N;
    int N2 = N * N; // Square of N
    int all_comb = 1 << N2; // number of all points combinations

    ull** memo = new ull* [all_comb]; // to record number of unlock patterns of each different shape of points
    for (int i = 0; i < all_comb; ++i) {
        memo[i] = new ull [N2](); // stands for possible end points
    }
    for (int i = 0; i < N2; ++i) {
        memo[1 << i][i] = 1; // initial condition
    }

    // record the points on the line defined by two given points
    int** points_on_line = new int* [N2];
    int x1, y1, x2, y2, dx, dy, tmp;
    for (int i = 0; i < N2; ++i) {
        points_on_line[i] = new int [N2];
    }
    for (int i = 0; i < N2; ++i) {
        x1 = i % N;
        y1 = i / N;
        for (int j = i + 1; j < N2; ++j) {
            x2 = j % N;
            y2 = j / N;
            dx = x2 - x1;
            dy = y2 - y1;
            tmp = 0;
            if (dy == 0) {
                for (int l = i + 1; l < j; ++l) {
                    tmp += (1 << l);
                }
            } else {
                for (int k = y1 + 1; k < y2; ++k) {
                    if ((k - y1) * dx % dy == 0) {
                        int tmp2 = (k - y1) * dx / dy;
                        tmp += (1 << (N * k + tmp2 + x1));
                    }
                }
            }
            points_on_line[i][j] = points_on_line[j][i] = tmp;
        }
    }

    // DP
    ull* sum = new ull [N2 + 1](); // to record the sum of unlock patterns using k points, where 1 <= k <= N2.
    for (int s = 1; s < all_comb; ++s) { // s stands for one of different permutations of points
        for (int i = 0; i < N2; ++i) { // i stands for a possible end point
            if ((s & (1 << i)) == 0)
                continue;
            sum[count_one(s)] += memo[s][i];
            for (int j = 0; j < N2; ++j) { // j stands for next possible point
                if ((s & (1 << j)) != 0 || (s | points_on_line[i][j]) != s)
                    continue;
                memo[s | (1 << j)][j] += memo[s][i];
            }
        }
    }

    ull t = 0;
    for (int i = N2; i >= 1; --i) {
        t += sum[i];
        printf("using %d points: %llu; using >= %d points: %llu\n", i, sum[i], i, t);
    }

    return 0;
}