12
\$\begingroup\$

Challenge

Create a program that outputs a square grid showing visible and non-visible points \$(x, y)\$ from the origin based on their greatest common divisor (GCD).

A point \$(x, y)\$ is considered visible from the origin \$(0, 0)\$ if the \$\gcd(x, y) = 1\$. Otherwise, it's non-visible.

x_y

Input

An integer \$n\$, representing the radius of the square grid from the origin along both \$x\$ and \$y\$ axes.

Output

A square grid centered at the origin, where each cell is:

  • ". " (dot followed by a space) for a visible point
  • "\$\ \ \$" (two spaces) for a non-visible point

Examples

Length from the origin: n = 6

  .       .   .       .   
.   . . . .   . . . .   . 
  .   .   .   .   .   .   
  . .   . .   . .   . .   
  .   .   .   .   .   .   
. . . . . . . . . . . . . 
          .   .           
. . . . . . . . . . . . . 
  .   .   .   .   .   .   
  . .   . .   . .   . .   
  .   .   .   .   .   .   
.   . . . .   . . . .   . 
  .       .   .       .   

Length from the origin: n = 5

  . . . .   . . . .   
.   .   .   .   .   . 
. .   . .   . .   . . 
.   .   .   .   .   . 
. . . . . . . . . . . 
        .   .         
. . . . . . . . . . . 
.   .   .   .   .   . 
. .   . .   . .   . . 
.   .   .   .   .   . 
  . . . .   . . . .   

Length from the origin: n = 4

  .   .   .   .   
.   . .   . .   . 
  .   .   .   .   
. . . . . . . . . 
      .   .       
. . . . . . . . . 
  .   .   .   .   
.   . .   . .   . 
  .   .   .   .   

Length from the origin: n = 3

  . .   . .   
.   .   .   . 
. . . . . . . 
    .   .     
. . . . . . . 
.   .   .   . 
  . .   . .   

Length from the origin: n = 2

  .   .   
. . . . . 
  .   .   
. . . . . 
  .   .   

Length from the origin: n = 1

. . . 
.   . 
. . . 

References

Visible Points in a Lattice

Visible Point -- from Wolfram MathWorld

Lattice points visible from the origin

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Is it necessary to output the trailing spaces on each line? \$\endgroup\$ Mar 11 at 16:05
  • \$\begingroup\$ Shouldn’t the lattice point (0, 0) a. k. a. the origin be marked, too? I mean it is “visible” from the origin. The line of sight has a length of zero, but this should not harm the mathematical conception of “visibility”, right? May we be allowed to mark or leave the origin unmarked at our discretion? \$\endgroup\$ Mar 11 at 16:36
  • 1
    \$\begingroup\$ Is it allowed to output with a different format (e.g. as a matrix, graphical output, etc.)? \$\endgroup\$
    – Yousername
    Mar 11 at 23:29
  • 1
    \$\begingroup\$ @wheatwizard, why remove the image from the post? The text in the first section now refers to four dashed line segments, but they're nowhere to be seen. \$\endgroup\$
    – ilkkachu
    Mar 12 at 9:58
  • 1
    \$\begingroup\$ @ilkkachu Unfortunately (potential) copyright infringement: The (most probable) source of the image does not indicate that the image may be re‑released under a CC‑By‑SA license here, nor did vengy disclose he/she is known as Austin, אבא, or Jasmine (the authors’ first names of the original source) in real life (thus a co‑owner of copyright). \$\endgroup\$ Mar 12 at 13:37

14 Answers 14

6
\$\begingroup\$

Jelly, 12 bytes

rNgþ`=1ị⁾. G

Try It Online!

-3 bytes thanks to totallyhuman (-1 myself on top of this)

Explanation

rNgþ`=1ị⁾. G    Main Link
rN              [n, ..., -n]
  gþ`           Outer product table over GCD
     =1         Check if equal to 1 (vectorizes)
       ị⁾. G    Index into [".", " "] and display as grid
\$\endgroup\$
4
  • \$\begingroup\$ 13 bytes. Palindromizing is expensive. \$\endgroup\$ Mar 11 at 16:20
  • \$\begingroup\$ @totallyhuman Oh neat, I didn't realize that'd work properly for negatives. I had a feeling bounce was inefficient but didn't know how else to do it; thanks! \$\endgroup\$
    – hyper-neutrino
    Mar 11 at 16:32
  • 1
    \$\begingroup\$ Thanks for making me feel stupid in turn with the rN. :P All these years and I still can't get the hang of this language... \$\endgroup\$ Mar 11 at 16:41
  • 1
    \$\begingroup\$ @totallyhuman lol, chain rules are hard can't blame you :P \$\endgroup\$
    – hyper-neutrino
    Mar 11 at 16:48
3
\$\begingroup\$

Haskell, 68 61 bytes

-7 bytes thanks to Lynn.

f n|r<-[-n..n]=unlines[do x<-r;" . "!!min(gcd x y)2:" "|y<-r]

Try it online!

unlines can be dropped if a list of lines is okay.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Some byte saves: f n|r<-[-n..n]=unlines[do x<-r;" . "!!min(gcd x y)2:" "|y<-r] \$\endgroup\$
    – Lynn
    Mar 20 at 2:40
  • \$\begingroup\$ @Lynn min! min!! I can't believe I spent that long trying to shorten that conditional and didn't think of min. Also interesting that do-notation is shorter here... Thanks! \$\endgroup\$ Mar 20 at 3:19
2
\$\begingroup\$

APL (Dyalog Unicode), 30 bytes SBCS

Assume ⎕io←0

{↑,⌿'. ' '  '[1≠∘.∨⍨⍵-⍳1+⍵+⍵]}

Try it on APLgolf!

{↑,⌿'. ' '  '[1≠∘.∨⍨⍵-⍳1+⍵+⍵]}
                    ⍵-⍳1+⍵+⍵   ⍝ indices ⍵ ⍵-1 ⍵-2 ... 2-⍵ 1-⍵ -⍵
                ∘.∨⍨           ⍝ pairwise GCD
              1≠               ⍝ is not 1
    '. ' '  '[              ]  ⍝ Choose between strings '. ' and '  '.
 ↑,⌿                           ⍝ Combine the strings
\$\endgroup\$
1
  • \$\begingroup\$ Nice! The output looks great! \$\endgroup\$
    – vengy
    Mar 11 at 15:58
2
\$\begingroup\$

JavaScript (V8), 89 bytes

n=>{for(y=~n;y++-n;)print((g=(a,b=y)=>x-~n?b?g(b,a%b):(a*a-1?"  ":". ")+g(--x):"")(x=n))}

Try it online!

Commented

n => {                  // n = input
  for(                  // main loop:
    y = ~n;             //   start with y = -n - 1
    y++ - n;            //   stop when y = n / increment y afterwards
  )                     //
  print(                // print the next line:
    ( g = (             //   g is a recursive function taking:
        a,              //     an integer a
        b = y           //     and an integer b initialized to y
      ) =>              //
      x - ~n ?          //   if x is greater than -n - 1:
        b ?             //     if b is not 0:
          g(b, a % b)   //       do a recursive call with [a, b] = [b, a mod b]
        :               //     else:
          ( a * a - 1 ? //       if a² is not equal to 1:
              "  "      //         append two spaces
            :           //       else:
              ". "      //         append a period and a space
          ) + g(--x)    //       decrement x and do a recursive call
      :                 //   else:
        ""              //     stop
    )(x = n)            //   initial call to g with a = x = n
  )                     // end of print()
}                       //
\$\endgroup\$
2
\$\begingroup\$

Ruby, 74 51 bytes

-23 (!) bytes thanks to Sisyphus

->n{a=-n..n
a.map{|y|a.map{" ."[2[_1.gcd y]]+" "}}}

Attempt This Online!

\$\endgroup\$
2
  • \$\begingroup\$ double map is shorter than each_slice: Attempt This Online! \$\endgroup\$
    – Sisyphus
    Mar 12 at 0:29
  • \$\begingroup\$ @Sisyphus Thansks for the assist. That's a nice trick, indexing into 2's bits. \$\endgroup\$
    – Jordan
    Mar 12 at 14:36
2
\$\begingroup\$

C (gcc), 107 bytes

-8 bytes, thanks to ceilingcat

g(a,b){return b?g(b,a%b):a*a;}x,y;f(l){for(y=~l;y++<l;puts(""))for(x=~l;x++<l;)printf(g(x,y)-1?"  ":". ");}

Try it online!

\$\endgroup\$
0
2
\$\begingroup\$

Python+Numpy+Pandas, 152 bytes

import numpy as np,pandas
def p(n):pandas.DataFrame([c for c in np.dstack(np.mgrid[-n:n+1,-n:n+1]).reshape(-1,2)if np.gcd(*c)==1]).plot.scatter(x=0,y=1)

Outputs a graphical plot (even though this isn't strictly the challenge, but when do you see Pandas in code golf?). Ex, p(3):

Example

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 33 bytes

E⊕N⭆⊕ι§ .∧∨ιλ⬤…²⊕ι∨﹪ιν﹪λν‖O↗↑←UE¹

Try it online! Link is to verbose version of code. Explanation:

E⊕N⭆⊕ι§ .∧∨ιλ⬤…²⊕ι∨﹪ιν﹪λν

Draw one octant of the diagram.

‖O↗↑←

Reflect to complete the diagram. (The reflections are performed serially, so first the octant is reflected diagonally to create the quadrant, then the other two reflections complete the negative axes.)

UE¹

Space the .s horizontally.

\$\endgroup\$
1
\$\begingroup\$

Pascal, 238 Bytes

This is a complete program as per ISO standard 7185 “Standard Pascal”.

program p(input,output);type Z=integer;var n,y:Z;function f(a,b:Z):Z;begin f:=a;if b>0 then f:=f(b,a mod b)end;begin read(n);n:=abs(n);for y:=-n to n do begin for n:=-n to n do write((' .')[ord(f(abs(n),abs(y))=1)+1],' ');writeLn end end.

Ungölfed:

program latticePointsVisibleFromOrigin(input, output);
    const
        mark = ' .';
    type
        Z = integer;
    var
        n, y: Z;
    { GreatestCommonDivisor for _non­negative_ _integers_ _only_. }
    function greatestCommonDivisor(a, b: Z): Z;
        begin
            greatestCommonDivisor ≔ a;
            if b > 0 then
            begin
                greatestCommonDivisor ≔ greatestCommonDivisor(b, a mod b)
            end
        end;
    { ─── main ────────────────────────────────────────────────── }
    begin
        readLn(input, n);
        n ≔ abs(n);
        
        { In Pascal `for`‑loop limits are evaluated (exactly) once. }
        for y ≔ n downto −n do
        begin
            for n ≔ −n to n do
            begin
                { `+1` because in Pascal `string` indices are one‑based. }
                write(output,
                    mark[ord(greatestCommonDivisor(abs(n), abs(y)) = 1) + 1],
                    ' ')
            end;
            writeLn(output)
        end
    end.
\$\endgroup\$
0
1
\$\begingroup\$

Scala 3, 148 bytes

A port of @Jordan's Ruby answer in Scala.


Golfed version. Attempt This Online!

n=>{val a=(-n to n);(for(x<-a;y<-a)yield(x,y)).map{case(x,y)=>if(BigInt(x).gcd(y)==1)". " else"  "}.grouped(n*2+1).foreach(r=> println(r.mkString))}

Ungolfed version. Attempt This Online!

object Main extends App {
  def F(n: Int): Unit = {
    val a = (-n to n).toList
    val pairs = for (x <- a; y <- a) yield (x, y)
    val pattern = pairs.map { case (x, y) => if (BigInt(x).gcd(y) == 1) ". " else "  " }
    pattern.grouped(n * 2 + 1).foreach(row => println(row.mkString))
  }

  F(6)
}
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 64 bytes

n->[print(concat([if(gcd(i,j)-1,"  ",". ")|j<-r]))|i<-r=[-n..n]]

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

TI-Basic, 65 bytes

Input N
For(I,~N,N
".
For(J,~N,N
Ans+sub(" .",1=gcd(abs(I),abs(J)),1)+" 
End
Disp sub(Ans,2,2N+1
End

~ represents the negative sign. The fifth line ends with a space. The output may be cut off if the input is too large.

\$\endgroup\$
1
\$\begingroup\$

Uiua SBCS, 31 bytes

⊏:" ."=1◌⊞⍢⊃◿∘±:↘1♭≡⊂0.⌵-⇡+1×2.

Try it!

⊏:" ."=1◌⊞⍢⊃◿∘±:↘1♭≡⊂0.⌵-⇡+1×2.
                        -⇡+1×2.  # [-n..n]
                       ⌵         # abs
                      .          # duplicate
               :↘1♭≡⊂0           # interleave zeros
         ⊞⍢⊃◿∘±                  # table by gcd
        ◌                        # pop
      =1                         # where is it equal to one?
⊏:" ."                           # change to string
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 13 bytes

(ŸÄDδ¿Θ»T„. ‡

Try it online or verify all test cases.

Explanation:

(              # Negate the (implicit) input-integer
 Ÿ             # Push a list in the range [(implicit) input, -input]
  Ä            # Take the absolute value of each: [n,n-1,...,0,...,n-1,n]
   Dδ¿         # Create a GCD-table of this list:
   D           #  Duplicate the list:
    δ          #  Pop both lists, and apply double-vectorized:
     ¿         #   Greatest Common Divisor
      Θ        # Check which values are 1 (1 if 1; 0 otherwise)
       »       # Join each inner list by spaces, and then each string by newlines
        T      # Push 10
         „.    # Push ". "
            ‡  # Transliterate all 1s to "."s and all 0s to spaces
               # (after which the result is output implicitly)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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