Calcular el número de Delacorte de un cuadrado

12

Reto: implementar el cálculo de un número de Delacorte en cualquier idioma. El código más corto gana.

Para una matriz cuadrada dada de enteros distintos 1..n² (longitud de lado posible n al menos entre 3 y 27), su número de Delacorte es la suma de los productos gcd (a, b) × distancia² (a, b) para cada distinto par de enteros {a, b}.

El siguiente ejemplo muestra un cuadrado de 3 × 3 con un número de Delacorte de 160.

3 2 9
4 1 8
5 6 7

En este cuadrado tenemos 36 pares distintos para calcular, por ejemplo, el par 4 y 6: mcd (4, 6) × distancia ² (4, 6) = 4

Otro cuadrado de ejemplo para pruebas: tiene un número de Delacorte de 5957:

10  8 11 14 12
21  4 19  7  9
 5 13 23  1 16
18  3 17  2 15
24 22 25  6 20

Los números de Delacorte se toman de este concurso de programación . Vea allí para más detalles ... El concurso terminó en enero de 2015. ¡Fue muy divertido!

Reglas:

Los saltos de línea necesarios cuentan como 1 carácter. Puede publicar su solución de golf con saltos de línea, pero solo se cuentan si es necesario en ese idioma.

Puede elegir cómo manejar la entrada y la salida y no tiene que contar el marco necesario de su idioma, como cabeceras de funciones principales o de inclusión estándar. Solo el código real cuenta (incluidas las definiciones de acceso directo / alias), como en este ejemplo de C #:

namespace System
{
    using Collections.Generic;
    using I=Int32; //this complete line counts
    class Delacorte
    {
        static I l(I[]a){return a.Length;} //of course this complete line counts

        static void CalculateSquare(int[] a, out int r)
        {
            r=0;for(I i=l(a);i-->0;)r+=a[i]; //here only this line counts
        }

        static void Main()
        {
            int result;
            CalculateSquare(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, out result);
            Console.Write(result); //should output 140 for the example
            Console.ReadKey();
        }
    }
}

También puede ingresar el cuadrado como una matriz bidimensional o desde una solicitud o como una cadena o algún tipo de colección estándar. Una matriz bidimensional es la única forma de no tener que calcular la longitud lateral del cuadrado usted mismo.
No se requiere una subfunción para el trabajo real, también puede poner el código directamente dentro de Main ().

Se permite aún más preparación de forma gratuita, como aquí:

using System;
unsafe class Delacorte
{
    static void CalculateSquare(int* a, out int r)
    {
        r=0;while(*a>0)r+=*a++; //only this line counts
    }

    static void Main()
    {
        var input = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; //adding a terminator
        int result;
        fixed (int* a = &input[0]) //necessary in C#
            CalculateSquare(a, out result);
        Console.Write(result);
        Console.ReadKey();
    }
}

Si no está seguro de si su larga preparación está en el espíritu de estas reglas o podría llamarse trampa, solo pregunte :)

maf-soft
fuente
¿Parece que, en el caso de Python, todas las inclusiones son gratis? Esto puede causar algunas optimizaciones extrañas ...
Falko
@Falko, la pregunta es, ¿qué son los estándares incluidos? Intente comprender el espíritu de las reglas y adáptelas a su idioma. Entonces, no: vea mi usingejemplo: si se usa para incluir una biblioteca porque de lo contrario no podría llamar a alguna función, es gratis. Si lo usa para definir algunos alias cortos para cualquier cosa, toda la instrucción cuenta.
maf-soft
@Optimizer: el significado de la función de distancia está algo oculto en el enlace : es el cuadrado de la distancia euclidiana entre los dos campos.
Falko
@Optimizer, en lugar de definirlo exactamente, di un ejemplo, para que pueda estar seguro de lo que significa. Pensé que era suficiente y agregué diversión ...
maf-soft
Y debo decir que aunque es una pregunta legítima, parece que la has publicado aquí para finalmente poder participar en ese concurso;)
Optimizer

Respuestas:

6

APL (38)

{.5×+/∊∘.{(∨/Z[⍺⍵])×+/⊃×⍨⍺-⍵}⍨⊂¨⍳⍴Z←⍵}

Esta es una función que toma una matriz como argumento correcto, así:

      sq5←↑(10 8 11 14 12)(21 4 19 7 9)(5 13 23 1 16)(18 3 17 2 15)(24 22 25 6 20)
      sq5
10  8 11 14 12
21  4 19  7  9
 5 13 23  1 16
18  3 17  2 15
24 22 25  6 20
      {.5×+/∊∘.{(∨/Z[⍺⍵])×+/⊃×⍨⍺-⍵}⍨⊂¨⍳⍴Z←⍵}sq5
5957

Explicación:

  • ⊂¨⍳⍴Z←⍵: almacena la matriz en Z. Haga una lista de cada posible par de coordenadas en Z.
  • ∘.{... }⍨: para cada par de coordenadas, combinado con cada par de coordenadas:
    • +/⊃×⍨⍺-⍵: calcular distance^2: restar el primer par de coordenadas de la segunda, multiplicar por sí mismos y sumar el resultado
    • ∨/Z[⍺⍵]: obtenga el número Zpara ambos pares de coordenadas y encuentre el MCD
    • ×: multiplíquelos entre sí
  • +/∊: suma los elementos del resultado de ese
  • .5×: multiplique por 0.5 (porque contamos cada par distinto de cero dos veces antes)
marinus
fuente
Esto sería 72 bytes si contamos usando bytes UTF-8.
kennytm
2
@KennyTM: el juego de caracteres APL cabe dentro de un byte. Existen codificaciones que usan esto. APL es anterior a Unicode por décadas. Parece que se acepta en este sitio contar los caracteres APL como bytes, siempre que no se usen caracteres Unicode. (es decir, utilizando puntos de código Unicode para cadenas codificar, o algo así.)
marinus
@marinus, eso suena razonable. ¿Qué opinas sobre los caracteres unicode en Mathematica?
maf-soft
@ maf-soft: bueno, si hay una codificación existente por la cual todos los caracteres utilizados encajan dentro de un byte (de modo que incluye tanto los caracteres 'especiales' como los 'normales', entonces no puede haber más de 256 caracteres únicos) caracteres), entonces se puede contar como un byte por carácter. Si no, entonces no puede. Sin embargo, si Mathematica usa menos de 128 caracteres Unicode únicos, se pueden asignar trivialmente en la mitad superior del byte, con ASCII en la mitad inferior. [1/2].
marinus
@ maf-soft: sin embargo, esta sería una codificación novedosa (~ "idioma"), por lo que necesitaría proporcionar un programa de traducción y, por regla general, solo podría usarlo en preguntas que son más nuevas que su programa de traducción. eso indica que solo puede responder preguntas en idiomas anteriores a la pregunta (esto para evitar que alguien defina un idioma con un comando de 1 byte para resolver exactamente la pregunta). [2/2]
marinus
5

Mathematica (83 82 79 69 67 66)

Preparación

a={{10,8,11,14,12},{21,4,19,7,9},{5,13,23,1,16},{18,3,17,2,15},{24,22,25,6,20}}

Código

#/2&@@Tr[ArrayRules@a~Tuples~2/.{t_->u_,v_->w_}->u~GCD~w#.#&[t-v]]

Si contamos con caracteres Unicode: 62 :

Tr[ArrayRules@a~Tuples~2/.{t_u_,v_w_}u~GCD~w#.#&[t-v]]〚1〛/2
kennytm
fuente
Puede usar la versión UTF de '-> `: 
swish
@swish ->toma 2 caracteres y toma 1 carácter, sin embargo, ->toma 2 bytes y toma 3 bytes en UTF-8. Por lo tanto, puede ser más largo dependiendo de las métricas.
kennytm
Bueno, mira la solución APL, así que supongo que la métrica está en caracteres en esta;)
swish
@swish Eso es algo que OP debería aclarar ya que los bytes UTF-8 son los predeterminados si no se indica :)
kennytm
@KennyTM: no estoy seguro de qué es lo mejor. Me gustaría seguir lo que es común en este sitio. Actualmente no tengo tiempo para averiguarlo. ¿Podría alguien ayudarme con algunos enlaces? También puede usar el chat mencionado en los comentarios de OP.
maf-soft
5

Python - 128112 90 89 88

Preparación:

import pylab as pl
from fractions import gcd
from numpy.linalg import norm
from itertools import product

A = pl.array([
    [10,  8, 11, 14, 12],
    [21,  4, 19,  7,  9],
    [ 5, 13, 23,  1, 16],
    [18,  3, 17,  2, 15],
    [24, 22, 25,  6, 20]])

Calcular el número de Delacorte (la línea que cuenta):

D=sum(gcd(A[i,j],A[m,n])*norm([m-i,n-j])**2for j,n,i,m in product(*[range(len(A))]*4))/2

Salida:

print D

Resultado:

5957
Falko
fuente
2
Puede contraer ambos forbucles en un solo generador y sumuna vez. Además, puede guardar P(R,R)en una variable *x,=product(R,R)utilizando la asignación destacada para hacer una copia. Aún mejor, puede hacer que sea el producto cuádruple product(R,R,R,R)y simplemente hacerlo for j,n,i,m in product(*[R]*4).
xnor
@xnor: ¡Genial! *[R]*4es lo que estaba buscando solo pero no pude ir a trabajar.
Falko
1
Ya que su preparación no cuenta para el recuento de bytes, ¿no puede hacer algo como from fractions import gcd as gguardar bytes en la sección importante?
FlipTack el
3

Pyth 43

Es casi seguro que esta respuesta se pueda seguir jugando; Particularmente no me gusta el cálculo de distancia.

K^lJ.5VJFdUN~Z*i@JN@Jd+^-/dK/NK2^-%dK%NK2;Z

Para configurar esto, almacene la matriz linealizada en la variable J. Puede hacer esto escribiendo:

J[3 2 9 4 1 8 5 6 7)

Pruébalo en línea .

Emite un flotador. Creo que esto es legítimo, dígame si he infringido una regla :)

Explicación:

                                             : Z=0 (implicit)
K^lJ.5                                       : K=sqrt(len(J))
      VJ                                     : for N in range(len(J))
        FdUN                                 : for d in range(N)
            ~Z*                              : Z+= the product of
               i@JN@Jd                       : GCD(J[N],J[d])
                      +^-/dK/NK2^-%dK%NK2    : (d/K-N/K)^2 + (d%K-N%K)^2 (distance)
                                         ;Z  : end all loops, and print Z
FryAmTheEggman
fuente
Wow, finalmente vencí a Pyth con APL.
marinus
@marinus Jaja, todavía lo estoy intentando, pero creo que me tienes vencido, al menos :)
FryAmTheEggman
Wow, esto es una locura. ¡Estoy leyendo el doc.txt ahora pero me resulta muy difícil de leer!
rubik
@rubik Al menos no es APL: D El documento no es 100% exacto porque todo este lenguaje es mantenido por un tipo: isaacg . Si tiene preguntas, no dude en preguntarme / él en el chat :)
FryAmTheEggman
2

CJam, 55

q~:Q__,mqi:L;m*{_~{_@\%}h;\[Qf#_Lf/\Lf%]{~-_*}/+*}%:+2/

Toma la matriz como STDIN en el siguiente formato:

[10  8 11 14 12
 21  4 19  7  9
  5 13 23  1 16
 18  3 17  2 15
 24 22 25  6 20]

Pruébalo en línea aquí

Optimizador
fuente
Creo que podría codificar la matriz de forma gratuita y usarla {}para hacer un bloque en lugar de usar stdin. Además, ¿está volcando la matriz en una matriz unidimensional? Creo que puede tomar la matriz ya formateada, vea los ejemplos del OP. (No conozco bien a CJam, así que tómalo con un grano de sal;))
FryAmTheEggman
Leer la matriz y convertirla en una sola lista es la q~]parte. que es más corto en comparación con cuando lo codifico y uso un bloque (supongo)
Optimizer