Nice problem!
I would have solved it like this:
octa1=: [:({.,#)/.~(i.@! ([: <./ 3 +/\ ,~)@A. >:@i.@])
Although probably not a good way of explaining it to non-J people.
It basically does the same as yours (I guess, you didn't share perm), but
simplified the repeating of the edge by just doubling the permuted list
(,~) and taking the minimum directly after the sum.
At the end it presents a nice summary with minimum sum and count of all
permutations.
Actually, even better in time, worse in space:
octa2=:({.,#)/.~ ([: <./ 3 +/\ ,~)@|:@:(i.@! A. >:@i.@])
When doing it this way, the overhead of doubling does become measurable:
octa3=:[:({.,#)/.~ ([: <./ 3 +/\ (,2&{.))@|:@:(i.@! A. >:@i.@])
10×pacex&> 'octa1 8';'octa2 8';'octa3 8'
0.182377 525632
0.0286247 1.28458e7
0.0256948 8.65149e6
I presume this is because the overhead of doing the counts and duplication
is done only once.
Best regards,
Jan-Pieter
On Sun, Mar 14, 2021, 23:01 Skip Cave <[email protected]> wrote:
> I found this problem on Quora. I had fun solving it in J. Are there more
> efficient ways?
>
> The first 8 natural numbers (1 to 8) are positioned on the vertices of an
> octagon. Is it possible to position the numbers such that the sum of any 3
> adjacent vertices is greater than 11? Greater than 13?
>
> Using the J programming language, brute force approach:
>
> Wikipedia: "J (programming language)"
>
> J primitives: NuVoc - J Wiki <https://code.jsoftware.com/wiki/NuVoc>
>
> Generate all permutations of the integers 1–8, & store them in n. Count the
> permutations & display the count:
>
> $n=.|:>:perm 8
>
> 8 40320
>
> So n contains the 40,320 possible permutations of the integers 1–8,
> representing all the possible permutations of the numbered vertices of an
> octagon.
>
> Now sum consecutive sets of three integers from each set of 8 integers with
> wraparound, which will create sets of 8 sums, and store the sums in s3.
> Count the sums & display the count:
>
> $s3=.+/"1[3,\"1|:n,2{.n
>
> 40320 8
>
> So s3 has 40,320 sets of 8 sums, where each set of 8 sums represents the 8
> sums of 3 adjacent vertices on each unique octagon.
>
> Now mark all the octagons have all their 3 consecutive vertex sums greater
> than 11, sum the marks, and list the sum:
>
> +/m=.*./"1[11<"1 s3
>
> 320
>
> So 320 of the 40,320 possible octagons have all their 3 consecutive vertex
> sums greater than 11:
>
> Use the mark vector to extract & display the first & last few sets of
> octagon vertices whose 3 consecutive vertex sums are greater than 11:
>
> {m#|:n
>
> │1 4 7 2 5 6 3 8│1 4 7 2 6 5 3 8│1 5 6 2 4 7 3 8│1 5 6 2 7 3 4 8│1 5 6 2 7
> 4 3 8│1 5 6 2 8 3 4 7│1 5 6 3 7 2 4 8│1 5 6 3 8 2 4 7│1 5 6 4 2 7 3 8│1 5 6
> 4 7 2 3 8│….
>
> …..│8 3 5 6 2 7 4 1│8 3 6 4 2 7 5 1│8 3 6 5 1 7 4 2│8 3 6 5 2 7 4 1│8 3 7 2
> 4 6 5 1│8 3 7 4 2 6 5 1│8 4 2 7 3 5 6 1│8 4 2 7 3 6 5 1│8 4 3 7 2 5 6 1│8 4
> 3 7 2 6 5 1│
>
> How many octagons have all their 3 consecutive vertex sums greater than 13?
>
> +/*./"1[13<"1 s3
>
> 0
>
> There are no octagons whose 3 consecutive vertex sums are all greater than
> 13.
>
> How many octagons have all their 3 consecutive vertex sums greater than 10?
>
> +/*./"1[10<"1 s3
>
> 3456
>
> So 3,456 octagons of the 40,320 possible octagons have all their 3
> consecutive vertex sums greater than 10.
>
> Skip Cave
> Cave Consulting LLC
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
