fundo

Eu tenho uma fileira de ímãs poderosos e um monte de objetos de metal entre eles. Onde os ímãs os puxarão?

Entrada

Sua entrada é uma matriz de números inteiros não negativos, que conterá pelo menos um 1. Você pode usar qualquer formato razoável.

Os 0s da matriz representam o espaço vazio e os 1s representam ímãs fixos. Todos os outros números são objetos de metal, que são puxados pelos ímãs. Todo objeto é puxado em direção ao ímã mais próximo (se houver um empate, o objeto é puxado para a direita) e viaja nessa direção até atingir o ímã ou outro objeto. No final, todos os objetos se agruparam ao redor dos ímãs. A ordem dos objetos é preservada.

Saída

Sua saída é a matriz em que todos os objetos foram puxados o mais próximo possível do ímã mais próximo. Ele deve ter o mesmo formato que a entrada.

Exemplo

Considere a matriz

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

A extremidade esquerda 2é puxada em direção ao primeiro par de ímãs, assim como o segundo 2. O 3ímã está a quatro passos nas duas direções, de modo que é puxado para a direita. O 5também é puxado para a direita e fica entre 3o ímã e o ímã. A saída correta é

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

Regras e pontuação

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Casos de teste

[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]

Pyth, 28. 20

[email protected]?bhaDk_x1QkQ~hZQ

Obrigado @ThomasKwa por jogar 6 bytes!

Isso abusa da classificação estável, atribuindo a todos os valores 1 ou maiores da lista o índice do 1 mais próximo (os vínculos são quebrados ao 1 mais à direita) e, em seguida, classificando a lista por esses valores. Os zeros recebem seu próprio índice como valor de classificação.

Suíte de teste

Conjunto de Verificação

Explicação:

[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

Exemplo:

Veja o caso de teste [1,0,3,0,1,0,3,0,1], por exemplo. Quando aplicamos a enumeração, todos os zeros obterão seu próprio índice como um valor de classificação, então eu vou pular esses e fazer um um e um três.

Para o primeiro, ficamos com os índices de ones: [0, 4, 8]. Depois, inverta-o e classifique pelo valor absoluto dos índices menos o índice de um, que aqui é zero. Então [0, 4, 8]voltamos novamente. O primeiro valor é 0então usamos isso.

Para os três, obtemos os índices revertidos e fazemos a mesma classificação, mas usando dois como o índice dos três; portanto, o 0e o 4dão o mesmo valor para a diferença absoluta, obtemos: [4, 0, 8]e pegamos o 4.

Em seguida, a matriz "valores de classificação" final será [0, 1, 4, 3, 4, 5, 8, 7, 8]. Graças à classificação estável, os vínculos são quebrados pela ordem em que os valores apareceram originalmente, para obtermos a matriz final que queremos.

Retina , 97 72 bytes

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

Espera-se que a entrada seja uma lista separada por vírgula de números inteiros unários (delimitadores iniciais e finais, como [...]funcionam muito bem).

Execute todos os casos de teste aqui. (Por conveniência, isso cuida da conversão de e para decimal automaticamente.)

Aqui está uma idéia completamente diferente que evita os caros grupos de balanceamento usando vários estágios. Atualmente, tem 6 bytes a mais, mas pode ser mais fácil de jogar:

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

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

Explicação

Itera sobre cada célula e, se ela contém metal, verifica se a próxima célula na direção do ímã mais próximo está vazia e, se estiver, a move para lá. Esse processo é repetido várias vezes até que todo o metal se mova o mais longe que puder.

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>

PHP, 337 caracteres

<?$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";?>

Sim, isso é muito longo, porque o PHP não é realmente uma linguagem para o golfe, mas funciona e eu me diverti fazendo com que seja bom para mim. Claro que estou aberto a possíveis falhas.

Também há um pequeno recurso de bug que pensa, por exemplo, aqui:

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

parece que os 12 ficaram mágicos na frente dos 3, mas isso não é verdade!

O 3 respeita o número maior e permite que ele se aproxime do maget!