Magnetic pull in an array

Question

Background

I have a row of powerful magnets and a bunch of metal objects between them. Where will the magnets pull them?

Input

Your input is an array of non-negative integers, which will contain at least one 1. You can use any reasonable format.

The 0s of the array represent empty space, and the 1s represent fixed magnets. All other numbers are metal objects, which are pulled by the magnets. Every object gets pulled towards the nearest magnet (if there's a tie, the object is pulled to the right), and it travels in that direction until it hits the magnet or another object. In the end, all the objects have clustered around the magnets. The order of the objects is preserved.

Output

Your output is the array where every object has been pulled as close to the nearest magnet as possible. It should have the same format as the input.

Example

Consider the array

[0,0,2,0,1,1,0,2,0,3,0,5,0,1,0]

The leftmost 2 gets pulled towards the first pair of magnets, as does the second 2. The 3 has a magnet four steps away in both directions, so it gets pulled to the right. The 5 also gets pulled to the right, and it goes between the 3 and the magnet. The correct output is

[0,0,0,2,1,1,2,0,0,0,0,3,5,1,0]

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

[0,1,0] -> [0,1,0]
[1,0,2,0,0,1,0] -> [1,2,0,0,0,1,0]
[7,0,5,0,0,1,0] -> [0,0,0,7,5,1,0]
[1,0,3,0,1,0,3,0,1] -> [1,0,0,3,1,0,0,3,1]
[1,0,0,0,0,0,0,7,3] -> [1,7,3,0,0,0,0,0,0]
[1,2,3,4,5,6,7,8,9,10,11,0,0,0,1] -> [1,2,3,4,5,6,7,0,0,0,8,9,10,11,1]
[12,3,0,0,1,0,1,3,0,0,6,12,0,0,0,1] -> [0,0,12,3,1,0,1,3,6,0,0,0,0,0,12,1]

Answer 1

Pyth, 28 20

[email protected]?bhaDk_x1QkQ~hZQ

Thanks @ThomasKwa for golfing 6 bytes!

This abuses stable sorting by assigning to all the values 1 or greater in the list the index of the nearest 1 (ties broken to the rightmost 1) and then sorting the list by these values. Zeroes are given their own index as their sort value.

Test Suite

Verification Suite

Explanation:

[email protected]?bhaDk_x1QkQ~hZQ  ##  implicit: Q = eval(input())
o                  Q  ##  Sort Q using the values of the lambda below
 @              ~hZ   ##  select the value from the matching index of the enumerate
  .e           Q      ##  enumerate with b = value, k = index
    ?b                ##  ternary on b
      haDk_x1Q        ##  if true, this thing
              k       ##  otherwise use the index as the sort weight
          _x1Q        ##  the indices of 1 in Q, given in reverse order 
                      ##  (the reverse makes it sort to the right because of stable sorts)
       aDk            ##  sort those indices by |index - k|
      h               ##  take the first value

Example:

Take the test case [1,0,3,0,1,0,3,0,1], for example. When we apply the enumeration, the zeros will all get their own index as a sort value, so I'll skip those, and do a one and a three.

For the first one, we get the indices of ones: [0, 4, 8]. Then reverse it, and sort by the absolute value of the indices minus the index of the one, which happens to be zero here. So we get [0, 4, 8] back again. The first value is 0 so we use that.

For the three, we get the reversed indices and do the same sorting but using two as the index of the three, so both the 0 and the 4 give the same value for the absolute difference, so we get: [4, 0, 8] and we take the 4.

Then the final "sorting values" array will be [0, 1, 4, 3, 4, 5, 8, 7, 8]. Thanks to the stable sort, the ties are broken by the order that the values originally appeared, so we get the final array we want.

Answer 2

Retina, 97 72 bytes

+`(?<=\b1(,1*)*?)(\B,(11+)|,(11+))\b(?!(?<-1>,1*)*,1\b)|(11+),\B
$3,$4$5

Input is expected to be a comma-separated list of unary integers (leading and trailing delimiters like [...] work just fine).

Run all test cases here. (For convenience, this takes care of the conversion from and to decimal automatically.)

Here is a completely different idea that avoids the expensive balancing groups by using multiple stage. It's currently 6 bytes longer, but might be more golfable:

,1\b
>1
\b1,
1<
(T`,`<`<1*,
)T`,`>`,1*>
+`(1+>)>
>$1
+`<(<1+\b)(?!>)
$1<
<|>
,

Answer 3

JavaScript (ES6), 108 bytes

a=>a.map(_=>a.map((x,i)=>x>1?a[j=(n=a.indexOf(1,i))<0|n-i>i-p?i-1:i+1]?0:a[a[i]=0,j]=x:x<1?0:p=i,p=-1/0))&&a

Explanation

Iterates over each cell and if it contains metal, checks if the next cell in the direction of the closest magnet is empty, and if it is, moves it there. This process is repeated many times until all metal has moved as far as it can go.

var solution =

a=>
  a.map(_=>                  // loop a.length times to ensure completeness
    a.map((x,i)=>            // for each cell item x at index i
      x>1?                   // if the cell contains metal
        a[j=                 // j = index of cell to move to
          (n=a.indexOf(1,i)) // n = index of next magnet
          <0|n-i>i-p?i-1:i+1 // set j to previous or next cell based on closest magnet
        ]?0:                 // if cell j is empty
          a[a[i]=0,j]=x      // set it to x and set cell i to 0
      :x<1?0:                // else if the cell contains a magnet
        p=i,                 // set p to the index of this magnet
      p=-1/0                 // p = index of previous magnet, initialise to -Infinity
    )
  )
  &&a                        // return a

<input type="text" id="input" value="1,2,3,4,5,6,7,8,9,10,11,0,0,0,1" />
<button onclick="result.textContent=solution(input.value.split(',').map(n=>+n))">Go</button>
<pre id="result"></pre>

Answer 4

PHP, 337 chars

<?$i=explode(",",$argv[1]);$m=$n=[];foreach($i as$k=>$v)if($v>0)eval("array_push(\$".($v<2?"m":"n").",$k);");for($p=0;$p<count($i);$p++)foreach($i as$k=>$v)if($v>1){$i[$k]=0;$r=-1;foreach($m as$_)if($r<0||abs($k-$r)>abs($_-$k))$r=$_;while($i[$r]>0)$r+=($r<$k?1:-1);$i[$r]=$v;}$s="";foreach($i as$v)$s.=$v.",";echo substr($s,0,-1)."\n";?>

Yes this is very long, because PHP is not really a language for golfing, but it works and I had FUN making it so it's fine to me. Of course I'm open to possible shortings.

Also there is a little bug feature which thinks, so for example here:

root@raspberrypi:~/stack# php magnet.php 12,3,0,0,1,0,1,3,0,0,6,12,0,0,0,1
0,0,3,12,1,0,1,3,6,0,0,0,0,0,12,1

it looks like the 12 magicly got in front of the 3, but that's not true!

The 3 respects the bigger number and lets it go closer to the maget!

Answer 5

Haskell, 127 bytes

(a:b)!(c:d)=c/=1&&a==1||b!d
_!_=1<0
infix 4#
x@(a:b)#0:i@(c:d)|i!x=a:0:b#i|x!i=c:x#0:d
x#a:b=a:x#b
x#[]=x
l=([]#)
l.l.l.reverse

Try it online!

Instead of moving the objects towards the magnets we move the empty space away from the magnets.

A big frustration for me was that the default was to the right. Defaulting to the left could have saved me 10 bytes. To default to the left we do l.l to default to the right we need l.l.l.reverse.

When we run l it naturally reverses the list, however this is actually pretty convenient since we need to run it on the list going both ways, so the output is ready to go for the second run. Unfortunately though since to default to the right this means we need to reverse it manually first, then run it twice, we end up needing an additional l to get it back to the correct order.