O Blow-up é uma ferramenta poderosa em geometria algébrica. Permite remover singularidades de conjuntos algébricos , preservando o restante de sua estrutura.

Se você não estiver familiarizado com nada disso, não se preocupe, o cálculo real não é difícil de entender (veja abaixo).

A seguir, estamos considerando a ampliação do ponto $(0,0)$ de uma curva algébrica em 2D. Uma curva algébrica em 2D é dada pelo locus zero de um polinômio em duas variáveis ​​(por exemplo, $p(x,y) = x^2 + y^2 - 1$ para o círculo unitário, ou $p(x,y) = y-x^2$ para uma parábola). A explosão dessa curva (em $(0,0)$) é dada por dois polinômios $r,s$ conforme definido abaixo. Ambos $r$ e $s$ descrevem $p$ com a (possível) singularidade em $(0,0)$ removida.

Desafio

Dado algum polinômio $p$ , encontre $r$ e $s$ como definido abaixo.

Definição

Antes de tudo, observe que tudo o que digo aqui é simplificado e não corresponde completamente às definições reais.

Dado um polinômio $p$ em duas variáveis $x,y$ a explosão é dada por dois polinômios $r,s$ novamente cada um em duas variáveis.

$r$$R(x,v) := p(x,vx)$$R(x,v)$$x$$R(x,v) = x^n \cdot r(x,v)$$n$$x$$r(x,v)$$r(x,v)$

$S(u,y) := p(uy,y)$$s$$S(u,y) = y^m \cdot s(u,y)$$m$$y$$s(u,y)$

Para tornar mais claro, considere seguir

Exemplo

$p(x,y) = y^2 - (1+x) x^2$$(0,0)$

Então encontramos

$$R(x,v) = p(x,vx) = v^2x^2-(1+x)x^2 = x^2 (v^2-1-x)$$

$r(x,v) = v^2 -1 -x$

similarmente

$$S(u,y) = p(uy,y) = y^2 - (1+ uy) u^2 y^2 = y^2 (1 - (1 + uy)u^2)$$

$s(u,y) = 1 - (1 + uy)u^2 = 1 - u^2 + u^3y$

Formato de Entrada / Saída

(O mesmo que aqui .) Os polinômios são representados como (m+1) x (n+1)matrizes / listas de listas de coeficientes inteiros, no exemplo abaixo, os termos dos coeficientes são dados em sua posição:

[   1 * 1,   1 * x,   1 * x^2,   1 * x^3,  ... , 1 * x^n ]
[   y * 1,   y * x,   y * x^2,   y * x^4,  ... , y * x^n ]
[   ...  ,   ...   ,   ...   ,    ...   ,  ... ,   ...   ]
[ y^m * 1, y^m * x, y^m * x^2, y^m * x^3 , ..., y^m * x^n]

Portanto, uma elipse 0 = x^2 + 2y^2 -1seria representada como

[[-1, 0, 1],
 [ 0, 0, 0],
 [ 2, 0, 0]]

Se preferir, você também pode trocar xe y. Em cada direção, você pode ter zeros à direita (ou seja, coeficientes de graus mais altos que são apenas zero). Se for mais conveniente, você também pode ter matrizes escalonadas (em vez de retangulares), de forma que todas as sub-matrizes não contenham zeros à direita.

• O formato de saída é o mesmo que o formato de entrada.

Exemplos

Mais a ser adicionado ( fonte para mais )

Trifolium
p(x,y) = (x^2 + y^2)^2 - (x^3 - 3xy^2)
r(x,v) = v^4  x + 2  v^2  x + x + 3  v^2 - 1
s(u,y) = u^4  y + 2  u^2  y + y - u^3 + 3  u

Descartes Folium
p(x,y) = y^3 - 3xy + x^3
r(x,v) = v^3  x + x - 3v
s(u,y) = u^3  y + y - 3u

Exemplos sem imagens

Trifolium:
p:
[[0,0,0,-1,1],
 [0,0,0, 0,0],
 [0,3,2, 0,0],
 [0,0,0, 0,0],
 [1,0,0, 0,0]]
r: (using the "down" dimension for v instead of y)
[[-1,1],
 [ 0,0],
 [ 3,2],
 [ 0,0],
 [ 0,1]]
s: (using the "right" dimension for u instead of x)
[[0,3,0,-1,0],
 [1,0,2, 0,1]]

Descartes Folium:
p:
[[0, 0,0,1],
 [0,-3,0,0],
 [0, 0,0,0],
 [1, 0,0,0]]
r:
[[ 0,1],
 [-3,0],
 [ 0,0],
 [ 0,1]]
s:
[[0,-3,0,0],
 [1, 0,0,1]]

Lemniscate:
p: 
[[0,0,-1,0,1],
 [0,0, 0,0,0],
 [1,0, 0,0,0]]
r:
[[-1,0,1],
 [ 0,0,0],
 [ 1,0,0]]
s:
[[1,0,-1,0,0],
 [0,0, 0,0,0],
 [0,0, 0,0,1]]

Powers:
p:
[[0,1,1,1,1]]

r:
[[1,1,1,1]]

s:
[[0,1,0,0,0],
 [0,0,1,0,0],
 [0,0,0,1,0],
 [0,0,0,0,1]]

Python 3 + numpy, 165 134 bytes

lambda p:(r(p),r(p.T).T)
from numpy import*
def r(p):w,l=where(p);s=w+l;n=min(s);o=zeros((len(p),max(s)-n+1));o[w,s-n]=p[w,l];return o

Experimente online!

A função pega uma numpymatriz 2D pcomo entrada e retorna uma tupla (r,s)de duas numpymatrizes 2D.

$r$$x^jy^i$$p$$x^{j+i}(\frac{y}{x})^i$$x^{j+i}u^i$$p(x,ux)$$(m+1)\times (n+1)$$P$$(m+1)\times (m+n-1)$$D$$p(x,ux)$$D[i,j+i]=P[i,j]$$D$$R$$r$

$s$$x$$y$$R$$P^T$

O código não destruído a seguir mostra o processo de computação acima.

Sem Golfe (Básico)

import numpy as np

def r(p):
    num_rows, num_cols = p.shape
    deg_mat = np.zeros((num_rows, num_rows + num_cols - 1))
    for i, row in enumerate(p):
        deg_mat[i, i:i+num_cols] = row
    non_zero_col_idx, = np.where(deg_mat.any(axis=0))
    return deg_mat[:,non_zero_col_idx.min():non_zero_col_idx.max()+1]

def rs(p):
    return r(p), r(p.T).T

Experimente online!

$R$$R[i,j+i-c]=P[i,j]$$c=\min_{P[i,j]\neq 0}i+j$

Ungolfed (Melhorado)

import numpy as np

def r(p):
    y_deg, x_deg = np.where(p)  # Retrieve degrees of y and x for non-zero elements in p
    total_deg = y_deg + x_deg
    min_total_deg = total_deg.min()
    max_total_deg = total_deg.max()
    out = np.zeros((p.shape[0], max_total_deg - min_total_deg + 1))
    out[y_deg, y_deg + x_deg - min_total_deg] = p[y_deg, x_deg]
    return out

def rs(p):
    return r(p), r(p.T).T

Experimente online!

APL (Dyalog Unicode) , 38 37 bytes

1 byte salvo graças ao ngn usando +/∘⍴no lugar do literal fictício0

⊢∘⍉\+/∘⍴{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍺↑⍵}¨⊂,⊂∘⍉

Experimente online!

(um trem com ⎕io(origem do índice) definido como 0)

⊂ argumento certo fechado

, concatenado com

• ⊂∘ anexo

• ⍉ argumento certo transposto

$s$ é calculado a partir do primeiro, partir do último$r$

¨ em cada

+/∘⍴{ ... } execute a seguinte função com argumento esquerdo

• +/ soma

  • • ⍴ a forma do argumento correto, ou seja, obter linhas + colunas

e o argumento correto será cada uma das matrizes incluídas.

⍺↑⍵e pegue o argumento esquerdo ⍺muitas linhas do argumento direito ⍵, se ⍵estiver deficiente em linhas (o que ocorrerá porque linhas + colunas> linhas), é preenchido com 0s suficientes

O cálculo da substituição de ou no lugar de ou é feito girando as colunas de pelo seu índice e, como é preenchido com 0s, as colunas de são efetivamente precedidas pela quantidade desejada de 0s.$vx$$uy$$y$$x$⍵⍵⍵

⊖ gire as colunas

• ⍉⍵ transposto ⍵

• ≢contar linhas, todas juntas, ≢⍉⍵obtém o número de colunas em⍵

• ⍳ intervalo 0 .. contagem-1

• -negado, para girar na outra direção e o padrão para ⊖, para produzir 0 ¯1 ¯2 ... - (contagem-1), isso vetoriza automaticamente em cada coluna, de modo que a coluna 0 seja girada por 0, a 1-por 1, ...

q← atribua isso à variável q

Agora, para dividir o polinômio pela maior potência de ou , as principais linhas com 0 devem ser removidas.$x$$y$

∨/ reduza por LCM em cada linha, se a linha for todos os 0, isso gera 0, caso contrário, fornece um número positivo

×obtenha seu sinal, 0→ 0e número positivo → 1

⍸ índices de verdades, ou seja, índices de 1s

⊃escolha o primeiro elemento, ⊃⍸simplesmente obtém o índice do primeiro 1

q↓⍨elimina o número de linhas q, ⎕io←0ajuda novamente a ⍸retornar o valor correto para eliminar as principais linhas com 0

(função de saída)

$s$ já foi alcançado, para obter o segundo valor deve ser transposto via$r$⊢∘⍉\

---

Outras abordagens estão listadas abaixo.

⍝(⊢∘⍉\+/∘⍴{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍺↑⍵}¨⊂,⊂∘⍉)¨a
⍝(⊢∘⍉\∘⌽⍴{q↓⍨⊃⍸×∨/q←(-⍳⍺)⊖⍵↑⍨+/⍴⍵}¨⊂∘⍉,⊂)¨a
⍝(⊢∘⍉\⌽∘⍴{q↓⍨⊃⍸×∨/q←(-⍳⍺)⊖⍵↑⍨+/⍴⍵}¨⊂,⊂∘⍉)¨a
⍝(⊢∘⍉\0{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⊂,⊂∘⍉)¨a
⍝(⊢∘⍉\+/∘⍴({⍵↓⍨⊃⍸×∨/⍵}(-∘⍳1⊃⊢∘⍴)⊖↑)¨⊂,⊂∘⍉)¨a
⍝(⊂∘⍉∘⊃@0⍴{q↓⍨⊃⍸×∨/q←(-⍳⍺)⊖⍵↑⍨+/⍴⍵}¨⊂∘⍉,⊂)¨a
⍝{⊢∘⍉\{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝(⊢∘⍉\(({⍵↓⍨⊃⍸×∨/⍵}(-∘⍳1⊃⍴)⊖⊢↑⍨1⊥⍴)¨⊂,⊂∘⍉))¨a
⍝(0 1{⍉⍣⍺⊢q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⊂,⊂∘⍉)¨a
⍝{⊢∘⍉\{q[;⍸×∨\∨⌿q←↑(,\0⍴⍨≢⍵),¨↓⍵]}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{q↓⍨1⍳⍨×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝(⊢∘⍉\(((⊢↓⍨1⍳⍨0≠∨/)(-∘⍳1⊃⍴)⊖⊢↑⍨1⊥⍴)¨⊂,⊂∘⍉))¨a
⍝{⊢∘⍉\{q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{q↓⍨+/0=∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{q↓⍨⌊/+⌿∧⍀0=q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝(⌽∘⍉¨1↓({⊖⍉q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}\3/⊂))¨a
⍝{⊢∘⍉\{↑(↓q)/⍨∨\×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝f←⊢∘⍉\⋄{f{q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}¨f⍵⍵}¨a
⍝{1↓⌽∘⍉¨{⊖⍉q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}\3/⊂⍵}¨a
⍝{f←{q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}⋄(f⍵)(⍉f⍉⍵)}¨a
⍝{⊢∘⍉\{↑(↓q)/⍨∨\0≠∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{(0~⍨∊⍵)@(↓⍉(⊢-⌊/)@1+⍀⍉↑⍸0≠⍵)⊢0⍴⍨,⍨⌈/⍴⍵}¨⍵(⍉⍵)}¨a