12
\$\begingroup\$

Challenge: implement calculation of a Delacorte Number in any language. Shortest code wins.

For a given square matrix of distinct integers 1..n² (possible side length n at least between 3 and 27), its Delacorte Number is the sum of the products gcd(a, b) × distance²(a, b) for each distinct pair of integers {a, b}.

The following example shows a 3×3 square with a Delacorte Number of 160.

3 2 9
4 1 8
5 6 7

In this square we have 36 distinct pairs to calculate, for example the pair 4 and 6: gcd(4, 6) × distance²(4, 6) = 4

Another example square for testing - this has a Delacorte Number of 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

Delacorte Numbers are taken from this programming contest - see there for further details... The contest ended in January 2015. It was great fun!

Rules:

Necessary line breaks count as 1 char. You may post your golfed solution with line breaks, but they are only counted if necessary in that language.

You can choose how to handle input and output and you don't have to count the necessary framework of your language, like standard-includes or main function headers. Only the actual code counts (including shortcut/alias definitions), like in this C# example:

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();
        }
    }
}

You may also input the square as 2-dimensional array or from a prompt or as string or some standard collection type. A 2-dimensional array is the only way not having to calculate the side length of the square yourself.
A sub-function for the actual work is not required, you could also put the code directly within Main().

Even more preparation is allowed for free, like here:

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();
    }
}

If you are unsure whether your lengthy preparation is in the spirit of these rules or could be called cheating, just ask :)

\$\endgroup\$
  • \$\begingroup\$ Sounds like, in case of Python, all includes are for free? This can cause some weird optimizations... \$\endgroup\$ – Falko Nov 10 '14 at 11:26
  • \$\begingroup\$ @Falko, the question is, what are standard-includes? Please try to understand the spirit of the rules and adapt them to your language. So, no: see my using example - if it is used to include a library because otherwise you could not call some function, it is free. If you use it to define some short alias for anything, the whole instruction counts. \$\endgroup\$ – maf-soft Nov 10 '14 at 13:04
  • \$\begingroup\$ @Optimizer: The meaning of the distance function is somewhat hidden in the link: It's the square of the euclidean distance between the two fields. \$\endgroup\$ – Falko Nov 10 '14 at 13:07
  • \$\begingroup\$ @Optimizer, instead of exactly defining it, I gave an example, so you can be sure what is meant. I thought that is enough and added fun... \$\endgroup\$ – maf-soft Nov 10 '14 at 13:11
  • \$\begingroup\$ And I must say that although its a legit question, it seems like that you have posted it here to finally be able to enter that contest ;) \$\endgroup\$ – Optimizer Nov 10 '14 at 13:13
6
\$\begingroup\$

APL (38)

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

This is a function that takes a matrix as its right argument, like so:

      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

Explanation:

  • ⊂¨⍳⍴Z←⍵: store the matrix in Z. Make a list of each possible pair of coordinates in Z.
  • ∘.{...}⍨: for each pair of coordinates, combined with each pair of coordinates:
    • +/⊃×⍨⍺-⍵: calculate distance^2: subtract the first pair of coordinates from the second, multiply both by themselves and sum the result
    • ∨/Z[⍺⍵]: get the number in Z for both pairs of coordinates, and find the GCD
    • ×: multiply them by each other
  • +/∊: sum the elements of the result of that
  • .5×: multiply by 0.5 (because we counted each nonzero pair twice earlier)
\$\endgroup\$
  • \$\begingroup\$ This would be 72 bytes if we count using UTF-8 bytes. \$\endgroup\$ – kennytm Nov 10 '14 at 22:50
  • 2
    \$\begingroup\$ @KennyTM: the APL charset fits within a byte. Encodings exist that use this. APL predates Unicode by decades. It seems to be accepted on this site to count APL characters as bytes, as long as no Unicode characters are used. (i.e. using Unicode codepoints to encode strings, or something.) \$\endgroup\$ – marinus Nov 11 '14 at 14:22
  • \$\begingroup\$ @marinus, that sounds reasonable. What do you think about the unicode chars in Mathematica? \$\endgroup\$ – maf-soft Nov 11 '14 at 16:32
  • \$\begingroup\$ @maf-soft: well, if there is an existing encoding by which all of the characters used fit within a byte (so that includes both the 'special' and the 'normal' characters, so there can't be more than 256 unique characters), then it can be counted as one byte per character. If not, then it can't. However, if Mathematica uses less than 128 unique Unicode characters, they can be trivially mapped into the upper half of the byte, with ASCII in the lower half. [1/2]. \$\endgroup\$ – marinus Nov 11 '14 at 17:05
  • \$\begingroup\$ @maf-soft: this would be a novel encoding (~ "language"), though, so you'd need to provide a translator program, and you could only use it on questions that are newer than your translator program, by the rule that states you can only answer questions in languages that predate the question (this to prevent someone defining a language with an 1-byte command to exactly solve the question). [2/2] \$\endgroup\$ – marinus Nov 11 '14 at 17:07
5
\$\begingroup\$

Mathematica (83 82 79 69 67 66)

Preparation

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}}

Code

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

If we count using Unicode characters: 62:

Tr[ArrayRules@a~Tuples~2/.{t_u_,v_w_}u~GCD~w#.#&[t-v]]〚1〛/2
\$\endgroup\$
  • \$\begingroup\$ You can use UTF version of '->`:  \$\endgroup\$ – swish Nov 11 '14 at 14:08
  • \$\begingroup\$ @swish -> takes 2 characters and takes 1 character, however, -> takes 2 bytes and takes 3 bytes in UTF-8. So it may be longer depending on the metrics. \$\endgroup\$ – kennytm Nov 11 '14 at 14:12
  • \$\begingroup\$ Well look at APL solution, so I guess the metric is in characters on this one ;) \$\endgroup\$ – swish Nov 11 '14 at 14:14
  • \$\begingroup\$ @swish That's something OP should clarify as UTF-8 bytes is the default if not stated :) \$\endgroup\$ – kennytm Nov 11 '14 at 14:15
  • \$\begingroup\$ @KennyTM - I'm not sure what's best. I'd like to follow what's common on this site. Currently I have no time to find out. Could someone help out with some links? You can also use the chat mentioned in the OP comments. \$\endgroup\$ – maf-soft Nov 11 '14 at 16:27
5
\$\begingroup\$

Python - 128 112 90 89 88

Preparation:

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

Computing the Delacorte Number (the line that counts):

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

Output:

print D

Result:

5957
\$\endgroup\$
  • 2
    \$\begingroup\$ You can collapse both for loops into a single generator and sum it once. Also, you can save P(R,R) to a variable by *x,=product(R,R), using the starred assignment to make a copy. Even better, you can make it be the four-fold product product(R,R,R,R) and just do for j,n,i,m in product(*[R]*4). \$\endgroup\$ – xnor Nov 12 '14 at 5:40
  • \$\begingroup\$ @xnor: Great! *[R]*4 is what I was looking for by myself but couldn't get to work. \$\endgroup\$ – Falko Nov 13 '14 at 6:27
  • 1
    \$\begingroup\$ seeing as your preparation doesn't count towards the byte count, can't you do something like from fractions import gcd as g to save bytes in the important section? \$\endgroup\$ – FlipTack Nov 4 '16 at 16:15
3
\$\begingroup\$

Pyth 43

This answer could almost certainly be golfed further; I particularly don't like the distance calculation.

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

To set this up, store the linear-ized array in the variable J. You can do this by writing:

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

Try it online.

Outputs a float. I think this is legitimate, please tell me if I've broken a rule :)

Explanation:

                                             : 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
\$\endgroup\$
  • \$\begingroup\$ Wow, I finally beat Pyth with APL. \$\endgroup\$ – marinus Nov 11 '14 at 14:24
  • \$\begingroup\$ @marinus Haha, I'm still trying, but I think you've got me beat, at least :) \$\endgroup\$ – FryAmTheEggman Nov 11 '14 at 14:32
  • \$\begingroup\$ Wow, this is crazy. I'm reading the doc.txt now but I find it really hard to read! \$\endgroup\$ – rubik Nov 11 '14 at 19:41
  • \$\begingroup\$ @rubik At least it isn't APL :D The doc isn't 100% accurate because this whole language is mantained by one guy: isaacg. If you have questions, feel free to ask me/him in chat :) \$\endgroup\$ – FryAmTheEggman Nov 11 '14 at 20:19
2
\$\begingroup\$

CJam, 55

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

Takes the matrix as STDIN in the following format:

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

Try it online here

\$\endgroup\$
  • \$\begingroup\$ I think you could hard-code the matrix for free and use {} to make a block rather than use stdin. Also, are you dumping the matrix into a one-dimensional array? I think you can take the matrix already formatted, see the OP's examples. (I don't know CJam well, so take this with a grain of salt ;) ) \$\endgroup\$ – FryAmTheEggman Nov 10 '14 at 14:57
  • \$\begingroup\$ Reading the matrix and converting it to single list is the q~] part. which is shorter as compared to when i hard code it and use a block (I guess) \$\endgroup\$ – Optimizer Nov 10 '14 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.