9
\$\begingroup\$

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
\$\endgroup\$
24
  • 4
    \$\begingroup\$ Note that requirements like determining if invalid input is given are often discouraged \$\endgroup\$ – Redwolf Programs Mar 5 at 16:40
  • 4
    \$\begingroup\$ It isn't immediately obvious to me that an algorithm with linear time complexity exists for this problem: can you be sure (or even prove) that there is (at least) one? Otherwise there's a worry (at least to me) that this might a challenge with no possible solution... \$\endgroup\$ – Dominic van Essen Mar 5 at 17:14
  • 3
    \$\begingroup\$ Well, then it might be nice to include it as an example. If there's only one algorithm, then keeping it secret risks reducing the challenge to a 'who's the first to find it' puzzle, rather than a code-golfing challenge... If there's more-than-one (or might be), then it shouldn't be a worry anyway... \$\endgroup\$ – Dominic van Essen Mar 5 at 17:22
  • 3
    \$\begingroup\$ I actually think the challenge wouldn't be as interesting without the time complexity requirement. I see how to solve it, but not a great way to golf it yet, and think it makes the golfing itself more interesting too. \$\endgroup\$ – Jonah Mar 5 at 17:35
  • 8
    \$\begingroup\$ We have precedent for challenge authors not revealing their algorithms in [restricted-complexity] challenges, and I actually agree that they shouldn't be revealed immediately (or if they are, hidden behind a spoiler/link), so that if people actually want to try to figure out a valid algorthm, they are free to do so without it being spoiled. However, if a reasonable amount of time (e.g. a week) passes without a valid answer, revealing the algorithm is a sensible thing to do \$\endgroup\$ – caird coinheringaahing Mar 5 at 18:18
11
\$\begingroup\$

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
   );
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Yes, this is the approach I was thinking of using. I think I've managed to simplify your output a bit though: 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));} \$\endgroup\$ – Neil Mar 5 at 20:36
  • \$\begingroup\$ @Neil Thanks for the help! \$\endgroup\$ – iota Mar 5 at 21:59
6
\$\begingroup\$

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 \$
\$\endgroup\$
2
  • \$\begingroup\$ The and can be a * as len(C)%2 is always 1 or 0. \$\endgroup\$ – ovs Mar 5 at 22:56
  • \$\begingroup\$ @ovs Thanks, good catch! \$\endgroup\$ – dingledooper Mar 5 at 23:33
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 63 bytes

≔E³Φθ⁼ι﹪λ³η≔⊟ηζ≔⊟ηε≔⊟ηδ¿∧∨δ¬∧εζ‹⊗⊖LδLθ«W∨εζ«F›LδLε⊞υ⊟δ⊞υ⊟ι»I⁺υδ

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

≔E³Φθ⁼ι﹪λ³η

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.

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

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.

W∨εζ«

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

F›LδLε⊞υ⊟δ

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.

»I⁺υδ

Print the results plus the very last 0 if any.

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

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.

\$\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.