The Nineteenth Byte

Q: Amount of permutations on an NxNxN Rubik's Cube

7:27 AM

@Anush gams.com/~bussieck/TR-93-01.pdf

New Main Posts

Introduction: A 3x3x3 Rubik's Cube has \$43,252,003,274,489,856,000\$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually calculated? A 3x3x3 Rubik's Cube has six sides, each with nine stickers. Looking at the (extern...

8:11 AM

Unfortunately that still have worst case time complexity Theta(n^2).

8:25 AM

@user202729 Thanks!

@user202729 is that saying that if the input is random it will run in O(n log n) time on average?

Yes, I think.

I didn't read the proof in the paper, just the result.

@user202729 also, is there a proof that max, + convolution can be solved using my max subarray problem?

the other way round is clear

in other words, are the equivalent?

Yes. Put a very large middle element, and spread the 2 other arrays as partial sum over the two halves.

max,+ convolution takes 2 arrays as inputs. Let's call them A and B. So we make a new single array (let's call it C) for the max subarray problem where we first put a very large middle element and then what else goes in C?

maybe it's a code-golf question in hiding :)

Something such that each subarray sum of length k correspond to some a[i]+b[k-i-1].

To the left is consecutive difference of a in reverse order and to the right is consecutive difference of b, I guess.

8:36 AM

what is the role of the very large middle element?

To ensure that the maximum subarray contains it.

I am a little consider. Can we try it with an example? Say A = [2, -1, 4] and B = [3,-2, 5]

what is C?

We can't get a corresponding a[i]+b[k-i-1] pair if the subarray lies entirely in one half.

that is true

ok so I see the middle element is there to make sure every max subarray always crosses the middle

[(4 - -1), (-1 - 2), LARGE, (-2 - 3), (5 - -2)], I think.

8:46 AM

let k = 2, In the max,+ problem we get 2+5=7 and 4+3 = 7

in the max subarray problem after the reduction we get....?

(I am using k as in (1) from gams.com/~bussieck/TR-93-01.pdf )

The subarray [LARGE] correspond to 2+3, [-1-2,LARGE] correspond to -1+3; [4--1,-1-2,LARGE] correspond to 4+3.

9:36 AM

Hey, would this work as a challenge? Given two words e.g. overflow and stack, determine their "correct" order by searching for "stack overflow" (right now for me 58M results on Google) and "overflow stack" (60K) and determining which is more popular. Return stack overflow (joined) or ["stack","overflow"] (=ordered) [2,1] (=indices of correct order) or false (=not right order) etc. in this case.

Any search engine or similar (e.g. Google Ngram viewer, Google Trends,…) is OK.

@user202729 thanks. I will go through this carefully later on

Fatalize

@Adám The main problem I see is that your byte count will heavily depend on how easy it is to parse the number of results depending on the search engine

@Fatalize So? The challenge is not just to select programming language and code in it, but also to find an appropriate search engine which gives results that are short for your chosen language to parse.

Of course, the actual web access needs to be golfed too.

Expired Data

@Adám won't this suffer issues of code being external

e.g. if what if i make my 'search engine' website which has a super short url and returns the order?

Fatalize

@Adám You can't control the search engine so your answer can become invalid independently of your own code

9:49 AM

@ExpiredData Why? There are already challenges that requires the program to "go online"

Expired Data

Sure, I guess I mean what defines a search engine..

@ExpiredData Had to exist as of challenge posting.

@Fatalize True, but true for all online services.

Expired Data

I don't think that's enforceable, i.e the engine might exist but what if new functionality is added to support it?

so the service has to exist as of challenge posting and the behaviour of the service can't have changed?

got an example of a challenge that needs you to go online? What about things like URLs which resolve in certain e.g. countries but not in others?

@ExpiredData 73