java中的项目euler 215

Question

我在java中将这个解决方案写入Project Euler#215.它不需要在不到一分钟的时间内完成W(32,10)的计算.我希望能得到一些关于如何加快速度的建议.我想知道添加线程是否合适,或者是否有方法来缓存buildWall()方法中每行的结果.

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);
        }
    }
}

Answer 1

您实际上构建了一个图形G,其节点等于宽度为32的可能行以及节点之间的边缘(如果我们的规则可以将一行放在另一行之上).该图表具有2,500个节点的顺序.

然后,您需要该图表中长度为10的路径数.有一个枚举这些路径的技巧.创建一个称为图的关联矩阵的东西,然后将该矩阵提升到10次幂.然后在结果中添加结果条目.注意,给定矩阵A,您可以通过计算A ^ 2计算A ^ 10,然后计算A ^ 4,然后计算A ^ 8,然后计算A ^ 8*A ^ 2.这需要4次矩阵乘法.然而,它仍然是很多操作.您可以使用额外的线性代数或组合技巧来进一步简化问题.特别地,A ^ 10的条目的总和可以写为(1,1,...... 1)A ^ 10(1,1,...,1)^ T. 实际上,您可以根据A的特征值确定W(32,n)的精确规则