optimize program

[Jjoshua2]

I'm wondering what big oh this program is and if there is any way to optimize it.
It has a ton of for loops which function like an odometer to try the scoring method with different parameters. I dont suppose there is a way to just tell c# how many for loops to put and have it put in more or less following that pattern? Maybe recursion? I couldn't figure out how though. Thanks!!

 class Program
    {
        static void Main(string[] args)
        {
            Optimize.timeStart = System.DateTime.Now.Ticks;
            Optimize.optimize(4, 8);
        }
    }

    public class Optimize {
	public static long timeStart;
	private static int[] solArr;
	
	public static int optimize(int darts, int regions) {
		if (darts <= 0 || regions <= 0)
			throw new Exception();	
		if (darts == 1)
			return regions;
		if (regions == 1)
			return darts;
		solArr = new int[regions+1];		
		int tmax;		
		int max = 0;
		
		solArr[1] = 1;
		for (int i = 2; i <= 5; i ++) {
			solArr[2] = i;
			int jmax = findMax(darts, 2);
			for (int j = i+1; j <= jmax; j++) {
				solArr[3] = j;
				int kmax = findMax(darts, 3);
				for (int k = j+1; k <= kmax; k++) {
					solArr[4] = k;
					int lmax = findMax(darts, 4);
					for (int l = k+1; l <= lmax; l++) {
						solArr[5] = l;
						int mmax = findMax(darts, 5);
						for (int m = l+1; m <= mmax; m++) {
							solArr[6] = m;
							int nmax = findMax(darts, 6);
							for (int n = m+1; n <= nmax; n++) {
								solArr[7] = n;
								int omax = findMax(darts, 7);
								for (int o = n+1; o <= omax; o++) {
									solArr[8] = o;
//									for (int p = o+1; p <= findMax(darts, 8); p++) {
//										solArr[9] = p;
									tmax = findMax(darts, regions);
										if (tmax >= max) {
											max = tmax;
											Console.Write(darts + ":");
											for (int index = 1; index <solArr.Length - 1; index++)
												Console.Write(solArr[index] + ", ");
											Console.Write(solArr[solArr.Length - 1]);
											Console.WriteLine("\nMax: " + max +"\tTime: " + (System.DateTime.Now.Ticks - timeStart)/10000 + " ms");
//										}
									}
								}
							}
						}
					}
				}
			}
		}
		return max;
	}
	
	private static int findMax(int darts, int regions) {
		int[] permutations = new int[solArr[regions]*darts + 1];
		for (int i = 0; i <= regions; i++) {
			for (int j = 0; j <= regions; j++) {
				for (int k = 0; k <= regions; k++) {
					for (int l = 1; l <= regions; l++)
					permutations[solArr[i] + solArr[j] + solArr[k] + solArr[l]] = 1;
				}
			}
		}
		for (int i = 5; i < permutations.Length; i++) {
			if (permutations[i] == 0)
				return i;
		}
		return permutations.Length;
	}
}

 

[Ken g6]

I'm wondering what big oh this program is

Too big! I'm not going to give you the answer - this looks like homework - but count how many loops deep the program goes. Don't forget to include loops inside functions inside loops!

and if there is any way to optimize it.

I'm not sure. What are you trying to do here? (In English, please.)

 

[Gamingphreek]

Dear sweet Lord. What in the WORLD are all those 'for' loops for??

As Ken said, this looks a lot like homework - so I'll repeat what he said. Count the number of 'for' loops and that will likely lead you to an accurate asymptotic analysis of it.

As for optimizing it, I honestly don't know what in the world you are trying to accomplish in this program. Recursion is most definitely not going to be faster.

Without knowing your goal for this code it would seem to me that refining your algorithm is the best way to optimize this.

-Kevin

 

[Markbnj]

Hahaha, nine levels of for loops. Buy your prof a beer for me.

 

[Jjoshua2]

Too big! ... I'm not sure. What are you trying to do here? (In English, please.)

I decided it was O(n^darts* n^regions), which I agree it too big. This is to solve the postage stamp problem. From http://en.wikipedia.org/wiki/Postage_stamp_problem
Consider that an envelope is able to hold a limited number of postage stamps. Then, consider the set of the values of the stamps -- positive integers only. Then, what is the smallest total postage which cannot be put onto the envelope?

For example, if the envelope can hold three stamps, and the possible stamp values are the set {1, 4, 6}, solutions for the totals 1 through 14 can be found. But to get a total of 15: three 6's would be too much; two 6's cannot be used, since there is no 3; using just one 6 will not work, because there is no combination to make 9 with two stamps; but with no 6's, the largest total (three 4's) would only be 12. So the answer to the problem is 15.

Same thing for darts. You get d throws and there are r regions on the board. What regions should they be so the thrower can hit anything from 1 to as high as possible.

 

[Jjoshua2]

Dear sweet Lord. What in the WORLD are all those 'for' loops for??

As Ken said, this looks a lot like homework - so I'll repeat what he said. Count the number of 'for' loops and that will likely lead you to an accurate asymptotic analysis of it.
-Kevin

It functions basically as an odometer. I want 0001 then 0002 then 0003 and each for loop is a digit on the odometer. I'm running my scoring method on all the possible arrays of darts length. Because of the way the scores work I only need to try 1,2,3,4... 1,2,3,5.. where each number is bigger than the one before.

Its actually not homework. I saw Al Zimmerman's programming contest Son of Darts. http://www.azspcs.net/Contest/SonOfDarts and I thought I would write a brute forcer for it, even though its not really any use for the contest because you would need a genetic algorithm or hill climbing approach. I'm taking CSE 143 at UW so I'm not very good yet, but it is kind of boring because the stuff we are doing is so simple like get a queue and return a stack that will empty out in the same order as dequeing. Even when the problems are harder they are not interesting. I saw a link to the Stamp problem as something you could implement a distributed project on, and I thought that would be cool, but I need software first.

 

[Jjoshua2]

Hahaha, nine levels of for loops. Buy your prof a beer for me.

And with my lastest code no longer. It still does it, its just not so obvious...

I made my bruteforce much more efficient, because it starts at the top and works down, not trying something that would give a less score than the max. Also it works for an arbitrary number N loops instead of fixed. Its makes my program ~1000x faster.

Also I made the findMax use bytes instead of ints which is faster and more memory efficient. I need to make it arbitrary depth, but more important is a way to use the fact that I'm hardly changing the problem each time I call it.

 using System;

namespace DartProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            Optimize.timeStart = System.DateTime.Now.Ticks;
            Optimize.darts = 4;
            Optimize.regions = 9;
            Optimize.bruteforce();
        }
    }

    public class Optimize
    {
        public static long timeStart;
        public static int darts;
        public static int regions;
        private static int[] solArr;
        
        public static int bruteforce()
        {
            solArr = new int[regions + 1];
            int i = 0;
            int max = 0;
            solArr[i] = 1;

        L: solArr[i] = solArr[i] - 1;
            for (i += 1; i <= regions; i++)
                solArr[i] = findMax(i - 1);
            if (findMax(regions) >= max)
            {
                max = findMax(regions);
                Console.Write(darts + ":");
                for (int index = 1; index < solArr.Length - 1; index++)
                    Console.Write(solArr[index] + ", ");
                Console.Write(solArr[solArr.Length - 1]);
                Console.WriteLine("\nMax: " + max + "\tTime: " + (System.DateTime.Now.Ticks - timeStart) / 10000 + " ms");
            }
            for (i = regions; i >= 1; i--)
                if (solArr[i] != solArr[i - 1] + 1)
                    goto L;
            Console.WriteLine("Time: " + (System.DateTime.Now.Ticks - timeStart) / 10000 + " ms");
            return max;
        }

        private static int findMax(int regions)
        {
            byte[] permutations = new byte[solArr[regions] * darts + 1];
            for (int i = 1; i <= regions; i++)
            {
                for (int j = 0; j <= regions; j++)
                {
                    for (int k = 0; k <= regions; k++)
                    {
                        for (int l = 0; l <= regions; l++)
                        {
                            //    for (int m = 0; m <= regions; m++) {
                            //         for (int n = 0; n <= regions; n++)
                            permutations[solArr[i] + solArr[j] + solArr[k] + solArr[l]] = 1; // + solArr[m] + solArr[n]
                            //        }
                        }
                    }
                }
            }
            for (int i = darts; i < permutations.Length; i++)
            {
                if (permutations[i] == 0)
                    return i;
            }
            return permutations.Length;
        }
    }
}

 

[Gamingphreek]

And you thought a for loop would be the best way to simply display leading 0's 😉?

Your optimization should start and end with you fixing that algorithm.

-Kevin (Gamingphreek)

 

[Jjoshua2]

And you thought a for loop would be the best way to simply display leading 0's 😉?
Your optimization should start and end with you fixing that algorithm.

I'm thinking you didn't see my other posts when you posted that? I'm not trying to print, I'm trying to score all possible arrays that might be an answer to the postage stamp problem, such as 1,4,9,15,20. They aren't necessarily single digits so its not just a string of numbers.

I found an article http://comjnl.oxfordjournals.org/cgi/reprint/12/4/377.pdf that explained the brute force approach, so that's how I implemented it. I couldn't quite understand the part on the scoring method. I tried to code it, but its not working.

 private static int findMax(int regions)
        {
            byte[] permutations = bArrPermutations(regions, darts);
            
            for (int i = darts + 1; i < permutations.Length; i++)
            {
                if (permutations[i] == 0)
                    return i;
            }
            return permutations.Length;
        }

        private static byte[] bArrPermutations(int regions, int darts)
        {
            if (darts == 0){
                byte[] temp = new byte[1];
                temp[0] = 1;
                return temp;
            }
            byte[] permutations = new byte[solArr[regions] * darts + 1];
            byte[] temp1 = bArrPermutations(regions, darts - 1);
            byte[] tempShift = new byte[temp1.Length + solArr[regions]];
            for (int i = tempShift.Length - 1; i >= solArr[regions]; i--)
            {
                tempShift[i] = temp1[i - solArr[regions]];
            }            
            for (int i = 0; i < temp1.Length; i++)
            {
                if (tempShift[i] == 1 || bArrPermutations(regions - 1, darts)[i] == 1)
                    permutations[i] = 1;
            }
            
            return permutations;
        }