14
\$\begingroup\$

Challenge

Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers are next to each other. The value of a permutation pi is the sum of abs(pi[i] - i) for all indices i.

Examples

  • (1, 3, 0, 2) has value 6
  • (0, 2, 4, 1, 3) has value 6
  • (0, 2, 4, 1, 3, 5) has value 6
  • (0, 2, 4, 1, 5, 3, 6) has value 8

Score of your answer

The score of your answer is the sum of the values of your permutations for n = 4 .. 14 plus the number of bytes your code takes. The lower the score, the better. Your code must give valid output for all those values of n.

You must be able to run your submission to completion on your machine.

In case of ties, time of last edit that resulted in the relevant score will be the decider.

Isn't this the same question as this one?

Answers to the linked question will not be competitive for this question as they make no effort to optimize the value of a permutation. For example for n=10, the permutation [1, 3, 5, 7, 9, 0, 2, 4, 6, 8] given by most of the answers there gives a value of 30. You can do much better than that.

For the permutation part of the question, the optimal value overall is at most 120. (Thank you to @Laikoni.) Whereas Dennis's answer to the previous question scores 222. (Thank you to @user202729.)

\$\endgroup\$
  • 4
    \$\begingroup\$ @JoKing every answer can be ported without any changes, but would score terribly bad in this challenge. Posting that code in this challenge is equivalent to posting code from code-review to a code-golf challenge. \$\endgroup\$ – Stewie Griffin May 15 '18 at 8:25
  • 2
    \$\begingroup\$ Mixing different quantities in the score can indeed be problematic. The answer with the best algorithm can usually be ported over to any language, in which case the scoring reduces to normal code golf. \$\endgroup\$ – Angs May 15 '18 at 8:57
  • 4
    \$\begingroup\$ The optimal values are [6,6,6,8,10,12,12,12,14,16,18] for a score of 120. Interestingly this pattern can be found in A078706. \$\endgroup\$ – Laikoni May 15 '18 at 9:46
  • 3
    \$\begingroup\$ Ok, it starts to differ from A078706 with n=17, which can have a score of 20. \$\endgroup\$ – Laikoni May 15 '18 at 10:01
  • 4
    \$\begingroup\$ I can understand the challenge clearly and unambiguously. If you disagree and vote to close, leave a comment here. \$\endgroup\$ – user202729 May 15 '18 at 13:53
7
\$\begingroup\$

Jelly, 36 34 33 32 31 30 bytes, result: 120

Thanks to Dennis for -1 byte! (implicitly by fixing a Jelly bug, although the feature postdates the challenge)

ðRḟISị“Ƥ¿‘Ʋœ?$;@µ2x5~4¦ṁ_4$Ä’

New feature: accumulated sum (Ä).

Try it online!

Use 1-indexing.

Takes linear time, too.


This C++ program generates the lexicographically smallest permutation, assuming that |i - pi| ≤ width (where width is a hardcoded constant) for all 0 ≤ i < n, with time complexity about O(width2 × 22×width × n) (which is just O(n) for fixed width): Try it online!


How?

  1. Write a C++ program attempting to solve the problem optimally.
  2. Observe the pattern. We note that the sequence of all elements except 4 last ones is a prefix of

    0 2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 17 19 16 18 20 22 24 21 23 25 ...
    
  3. Computes the sequence's incremental difference.

    2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2
    

    Note the period 5.

  4. The Jelly implementation:

    • n-4 first elements are taken from the sequence above. O(n).
    • For 4 last elements, just brute force all 24 possibilities. O(1).

      (note: I no longer brute force all 24 possibilities from the 32-bytes version)

\$\endgroup\$
  • \$\begingroup\$ Ah, you went with a different prefix to me. Mine starts 0 2 4 1 3 5 8 6, and has a bigger branching factor but doesn't have such a simple pattern. \$\endgroup\$ – Peter Taylor May 15 '18 at 14:13
7
\$\begingroup\$

CJam (60 bytes + 120 = 180 score)

{_5/4*8e!961=7_)er<:A\,^e!{A\+}%{2ew::-:z1&!},{_$.-:z1b}$0=}

Online test suite with integrated scoring

Extension up to n=24

Dissection

{
  _5/4*        e# Work out how much of the hard-coded prefix to use
  8e!961=7_)er e# Prefix [0 2 4 1 3 5 8 6]
               e# I identified this by brute forcing up to n=10 and looking for patterns
               e# I then used the identified prefix [0 2 4 1] to brute-force further
  <:A          e# Take the desired prefix of the hard-coded array, and store a copy in A
  \,^e!        e# Generate all permutations of the values in [0 .. n-1] which aren't in A
  {A\+}%       e# Prepend A to each of them
  {            e# Filter...
    2ew::-     e#   Take each difference of two consecutive elements
    :z         e#   Find their absolute values
    1&         e#   Test whether 1 is among those absolute values
    !          e#   Reject if it is
  },
  {            e# Sort by...
    _$.-       e#   Take pairwise differences of permutation with the identity
    :z         e#   Absolute values
    1b         e#   Add them (by interpreting in base 1)
  }$
  0=           e# Take the first
}
\$\endgroup\$
  • \$\begingroup\$ Very impressive! I look forward to discovering how you did it. \$\endgroup\$ – Anush May 15 '18 at 10:34
  • \$\begingroup\$ Is it optimal all the way up to 24? \$\endgroup\$ – Anush May 15 '18 at 13:55
  • \$\begingroup\$ @Anush According to my program, likely. \$\endgroup\$ – user202729 May 15 '18 at 14:01
  • \$\begingroup\$ @Anush, I haven't proven it so, but I believe it likely. \$\endgroup\$ – Peter Taylor May 15 '18 at 14:02
  • \$\begingroup\$ I am even more intrigued by your algorithm! \$\endgroup\$ – Anush May 15 '18 at 14:08
6
\$\begingroup\$

Haskell, 146+89 score+bytes

f i|k<-mod i 4=scanl(+)1$take(i-2-k)(cycle[2,-3,2,3])++[[2],[2,2],[5,-3,2],[5,-3,2,2]]!!k

Repeats pattern [1,3,0,2], last mod i 4 elements are hand tuned.

Previous algorithm (132+116):

f i=last$filter(\a->all(`elem`a)[0..i-1]).(!!(i-1)).iterate((\l->map((:l).(+head l))[-3,2,-2,3])=<<)$pure<$>[i-3..i]

Bruteforces the correct number of jumps of length ±2 or ±3. Selects the last one that has the correct numbers in it, seems to work just fine and is a lot cheaper than implementing the score. Tio just runs out time before the last score, which is 18.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 120 + 20 = 140

(Copying one of my solutions from the other challenge would have scored me 227)

o á k_äa d¥1ÃñxÈaYÃg

Try it or use this version to check scores. Both versions may start crapping out on you around 9.


Explanation

o                        :Range [0,input)
  á                      :All permutations
    k_      Ã            :Remove sub-arrays that return true
      äa                 :  Get the consecutive absolute differnces
         d¥1             :  Do any equal 1?
               È  Ã      :Pass the integers in each remaining sub-array through a function
                aY       :  Get the absolute difference with the integer's index
              x          :Reduce by addition
             ñ           :Sort the main array by those values
                   ñ     :Return the first sub-array
\$\endgroup\$
  • 9
    \$\begingroup\$ "You must be able to run your submission to completion on your machine." Did you seriously manage to process 87E9 permutations of 14 elements in the two hours since the question was posted? \$\endgroup\$ – Peter Taylor May 15 '18 at 10:16
  • 3
    \$\begingroup\$ Besides, consider that Japt is based on Javascript, can it really handle 87E9 permutations? This question say that Javascript array can have length of at most ~4E9. Does Japt have generating function or something...\ \$\endgroup\$ – user202729 May 15 '18 at 13:56
2
\$\begingroup\$

Ruby, 120 score + 112 106 91 82 bytes

->n{(0...n).map{|a|a+(a+2)%5-([[],[],[0,4,3],[-1,4,4,4],[1,1,6,1]][n%5][a-n]||2)}}

Try it online!

The sequence is basically (a-2)+(a+2)%5.

If n mod 5 is not 0 or 1, the last 3 or 4 elements are different.

This is still half-hardcoded, always finds the best solution, maybe it could be golfed a little more, but I have run out of ideas.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 148 score + 109 73 bytes

n=>[...Array(n)].map(_=>l=!m|l>n%5+2&&l>m+2?[+m,m=l+2][0]:l+2,m=n>4,l=~m)

Try it online! Explanation: l keeps track of the last number generated and m keeps track of the next number of the opposite parity to l; once l exceeds m+2 the variables are exchanged. An adjustment is made at the start of the sequence so that sequences whose lengths are not multiples of 5 do not miss out any numbers, and another adjustment is made for n=4.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.