Triángulo Seidel

14

El Triángulo de Seidel es una construcción matemática similar al Triángulo de Pascal, y es conocido por su conexión con los números de Bernoulli.

Las primeras filas son:

      1
      1  1
   2  2  1
   2  4  5  5
16 16 14 10 5
16 32 46 56 61 61

Cada fila se genera de la siguiente manera:

Si el número de fila es par (1 indexado):

  • Baja el primer elemento de la fila anterior

  • Cada elemento siguiente es la suma del elemento anterior y el elemento que está encima

  • Duplicar el último artículo

Si el número de fila es impar:

  • Baja el último elemento de la fila anterior

  • Yendo hacia atrás , cada elemento es la suma del elemento anterior y el elemento que está encima

  • Duplica lo que ahora es el primer elemento.

Básicamente, construimos el triángulo en un patrón de zig-zag:

    1
    v
    1 > 1
        v
2 < 2 < 1
v
2 > 4 > 5 > 5

Para obtener más información, consulte la página de Wikipedia sobre los números de Bernoulli.

El reto:

Dado n, ya sea como argumento de función o desde STDIN, imprima o devuelva la nfila th del triángulo de Seidel o las primeras nfilas. Puede usar 0 o 1 indexación.

No es necesario que maneje una entrada negativa o no entera (ni 0, si está indexada en 1). No tiene que manejar salidas más grandes que2147483647 = 2^31 - 1

Como se trata de código de golf, hazlo en el menor número de bytes posible.

Ejemplos:

En estos ejemplos, el valor de retorno es la nfila th, indexada en 0.

Input   ->  Output

0           1
1           1 1
2           2 2 1
6           272 272 256 224 178 122 61
13          22368256 44736512 66750976 88057856 108311296 127181312 144361456 159575936 172585936 183194912 191252686 196658216 199360981 199360981
Bolce Bussiere
fuente
"No tiene que manejar salidas más grandes que el tipo int predeterminado de su idioma" hace que esto sea trivial para idiomas con entradas de solo 1 bit
solo ASCII
¿Se pueden generar las filas siempre ordenadas de pequeñas a grandes?
Angs
@ Solo ASCII Cambiado para que coincida con el máximo int de C ++
Bolce Bussiere
@Angs No, las filas deben ordenarse como se muestra
Bolce Bussiere
@ Solo ASCII Esa es una laguna predeterminada (aunque en mi opinión está un poco mal redactada, ya que depende de lo que la gente considere "razonable")
user202729

Respuestas:

7

Brain-Flak , 66 bytes

<>(())<>{({}[()]<(()[{}]<<>{(({}<>{}))<>}>)>)}{}{{}<>{({}<>)<>}}<>

Pruébalo en línea!

La fila está indexada en 0.

# Push 1 (the contents of row 0) on other stack; use implicit zero as parity of current row
<>(())<>

# Do a number of times equal to input:
{({}[()]<

  # Subtract the row parity from 1
  (()[{}]<

    # For each entry in old row:
    <>{

      # Add to previous entry in new row and push twice
      (({}<>{}))<>

    }

  >)

>)}{}

# If row parity is odd:
{{}

  # Reverse stack for output
  <>{({}<>)<>}

# Switch stacks for output
}<>
Nitrodon
fuente
4

JavaScript (SpiderMonkey) , 67 bytes

Este código abusa del sort()método y no funciona en todos los motores.

Las filas están indexadas en 0.

f=(n,a=[1],r)=>n--?f(n,[...a.map(n=>k+=n,k=0),k].sort(_=>n|r),!r):a

Pruébalo en línea!

¿Cómo?

Invertimos condicionalmente una matriz utilizando el sort()método con una función de devolución de llamada que ignora sus parámetros y devuelve 0 o un entero positivo. ¡No intentes esto en casa! Esto solo funciona de manera confiable en SpiderMonkey.

let A = [1,2,3,4,5] and B = [1,2,3,4,5,6,7,8,9,10,11]

             | SpiderMonkey (Firefox)  | V8 (Chrome)             | Chakra (Edge)
-------------+-------------------------+-------------------------+------------------------
A.sort(_=>0) | 1,2,3,4,5               | 1,2,3,4,5               | 1,2,3,4,5
A.sort(_=>1) | 5,4,3,2,1               | 5,4,3,2,1               | 1,2,3,4,5
B.sort(_=>0) | 1,2,3,4,5,6,7,8,9,10,11 | 6,1,3,4,5,2,7,8,9,10,11 | 1,2,3,4,5,6,7,8,9,10,11
B.sort(_=>1) | 11,10,9,8,7,6,5,4,3,2,1 | 6,11,1,10,9,8,7,2,5,4,3 | 1,2,3,4,5,6,7,8,9,10,11

Tenga en cuenta que V8 probablemente esté utilizando diferentes algoritmos de clasificación dependiendo de la longitud de la matriz (menos o más de 10 elementos).

Comentado

f = (                     // f = recursive function taking:
  n,                      //   n   = row counter
  a = [1],                //   a[] = current row, initialized to [1]
  r                       //   r   = 'reverse' flag, initially undefined
) =>                      //
  n-- ?                   // decrement n; if it was not equal to zero:
    f(                    //   do a recursive call with:
      n,                  //     - the updated value of n
      [ ...a.map(n =>     //     - a new array:
          k += n, k = 0   //       - made of the cumulative sum of a[]
        ), k              //         with the last value appended twice
      ].sort(_ => n | r), //       - reversed if n is not equal to 0 or r is set
      !r                  //     - the updated flag r
    )                     //   end of recursive call
  :                       // else:
    a                     //   stop recursion and return a[]
Arnauld
fuente
¿Qué característica específica del mono araña utiliza esto?
Downgoat
@Downgoat Está aprovechando la implementación específica de sort()este motor. He añadido una explicación.
Arnauld
3

Haskell , 89 87 82 bytes

(cycle[r,id]!!)<*>s
r=reverse
s 0=[1]
s n=let a=zipWith(+)(0:a)$(r.s$n-1)++[0]in a

Simplemente simprime las líneas en el orden de zig-zag, la función anónima en la primera fila invierte la mitad de las filas.

¡Gracias a @nimi por guardar 5 bytes!

Pruébalo en línea!

Angs
fuente
2

Python 3 , 98 91 bytes

from itertools import*
f=lambda n:n and[*accumulate(f(n-1)[::n&1or-1]+[0])][::n&1or-1]or[1]

Pruébalo en línea!

El cambio a la numeración de filas basada en 0 ahorró 7 bytes.

RootTwo
fuente
2

Julia 0.6 , 85 bytes

r(l,n=cumsum(l))=[n...,n[end]]
w=reverse
f(n)=n<2?[1]:n%2<1?r(f(n-1)):w(r(w(f(n-1))))

Pruébalo en línea!

Esta es una solución recursiva en Julia. Tenga en cuenta que tiene indexación basada en 1. De ahí las pruebas.

Versión sin golf, para entender la lógica:

function new_row(last_row)
    new_row = cumsum(last_row)
    push!(new_row, new_row[end])
    return new_row
end


function triangle(n)
    if n == 1
        return [1]
    elseif mod(n,2) == 0
        return new_row(triangle(n-1))
    else
        return reverse(new_row(reverse(triangle(n-1))))
    end
end

Como bono, aquí hay una versión no recursiva, pero esto es más largo:

w=reverse;c=cumsum
r(l,i)=i%2<1?c([l...,0]):w(c(w([0,l...])))
f(n,l=[1])=(for i=2:n l=r(l,i)end;l)
niczky12
fuente
1

Python 2 , 103 97 bytes

f=lambda n,r=[1],k=2:n and f(n-1,[sum(r[-2::-1][:i],r[-1])for i in range(k)],k+1)or r[::-(-1)**k]

Pruébalo en línea!

Versión no recursiva (más fácil de leer):

Python 2 , 106 bytes

def f(n,r=[1],j=1):
 while n:
	a=r[-2::-1];r=r[-1:];n-=1;j=-j
	for x in a+[0]:r+=[r[-1]+x]
 return r[::-j]

Pruébalo en línea!

¡Seguramente, mejor es posible!

Chas Brown
fuente
1

Python 3 , 91 bytes

from numpy import *
s=lambda n:n and cumsum(s(n-1)[::n%2*2-1]+[0]).tolist()[::n%2*2-1]or[1]

Pruébalo en línea!

Guoyang Qin
fuente
Puede eliminar el espacio entre importy*
12Me21