Al Zimmermann's contest.

31 posts

Flag Post

http://www.azspcs.net/

Quoting him: “Welcome to Al Zimmermann’s Programming Contests. You’ve entered an arena where demented computer programmers compete for glory and for some cool prizes.”

Math+logic problem to solve.
Prizes for first and second places.

You can check the archives to get an idea of the kind of problems he comes up with. It’s a pretty fun contest.

Make sure to register if you’re interested. The next contest starts in four days.


Also, we should have a thread to keep track of current programming related contests around the web.

 
Flag Post

It really would be nice to see the actual description of the current project before running off and registering for it. Super cool discovery though. Thanx! Basically all we have to get ahead of the game with is the name of the project so we can just keep our eyes out for something that might include interest. And those statues are rad!

 
Flag Post

Now that the contest has begun, any strategies someone’s willing to share. I’ll be honest, I’m a bit lost as of how to attack this.

 
Flag Post

I remember the same question being asked ages ago somewhere (relating to SLP’s) and I remember the answer of finding the optimal k as being “There is no known way of 100% finding the lowest k value”. So this should be….fun?

Right now, I am just bruteforcing from k=1 until I hit k=50 (at which point I tell my program to give up…)

EDIT: OK, this is a little trickier than I first thought. I need to do some background reading into the area first to get a better idea of how to tackle this, as even with really low values of N, my current algorithm takes far too long once it hits around N=11. (It takes around 30 minutes of execution time to get N=11, and the way it works means I cannot get the ‘winning’ sequence right now.)

For N=1→11 I got;

N = 1, N! = 1, k = 0
N = 2, N! = 2, k = 1
N = 3, N! = 6, k = 3
N = 4, N! = 24, k = 4
N = 5, N! = 120, k = 7 (Definitely not the optimal answer…)
N = 6, N! = 720, k = 7 (?)
N = 7, N! = 5,040, k = 7 (?)
N = 8, N! = 40,320, k = 7 (?)
N = 9, N! = 362,880, k = 8 (?)
N = 10, N! = 3,628,800, k = 9 (?)
N = 11, N! = 39,916,800, k = 11 (?)

Just from thinking this through, I would think almost every sequence should have a k value of around 8 or lower.

 
Flag Post

Someone in the discussion group posted a link to a math site which contains some results (and no proof, or any other info on how in the world you’d tackle something like this). Apparently the best score is known for up to 12!
For n = 5, you can get down to 6 steps and there are several ways to achieve it. For 6, 7, and 8, k = N.
N = 9, k = 8.
N = 10, 11; k = 9.
N = 12, k = 10.
I found a solution in 11 steps for N = 13, and it’s got me a full point, so I know nobody has submitted a better one. From my score on N = 14, I also know that at least one person found a solution in 11 steps.

I don’t have a program, btw, I’m doing trial and error by hand.

 
Flag Post

I’m not sure if this is helpful or not, but factorising the target number into primes might help…

 
Flag Post

Collaboration is banned ;-)

And yeah I’d start by working out what prime factors you need for the factorial.

Take n=5. The final step is has prime factors 2, 2, 2, 3, 5. You want a 4 and a 6 (2,2 and 2,3), or and 8 (2,2,2) and a 3, and the 5. So trying 4 and 6: 1, 2, 4, 5, 6, 20, 120. Trying 3 and 8: 1, 2, 3, 5, 8, 40, 120. You can multiply up pretty quickly at the end.

Looking then at n=11, the prime factors are 2, 3, 2,2, 5, 2,3, 7, 2,2,2, 3,3, 2,5, 11 or [2,2,2,2,2,2,2,2],[3,3,3,3],[5,5],7,11. Looks like a good starting pattern would be 1,2,3,5,7,9,11 in most cases; that gets all the primes in play for multiplying up. Now work out how to mix in in the most efficient way possible. We need 11 and 7 once, so make the 77. We want 5×3×3 twice, so make 45 which we will want to square. And then we want 8 2s, that’s 16 squared (in the 45). Conclusion: we want to go 11, 7, [5×3×3], and [2×2×2x2] for prime factors
=> 1,2,3,5,7,9,11,16,45,77,720,518400,39916800, k=12
Secondary conclusion: not such a good method :p

 
Flag Post
Originally posted by BobJanova:

Collaboration is banned ;-)

That’s quite an oversimplification. Discussing strategies and algorithms is encouraged, and only two things are forbidden: Sharing solutions and sharing code.

Originally posted by Al Zimmermann:


What information about my solutions can I share in the discussion group?

There are two types of information that you are forbidden to post. The first is specific solutions. The second is code. You may post scores, so if you want to tell everyone that you got a raw score of 99 for n = 20 (whether true or not), go right ahead. Officially, you may also discuss the algorithms you are using but be aware that doing so annoys some people.

Yes, I translate “annoys some people” into “is encouraged.” Got a problem with that? ;p

As far as the algorithmic, there is no systematic rule to it, except one, that I could find: Anytime you can square a useful number and get another useful number, it’s probably a good idea to do it. For instance 8*9*10=6! so 6! is probably a good start on the way to 10!. Unfortunately, that doesn’t mean at all that it’s also a good start on the way to 11! or 12!.
If you can express a bunch of orphan odd factors into one less than the square of an easily made number, that helps too.

 
Flag Post

hmm, N=5, one of the possible answers seems to be 1-2-4-5-6-30-120, is this optimal?

 
Flag Post
Originally posted by vesperbot:

hmm, N=5, one of the possible answers seems to be 1-2-4-5-6-30-120, is this optimal?

I think 6-step is optimal for N=5, so yep.

 
Flag Post

Here’s a technical question: What do you guys use to represent large factorials and do computations on them? 37!, for instance, is a 44-digit number (which requires 144 bits to represent in binary form.) My calculator is struggling just to display it, obviously, but it also overflows typical integer definitions on any programming language I know. How do you perform operations on a number that large?

 
Flag Post

If you want the whole number, use an extended precision integer class, e.g. .Net 4’s BigInteger. For a problem like this I’d think that prime factor representation might be pretty good, as I’m fairly sure that for the larger end of the scale you need to make factor sets and then multiply up.

That’s quite an oversimplification

I know, hence the smiley and joining the collaboration :p

 
Flag Post

When it comes to representing (and I’m not even talking about manipulating !) the larger numbers, it doesn’t seem like any standard integer type is going to work. So I’ve started looking into languages that can handle integers of arbitrary precision, and the first one listed in that article is Lisp.

Lisp (which, disclaimer, I have never used) is apparently all about lists, which is a very happy coincidence because this problem is all about lists as well. Making them, extending them, pruning them, etc… So any Lisp experts around who would kindly point me to standard resources for making (and compiling? Is Lisp interpreted or compiled?) Lisp programs would be highly appreciated.

 
Flag Post

Lisp IIRC is interpreted. Making Lisp programs is highly different from making say Actionscript programs, as Lisp is all about functions, there are NO variables in standard Lisp, all “variables” you can use are function parameters, and the main standard way of writing a Lisp program is extensive use of recursion. I guess learning Lisp will be an endeavor worthy to take, but too lengthy to do something for this challenge.

 
Flag Post

Yea, it’s kind of crazy. For now I went the toy route and wrote a little program in AS3 to assist me in my manual computations. I was surprised to see it was able to brute force its way through 11! before crashing from what I assume was lack of memory.

 
Flag Post

Hello, guys.
I’m solving on my own.

Ruby (I choose the slowest language, WHY NOT?).
6 6
7 7
8 8
9 8
10 9
11 9
12 10

13 11
14 11
15 13 (Ruby + paper)
16 14 (Ruby + paper)
17 16 (Ruby + paper)
18 17 (Ruby + paper)
19 19 (Ruby + paper)

36 29 (Mathematica + paper)

 
Flag Post

Cool. My AS3 solver finally beat my pen and paper skills today. So now I can report that best so far in the contest are:
13!: (11)
14!: (11)
15!: (12)
16!: (12)
17!: (12)
18!: (13)
19!: (13)
My algorithm’s 20! best is currently (17) but I’ve only explored a tiny part of the search space, so I haven’t bothered entering it. Especially since I can construct a better solution from the ones I have for 19!

On the one hand it’s pretty scary that people manage the kinds of scores they do, but on the other hand it’s kind of reassuring too: It means the computational search effort doesn’t scale as horribly as one might think from one problem to the next, since the number of steps needed only increases slowly.

Out of curiosity Nakilon, did you skip results between 19! and 36! or you just decided to take a crack at 36! independently of the rest of your search?

 
Flag Post

since I gave up on the topcoder $10k contest I’m gonna start taking a crack at this eventually…

EDIT: Ok the trivial solution ((2n-3)-step) gives me a score of 8.95, which basically means that even at the top end k is not too much smaller than n… of the solutions found so far.

Anyways, I think the breakthroughs to good scores will be from adding random big numbers and suddenly getting a useful number. When you mix addition and multiplication together lots of complicated and weird things happen. I think any solution which generates all the factors and then multiplies them together is not going to be the optimal one (for the larger cases).

 
Flag Post

Well, perhaps first multiplying to large powers of 2 (say 64) then adding with lower powers easily gets 2^X*5, 2^X*7, 2^X*3^2, 2^X*17, 2^X*3*5, which is more optimal than just generating one of each and then multiply them. After all, a factorial contains a lot of twos in its factorization.

 
Flag Post

@Ace_Blue does your solver work from 1 and go forward, or from N! and go backward? Does it backtrack, or is it greedy?

I’m considering backwards search w/ backtracking. But, even if addition is limited to very small numbers, I’m finding that there are just too many “viable” ways of factoring out primes. Sometimes it’s best to take out a full square, other times it’s best to leave some terms in because there are tricks to get rid of them. Given p1^n1*p2^n2*p3^n3…, I don’t see a technique to break that in half that consistently produces short programs.

Thoughts? Advice?

 
Flag Post

I have more than one. It’s getting to spaghetti code at this point, too, because I keep adding and changing stuff around. But you’re right about the many ways to go. Trying to enumerate every possibility is doomed to failure. I think when you reach a length of 15 there are several quadrillion possibilities already, and it seems that the best attempts for the later problems have length upward of 20…

As for hints: (2N)! = k * N! is a popular way of extending solutions to larger problems fairly cheaply.
Finding large numbers that can be made cheaply and happen to be one more than a product of cumbersome primes is handy. For instance 104975 is 5 * 5 * 13 * 17 * 19, but is also one less than 18^4, which makes it fast to build.
If you can decompose N! into a^2 * b rather than a * b it usually makes your life easier. And yet sometimes (a^2 – 1) * b or (a^2 – 1) * b^2 * c work better.
The shortest way to a * b may not be a combination of the shortest path to a and the shortest path to b. Sometimes it is shorter to go for a and b together at once, which sucks because such paths would not look attractive at the outset.
If you’re going to explore all options down a path systematically it is a good idea to know in advance what length the solution should be.
Backtracking more than one step is a bit of a nightmare. If you want to go that route think hard about how you’re going to decompose your target.
The last operation even for small factorials is usually a product. But is it always a product?
You only need one solution of the shortest length for each problem. Maybe devising a method that finds them all is not the best use of your time.

 
Flag Post

Many thanks for the tips. What a bizarre optimization problem … I’ve never seen a simple formulation with such an ugly solution space.

Would love to see your code once the contest is over, if you decide to open source it.

 
Flag Post

And the contest is over. I managed an honorable finish for a first-time contestant (top 50), with nothing but a series of AS3 solvers. How about you guys?

 
Flag Post

I gave up and was waiting for the next contest, which it turns out is actually the same as this one was :/
1000!
A rough guess at what the top solution is at the moment: 383 (based on the guy who says his raw score is 1000).
More pressingly, how in the world do I calculate 1000!?
Wikipedia says, 4.0238726008×10^2,567.
I read a bit further, and it says to make an Array with a length of 2568(?) and do the multiplication manually, hence avoiding overflow.

 
Flag Post

Read the instructions carefully, you are not required to ever write down 1000! explicitly, even when registering your solution. As for how to decompose 1000! into a viable sequence, your guess is as good as mine. It’s an almost entirely different problem from the last one, since none of the methods previously used for optimizing sequences can be applied to it. New techniques need to be developed to solve it. Still, I’ve had my fill of factorials for a while and I’m not going to enter that contest. I think I’ll wait for September and the new theme.