FAQ  •  Login

Level 32

Moderators: UncleTimmy, mjpieters

Enjoying the challenge? Need a hint?
Make a donation and help keep the site running! -thesamet
<<

new2py

Posts: 7

Joined: Thu Jun 30, 2005 5:39 pm

Post Sun Jul 03, 2005 10:05 pm

Level 32

I love these sorts of puzzles, but I'm a bit embarrassed that I was reduced to writing a second solver in C, when the Python version proved too slow after all my optimisations :(

A hint for those who have been waiting a few days for a solution to be found: there are a couple of different algorithms you can use here, one of which scales really well. If you get bored, try a dramatically different approach.

PS., the Javascript doesn't work correctly in Safari - particularly on the third page :(
<<

mjpieters

Site Admin

Posts: 172

Joined: Wed May 04, 2005 8:56 am

Location: Norway

Post Mon Jul 04, 2005 12:15 am

Re: Level 32

new2py wrote: the Javascript doesn't work correctly in Safari - particularly on the third page


Botheration! It works fine in konqueror.... It's all standard ECMAscript and DOM.
<<

mfuzzey

Posts: 5

Joined: Mon Jun 06, 2005 3:25 pm

Location: Besancon, France

Post Tue Jul 05, 2005 2:49 pm

How slow?

How long *should* it take in python?

My first attempt ran all night and consumed huge quantities of memory :)

Much more aggressive pruning made the warm up solution run about 10 times faster - the serious one has been running 15 minutes and is still going...

Martin
<<

new2py

Posts: 7

Joined: Thu Jun 30, 2005 5:39 pm

Post Tue Jul 05, 2005 3:25 pm

Timings

Well, on my G4 powerbook the C version of the brute-force solver took about 40 seconds on the second puzzle.

My Python solver improved in performance more than 50x through optimisation, but didn't come close to solving the second puzzle due to obscene memory usage - it didn't get more than two levels deep.

All I can recommend is:
1. To further improve your current solution, minimise memory usage as much as you can.
2. Think about radically different algorithms for solving the problem - there is one which will solve it in seconds, even in Python.
3. If all else fails, do what I did and write a highly optimised version in a different language.
<<

DJohn

Posts: 8

Joined: Thu May 12, 2005 6:33 am

Post Wed Jul 06, 2005 2:41 am

There is a fast algorithm that isn't much more complicated than the dumb brute force one. My totally-unoptimised-who-cares-about-speed Lua implementation solved the big one in 45 seconds.

Work in two directions. Work on one thing at a time.

Use what you know to find all possibilities for each piece. Your knowledge comes from more than one place.

Increase your knowledge at every opportunity.

Or you can cheat and google for someone's ready-made solver.

This was a good level. It was the first that felt (to me) like it needed some real programming.
<<

UncleTimmy

Posts: 118

Joined: Thu May 05, 2005 3:44 pm

Post Thu Jul 07, 2005 8:16 am

Re: How slow?

mfuzzey wrote:How long *should* it take in python? ...


There are two quite different Python programs on the solutions Wiki today that solve "the big one" in less than a second (on fast boxes), at least one of them including the time to display progress-so-far using Tk.

Both of those are non-trivial programs. This level is much more (than previous levels) about coming up with a "good" algorithm. My first program to solve this would not have finished over the age of the universe (there's a discussion of that on the Wiki :wink:). My second solved the big one in about 3 hours, including time to prove that the solution was unique. My third attempt cut that to about 3 minutes. My current fastest Python program solves it in less than a fifth of a second (with Tk progress-so-far updating disabled; about 0.6 seconds with Tk updating).

So if you can get the solution using Python in somewhere between a fraction of a second and the lifetime of the universe, you're doing exactly as well as I did :wink:.
<<

ajohnson

Posts: 38

Joined: Fri May 13, 2005 2:16 pm

Post Thu Jul 21, 2005 9:04 am

hmm, my brute force approach solved the little one in less than a second. The big one has been running over night. As an exersize to figure out the scope of this I tried to work out how to calculate how many figures I'd be going through. The little one came out to 10500, which appears to be right. The big one, however, came out to 82328990834424911796572570759111661840585435283304767104151084911820800000000000000000000000.

I'm not sure if that's correct, but I'm only on #42209000. I guess I'll have to re-write for some pruning :)
<<

UncleTimmy

Posts: 118

Joined: Thu May 05, 2005 3:44 pm

Post Thu Jul 21, 2005 1:48 pm

ajohnson wrote:... The big one, however, came out to 82328990834424911796572570759111661840585435283304767104151084911820800000000000000000000000.

I'm not sure if that's correct, but I'm only on #42209000. I guess I'll have to re-write for some pruning :)

You'll eventually see that same number again, on the solutions Wiki. Unfortunately, it appears in a discussion of why my first algorithm would not have completed over the lifetime of the universe :wink:.
<<

ajohnson

Posts: 38

Joined: Fri May 13, 2005 2:16 pm

Post Fri Jul 22, 2005 7:23 pm

Well, I rewrote my brute force version in c , and while it ran much faster, the universe would still end. I added pruning and it got better, but it would've probably still taken days. Aggressive googling finally turned up a few algorithms (had to figure out what to look for), which I was able to translate into a script that ran in 1.25 seconds :)

I'm going to re-read my code a few times until I understand it completely while I also stare at #33 :) So far I know that it works in two directions, along with a few other tidbits of info that would probably be spoilers to anyone not actually on #32
<<

Nic

Posts: 4

Joined: Thu Oct 20, 2005 5:28 am

Post Mon Mar 06, 2006 7:14 am

I wrote a Pascal program that solves the second puzzle (32x32 one) in 2-3 seconds. But when I try the URL it _looks_ like I get a 404. The solver works, though... hmmm.. does that thing have a name I should know?
<<

newfweiler

Posts: 4

Joined: Thu Mar 22, 2007 1:41 pm

Post Wed Apr 04, 2007 9:46 am

Solved it!

There is a specific word for that thing. You've seen the word enough times.

I figured out a way to solve the puzzle efficiently for the big one. My program that solved the little one would have taken centuries to solve the big one. I thought of a way of reducing the possibilities, figuring I'd get down to a manageable size. As it turned out, I could apply this over and over and it eventually reduced the possibilities to 1. I haven't tried to prove whether this will work in all cases.
<<

Sam13

Posts: 1

Joined: Thu Jul 22, 2010 10:49 pm

Post Tue Jul 27, 2010 10:08 pm

Re: Level 32

Hello.........

Much more aggressive pruning made the warm up solution run about 10 times faster - the serious one has been running 15 minutes and is still going..

Thanksss.........
best way to get rid of acne

Return to Python Challenge Hints

Who is online

Users browsing this forum: No registered users and 4 guests

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.