15
\$\begingroup\$

This puzzle is derived from CodinGame SamSi's "Heart of the City" puzzle.

Description

You decide to take a walk in an n * n tile city and go to the center tile. All of the buildings are infinitely small, but you have super vision and can see everything close up and far away.

Constraints

n is always odd

You can see any building that is not directly obstructed by another one

Task

Mark each building visible with *. The building is visible iff it is not blocked by another building on the exact same line of vision.

In other words, if @ is the origin, the building is visible iff the x-coordinate and the y-coordinate are co-prime to each other.

Example input and output

Input:

7

Output:

 ** **
* * * *
*******
  *@*
*******
* * * *
 ** **

* is a visible building, is an invisible building, and @ is where you are.

Scoring

Remember, this is , so the answer with the least bytes wins.

var QUESTION_ID=91394,OVERRIDE_USER=59057;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}*{font-family:"Helvetica",sans-serif}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • \$\begingroup\$ Can you clarify on how the output is generated? \$\endgroup\$ – Leaky Nun Aug 28 '16 at 5:06
  • \$\begingroup\$ I think it'll be good to have an example where the input is much bigger than 5, since the output for 5 isn't particularly illustrative \$\endgroup\$ – Sp3000 Aug 28 '16 at 5:07
  • \$\begingroup\$ Are we always at the centre? What about when the input is even? \$\endgroup\$ – Leaky Nun Aug 28 '16 at 5:08
  • 1
    \$\begingroup\$ @LeakyNun "n is always odd" \$\endgroup\$ – Sp3000 Aug 28 '16 at 5:08
  • \$\begingroup\$ @LeakyNun The output can be generated however you want, but it has to follow the output specifications. Am I correct with the 7x7 input/output? \$\endgroup\$ – Soren Aug 28 '16 at 5:10

10 Answers 10

8
\$\begingroup\$

Excel-VBA, (47*n^2) bytes and 121 bytes

Instruction:

Excel turns out to be very handy for this challenge and there are combination of Excel formulas to get the exact pattern as the OP's shown for a given input. Luckily enough for me, Excel has a GCD function - a built-in formula to return greatest common divisor of positive integers so I don't have to create one using Euclidean algorithm. Why do I need a GCD function here? It's because two numbers are called coprime, if their greatest common divisor equals 1. The numbers here is the coordinate of the position, x and y, relative to the origin, @. Here is the Excel formula

=IF(GCD(ABS(COLUMN()-m),ABS(m-ROW()))=1,"*","")

where m is the name of a reference cell and it's equal to the smallest integer greater than or equal to n/2, ceiling(n/2), where n is the name of a reference cell for the input. Paste this formula in cell A1, then drag all over range with the size n x n. The length of the formula is 47 bytes but you have to replicate it n x n times, so it's equal to (47*n^2) bytes.

To automate the process and to reduce the use of characters, we can use VBA since it's integrated with Excel. First thing first, set a worksheet Excel like the following:

enter image description here

Then put the following code in the Immediate Window

n=[A1]:m=Int(n/2)+1:Range("A1",Cells(n,n))="=IF(GCD(ABS(COLUMN()-"&m &"),ABS("&m &"-ROW()))=1,""*"","""")":Cells(m,m)="@"

Ungolfed the code:

Sub A()
    n = [A1]
    m = Int(n / 2) + 1
    Range("A1", Cells(n, n)) = "=IF(GCD(ABS(COLUMN()-" & m & "),ABS(" & m & "-ROW()))=1,""*"" ,"""")"
    Cells(m, m) = "@"
End Sub

Explanation:

  1. n = [A1] : Set n as the input and assign the value of cell A1 to n.
  2. m = Int(n / 2) + 1 : Custom way to return the same output as the ceiling function for argument n/2.
  3. Range("A1", Cells(n, n)) = "=IF(GCD(ABS(COLUMN()-" & m & "),ABS(" & m & "-ROW()))=1,""*"" ,"""")" : Paste the formula above to every cell in the range with size n x n start from cell A1.
  4. Cells(m, m) = "@" : Assign the center of the range with a character @.

Output:

Figure below is the example output for the input n = 11

enter image description here

I set the font color to red to make it look more attractive. Even better

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Why do you "paste" the formula in every cell instead of calculating it directly in the VBA function? \$\endgroup\$ – Vale Aug 29 '16 at 8:28
  • \$\begingroup\$ @Vale Because it'll be lengthier since I have to use looping statement, IF statement, WorksheetFunction, and so on. \$\endgroup\$ – Anastasiya-Romanova 秀 Aug 29 '16 at 8:32
  • \$\begingroup\$ but in your byte count you put 47*n^2...? \$\endgroup\$ – Vale Aug 29 '16 at 8:57
  • \$\begingroup\$ @Vale You perhaps haven't read this: "The length of the formula is 47 bytes but you have to replicate it n x n times, so it's equal to (47*n^2) bytes" in my answer. See also the discussion in the comment section of ugoren's answer. I hope it makes the thing clearer. \$\endgroup\$ – Anastasiya-Romanova 秀 Aug 29 '16 at 11:14
  • \$\begingroup\$ @Anastasiya-Romanova秀 as per convention, the correct byte count for this solution would be 121 bytes as only the program itself contributes to the bytecount. In the case you referenced, the source must be copied and pasted into each individual cells, whereas in your solution that is all done programmatically. \$\endgroup\$ – Taylor Scott Sep 3 '17 at 21:15
4
\$\begingroup\$

Jelly, 16 bytes

:2ạḶgþ`«2ị“* @”Y

Try it online!

How it works

:2ạḶgþ`«2ị“* @”Y  Main link. Argument: 2n + 1

:2                Perform integer division by 2, yielding n.
   Ḷ              Yield [0, ..., 2n].
 ạ                Take the absolute difference of the result to both sides.
                  This yields A := [n, ... 0, ... n].
      `           Call the quicklink to the left with left and right argument A.
     þ              Table; call the link to the left for all x in A and all y in A.
    g                 Yield the GCD of x and y.
       «2         Truncate the GCD at 2, leaving 0 for the origin, 1 for coprime
                  coordinates, and 2 otherwise.
         ị“* @”   Index into that string, mapping [1, 2, 0] to ['*', ' ', '@'].
               Y  Join, separating by linefeeds.
\$\endgroup\$
  • \$\begingroup\$ Can you add an expanded, commented view of the code? \$\endgroup\$ – Soren Aug 28 '16 at 16:06
  • \$\begingroup\$ I already did. Is it missing something? \$\endgroup\$ – Dennis Aug 28 '16 at 16:10
  • \$\begingroup\$ I wasn't seeing it for some reason.... it's looking good now! \$\endgroup\$ – Soren Aug 28 '16 at 16:11
3
\$\begingroup\$

J, 24 bytes

'@* '{~2<.[:+./~<.@-:-i.

A port of Dennis' answer in Jelly.

\$\endgroup\$
3
\$\begingroup\$

Perl 6, 77 or 74 bytes

Full program (77 bytes):

my \h=Int(get/2);say |map {$_|$^j??2>$j gcd$_??'*'!!' '!!'@'},-h..h for -h..h

(try it online)

If it is acceptable to return the output from a lambda as a list of lists of 1-character strings (74 bytes):

{my \h=$_ div 2;map {map {$^i|$_??2>$i gcd$_??'*'!!' '!!'@'},-h..h},-h..h}

(try it online)

\$\endgroup\$
3
\$\begingroup\$

S.I.L.O.S, 236 bytes

GOTO s
funcg
if q p
r=p
return
lblp
t=p
t%q
p=q
q=t
GOSUB g
return
lbls
readIO
m=i
m/2
a=i
lbla
a-1
a-m
b=i
lblb
b-1
b-m
p=a
p|
q=b
q|
GOSUB g
r-1
A=r
A|
r/A
r*-1
r+1
p=r
r*r
r*6
p*4
r+p
r+32
printChar r
b+m
if b b
printLine 
a+m
if a a

Try it online!

Port of my answer in C.

\$\endgroup\$
  • \$\begingroup\$ the output for 15 is interesting \$\endgroup\$ – Rohan Jhunjhunwala Aug 28 '16 at 16:49
3
\$\begingroup\$

C, 147 145 135 133 bytes

2 bytes thanks to Dennis.

10 bytes thanks to Arnauld.

2 bytes thanks to H Walters.

r,m,i,j;g(a,b){r=b?g(b,a%b):a;}main(n){scanf("%d",&n);for(m=n/2,i=-m;i<=m;putchar(r?r*r-1?32:42:64),i+=++j%n<1&&puts(""))g(i,j%n-m);}

Ideone it!

Golfing advice welcome as always.

\$\endgroup\$
  • \$\begingroup\$ I you define another global variable (say x) and do x= instead of return in the g()function, then I think you can do {g(i,j-m);putchar(x?x*x-1?32:42:64);} and save 7 bytes. (Or 8 bytes if you also remove the line break. Is it really required?) \$\endgroup\$ – Arnauld Aug 28 '16 at 10:25
  • \$\begingroup\$ @Arnauld Thanks, updated \$\endgroup\$ – Leaky Nun Aug 28 '16 at 10:36
  • \$\begingroup\$ Hmm. You don't need to declare m,i,j twice, do you? \$\endgroup\$ – Arnauld Aug 28 '16 at 10:40
  • \$\begingroup\$ @Arnauld Apparently I'm an idiot. \$\endgroup\$ – Leaky Nun Aug 28 '16 at 10:41
  • 1
    \$\begingroup\$ Change ++j to ++j%n (+2 bytes), and j-m to j%n-m (+2 bytes). Then you can remove ,j%=n (-5 bytes). \$\endgroup\$ – H Walters Aug 28 '16 at 17:30
3
\$\begingroup\$

Javascript (ES6), 114 113 105 bytes

This started as a port of Leaky Nun's C version and was then further optimized. Most optimizations are specific to JS.

n=>(r=j=>i<n?('*@*'[1+(g=(i,j)=>j?g(j,i%j):i)(i-m,j-m)]||' ')+(++j<n?'':(i++,`
`))+r(j%n):'')(i=0,m=n>>1)

Example:

let f =
n=>(r=j=>i<n?('*@*'[1+(g=(i,j)=>j?g(j,i%j):i)(i-m,j-m)]||' ')+(++j<n?'':(i++,`
`))+r(j%n):'')(i=0,m=n>>1)

console.log(f(7))

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

Pyth, 40 bytes

L@"@* "hS[b2)jsMcQyM.aMiM*.**2[r_/Q2h/Q2

I'm very new to Pyth, so this can likely be golfed further.

Try it online

How it works

L@"@* "hS[b2)jsMcQyM.aMiM*.**2[r_/Q2h/Q2   

L@"@* "hS[b2)                              Lambda y. Input: b
L                                          Declare lambda
         [b2)                              List [b, 2]
        S                                  Sort ascending
       h                                   Head. Yield first element a, clamping to max 2
  "@* "                                    String literal "@* "
 @                                         Index into string with a, yielding string[a]

             jsMcQyM.aMiM*.**2[r_/Q2h/Q2   Program. Input: Q
                                _/Q2 /Q2   -Q//2 and Q//2
                                    h      Head. Q//2+1
                               r           Range [-Q//2, Q//2+1]
                              [            List
                            *2             Duplicate
                          .*               Splat. Unpack
                         *                 Cartesian product. Yield all coordinate pairs
                       iM                  Map GCD over above
                    .aM                    Map absolute value over above
                  yM                       Map y over above, yielding required characters
                cQ                         Chunk. Split above into Q pieces
              sM                           Map concatenate over above
             j                             Join on newlines
                                           Implicitly print
\$\endgroup\$
2
\$\begingroup\$

GolfScript, 98 83 bytes

~:l.2/~):o:i;{o{.abs i abs.!!{{.@\%.}do}*;1={'*'}{' '}if\.i|!{\;'@'\}*)}l*;i):i;n}*

Try it online!

Input = 11

 **** **** 
* * * * * *
** ** ** **
* * * * * *
***********
    *@*    
***********
* * * * * *
** ** ** **
* * * * * *
 **** **** 
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 23 bytes

'@ * '[3⌊∨/|↑(⊖-⌽)⍳2⍴⎕]

Try it online!

\$\endgroup\$

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.