Fibo challenge

14 posts / 0 new
Last post
Mark
Offline
Joined: 2007-03-06
Fibo challenge

I made this remodel when dealing
with fibo levels.


  

Title: Fibo Challenge
Author: Dries de Clercq and Minglw and Marko Dzekic


  

W. M. Dekker
Offline
Joined: 2004-12-26

What can I do with this "Remodeled" level?
Where can I find that? In wich collection?
What does this message mean?

Mark
Offline
Joined: 2007-03-06

I've sent you an e-mail.

W. M. Dekker
Offline
Joined: 2004-12-26

Mark,
I stored and printed the "Fibo challenge level.txt" you send to me.
I also copied the "Fibo challenge level" collection. Level 1: 1" into
my map: C:\Sokoban\Levels
I wil give it a try. I let you know.
Kind regards,
Wim Dekker

minglw
Offline
Joined: 2005-10-20

Before you spend lots of time on this level....

just want to warn you that this levels requires lots of time even to just watch the solution. (assuming you have the solution already, of course)

The best known solution for this level requires 6170760 pushes and 18299781 moves. (yes, that's 18 million+ moves)

So, assuming you're watching the solution at 100 moves per second, it will take a little more than 50 hours to see the entire solution.

Mark
Offline
Joined: 2007-03-06

I didnt solve the level manualy, since this would take
to much time but I've built the LuRd using wordpad.

FIBO LEVELS LURD ALGORITHM

GLOBAL SOLVE

n =number of all boxes
n-2 =boxes in vertical line
2 =boxes aside
rescue boxes = M = (n/2)-1
n=2x(M+1)

------------------------------------------------------

GLOBAL LURD BUILDING

1 = (rDDDLU)x1

2 = (rdDDLU)x((n/2)-3)= (rdDDLU)x(M-2)

3 = RESCUE BOXES 1+2+3+4+...+M

4 = rdL

------------------------------------------------------

RESCUING BOXES

BOX 1 (BASIC LURD)

drrddLLUlldRdrUrruulDuullDDRUdlldRdrUluurrrddLLUlldRdrUrruulD

BOX 2

= ux4,ll,(DDRUdl)x1,DD,Basic2.

which is:

uuuullDDRUdl
DD
RUdddlUluRurrrddLLUdrruulDlddlUluRuuurrD
DLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluR
urrrddLLUlldRdrUrruulD

BOX 3

= ux6,ll,(DDRUdl)x2,DD,Basic2,
(LdlluR),ux5,rr,(DDLUrd)x1,DDLU,rescue box 1+2.

BOX 4

= ux8,ll,(DDRUdl)x3,DD,Basic2,
(LdlluR),ux5,rr,(DDLUrd)x1,DDLU,rescue box 1+2,
(LdlluR),ux7,rr,(DDLUrd)x2,DDLU,rescue box 1+2+3.

RESCUE ANY BOX:

BOX-A (three steps):

u x (Ax2),ll,(DDRUdl)x(A-1),DD,

basic2=
RUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUll
dRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulD,

(LdlluR),ux5,rr,(DDLUrd)x1,DDLU,rescue box 1+2,
(LdlluR),ux7,rr,(DDLUrd)x2,DDLU,rescue box 1+2+3,
(LdlluR),ux9,rr,(DDLUrd)x3,DDLU,rescue box 1+2+3+4,
................
(LdlluR),u x ((Ax2)-1),rr,(DDLUrd)x(A-2),DDLU,rescue box 1+2+3+...+(A-1).

W. M. Dekker
Offline
Joined: 2004-12-26

Mark,
Sorry, I basicly understand how you created the solution, using an algorithm.
But for me: It's to long ago, that I used my brains on this mathematical level.
So, I'll stop whith this level, certainly after the warning of Minglw.

Maybe you can send me the whole LuRd - solution, by sending that as a wordpad txt document.
I will not spend 50 hours, watching the total solution, but certainly how one colomn is solved.

Thanks in advance.

minglw
Offline
Joined: 2005-10-20

I don't think anyone solved this level did it manually.
It's just too much work and time.

About a little over a month ago, I wrote a program basically to find solutions for FIBO levels of this type...

; I noticed there are at least two different Fibo level configurations,
; one has an even number of boxes and one has an odd number of boxes.
; I called this the even style Fibo level.

All levels below even style Fibo levels.

; even style
; 4-boxes


  

; even style
; 6-boxes


  Level: '4' Nr: 4 Collection: '81'

; even style
; 8-boxes


  Level: 'PICOKOSMOS 17' Nr: 17 Collection: 'Pico Cosmos'

; even style
; 10-boxes


  

Using the program I've created, I was able to collect the info in the table below.

=================
Further analysis:
=================

---------------------------------------------------------------------------------
| N-Boxes level | Total Pushes | Total Moves |
|---------------|-------------------------------|-------------------------------|
| 4 | 15 | 48 |
|---------------|-------------------------------|-------------------------------|
| 6 | 57 | 170 |
|---------------|-------------------------------|-------------------------------|
| 8 | 167 | 494 |
|---------------|-------------------------------|-------------------------------|
| 10 | 455 | 1,346 |
|---------------|-------------------------------|-------------------------------|
| 12 | 1,209 | 3,580 |
|---------------|-------------------------------|-------------------------------|
| 14 | 3,183 | 9,432 |
|---------------|-------------------------------|-------------------------------|
| 16 | 8,351 | 24,756 |
|---------------|-------------------------------|-------------------------------|
| 18 | 21,881 | 64,878 |
|---------------|-------------------------------|-------------------------------|
| 20 | 57,303 | 169,922 |
|---------------|-------------------------------|-------------------------------|
| 22 | 150,039 | 444,934 |
|---------------|-------------------------------|-------------------------------|
| 24 | 392,825 | 1,164,928 |
|---------------|-------------------------------|-------------------------------|
| 26 | 1,028,447 | 3,049,900 |
|---------------|-------------------------------|-------------------------------|

(NOTE: blanks are not displayed properly, if you copy the info above and paste it onto an editor, the table lines up properly.)

The level you created, the man's position is off by one from the levels I've analyzed. So, for the 26-boxes sub Fibo levels, the number of moves required is 3,049,899.

I saw your script but I haven't used, no clue how many moves/pushes it produces.
Also, how long does it take your script to produce the solution for, say, the 50-boxes FIBO level ?

Mark
Offline
Joined: 2007-03-06

You dont have to watch the solution.
Bjorns new program can not only turn off the players movement,
but can also jump instantly to a finish.

Mark
Offline
Joined: 2007-03-06

To Ming:

This string is not ideal.
At 26 boxes it gives 3.115.585 moves, but the optimal is
3,049,900.

The good part of it is that I can make a string to a rescue box in
about 2 minutes. I've done it up to 26 box.

So:
28 box (12th rescue).....2 minutes
30 box (13th rescue).....4 minutes

The problem is that wordpad gives up at 12th rescue,
and notepad after 14th rescue.

minglw
Offline
Joined: 2005-10-20

Hi Mark, thanks for the info.

I found that for every two boxes added, the amount of pushes/moves (and time) required is roughly 2.6180339 (1+golden ratio) times.
This is probably true as N (the number of boxes) approaches infinity.

When I first finished the program, I thought it would be nice to get the solution (or even just find out the number of pushes/moves required) for all level up to 100-bxoes. Of course, I found out quickly that would be difficult (at least with the program I have at the time).

My program writes the output to the standard output (screen) so there's really no limitation on the solution size. The output can be redirected to a file if one wants to save it.
My first version of the program runs slow, it took 57 minutes and 26 seconds to produce the solution for the 46-boxes FIBO level.

And if you figure that for every 2 boxes added, it will increase by roughly 2.618 times, then when you get to 100-boxes, it takes a long long time for the program to run.

So, I am not surprised to hear you say that your script didn't get to the 50-boxes levels.

After many optimizations to my program, now it can find out the number of moves/pushes for all FIBO levels under 150-boxes within a second.
(of course, my program doesn't print out the solution, because doing I/O takes lots of time.) It just calculates the pushes/moves. (but it also verifies the solution as well... so, it's not just adding numbers.) Basically, it solves the level and counts the moves/pushes. I added caching to speed up the program.

Pages