Puzzles/Joy of n
Posed by Jose Mario Quintana.
A few days ago while riding the train back from work I stumbled upon Scott Kim's The Joy of Six boggler in the July issue of the Discover magazine. There was a picture of six books numbered 1 2 3 4 5 6 on a shelf followed by the text:
"Six books sit side by side on a shelf. Put the books in order so that the sequence of the numbers on their spines satisfies the following conditions:
1. [Easy].
2. [Easy].
3. [Challenging] Rearrange the books yet again so that adjacent book numbers form two-digit numbers that cannot be divided by 3, 4 or 5. For instance, the order 1-2-3-4-5-6 fails on several counts: The two-digit number 12 divides evenly by 3 and 4; the number 45 divides evenly by 3 and 5; and 56 divides evenly by 4."
However, "challenging" depends whether or not one has J in a pocket (pc). Furthermore, one can define a general verb JoyOf=. ... so that JoyOf 6 solves, in particular, the puzzle above. A spoiler follows several lines below.
Solution 0
test=. -.@(0&e.)@,@(2: |~&.]/&3 4 5@".@(,"2)@:(":"0)\ ]) anagrams=. i.@! A. i. JoyOf=. (test"1 # ])@(anagrams { >:@i.) f. JoyOf (-.@(0&e.)@,@(2: |~&.]/&3 4 5@".@(,"2)@:(":"0)\ ])"1 # ])@((i.@! A. i.) { >:@i.) JoyOf 6 5 3 1 4 6 2
However, to continue the sequence,
(#@JoyOf"0) 2 3 4 5 6 7 8 9 0 1 2 0 1 2 30 208
one would require a different approach...
Solution 1
The puzzle can be solved effectively using methods similar to those for solving the n queens problem, which is also a problem of selecting permutations of order n satisfying particular properties.
For example, for n=:9 , it is obvious that
1 2 ...
is not going to work (12 is divisible by 3 and 4; queens on (1,1) and (2,2) would attack each other), but there are !7 permutations beginning with 1 2, and it is wasteful to generate all of them only to discard them.
J2=: 4 : 0 t=. 1+(n,n)#:i.*:n=.y t #~ (~:/"1 t) *. *./ 0 ~: (,x) |/ -.&' '"1&.": t ) JoyOf1=: 3 4 5&$: : (4 : 0) n=. y if. 2>n do. i.0,n return. end. t=. x J2 n x=. ((~.{."1 t)i. i.1+n) { (</./|:t),a: for. i.n-2 do. t=. t ((#&>@] # [) ,. ;@]) ({:"1 t){x t=. t #~ *./@~:"1 t end. t )
This version accepts a left argument of the divisors (3 4 5 are used if the left argument is elided). It builds the solution one column at a time, starting with 2 columns. The new column uses only those values that, when combined with the last existing column, would not form multiples of the divisors. Then rows with duplicate entries are removed.
Solution 2
For N>9 soltion is given by
JoyOfGreaterThan9=:[: i. 0: , ]
Proof: for any permutation either 10 or 5 is not in the leftmost position, there fore 10 #.n 10 or 10 #. n 5 is divisble by 5
So, the sequence above extends to
0 1 2 0 1 2 30 208 0 0 0 0 0 ....
Contributed by Roger Hui, with further contributions by Andrew Nikitin.