in reply to Re: Pattern enumeration.
in thread Pattern enumeration.

It can solve the 6x6 case, with 6 symbols in two minutes in my computer.... it should be able to solve the 8x8,6 case in 5000 minutes,

Um. 6x6x6 is 6^36; 8x8x6 is 6^64. 6^64 / 6^36 = 6140942214464815497216 *2 minutes = A very long time :)

Discovering the logic behind is left as an exercise to the reader ;-)

Of course, maybe it is a non-linear algorithm. But it will take me a while to discover the logic :)

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
RIP an inspiration; A true Folk's Guy

Replies are listed 'Best First'.
Re^3: Pattern enumeration.
by salva (Canon) on Jul 28, 2010 at 12:29 UTC
    Um. 6x6x6 is 6^36; 8x8x6 is 6^64. 6^64 / 6^36 = 6140942214464815497216 *2 minutes = A very long time :)

    That would be true if I had used the brute force algorithm that has complexity O(SN2) or worse... but I had not used it!

    My solution has complexity O(N2S2N) so, roughly, t6x6,6 = k*62*62*6 = 2min, so k = 2/78364164096 and t8x8,6 = k*82*62*8 = 180551034077184*2/78364164096 = 4608min

    My solution has complexity O(N22NS2N) so, roughly, t7x7,6 = k*72*27*62*7 = 139min, so k = 139/A and t8x8,6 = k*82*62*8 = 180551034077184*139/A = 13000min

[reply]

      Seems we have a winner. At least the 6x6x6 case result gels very nicely with the result from my random approximator: 

      C:\test>salva-pc.exe 6 6
the number of patterns is: 000009db3f0a5d231378f10a55ce

C:\test>perl -E"say 0x9db3f0a5d231378f10a55ce / 6**36"
Integer overflow in hexadecimal number at -e line 1.
0.295742865234832

c:\test>851480 -I=1e7 -D=6
  10000000  0.295624800000000

      [download]

      I'll leave the 8x8x6 case running while I sleep.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
        A new version of the program that reduces computation time by 60% pruning the search tree earlier and by exploiting a new symmetry.
        Read more... (9 kB)
        It solves the 7x7,6 case in 68 min
[reply]
[d/l]

      Hm. 9 days huh. I've suspended the run a gnat's cock shy of 2 days runtime while I decide whether I really need to know this exactly.

      BTW. T'would have been nice if you had brought this update to my attention when you posted it.

[reply]
        That was for the first version, the later one runs much faster. Actually it took it 2600 minutes to solve the 8x8,6 case: 
        $ time /tmp/pc 8 6
the number of patterns is: 00000003e2e2292feeb6f4b8019b3e59cd564cb95ff
+f38e0

real    2591m18.080s
user    2591m17.920s
sys     0m0.150s

        [download]

        update: 0x3e2e2292feeb6f4b8019b3e59cd564cb95fff38e0 is 5679780382528065079883438054186157407164239395040 or 5.679780382528065079883438054186157407164239395040e+48

[reply]
[d/l]

In Section Seekers of Perl Wisdom