Three, Three, No

Question

Given a non-empty sequence of non-negative integers, output any permutation of it in which no two adjacent elements have a sum that is divisible by 3. If it is impossible, either crash the program, return an empty sequence, or output nothing.

The asymptotic time complexity must be linear in the size of the input sequence.

Example Input and Possible Output:

1,2,3 -> 1,3,2
9,5,3,6,2 -> 9,5,3,2,6
5,6,15,18,2 -> 6,5,15,2,18
1,2,3,4,5,6,7,8,9,10 -> 3,1,6,4,7,10,9,2,5,8 
6,1,6,6 -> no solution
4,3,7,6,6,9,0 -> no solution

Answer 1

JavaScript (V8), 189 164 bytes

a=>{z=[],o=[],t=[],l='length',r=x=>x[l]&&!print(x.pop());a.map(x=>[z,o,t][x%3].push(x));(z[l]-1>o[l]+t[l]||!z[l]&&o[l]&&t[l])&&$;while(z[l]>o[l]&&r(z),r(o)||r(t));}

Try it online!

Saved 25 bytes thanks to Neil

Explanation

Under modulus 3, the question is reduced, with there being only 3 states for a number: 0, 1, or 2. We need to find a permutation of the sequence such that no two adjacent elements add to 0 (under modulus 3). This means that 0 cannot be placed next to 0 and 1 cannot be placed next to 2. With this in mind, we can place the 1s and 2s on separate sides with one 0 used to separate the 1s and the 2s and the other zeros placed between consecutives 1s or 2s (or at the ends). To implement this, we can use arrays to store the numbers that are 0, 1, and 2 under modulus 3. Each time a number of a certain type is needed, we just pop a number from the appropriate array.

a=>{z=[],o=[],t=[],
   //arrays to store numbers that are zero, one, and two under modulus three 
   //(later referred to as zero array, one array, and two array)
    l='length', //store length key to save bytes on multiple accesses
    r=x=>x[l]&&!print(x.pop());
    //function to print and remove last element of array if not empty
    //returns true if element removed
    a.map( 
    //abuse map instead of forEach to save bytes; discard returned array
      x=>[z,o,t][x%3].push(x));
    //add each number to appropriate array based on remainder when divided by 3
    (z[l] - 1 > o[l] + t[l] //too many zeroes; zeroes cannot be separated
       || //or 
    !z[l] && o[l] && t[l]) //no zeroes to separate ones and twos
       && $;//then terminate with ReferenceError ($ is not defined)
    while(z[l]>o[l]&&r(z), //remove from zero array if there are more zeroes than ones
   //(ensure that there will be at least one 0 left to separate 1s from 2s)
       r(o)||r(t) 
   //try to remove from one array, then from two array if the former is empty
   );
}

Answer 2

Python 2, 129 127 114 bytes

-2 bytes thanks to @ovs

Gives NameError or IndexError on impossible cases.

C=x,y,z=[[],[],[]]
for i in input():C[i%3]+=i,
M=[]
while x:M+=C[len(M)%2*-~(z>[])].pop(),
y>M==[]<z<_
print y+M+z

Try it online!

Idea

My method looks to be the same as previous answers. The idea is that the problem is the exact same if we apply \$ \text{mod 3} \$ to each element. Then the constraint is satisfied if no two adjacent elements are 0,0 or 1,2.

One way to solve this is to alternate 0,1,0,1,0,1,0,2,0,2,0,2... until all zeros are gone. Then simply add all remaining 1s to the left side and all remaining 2s to the right side.

Finally there are two cases in which the answer is impossible. Denote \$ cnt_{i} \$ as the number of elements equal to \$ i \$ in the sequence.

• Case 1: \$ cnt_{0} = 0 \$, \$ cnt_{1} > 0 \$, \$ cnt_{2} > 0 \$
• Case 2: \$ cnt_{0} > cnt_{1} + cnt_{2} + 1 \$

Answer 3

Python 3, 172 bytes

def f(l):
 s=a,b,c=[tuple(e for e in l if e%3==x)for x in(0,1,2)];u,v,w=map(len,s)
 if u<=v+w+1and u:return c[max(u-v,0):]+sum([*zip(a[v:],c)]+[*zip(a,b)],())+b[u:]+a[v+w:]

Try it online!

This makes use of the same idea as the earlier answer, but constructs the final array using a different approach. Instead of taking from each list element by element we construct the output directly by using the lengths of the arrays. Because of this, we have to test if there is a solution before returning the construction.

This can probably be golfed quite a bit more, but I haven't been able to make progress in a while.

Answer 4

Charcoal, 63 bytes

≔Ｅ³Φθ⁼ι﹪λ³η≔⊟ηζ≔⊟ηε≔⊟ηδ¿∧∨δ¬∧εζ‹⊗⊖ＬδＬθ«Ｗ∨εζ«Ｆ›ＬδＬε⊞υ⊟δ⊞υ⊟ι»Ｉ⁺υδ

Try it online! Link is to verbose version of code. Doesn't output anything unless a solution exists. Explanation:

≔Ｅ³Φθ⁼ι﹪λ³η

Split the input elements up into three arrays depending on their residue modulo 3.

≔⊟ηζ≔⊟ηε≔⊟ηδ

Assign the arrays to separate variables to save bytes. I'll call them 0s, 1s and 2s for the purposes of the explanation, although the verbose variable names are actually d, e and z.

¿∧∨δ¬∧εζ‹⊗⊖ＬδＬθ«

Check for a solution: there must be 0s if there are both 1s and 2s, but the 0s can't account for more than half the number of entries, rounded up.

Ｗ∨εζ«

Repeat until both the 1s and 2s have been exhausted.

Ｆ›ＬδＬε⊞υ⊟δ

If there are more 0s than 1s then move one of them to the output list.

⊞υ⊟ι

Output one of the 1s if any, otherwise one of the 2s.

»Ｉ⁺υδ

Print the results plus the very last 0 if any.

Answer 5

J, 78 bytes

[:(#~[:*/0<3|2+/\])]{~(]/:&/:0(i.&3(|.@{.,}.)])@-.~,@|:@(]/.~=&1)@/:)&(1+3&|)~

Try it online!

This turned out to be difficult to golf well.

I'll try to shave off more bytes tomorrow night and add an explanation.

Answer 6

APL(Dyalog Unicode), 170 168 bytes ^SBCS

{y←⍳(≢⍵)⌊2×+/I←0=3|⍵⋄y[1-⍨2×⍳+/I]←⍵[⍸I]⋄z←(≢b←⍵[⍸J←1=3|⍵])⌊⌊2÷⍨1-⍨≢y⋄y[2×⍳z]←b[⍳z]⋄c←⍵[⍸K←2=3|⍵]⋄y[2×z+⍳w]←c[⍳w←(⌊2÷⍨≢y)-z]⋄x←÷(~(∨/K)∧∨/J)∨∨/I⋄b[z+⍳z-⍨≢b],y,c[w+⍳w-⍨≢c]}

Try it on APLgolf!

A dfn submission. Assumes ⎕IO ← 1. Uses an adapted version of the algorithm from this Python answer. This JS answer appears to use the same algorithm, as does this other Python answer.

Ungolfed:

a ← ⎕                ⍝ input array
I ← 0=3|a            ⍝ n%3 == 0 for n in a
y ← ⍳(≢a)⌊2×+/I      ⍝ initialise result
y[1-⍨2×⍳+/I] ← a[⍸I] ⍝ set indices that are odd to multiples of three

J ← 1=3|a          ⍝ n%3 == 1 for n in a
b ← a[⍸J]          ⍝ a[i] for i in range(len(a)) if J[i]
z ← (≢b)⌊⌊2÷⍨1-⍨≢y ⍝ min(len(b), len(y-1)//2)
y[2×⍳z] ← b[⍳z]    ⍝ y[2*i] = b[i] for i in range(z)

K ← 2=3|a         ⍝ n%3 == 2 for n in a
c ← a[⍸K]         ⍝ a[i] for i in range(len(a)) if K[i]
w ← (⌊2÷⍨≢y)-z    ⍝ len(y)//2 - z # garanteed to be positive or 0
y[2×z+⍳w] ← c[⍳w] ⍝ y[2*(z+i)] = c[i] for i in range(w)

÷(~(∨/K)∧∨/J)∨∨/I ⍝ error if there is no multiples of three, but there are numbers 1 more than a multiple of three and numbers that are 2 more than a multiple of three

b[z+⍳z-⍨≢b],y,c[w+⍳w-⍨≢c] ⍝ all of b not in y + y + all of c not in y

Explanation:

_{NOTE: APL uses 1-based indexing, as do I in this explanation}

1. I handle the multiples of three:

   1. I create an array where every index in said array that is a multiple of three in the input array - \$a\$ - is \$1\$, and I assign it to the variable \$I\$ -- I ← 0=3|a.

   2. I initialise an array, \$y\$, that is from \$1\$ to the minimum of the length of \$a\$ and two times the amount of multiples of three there is in \$a\$ (the amount of \$1\$'s in \$I\$) -- y ← ⍳(≢a)⌊2×+/I.

   3. I set all the odd indices of \$y\$ (\$y_n\$ for every second \$n\$ from \$1\$ to \$2\$ times the sum of \$I\$) to the multiples of three in \$a\$.

2. I handle numbers that are one more than a multiple of three:

   1. I create an array where every index in said array that is one more than a multiple of three in the input array - \$a\$ - is \$1\$, and I assign it to the variable \$J\$ -- J ← 1=3|a.

   2. I create an array, \$b\$ that contains all the numbers in \$a\$ that is one more than a multiple of three -- b ← a[⍸J].

   3. I create a variable \$z\$, that holds the minimum of the length of \$b\$ and \$floor(\frac{len(y)-1}{2})\$ -- z ← (≢b)⌊⌊2÷⍨1-⍨≢y -- I subtract one from the length of \$y\$ so that the final constructed array doesn't end with a number that is 1 more than a multiple of three. To see what would happen without the subtraction, you can go to the APLgolf link, change z ← (≢b)⌊⌊2÷⍨1-⍨≢y to z ← (≢b)⌊⌊2÷⍨≢y, and click "Run".

   4. I then assign to every index \$n\$ of \$y\$, where \$n\$ is every second number from \$2\$ to \$2z\$, the first \$z\$ values of \$b\$ -- y[2×⍳z] ← b[⍳z].

3. I handle numbers that are two more than a multiple of three:

   1. I create an array where every index in said array that is two more than a multiple of three in the input array - \$a\$ - is \$1\$, and I assign it to the variable \$K\$ -- K ← 2=3|a.

   2. I create an array, \$c\$ that contains all the numbers in \$a\$ that is two more than a multiple of three -- c ← a[⍸K].

   3. I create a variable \$w\$, and assign to it \$floor(\frac{len(y)}{2})-z\$ -- w ← (⌊2÷⍨≢y)-z -- this is how many open spots are left in the array.

   4. I then assign to every index \$n\$ of \$y\$, where \$n\$ is every second number from \$2(z+1)\$ to \$2(z+w)\$, the first \$w\$ values of \$c\$ -- y[2×z+⍳w] ← c[⍳w].

4. I handle arrays that don't contain multiples of three, but do contain the other two categories -- ÷(~(∨/K)∧∨/J)∨∨/I:

   1. Throw DOMAIN ERROR: Divide by zero if the following is false -- ÷:

      1. There is at least one multiple of three -- ∨/I...

      2. OR -- ∨...

      3. NOT -- (~...)...

         1. There is at least one number that is one more than a multiple of three -- ∨/J...

         2. AND -- (...)∧...

         3. There is at least one number that is two more than a multiple of three -- ∨/K

   2. TLDR: Throw DivByZero if there are no multiples of three, and both numbers one more than a multiple of three, and two more than a multiple of three.

5. Output

   1. Every element in \$b\$ that wasn't used, catenate to... -- b[z+⍳z-⍨≢b],...

   2. \$y\$ catenate to... -- y,...

   3. Every element in \$c\$ that wasn't used -- c[w+⍳w-⍨≢c]