Revisit 一道应聘智力题的编程求解, Einstein puzzle

Another brain teaser, titled 一道应聘智力题的编程求解 , http://www.iteye.com/topic/608112 .

 

This is the Einsten's puzzle. There are a few variations but the puzzle is the same.

 

The consensus is that the brutal force way of looping through all possibilities is taking a long time, if not impossible. Since I did some coding on Taxas Hold'em poker game with brutal force, this puzzle is easier to a certain extent. So here is my brutal force results.

 

If I am not pre-calculate any result, just apply all rules to each possibility,

 

time=2021546 milliseconds
count=24883200000
speed=12308 / millisecond

 

The total cases is (5!)^5 = 120^5 = 24883200000. So the total time is about <40 minutes.

 

If I use only the rules 1, 2, 3, 9, and 13 to set the attributes, the result is acceptably fast:

 

time=750 millisecond
count=7962624
speed=10616 / millisecond

 

The total cases is 7962624 = (4!)^5 = 24^5.

 

In both cases, there is only 1 solution found. However, there is a twist: The rule #4 is 绿房子在白房子左边, this translation from English is skeptical. It should be the greenhouse is the left neighbour of the whitehouse, meaning they are next to each other. Plainly saying 绿房子在白房子左边 could result the case where they are not neighbours.

 

I am using Intel Duo Core, 2.66 GHZ, windows xp machine, several years old.

 

Now let's look at the code. For performance reason, we need to tightly design the game states. The person state is defined as an integer, as shown in the picture. Starting from nationality, each bit is for one country, if the bit is 1, then the person is of this nationality; if the bit is 0, he is not. Similarly, we define all possibilites. There are 6 attributes, each has 5 possibilities, so totally there are 30 bits, and thus we can fit this into an integer. The reason we choose this layout because later on we could use bit operations for rules.

 

So the first class is

/**
 * There are 6 attributes:
 *      nationality
 *      house color
 *      house location
 *      pet
 *      drink
 *      cigaratte
 * Each has 5 possible values, so we could repesent these values using 5 bits.
 * Then 6 attributes need 30 bits, and thus can fit into one integer.
 */
public interface BitAttr
{
    public static final int ATTR_WIDTH = 5;

    public static final int PALL_MALL = 0x1;
    public static final int DUNHILL = PALL_MALL << 1;
    public static final int BLUE_MASTER = PALL_MALL << 2;
    public static final int PRINCE = PALL_MALL << 3;
    public static final int BLEND = PALL_MALL << 4;
    public static final int CIGARATTE_MASK = 31;
    public static final int[] CIGARATTES = new int[] {
        PALL_MALL, DUNHILL, BLUE_MASTER, PRINCE, BLEND
    };

    public static final int BEER = PALL_MALL << ATTR_WIDTH;
    public static final int TEA = BEER << 1;
    public static final int MILK = BEER << 2;
    public static final int WATER = BEER << 3;
    public static final int COFFEE = BEER << 4;
    public static final int DRINK_MASK = CIGARATTE_MASK << ATTR_WIDTH;
    public static final int[] DRINKS = new int[] {
        BEER, TEA, MILK, WATER, COFFEE
    };

    public static final int CAT = BEER << ATTR_WIDTH;
    public static final int DOG = CAT << 1;
    public static final int FISH = CAT << 2;
    public static final int BIRD = CAT << 3;
    public static final int HORSE = CAT << 4;
    public static final int PET_MASK = DRINK_MASK << ATTR_WIDTH;
    public static final int[] PETS = new int[] {
        CAT, DOG, FISH, BIRD, HORSE
    };

    public static final int FIRST = CAT << ATTR_WIDTH;
    public static final int SECOND = FIRST << 1;
    public static final int THIRD = FIRST << 2;
    public static final int FORTH = FIRST << 3;
    public static final int FIFTH = FIRST << 4;
    public static final int LOCATION_MASK = PET_MASK << ATTR_WIDTH;
    public static final int[] LOCATIONS = new int[] {
            FIRST, SECOND, THIRD, FORTH, FIFTH
    };

    public static final int RED = FIRST << ATTR_WIDTH;
    public static final int GREEN = RED << 1;
    public static final int YELLOW = RED << 2;
    public static final int WHITE = RED << 3;
    public static final int BLUE = RED << 4;
    public static final int COLOR_MASK = LOCATION_MASK << ATTR_WIDTH;
    public static final int[] COLORS = new int[] {
        RED, GREEN, YELLOW, WHITE, BLUE
    };

    public static final int BRITISH = RED << ATTR_WIDTH;
    public static final int GERMAN = BRITISH << 1;
    public static final int DENMARK = BRITISH << 2;
    public static final int SWEDISH = BRITISH << 3;
    public static final int NORWEGIAN = BRITISH << 4;
    public static final int NATIONALITY_MASK = COLOR_MASK << ATTR_WIDTH;
    public static final int[] NATIONALITIES = new int[] {
        BRITISH, GERMAN, DENMARK, SWEDISH, NORWEGIAN
    };
}

 

Of course, we sacrafice strong types for performance, since we are using integer types for everything. We'll come back for this later. Now we can define the rules using this class. Ideally, we should separate these rules into separate classes, but I am lazy for now, so don't follow this practice, it's just to show the logic. The reason we choose integer type because the bit operations are fast and cheap.

 

public class BitClue
{
    public static void main(String[] args)
    {
        int[] people = new int[5];
        people[0] = BitAttr.BRITISH | BitAttr.RED | BitAttr.THIRD | BitAttr.BIRD | BitAttr.MILK | BitAttr.PALL_MALL;
        people[1] = BitAttr.GERMAN | BitAttr.GREEN | BitAttr.FORTH | BitAttr.FISH | BitAttr.COFFEE | BitAttr.PRINCE;
        people[2] = BitAttr.DENMARK | BitAttr.BLUE | BitAttr.SECOND | BitAttr.HORSE | BitAttr.TEA | BitAttr.BLEND;
        people[3] = BitAttr.SWEDISH | BitAttr.WHITE | BitAttr.FIFTH | BitAttr.DOG | BitAttr.BEER | BitAttr.BLUE_MASTER;
        people[4] = BitAttr.NORWEGIAN | BitAttr.YELLOW | BitAttr.FIRST | BitAttr.CAT | BitAttr.WATER | BitAttr.DUNHILL;

        BitClue clues = new BitClue();
        
        if (clues.apply1(people) &&
            clues.apply2(people) &&
            clues.apply3(people) &&
            clues.apply4(people) &&
            clues.apply5(people) &&
            clues.apply6(people) &&
            clues.apply7(people) &&
            clues.apply8(people) &&
            clues.apply9(people) &&
            clues.apply10(people) &&
            clues.apply11(people) &&
            clues.apply12(people) &&
            clues.apply13(people) &&
            clues.apply14(people) &&
            clues.apply15(people))
        {
            System.out.println(true);
        }
    }

    public boolean apply1(int[] people)
    {
        int rule = BitAttr.BRITISH | BitAttr.RED;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply2(int[] people)
    {
        int rule = BitAttr.SWEDISH | BitAttr.DOG;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply3(int[] people)
    {
        int rule = BitAttr.DENMARK | BitAttr.TEA;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply4(int[] people)
    {
        int greenHouse = 0, whiteHouse = 0;
        for (int person : people)
        {
            if ((person & BitAttr.GREEN) == BitAttr.GREEN)
            {
                greenHouse = person;
            }
            if ((person & BitAttr.WHITE) == BitAttr.WHITE)
            {
                whiteHouse = person;
            }
        }

        // green  or white house not found.
        if (greenHouse == 0 || whiteHouse == 0) return false;

        int greenLocation = greenHouse & BitAttr.LOCATION_MASK;
        int whiteLocation = whiteHouse & BitAttr.LOCATION_MASK;

        // assuming 12345
        return (whiteLocation >> 1) == greenLocation;
    }

    public boolean apply5(int[] people)
    {
        int rule = BitAttr.GREEN | BitAttr.COFFEE;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply6(int[] people)
    {
        int rule = BitAttr.PALL_MALL | BitAttr.BIRD;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply7(int[] people)
    {
        int rule = BitAttr.YELLOW | BitAttr.DUNHILL;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply8(int[] people)
    {
        int rule = BitAttr.THIRD | BitAttr.MILK;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply9(int[] people)
    {
        int rule = BitAttr.NORWEGIAN | BitAttr.FIRST;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply10(int[] people)
    {
        int blend = 0, cat = 0;
        for (int person : people)
        {
            if ((person & BitAttr.BLEND) == BitAttr.BLEND)
            {
                blend = person;
            }
            if ((person & BitAttr.CAT) == BitAttr.CAT)
            {
                cat = person;
            }
        }

        // not found.
        if (blend == 0 || cat == 0) return false;

        int blendLocation = blend & BitAttr.LOCATION_MASK;
        int catLocation = cat & BitAttr.LOCATION_MASK;

        return (blendLocation >> 1) == catLocation ||
               (blendLocation << 1) == catLocation ;
    }

    public boolean apply11(int[] people)
    {
        int horse = 0, dunhill = 0;
        for (int person : people)
        {
            if ((person & BitAttr.HORSE) == BitAttr.HORSE)
            {
                horse = person;
            }
            if ((person & BitAttr.DUNHILL) == BitAttr.DUNHILL)
            {
                dunhill = person;
            }
        }

        // not found.
        if (horse == 0 || dunhill == 0) return false;

        int horseLocation = horse & BitAttr.LOCATION_MASK;
        int dunhillLocation = dunhill & BitAttr.LOCATION_MASK;

        return (horseLocation >> 1) == dunhillLocation ||
               (horseLocation << 1) == dunhillLocation ;
    }

    public boolean apply12(int[] people)
    {
        int rule = BitAttr.BLUE_MASTER | BitAttr.BEER;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply13(int[] people)
    {
        int rule = BitAttr.GERMAN | BitAttr.PRINCE;
        for (int person : people)
        {
            if ((person & rule) == rule) return true;
        }
        return false;
    }

    public boolean apply14(int[] people)
    {
        int norwegian = 0, blue = 0;
        for (int person : people)
        {
            if ((person & BitAttr.NORWEGIAN) == BitAttr.NORWEGIAN)
            {
                norwegian = person;
            }
            if ((person & BitAttr.BLUE) == BitAttr.BLUE)
            {
                blue = person;
            }
        }

        // not found.
        if (norwegian == 0 || blue == 0) return false;

        int norwegianLocation = norwegian & BitAttr.LOCATION_MASK;
        int blueLocation = blue & BitAttr.LOCATION_MASK;

        return (norwegianLocation >> 1) == blueLocation ||
               (norwegianLocation << 1) == blueLocation ;
    }

    public boolean apply15(int[] people)
    {
        int blend = 0, water = 0;
        for (int person : people)
        {
            if ((person & BitAttr.BLEND) == BitAttr.BLEND)
            {
                blend = person;
            }
            if ((person & BitAttr.WATER) == BitAttr.WATER)
            {
                water = person;
            }
        }

        // not found.
        if (blend == 0 || water == 0) return false;

        int blendLocation = blend & BitAttr.LOCATION_MASK;
        int waterLocation = water & BitAttr.LOCATION_MASK;

        return (blendLocation >> 1) == waterLocation ||
               (blendLocation << 1) == waterLocation ;
    }
}

 

Now we are ready to loop through all cases. In order to create all permutations, I use a class from this site: http://www.uwe-alex.de/Permutation/Permutation.html , you can pick anything you want since there are many implementations for different purposes. We basically just loop through all permutations, set the bits, check the result, unset the bits, set the bits for the next case, and so on.

 

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

public class BitEinsteinPuzzle
{
    public static void main(String[] args)
    {
        BitEinsteinPuzzle puzzle = new BitEinsteinPuzzle();
        puzzle.solve();
    }

    public void solve()
    {
        int[] people = new int[5];
        BitClue clues = new BitClue();

        // now prefix nationality
        System.arraycopy(BitAttr.NATIONALITIES, 0, people, 0, people.length);

        int[][] allCases = createPermutations(5);
        int[] perm1, perm2, perm3, perm4, perm5;
        long count=0;
        long begin = System.currentTimeMillis();
        for (int i=0; i<allCases.length; i++)
        {
            System.out.println("i=" + i + ", time=" + ((System.currentTimeMillis() - begin) / 1000.0));
            perm1 = allCases[i];
            for (int a=0; a<people.length; a++)
                people[a] |= BitAttr.COLORS[perm1[a]];
            for (int[] loc : allCases)
            {
                perm2 = loc;
                for (int a = 0; a < people.length; a++)
                    people[a] |= BitAttr.LOCATIONS[perm2[a]];
                for (int[] pet : allCases)
                {
                    perm3 = pet;
                    for (int a = 0; a < people.length; a++)
                        people[a] |= BitAttr.PETS[perm3[a]];
                    for (int[] drink : allCases)
                    {
                        perm4 = drink;
                        for (int a = 0; a < people.length; a++)
                            people[a] |= BitAttr.DRINKS[perm4[a]];
                        for (int[] cigaratte : allCases)
                        {
                            perm5 = cigaratte;
                            for (int a = 0; a < people.length; a++)
                                people[a] |= BitAttr.CIGARATTES[perm5[a]];

                            // now people is ready to test
                            if (clues.apply1(people) &&
                                clues.apply2(people) &&
                                clues.apply3(people) &&
                                clues.apply4(people) &&
                                clues.apply5(people) &&
                                clues.apply6(people) &&
                                clues.apply7(people) &&
                                clues.apply8(people) &&
                                clues.apply9(people) &&
                                clues.apply10(people) &&
                                clues.apply11(people) &&
                                clues.apply12(people) &&
                                clues.apply13(people) &&
                                clues.apply14(people) &&
                                clues.apply15(people))
                            {
                                String[] v = BitPerson.convert(people);
                                for (String s : v) System.out.println(s);
                                System.out.println("--------------------------------------------------------");
                            }

                            count++;

                            for (int a = 0; a < people.length; a++) // erase values for next loop
                                people[a] ^= BitAttr.CIGARATTES[perm5[a]];
                        }

                        for (int a = 0; a < people.length; a++) // erase values for next loop
                            people[a] ^= BitAttr.DRINKS[perm4[a]];
                    }

                    for (int a = 0; a < people.length; a++) // erase values for next loop
                        people[a] ^= BitAttr.PETS[perm3[a]];
                }

                for (int a = 0; a < people.length; a++) // erase values for next loop
                    people[a] ^= BitAttr.LOCATIONS[perm2[a]];
            }

            for (int a=0; a<people.length; a++) // erase values for next loop
                people[a] ^= BitAttr.COLORS[perm1[a]];
        }

        long end = System.currentTimeMillis() - begin;
        System.out.println("time=" + end);
        System.out.println("count=" + count);
        System.out.println("speed=" + (count / end));
    }

    public static int[][] createPermutations(int size)
    {
        List<int[]> ret = new ArrayList<int[]>();

        Permutation p=new Permutation(size);
        int[] a = new int[size];
        for (int i=0; i<size; i++)
        {
            a[i] = p.get(i);
        }
        ret.add(a);
        do
        {
            p.next();
            a = new int[size];
            for (int i=0; i<size; i++)
            {
                a[i] = p.get(i);
            }
            ret.add(a);
        }
        while (p.hasNext());

        return ret.toArray(new int[ret.size()][]);
    }
}

 

For the debug purpose and user interface, bits are less readable, so we build another class to interprete the bits.

 

public class BitPerson
{
    public static final String PALL_MALL = " Pall Mall   ";
    public static final String DUNHILL = " Dunhill     ";
    public static final String BLUE_MASTER = " Blue Master ";
    public static final String PRINCE = " Prince      ";
    public static final String BLEND = " Blend       ";
    public static final String[] CIGARATTES = new String[] {
        PALL_MALL, DUNHILL, BLUE_MASTER, PRINCE, BLEND
    };

    public static final String BEER = " Beer   ";
    public static final String TEA = " Tea    ";
    public static final String MILK = " Milk   ";
    public static final String WATER = " Water  ";
    public static final String COFFEE = " Coffee ";
    public static final String[] DRINKS = new String[] {
        BEER, TEA, MILK, WATER, COFFEE
    };

    public static final String CAT = " Cat   ";
    public static final String DOG = " Dog   ";
    public static final String FISH = " Fish  ";
    public static final String BIRD = " Bird  ";
    public static final String HORSE = " Horse ";
    public static final String[] PETS = new String[] {
        CAT, DOG, FISH, BIRD, HORSE
    };

    public static final String FIRST = " 1st ";
    public static final String SECOND = " 2nd ";
    public static final String THIRD = " 3rd ";
    public static final String FORTH = " 4th ";
    public static final String FIFTH = " 5th ";
    public static final String[] LOCATIONS = new String[] {
            FIRST, SECOND, THIRD, FORTH, FIFTH
    };

    public static final String RED = " Red    ";
    public static final String GREEN = " Green  ";
    public static final String YELLOW = " Yellow ";
    public static final String WHITE = " White  ";
    public static final String BLUE = " Blue   ";
    public static final String[] COLORS = new String[] {
        RED, GREEN, YELLOW, WHITE, BLUE
    };

    public static final String BRITISH = " British   ";
    public static final String GERMAN = " German    ";
    public static final String DENMARK = " Denmark   ";
    public static final String SWEDISH = " Swedish   ";
    public static final String NORWEGIAN = " Norwegian ";
    public static final String[] NATIONALITIES = new String[] {
        BRITISH, GERMAN, DENMARK, SWEDISH, NORWEGIAN
    };

    public static String[] convert(int[] people)
    {
        String[] ret = new String[people.length];
        for (int i=0; i<ret.length; i++)
        {
            ret[i] = convert(people[i]);
        }
        return ret;
    }

    public static String convert(int person)
    {
        int mask = 31;

        int field = (mask & person);
        field = getIndex(field);
        String ret = CIGARATTES[field];

        mask <<= BitAttr.ATTR_WIDTH;
        field = (mask & person) >>> BitAttr.ATTR_WIDTH;
        field = getIndex(field);
        ret = DRINKS[field] + "|" + ret;

        mask <<= BitAttr.ATTR_WIDTH;
        field = (mask & person) >>> BitAttr.ATTR_WIDTH * 2;
        field = getIndex(field);
        ret = PETS[field] + "|" + ret;

        mask <<= BitAttr.ATTR_WIDTH;
        field = (mask & person) >>> BitAttr.ATTR_WIDTH * 3;
        field = getIndex(field);
        ret = LOCATIONS[field] + "|" + ret;

        mask <<= BitAttr.ATTR_WIDTH;
        field = (mask & person) >>> BitAttr.ATTR_WIDTH * 4;
        field = getIndex(field);
        ret = COLORS[field] + "|" + ret;

        mask <<= BitAttr.ATTR_WIDTH;
        field = (mask & person) >>> BitAttr.ATTR_WIDTH * 5;
        field = getIndex(field);
        ret = NATIONALITIES[field] + "|" + ret;

        return ret;
    }

    private static int getIndex(int field)
    {
        if (field == 1) return 0;
        else if (field == 2) return 1;
        else if (field == 4) field = 2;
        else if (field == 8) field = 3;
        else if (field == 16) field = 4;
        return field;
    }

    public static void main(String[] args)
    {       
        int[] people = new int[5];
        people[0] = BitAttr.BRITISH | BitAttr.RED | BitAttr.THIRD | BitAttr.BIRD | BitAttr.MILK | BitAttr.PALL_MALL;
        people[1] = BitAttr.GERMAN | BitAttr.GREEN | BitAttr.FORTH | BitAttr.FISH | BitAttr.COFFEE | BitAttr.PRINCE;
        people[2] = BitAttr.DENMARK | BitAttr.BLUE | BitAttr.SECOND | BitAttr.HORSE | BitAttr.TEA | BitAttr.BLEND;
        people[3] = BitAttr.SWEDISH | BitAttr.WHITE | BitAttr.FIFTH | BitAttr.DOG | BitAttr.BEER | BitAttr.BLUE_MASTER;
        people[4] = BitAttr.NORWEGIAN | BitAttr.YELLOW | BitAttr.FIRST | BitAttr.CAT | BitAttr.WATER | BitAttr.DUNHILL;

        String[] v = convert(people);
        for (String s : v)
            System.out.println(s);

    }
}

 

This class is used for printing out the result. The spaces are just for nice printout/alignment.

 

 British   | Red    | 3rd | Bird  | Milk   | Pall Mall   
 German    | Green  | 4th | Fish  | Coffee | Prince      
 Denmark   | Blue   | 2nd | Horse | Tea    | Blend       
 Swedish   | White  | 5th | Dog   | Beer   | Blue Master 
 Norwegian | Yellow | 1st | Cat   | Water  | Dunhill  

 

 

The approach of this solution is actually seen in various cases, Hua-Rong-Dao, Taxas Hold'em, and other cases.

 

The old saying goes, an exact measure is worth a thousand experts' opinion.

 

Updates:

 

There are quite a few leeway we could play to make it faster. In the main for loops, we check the results at the inner most loop with 14 conditions. If we spread these conditions among the for loops, we effectively cut a lot of search branches. Another way is swap the order of the for loops.

 

Here is an example where we just spread the checks:

 

public class BitEinsteinPuzzleNew
{
    public static void main(String[] args)
    {
        BitEinsteinPuzzleNew puzzle = new BitEinsteinPuzzleNew();
        puzzle.solve();
    }

    public void solve()
    {
        int[] people = new int[5];
        BitClue clues = new BitClue();

        // now prefix nationality
        System.arraycopy(BitAttr.NATIONALITIES, 0, people, 0, people.length);

        int[][] allCases = createPermutations(5);
        int[] perm1, perm2, perm3, perm4, perm5;
        long count=0;
        long begin = System.currentTimeMillis();
        for (int i=0; i<allCases.length; i++)
        {
            System.out.println("i=" + i + ", time=" + ((System.currentTimeMillis() - begin) / 1000.0));
            perm1 = allCases[i];
            for (int a=0; a<people.length; a++)
                people[a] |= BitAttr.COLORS[perm1[a]];
            if (!clues.apply1(people))
            {
                for (int a=0; a<people.length; a++) // erase values for next loop
                    people[a] ^= BitAttr.COLORS[perm1[a]];
                continue;
            }
            for (int[] loc : allCases)
            {
                perm2 = loc;
                for (int a = 0; a < people.length; a++)
                    people[a] |= BitAttr.LOCATIONS[perm2[a]];
                if (!clues.apply4(people) || !clues.apply9(people) ||
                    !clues.apply14(people))
                {
                    for (int a = 0; a < people.length; a++) // erase values for next loop
                        people[a] ^= BitAttr.LOCATIONS[perm2[a]];
                    continue;
                }
                for (int[] pet : allCases)
                {
                    perm3 = pet;
                    for (int a = 0; a < people.length; a++)
                        people[a] |= BitAttr.PETS[perm3[a]];
                    if (!clues.apply2(people))
                    {
                        for (int a = 0; a < people.length; a++) // erase values for next loop
                            people[a] ^= BitAttr.PETS[perm3[a]];
                        continue;
                    }
                    for (int[] drink : allCases)
                    {
                        perm4 = drink;
                        for (int a = 0; a < people.length; a++)
                            people[a] |= BitAttr.DRINKS[perm4[a]];
                        if (!clues.apply3(people) || !clues.apply5(people) ||
                            !clues.apply8(people))
                        {
                            for (int a = 0; a < people.length; a++) // erase values for next loop
                                people[a] ^= BitAttr.DRINKS[perm4[a]];
                            continue;
                        }
                        for (int[] cigaratte : allCases)
                        {
                            perm5 = cigaratte;
                            for (int a = 0; a < people.length; a++)
                                people[a] |= BitAttr.CIGARATTES[perm5[a]];

                            // now people is ready to test
                            if (//clues.apply1(people) &&
                                //clues.apply2(people) &&
                                //clues.apply3(people) &&
                                //clues.apply4(people) &&
                                //clues.apply5(people) &&
                                clues.apply6(people) &&
                                clues.apply7(people) &&
                                //clues.apply8(people) &&
                                //clues.apply9(people) &&
                                clues.apply10(people) &&
                                clues.apply11(people) &&
                                clues.apply12(people) &&
                                clues.apply13(people) &&
                                //clues.apply14(people) &&
                                clues.apply15(people))
                            {
                                String[] v = BitPerson.convert(people);
                                for (String s : v) System.out.println(s);
                                System.out.println("--------------------------------------------------------");
                            }

                            count++;

                            for (int a = 0; a < people.length; a++) // erase values for next loop
                                people[a] ^= BitAttr.CIGARATTES[perm5[a]];
                        }

                        for (int a = 0; a < people.length; a++) // erase values for next loop
                            people[a] ^= BitAttr.DRINKS[perm4[a]];
                    }

                    for (int a = 0; a < people.length; a++) // erase values for next loop
                        people[a] ^= BitAttr.PETS[perm3[a]];
                }

                for (int a = 0; a < people.length; a++) // erase values for next loop
                    people[a] ^= BitAttr.LOCATIONS[perm2[a]];
            }

            for (int a=0; a<people.length; a++) // erase values for next loop
                people[a] ^= BitAttr.COLORS[perm1[a]];
        }

        long end = System.currentTimeMillis() - begin;
        System.out.println("time=" + end);
        System.out.println("count=" + count);
        System.out.println("speed=" + (count / end));
    }

    public static int[][] createPermutations(int size)
    {
        List<int[]> ret = new ArrayList<int[]>();

        Permutation p=new Permutation(size);
        int[] a = new int[size];
        for (int i=0; i<size; i++)
        {
            a[i] = p.get(i);
        }
        ret.add(a);
        do
        {
            p.next();
            a = new int[size];
            for (int i=0; i<size; i++)
            {
                a[i] = p.get(i);
            }
            ret.add(a);
        }
        while (p.hasNext());

        return ret.toArray(new int[ret.size()][]);
    }
}

 

 The result is a little bit amusing:

 

time=16 milliseconds
count=23040 cases
speed=1440 / milliseconds

 

Yes, that's 16 milliseconds.