hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Any hints?
Goto page Previous  1, 2, 3  Next
 
Reply to topic    hacker.org Forum Index » Modulo Puzzle View previous topic
View next topic
Any hints?
Author Message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
I even tried using a machine with 300gig of memory and 100cpus. Precalculating a lookup table for the smallest 5-6-7 pieces and using the inc-power based early out does not seem to be enough. At least not when you use every tile instead of using a tiles%2 or tiles%3 approach.

I am currently busy with socioeconomic activism (capitalism is a bitch to overcome) but I will look into this later this year and share a few thoughts. Smile
Wed May 28, 2014 4:33 am View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
After talking to 2-3 people I can confirm that they managed to solve levels beyond 44 using a totally different approach than iteration/recursion with pruning/backtracking/early outs. I expected something like that because even with a heuristic that prunes 2/3 of the entire search space lvl 44 already comes with 4.81761e+026 possibilities and would take around 2-3 weeks on 16 cores.

So it's time to learn something new and approach this challenge in a totally new way ... Wink
Tue Sep 16, 2014 6:12 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 333
Location: Praha 5

Post Reply with quote
I have started today with meet in the middle, what was OK for levels upto 30 and with some luck I got to solve even 33. I have looked at level 34 and it's absolutely out of reach of this approach. Fortunately the meet in the middle could be recoded to just provide middle stops. The board 34 clearly provides better methods for early stops (large board*depth). Seems one should find a lot of possible fast stops methods to be able to solve further levels.

Hmmm. I have expected there would be much earlier cuts on level 34 based on number of remaining squares ... or I coded something wrong ... hmmm, I have read the board wrongly:( I tought the depth is 5 Sad. With the depth 3 its natural Wink.
Sun Oct 26, 2014 10:31 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 333
Location: Praha 5

Post Reply with quote
camel wrote:

Code:
my $doc='<param name="board" value="0040040400000,4434244404040,4433242322330,0040443314340,0000004010244,0004043442044,0003434302334,0444334004030,4403334004444,0333400404334,0040044440404,0040004444000,0434000403440,0404000444000"><param name="depth" value="5"><param name="pieces" value=".X.X,XX.X,.XXX,XX.. XXX ..X,XXX,X.. XXX,X..,X.. X,X,X X.X,XXX X..,XX.,.XX XX,XX XX X.X,XXX,X.X .XXX,..X.,XXX. X.X,XXX X..,XXX,..X X XX.X,X..X,XXXX,..X. XX.,.XX X.X,XXX,X.X XX.,.XX X.X,X.X,XXX XXX,X.X,XXX .X..,XX.X,.XXX ...X,X.XX,X.X.,XXX.,X.X. XXX,X.X X.X,XXX XXXX,X...,X... X..,XX.,.XX .XX.,XX..,.XXX XXX.,..XX,XXX.,.X.."><input type="text" name="gotolevel" size="3" value="9999" />';



My solver did it in 1716 ms (when meat in the middle disabled). (With meet in the middle allowed it solves the same board in 1452ms ... after 173957ms filling the meet in the middle tables).

But I am stuck on 38
Code:

3
02121020,11200002,20012211,02100020,22220220,00011120,22110110,01100120
X..,X..,XXX,X.. X..,XX.,XXX,X.X,XX. XX..,.XXX,.XX.,..X.,..X. ...X.,..XX.,..XXX,.XX..,XX... XX..X,XXXXX,.X.X. .XX,XXX,.XX,.XX .XX,XXX,.X. X..,X..,XX.,XXX X...,XXXX,.XXX,XXX.,..X. ..XX.,..XXX,..XXX,XXXXX,.XX.. ...XX,XXXXX,..XXX,..XXX,.XX.. ..XXX,..X..,XXX..,.XX.. ..XX.,.XXX.,XXXXX,XXX.X,..X.. ..XX,XXX.,XXXX,..X. .X...,.XXX.,XXXXX,XXX..,..X.. X.X..,X.X.X,XXXXX,XXX.. X...X,XXXXX

anyways Sad.

For meet in the middle I have tried to maximize the possible table size ... I use zobrist hashing and I just set corresponding bit in the table. (Several board states could address the same bit, but when bit is not set I am sure the position is not solvable). I use 7 tables with halving size each next, addressing by different bits of 64 bit zobrist key. First table (the largest) is for level having about half possible options as is its size. There is probability about 1/2 of false match on the first level, but the probability goes quickly to 0 on next levels as the level sizes decrease much faster than the table sizes.

I am not sure the adressing overhead is worth it and heuristic counting how many squares are opened seems cuts good enough anyways. ... OK seems in levels where more than say 15 squares are left to open the meet in the middle helps.

After really long search I have solved
Code:

3
02121020,11200002,20012211,02100020,22220220,00011120,22110110,01100120
X..,X..,XXX,X.. X..,XX.,XXX,X.X,XX. XX..,.XXX,.XX.,..X.,..X. ...X.,..XX.,..XXX,.XX..,XX... XX..X,XXXXX,.X.X. .XX,XXX,.XX,.XX .XX,XXX,.X. X..,X..,XX.,XXX X...,XXXX,.XXX,XXX.,..X. ..XX.,..XXX,..XXX,XXXXX,.XX.. ...XX,XXXXX,..XXX,..XXX,.XX.. ..XXX,..X..,XXX..,.XX.. ..XX.,.XXX.,XXXXX,XXX.X,..X.. ..XX,XXX.,XXXX,..X. .X...,.XXX.,XXXXX,XXX..,..X.. X.X..,X.X.X,XXXXX,XXX.. X...X,XXXXX

instead. ... Oops ... have I finally solved the original task?

And 39 was trivial ... ForwardTime: 126ms (after BackTime: 54881ms preprocessing).
Probably main reason is ... there exists a lot of solutions ...

I have cheated a bit by choosing easier level when the original looked difficult Wink. So finally I went among 43 level solvers ...

Level 44 is difficult especially because it has only one solution with very high probability. (It has statistically no solution, but one is guaranted by puzzle generator (I hope;)). I have chosen among given boards to have good chance to finish the computation. On previous levels, I have chosen manually from about at most 4 tasks by feel. On level 44 I have chosen from more tasks, I have used some statistics to allow the decision. Seems the chosen task is solvable in less than a day.

Yes ... it was 8h 9m 7s 428 ms forward time, 31s 30ms preprocessing. I have searched more than half of the search space.

Wow second seen task on 45 ... ForwardTime: 13s 191ms, preprocessing time 38s 657ms.

First task on 46 level estimated time 3h ... it is not worth a risk to try other tasks.

After solving 46 (in 56 minutes), I have returned to 38
Code:

3
00220100,22000000,22120100,00211002,22210120,22200010,00011002,00222220
..X,XXX,.X.,.XX,XXX XX.,.XX,XX.,.X. XXXXX,XXX..,XXXX.,.X...,.X... ..X,..X,XXX,.X.,.XX X.X..,XXXX.,.XXXX,.XXXX .XXXX,.XXX.,XXX..,..X.. XX..X,.XXXX ..X..,.XX..,XXXX.,.XXXX,...X. X..,XXX ..XX,..X.,X.X.,XXXX,.XX. X.X,XXX,.X.,.XX,..X .XX..,XXXXX,..XX.,...X.,...X. .X..,XXXX XXXX.,XXXX.,XXXXX,.X... X.X..,XXX..,.XXXX,..XX. ..X..,XXX..,.XXX.,XXXXX,..X.X ..XX,..X.,XXX.
was under 8min ...

And now I can see my solution of 46 was not accepted ... and tasks are much harder now Sad ... OK it was 45 rather than 46.

I have automated task selection ... but I have bug in level selection ... and therefore I have solved levels 47 and 48 several times Wink.

Level 50 seems to be next crucial level?!

Seems I should implement active border size reduction to be able to pass level 55.
... I had already 1/48 of level 55 solved ... and I have decided to restart the search ...

Wow good decision Smile I did it Wink.

But level 56 seems to bee too much ... may be using something faster than java? (Days->Hours would help...)
My attempt on level 56 is to reduce borders by placing several pieces and the task is chosen if the resulting expected solution time is reasonable. This selects one of about 80 tasks ... but the solution times are underestimated as always till now there was no solution in the reduced puzzle:(.
Task selection is much faster than task solving ... may be I should be more strict in the selection process.
Sat Nov 01, 2014 12:09 am View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 333
Location: Praha 5

Post 100 days Reply with quote
After 100 days of permanent single thread trying to find good reduced task (for level 56) and solving still solution not found (about 60 tasks tried).
Mon Feb 16, 2015 6:40 pm View user's profile Send private message
Valar_Dragon



Joined: 04 Jan 2015
Posts: 21

Post Reply with quote
Holy cow, thats quite some dedication. I can't imagine leaving a program running on my computer for 100 days o_O
Mon Feb 16, 2015 11:48 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 333
Location: Praha 5

Post Reply with quote
Fortunately it's in office I am not visiting daily Wink, ... not on my laptop.

Actually I have misestimated ... 100 days anniversary is about 25.2.2015.
Wed Feb 18, 2015 10:56 am View user's profile Send private message
AMindForeverVoyaging
Forum Admin


Joined: 28 May 2011
Posts: 474
Location: Germany

Post Reply with quote
That's still insane. Razz
Wed Feb 18, 2015 8:53 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 333
Location: Praha 5

Post Reply with quote
camel wrote:
After talking to 2-3 people I can confirm that they managed to solve levels beyond 44 using a totally different approach than iteration/recursion with pruning/backtracking/early outs. I expected something like that because even with a heuristic that prunes 2/3 of the entire search space lvl 44 already comes with 4.81761e+026 possibilities and would take around 2-3 weeks on 16 cores.

So it's time to learn something new and approach this challenge in a totally new way ... Wink


Hmmm, I am still fighting with 56 level, and I don't think I have more than early outs combined with meet in the middle and task selection process. I am curious what else the top 3 guys did (exept of massive paralelism?) I still hope they were lucky with task selection on level 56 Wink and remaining levels till 61 are easy.
Tue Feb 24, 2015 6:49 pm View user's profile Send private message
Hckr



Joined: 25 Mar 2010
Posts: 27

Post Reply with quote
If i am right, it has nothing to do with massive parallelism. Should be a property of the puzzle, you can make use of. Its just an idea at this point, but i hope i can overcome my lazyness soon to try it out Smile
Wed Feb 25, 2015 10:09 pm View user's profile Send private message
lvhao945



Joined: 14 Oct 2011
Posts: 18
Location: none

Post Reply with quote
level 44 Twisted Evil
Fri Feb 27, 2015 10:18 am View user's profile Send private message AIM Address Yahoo Messenger MSN Messenger
Fettpet



Joined: 03 Sep 2012
Posts: 4

Post Reply with quote
Hi hackers,

a question about level 38. How long do it calculate to generate a solution? I translate the modulo puzzle into sat and start a sat-solver. In level 38, I test 100 instances with 10h timeout. Zero are solved.

mfg
Fettpet
Mon Apr 06, 2015 9:24 pm View user's profile Send private message
eulerscheZahl



Joined: 29 Nov 2012
Posts: 56
Location: Germany

Post Reply with quote
Hi,
I don't want too run it again, but as far as I know, it took about 8 hours (C#, 64bit single-core application, Intel i7). I tried two or three different puzzles until I found a solution, as I didn't want my computer to run during the night.

I have an idea, how I could probably speed it up a little bit, but I was too lazy to code it until now.
Tue Apr 07, 2015 3:48 pm View user's profile Send private message
Hckr



Joined: 25 Mar 2010
Posts: 27

Post Reply with quote
Mine too (about 8 hours). If you choose a good level instance you should be able to solve it in reasonable time.
Wed Apr 08, 2015 10:53 am View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 333
Location: Praha 5

Post Reply with quote
Fettpet wrote:
Hi hackers,

a question about level 38. How long do it calculate to generate a solution? I translate the modulo puzzle into sat and start a sat-solver. In level 38, I test 100 instances with 10h timeout. Zero are solved.

mfg
Fettpet


Unfortunately I cannot test it as my code is still running on level 56 ... on faraway computer.
May be I will interrupt it to make a test. But I remember level 38 was one of worst.

But I have logs ... it took me 800s on the well chosen task.
It took 1400s on another one. But I think this was the level I start chosing the tasks ... Seems I coded the task selection on level 44, but I have tested it on level 38 (the 800s run).

The code is single threaded java, it was run on intel core i5 laptop. 2.5GHz, 4GB RAM.
Wed Apr 08, 2015 10:09 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Modulo Puzzle All times are GMT
Goto page Previous  1, 2, 3  Next
Page 2 of 3

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.