Simulador de propagação de fogo

28

Suponha que tenhamos uma matriz como esta:

11111
12221
12321
12221
11111

Essa matriz representa um terreno e cada célula representa uma parte do terreno. O número em cada célula representa o tempo que a parte do terreno precisa ser completamente queimada (em minutos, se for necessária uma unidade de medida), de acordo com a sua combustibilidade . Se um incêndio começa em qualquer posição (célula), essa célula precisa ser completamente queimada antes que o fogo se propague para as células adjacentes (somente horizontal e vertical, não diagonal). Portanto, se um incêndio é iniciado na posição central, ele precisa:

11111        11111        11111        11011        10001        00000
12221  3 m.  12221  2 m.  12021  1 m.  11011  1 m.  00000  1 m.  00000
12321 -----> 12021 -----> 10001 -----> 00000 -----> 00000 -----> 00000
12221        12221        12021        11011        00000        00000
11111        11111        11111        11011        10001        00000

Explicação:

  • O fogo começa em [2,2] (baseado em 0), que possui um tempo de gravação de 3.
  • Após 3 minutos, [1,2], [2,1], [2,3], [3,2] começam a queimar.
  • Após 2 minutos, essas células terminam a queima e o fogo se propaga para todas as células adjacentes, mas [0,2], [2,0], [2,4], [0,4] precisam de apenas mais 1 minuto para queimar, portanto
  • Após 1 minuto, essas células são queimadas e a célula se propaga para as células adjacentes.
  • Após mais 1 minuto, o restante das células da etapa 3 termina a queima e o fogo se propaga para as células adjacentes (que já estão queimadas, para que nada aconteça).
  • Após 1 último minuto, o fogo acaba queimando todo o terreno.

Portanto, a solução para esse caso é de 8 minutos. Se o fogo começar na célula superior esquerda [0,0]:

11111     01111     00111     00011     00001     00000
12221  1  12221  1  02221  1  01221  1  00121  1  00011   1
12321 --> 12321 --> 12321 --> 02321 --> 01321 --> 00321  -->
12221     12221     12221     12221     02221     01221
11111     11111     11111     11111     11111     01111

00000     00000     00000     00000     00000
00000  1  00000  1  00000  1  00000  1  00000
00221 --> 00110 --> 00000 --> 00000 --> 00000
00221     00121     00020     00010     00000
00111     00011     00001     00000     00000

Então agora o tempo total é de 10 minutos.

O desafio

Dada uma matriz NxM (N> 0, M> 0) de valores inteiros que representam o tempo que cada célula precisa ser completamente consumida, escreva o programa / função mais curto que leva essa matriz e um par de números inteiros com a posição em que o incêndio começa , e retorna / imprime o tempo necessário para que o fogo consuma completamente todo o terreno.

  • Cada célula terá um tempo de gravação positivo (diferente de zero). Você não pode assumir um valor máximo para as células.
  • A matriz não precisa ser quadrada nem simétrica.
  • A matriz pode ser indexada em 0 ou 1, como desejar.
  • A posição pode ser dada como um único parâmetro com uma tupla de números inteiros, dois parâmetros separados de qualquer outro formato razoável.
  • As dimensões da matriz não podem ser especificadas como parâmetros de entrada.
  • Você não precisa produzir cada etapa intermediária, apenas a quantidade de tempo solicitada. Mas não vou reclamar se as etapas forem visualizadas de alguma forma.

Outro exemplo:

Fire starts at [1,1] (a '>' represents a minute):

4253   4253   4253   4153   4043   3033   2023    0001   0000
2213 > 2113 > 2013 > 1003 > 0002 > 0001 > 0000 >> 0000 > 0000 
1211   1211   1211   1111   1001   0000   0000    0000   0000

Output: 9

Este é o , por isso o programa mais curto para cada idioma pode ganhar!

Charlie
fonte
1
@LeanderMoesinger tem que trabalhar com qualquer matriz. O que quero dizer é que seu programa ou função não pode aceitar as dimensões da matriz como parâmetros de entrada, mas é claro que você pode calcular essas dimensões dentro do seu código.
26617 Charlie
A entrada pode ser tomada como um número único na ordem principal da coluna ? Ou seja, as entradas da matriz são numeradas para baixo e depois para o outro lado
Luis Mendo
1
@LuisMendo sim, é claro. Mas observe que o tempo de gravação de cada célula pode ser maior que 9, se isso importa para a parte "número único".
30617 Charlie
Obrigado. Não, isso não importa. Eu quis dizer um número único, mas possivelmente com vários dígitos. O número irá variar de 1aM*N
Luis Mendo

Respostas:

12

Matlab, 235 257 190 182 178 bytes

Entrada: Matriz A, vetor 1x2 pcontendo as coordenadas de partida.

function t=F(A,p)
[n,m]=size(A);x=2:n*m;x(mod(x,n)==1)=0;B=diag(x,1)+diag(n+1:n*m,n);k=sub2ind([n m],p(1),p(2));t=max(distances(digraph(bsxfun(@times,((B+B')~=0),A(:))'),k))+A(k)

Explicação:

Em vez de simular a propagação do fogo, também podemos entender isso como um problema "encontre o caminho mais curto e mais longo". A matriz é convertida em um gráfico direcionado ponderado. Os pesos dos caminhos para um único nó correspondem ao tempo para queimar o referido nó. Por exemplo, para uma matriz

5   7   7   10
5   2   2   10
4   5   2   6

temos o gráfico conectado:

gráfico

Onde o nó 1 é o elemento da matriz superior esquerdo e o nó 12, o elemento inferior direito. Dadas as coordenadas iniciais p, o caminho mais curto para todos os outros nós é calculado. Então, o comprimento do caminho mais longo desses caminhos mais curtos + o tempo para gravar o nó inicial é igual ao tempo para gravar toda a matriz.

Versão sem golfe e comentada com valores iniciais de amostra:

% some starting point
p = [3 2];
% some random 5x6 starting map, integers between 1:10
A = randi(10,5,6); 

function t=F(A,p)
% dimensions of A
[n,m] = size(A);
% create adjacency matrix
x=2:n*m;
x(mod(x,n)==1)=0;
B = diag(x,1)+diag(n+1:n*m,n);
B = B+B';
B = bsxfun(@times,(B~=0),A(:))';
% make graph object with it
G = digraph(B);
% starting node
k = sub2ind([n m], p(1), p(2));
% calculate the shortest distance to all nodes from starting point
d = distances(G,k);
% the largest smallest distance will burn down last. Add burntime of initial point
t = max(d)+A(k);
Leander Moesinger
fonte
1
Bem-vindo ao PPCG!
Stephen
Abordagem muito agradável e muito bem explicada!
26617 Charlie
Ei, uma vez que este é o meu primeiro golfe, tenho que perguntar se está tudo bem que eu tenha omitido o ;depois de cada linha. No Matlab, eles impedem que os resultados de cada comando sejam exibidos no console. Atualmente, o código é MUITO falador e gera spam no console. Mas como esse não é um estado estrito de falha, eu o mantive assim. Mas isso não importa muito, é apenas 4 bytes
Leander Moesinger
1
@LeanderMoesinger o spam vai para a mesma área de saída do seu programa? Se o spam, por exemplo, entrar em STDERR ou equivalente e a saída entrar em STDOUT ou equivalente, você deverá removê-los. Se ambos saírem no mesmo local, eu não saberia.
Stephen
@ É uma área de saída diferente, mas posso evitá-la completamente colocando tudo em uma linha. Obrigado pelo esclarecimento!
Leander Moesinger
9

JavaScript (ES6), 156 152 146 144 143 bytes

Guardado 1 byte graças a Kevin Cruijssen

Uma implementação bastante ingênua. Recebe entrada na sintaxe de curry (a)(s), onde a é uma matriz 2D e s é uma matriz de dois números inteiros [ x, y ] representando as coordenadas baseadas em 0 da posição inicial.

a=>s=>(g=t=>(a=a.map((r,y)=>r.map((c,x)=>(z=(h,v)=>(a[y+~~v]||[])[x+h]<1)(-1)|z(1)|z(0,-1)|z(0,1)|x+','+y==s&&c?u=c-1:c),u=-1),~u?g(t+1):t))(0)

Formatado e comentado

a => s => (                                // given a and s
  g = t => (                               // g = recursive function with t = time counter
    a = a.map((r, y) =>                    // for each row r of the input array:
      r.map((c, x) =>                      //   for each cell c in this row:
        (                                  //     z = function that takes
          z = (h, v) =>                    //         2 signed offsets h and v and checks
            (a[y + ~~v] || [])[x + h] < 1  //         whether the corresponding cell is 0
        )(-1) | z(1) |                     //     test left/right neighbors
        z(0, -1) | z(0, 1) |               //     test top/bottom neighbors
        x + ',' + y == s                   //     test whether c is the starting cell
        && c ?                             //     if at least one test passes and c != 0:
          u = c - 1                        //       decrement the current cell / update u
        :                                  //     else:
          c                                //       let the current cell unchanged
      ),                                   //   end of r.map()
      u = -1                               //   start with u = -1
    ),                                     // end of a.map() --> assign result to a
    ~u ?                                   // if at least one cell was updated:
      g(t + 1)                             //   increment t and do a recursive call
    :                                      // else:
      t                                    //   stop recursion and return t
  )                                        // end of g() definition
)(0)                                       // initial call to g() with t = 0

Casos de teste

Arnauld
fonte
==0pode ser jogado <1se não me engano.
Kevin Cruijssen
1
@KevinCruijssen Isso é realmente seguro como undefined<1é falso. Obrigado!
precisa
8

Oitava, 67 bytes

function n=F(s,a)n=0;do++n;until~(s-=a|=imdilate(~s,~(z=-1:1)|~z')

Experimente online!

Para visualizar resultados intermediários, você pode tentar isso!

Uma função que assume como matriz de entrada do terreno ae coordenada inicial como uma matriz de 0 e 1 com o mesmo tamanho do terreno.

Na verdade, não há necessidade de, endfunctionno entanto, executar o exemplo em que ele deve ser adicionado.

Explicação:

Aplique repetidamente a dilatação da imagem morfológica no terreno e subtraia as áreas queimadas.

Resposta ungolfed:

function n = Fire(terrain,burned)
    n = 0;
    mask = [...
            0  1  0
            1  1  1
            0  1  0];
    while true
        n = n + 1;
        propagation = imdilate(~terrain, mask);
        burned = burned | propagation;
        terrain = terrain - burned;
        if all(terrain(:) == 0)
            break;
        end
    end
end
rahnema1
fonte
Essa é uma boa resposta, mas talvez o algoritmo esteja contando o estado inicial como uma etapa e retornando 11 em vez de 10 no seu exemplo. Se mudar a célula inicial para ser [3 3], o resultado é 9 em vez de 8.
Charlie
@CarlosAlejo OH, meu mal. Resposta atualizada alterada n=1para n=0.
rahnema1
7

MATL , 26 25 bytes

Eu realmente queria ver mais algumas respostas usando os idiomas de golfe por aqui

`yy)qw(8My~1Y6Z+fhy0>z}@&

O formato de entrada é:

  • A primeira entrada é uma matriz usando ;como separador de linhas.

  • A segunda entrada é um número único que aborda uma entrada da matriz na ordem principal da coluna com base em 1 (permitido pelo desafio). Por exemplo, a coordenada principal da coluna de cada entrada em uma matriz 3 × 4 é dada por

    1  4  7 10
    2  5  8 11
    3  6  9 12
    

    Assim, por exemplo, as coordenadas baseadas em 1 (2,2) correspondem a 5.

Experimente online! Ou verifique todos os casos de teste .

Explicação

O código mantém uma lista de entradas que estão sendo gravadas. A cada iteração, todas as entradas dessa lista são decrementadas. Quando uma entrada chega a zero, suas entradas vizinhas são adicionadas à lista. Para salvar bytes, as entradas que atingem zero não são removidas da lista; em vez disso, eles continuam "queimando" com valores negativos. O loop é encerrado quando nenhuma das entradas possui valores positivos.

Veja o programa executando passo a passo com código ligeiramente modificado.

Código comentado:

`      % Do...while
  yy   %   Duplicate top two arrays (matrix and array of positions to be decremented)
       %   In the first iteration this implicitly takes the two inputs
  )    %   Reference indexing. This gives the values that need to be decremented
  q    %   Decrement
  w    %   Swap. This brings the array of positions that have been decremented to top
  (    %   Assignment indexing. This writes the decremented values back into their
       %   positions
  8M   %   Push array of positions again
  y    %   Duplicate decremented matrix
  ~    %   Negate. This replaces zeros by 1, and nonzeros by 0
  1Y6  %   Push predefined literal [0 1 0; 1 0 1; 0 1 0] (4-neighbourhood)
  Z+   %   2D convolution, maintaining size
  f    %   Find: gives column-major indices of neighbours of totally burnt entries
  h    %   Concatenate. This updates the array of positions to be decremented
  y    %   Duplicate decremented matrix
  0>   %   This gives 1 for positive entries, and 0 for the rest
  z    %   Number of nonzeros. This is the loop condition (*)
}      % Finally (execute before exiting loop)
  @    %   Push iteration number. This is the output
  &    %   Specify that the final implicit display function will display only the top
       %   of the stack
       % Implicit end. If the top of the stack (*) is not 0 (i.e. there are entries
       % that have not been totally burnt) the loop proceeds with the next iteration.
       % Else the "finally" branch is executed and the loop is exited
       % Implicit display (only top of the stack)
Luis Mendo
fonte
2
Agora é isso que chamo de código curto! :-)
Charlie
4

Python 2 , 170 bytes

s,m=input()
t={s}
r=0
while max(sum(m,[]))>0:
 r+=1
 for a,b in t|t:
	try:a<0<x;b<0<x;m[a][b]-=1;t|=m[a][b]==0and{(a+1,b),(a-1,b),(a,b+1),(a,b-1)}or t^t
	except:0
print r

Experimente online!

ovs
fonte
4

Python 3 , 277 266 bytes

def f(m,s):
 p={s};w=len(m);t=0
 while sum(sum(m,[])):
  t+=1;i=0
  for x,y in p:
   try:m[x][y]=max(0,m[x][y]-1)
   except:0
  for v in sum(m,[]):
   if v<1:
    for l in[(1,0),(-1,0),(0,1),(0,-1)]:a,b=max(0,i%w+l[0]),max(0,i//w+l[1]);p.add((a,b))
   i+=1
 print(t)

Experimente online!

Define uma função fque utiliza uma matriz 2D e uma tupla de pontos. A primeira coisa a função faz é definir um conjunto de tuplos que contêm o valor inicial tupla passou em: p={s}. A função passa por cada tupla de pontos pe subtrai um da matriz mnesse ponto, a menos que o valor já seja zero. Em seguida, percorre mnovamente encontrando todos os pontos com o valor zero e adicionando os quatro vizinhos desse ponto ao conjunto p. É por isso que escolhi usar um conjunto, porque os conjuntos em Python não permitem valores duplicados (o que estragaria bastante a subtração). Infelizmente, devido ao empacotamento do índice da lista (por exemplo list[-1] == list[len(list)-1]:), os índices precisam ser restringidos para que não fiquem negativos e adicionem as coordenadas erradas p.

Nada de especial, ainda se acostumando ao golfe. Definitivamente espaço para melhorias aqui, eu vou continuar rachando.

MooseOnTheRocks
fonte
Você poderia escrever um exemplo de execução em Experimente online para que todos possamos testar seu código?
27717 Charlie
@CarlosAlejo Claro, acrescentou ao post.
MooseOnTheRocks
4

APL (Dyalog) , 93 66 57 bytes

{⍵{^/,0≥⍺:0⋄1+x∇⍵∨{∨/,⍵∧⍲/¨2|⍳3 3}⌺3 30=x←⍺-⍵}(⊂⍺)≡¨⍳⍴⍵}

Experimente online! ou visualize online!


Esta função toma a matriz do terreno como argumento da direita e as coordenadas (com base em 1) do primeiro disparo como argumento da esquerda. Retorna o número de minutos necessários para gravar tudo.


Atualizações

Finalmente encontrei uma maneira de jogar golfe na função spread.
* Suspiro * seria muito mais fácil se o mundo fosse toroidal .


O TIO acabou de atualizar para o Dyalog 16.0 , o que significa que agora temos o novo operador de estêncil brilhante

TwiNight
fonte
Resposta muito boa! A saída intermediária ajuda a visualizar o progresso!
Charlie
2

Python 2 , 268 bytes

def f(m,y,x):t,m[y][x]=m[y][x],0;g(m,t)
def g(m,t):
	n,h,w=map(lambda r:r[:],m),len(m),len(m[0])
	for l in range(h*w):r,c=l/h,l%h;n[r][c]-=m[r][c]and not all(m[r][max(c-1,0):min(c+2,w+1)]+[m[max(r-1,0)][c],m[min(r+1,h-1)][c]])
	if sum(sum(m,[])):g(n,t+1)
	else:print t

Experimente online!

Faça iterações recursivas ao longo do tempo, nas quais o número de cada bloco é reduzido se for cardinalmente adjacente a um 0. Algoritmo muito simples que, acredito, ainda pode ser jogado para a eficiência booleana ...

* observação: meu 'Experimente online!' O código inclui o log de depuração de bônus no rodapé. Eu gosto de assistir o progresso do algoritmo.

Coty Johnathan Saxman
fonte
2

Haskell , 138 133 bytes

u#g|all((<=0).snd)g=0|2>1=1+(u:[[(x+1,y),(x-1,y),(x,y-1),(x,y+1)]|((x,y),0)<-n]>>=id)#n where n=d<$>g;d p|elem(fst p)u=pred<$>p|2>1=p

Experimente online!

Assume que a entrada é uma lista de ((x, y), célula). Ungolfed:

type Pos = (Int, Int)

ungolfed :: [Pos] -> [(Pos, Int)] -> Int
ungolfed burning grid
  | all ((<=0).snd) grid = 0 
  | otherwise = 1 + ungolfed (burning ++ newburning) newgrid
 where
  newgrid = map burn grid
  burn (pos,cell) | pos `elem` burning = (pos, cell - 1)
                  | otherwise = (pos, cell)
  newburning = do
    ((x,y),cell) <- newgrid
    guard (cell <= 0)
    [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]
bartavelle
fonte