project euler 215 in java [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 11 years ago.

I wrote this solution to Project Euler #215 in java. It doesn't complete the calculations for W(32,10) in less than a minute and It needs to. I was hoping I could get some advice on how to make it faster. I was wondering if adding threads would be appropriate or if there is a way to cache results from each row in the buildWall() method.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.HashMap;
import java.util.Map;

class BlockCombos
{
    static ArrayList<String> possibleRows = new ArrayList<String>();
    static long validWalls = 0;
    static Map<Integer, List> map = new HashMap<Integer, List>();
    static int[][] cache;

    public static void main(String[] args) 
    {
        if (args.length != 2) 
        {
            System.out.println("Error: You need to enter a height and width.");
        }
        else
        {
            int height = Integer.parseInt(args[1]);
            int width = Integer.parseInt(args[0]);

            //numbers proportionate to block widths
            //reduced for less overhead (actual widths do not matter)
            ArrayList<Integer> numbers = new ArrayList<Integer>();
            numbers.add(new Integer(2));
            numbers.add(new Integer(3));

            startGetBlockCombos(numbers,width);

            int i = 0; //initial row
            for(String row : possibleRows)
            {
                //possible rows
                char[] rowArr = row.toCharArray();
                List<Integer> compatiblerows = new ArrayList<Integer>();
                int k = 0; //rowtocheck index
                for(String rowToCheck : possibleRows)
                {
                    char[] rowToCheckArr = rowToCheck.toCharArray();
                    for(int x = 0; x < rowToCheckArr.length-1; x++)
                    {   

                        if(rowArr[x] == '1' && rowToCheckArr[x] == '1')
                        {
                            //set not compatible
                            break;
                        }
                        else if (x == rowToCheckArr.length-2)
                        {
                            compatiblerows.add(k);
                        }
                    }
                    k ++; //rowtocheck index
                }
                Integer key = new Integer(i);
                map.put(key, compatiblerows);
                i++; //row index
            }

            possibleRows.clear(); //a little clean up
            cache = new int[map.size()][height];
            startBuildWalls(height);
            System.out.print(validWalls);
        }
    }

    static void startBuildWalls(int height)
    {
        height = height-1;
        for(int x = 0; x < map.size(); x++)
        {
            buildWalls(x, height);
        }
        //testing threads from static method

    }
    static void buildWalls(int currentRow, int rowsToGo)
    {
        rowsToGo -=1;
        if(rowsToGo > 0)
        {
            @SuppressWarnings("unchecked")
            List<Integer> nextRows = (List<Integer>)map.get(Integer.valueOf(currentRow));

            for(int row : nextRows)
            {
                buildWalls(row,rowsToGo);
            }
        }
        else
        {
            validWalls++;
            return;
        }
    }

    static void startGetBlockCombos(ArrayList<Integer> numbers, int target) 
    {
        ArrayList<Integer> part = new ArrayList<Integer>();
        getBlockCombos(numbers,target,part);
    }

    static void getBlockCombos(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) 
    {
        int s = 0;
        for (int x: partial)
        {
            s += x;
        }
        if (s == target)
        {
            Integer row[] = new Integer[partial.size()];
            row = partial.toArray(row);
            String rowString = "";

            for (int b : row)
            {
                if (b == 2)
                {开发者_如何学编程
                    rowString = rowString +"01";
                }
                else
                {
                    rowString = rowString + "001";
                }
            }

            BlockCombos.possibleRows.add(rowString);
        }
        else if (s > target)
        {
            return;
        }
        for(int i=0;i<2;i++) 
        {
            int n = numbers.get(i);
            ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
            partial_rec.add(n);
            getBlockCombos(numbers,target,partial_rec);
        }
    }
}

---

You are essentially building a graph, G, with nodes equal to the possible rows of width 32 and edges between nodes if one row can be put on top of the other by our rules. This graph has on the order of 2,500 nodes.

Then you want the number of paths in that graph of length 10. There is a trick to enumerating these paths. Create something called the incidence matrix of the graph, and then raise that matrix to the 10th power. Then add up the resulting entries in the result. Note that, given a matrix, A, you can compute A^10 by compute A^2, then A^4, then A^8, then A^8 * A^2. That requires 4 matrix multiplications. It's still a lot of operations, however. There are probably additional linear algebraic or combinatorial tricks you could play to simplify the problem further. In particular, the sum of the entries of A^10 can be written as (1,1,....1)A^10(1,1,...,1)^T. You can actually ge an exact rule for W(32,n) based on the eigenvalues of A

---

I'm guessing a large portion of your slower algorithm comes from the extreme amount of primitive-to-object and object-to-primitive combined with overly generic datastructures. String objects are slow in almost every language I know of, and this following code segment is probably the one that would show up the strongest if you were to run your code through a profiler. (Which would be worth doing, by the way.)

        String rowString = "";

        for (int b : row)
        {
            if (b == 2)
            {
                rowString = rowString +"01";
            }
            else
            {
                rowString = rowString + "001";
            }
        }

I do not know any language where string concatenation is a fast operation. These concat operations here create a new String object from the "01" and "001" strings (the first time through), create a new string object to hold the concatenation with the rowString string, replace a reference, all to append the string to a variable-sized BlockCombos object.

If I had to improve upon this, I'd probably switch away from strings to static-sized arrays of char. (Robin recommends switching to StringBuilder -- which, if this were variable-sized objects I would probably agree with. I think arrays of char still make most sense because the length of your objects is fixed and known ahead of time.)

One thing to definitely think about -- they asked for 32x10. That 32 is exactly long enough to store a row as a single integer, if you use 1 bits to indicate brick boundaries. Then your giant loop checking boundaries between rows can be reduced to a simple bitwise AND operation. If the result is non-zero, then you've got brick boundaries stacked. That would replace an entire loop with a single VM instruction, but would definitely change how you build walls.