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

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

Replies are listed 'Best First'.
Re^4: Pattern enumeration.
by BrowserUk (Patriarch) on Jul 28, 2010 at 13:22 UTC

    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]
[reply]
[d/l]
Re^4: Pattern enumeration.
by BrowserUk (Patriarch) on Jul 30, 2010 at 15:44 UTC

    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]

        I'd already switched to the second version, but not the third. When you posted the third version, I roughly calculated that the time that the second version had already been running more than offset the further 25% saving of switching, so I stuck with it.

        A day or so later I saw your revised runtime estimates. At that point I suspended the process for a while, but then decided to let the code run to completion. It has currently clocked up 100 hours.

        If I am interpreting your numbers correctly--13000 * .6 /60 = 130--it should complete here sometime Wednesday.

        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]

In Section Seekers of Perl Wisdom