34
\$\begingroup\$

You are an explorer, mapping an unknown world. Your ship is carried on the wind. Where it goes, who knows?

Each day, in your spyglass, you see features to the north, south, east and west. You always see four such features, corresponding to the cardinal directions. Your spyglass reports ASCII symbols like this:

~~.*, ~~~~, ~.^^, ~#~#

The symbols are in the order (north, south, east, west).

These are the symbols: ~ = sea, . = coast, ^ = mountain, * = tree, # = invalid (no observation, this occurs whenever you see the edge of the world, or the landscape is obscured by fog). Your spyglass sees exactly one unit in every direction.

Each night, you look up at the stars to see how far you've travelled. Looking at the stars reports an ascii symbol like this:

n, s, e, w

corresponding to North, South, East and West, respectively. You always move exactly one unit to the north, south, east or west every night. So you, as explorer will be receiving an endless stream of symbols:

~~.*n~~~~s~~.*s~.**

Your task is to output a 2D map of the world (where ? are unknown parts of the map, north is up, east is right):

?~~~??????
?~~~??????
?~~~.^^.??
?~~.***.~~
~~.*^^*.~~
~~~..~~~~~
~~~~~~~~~~
~~~~~~~~~~

For the sake of simplicity let's assume you start in the bottom left corner of the map. Assume all maps are 8x8.

Here is a simple 3x3 example. Assume the map looks like this:

~.~
~^~
~.~

With the following input: ~#.#n~~^#s

You will get this output:

~??
~^?
~.?

More example inputs and outputs:

input ~#~#n~~~#n~~~#n~~~#n~~~#n~~.#n~~.#n#~~#e#.~~e#.~~e#.~~e#.~~e#~~~e#~~~e#~#~s~~#~s~~#~s~~#~s~~#.s~~#~s~~#~s~##~w~#~~w.#~~w^#~~w.#~~

output

~~~~~~~~ 
~....~~~ 
~.????~~ 
~~????~~ 
~~????.~ 
~~????~~ 
~~?.^.~~ 
~~~~~~~~

Input:

~#~#e~#~~e~#~~e.#~~e^#~~n.~..n~^~.n~.~~n.~~.n.~~*n~.~.n#.~~w#.~~w#.~~s~*..s..*.s*~.~s.~~~s

Output:

?~~~~~?? 
?....~?? 
?.**.~?? 
?~..~~?? 
?~~~~~?? 
?~~..~?? 
~~~.^.?? 
~~~~~~?? 
\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This is a nice first challenge. A couple things are unclear to me though: Must all symbols in the output be space separated? That seems to be the case in the example output but it isn't explicitly stated anywhere. Also, what purpose do the star directions serve? I thought maybe they controlled where on the map the symbols go, but following the examples and starting in the bottom left, that doesn't seem to be the case. Can you elaborate on that? \$\endgroup\$ – Alex A. Mar 30 '16 at 16:55
  • \$\begingroup\$ Output does not have to be space seperated, that's an error on my part. The "#" represents "no observation". They occur whenever you are on the boundary of the map, but could also occur randomly. \$\endgroup\$ – user52676 Mar 30 '16 at 16:57
  • 4
    \$\begingroup\$ Excellent. As Alex said, this is a great first challenge. I hope to see more from you in the future! :) (FYI, the Sandbox is a great place to get feedback on future challenges.) \$\endgroup\$ – El'endia Starman Mar 30 '16 at 17:18
  • 1
    \$\begingroup\$ I suspect the first example (where the input is ~#~#n~~~#n~~~#n~~~#n~~~#n~~.#n~~.#n#~~#e#.~~e#.~~e#.~~e#.~~e#~~~e#~~~e#~#~s~~#~s~~#~s~~#~s~~#.s~~#~s~~#~s~##~w~#~~w.#~~w^#~~w) is wrong, and the output should have ?? where it says ?. \$\endgroup\$ – Leaky Nun Mar 30 '16 at 17:57
  • 3
    \$\begingroup\$ It's a magical air ship ;) \$\endgroup\$ – user52676 Mar 31 '16 at 9:59
8
\$\begingroup\$

MATL, 68 59 58 bytes

'?'7XJQtX"'s'jh5e"@2#1)t35>)-1l8t_4$h9M)b'nsew'=8M*sJ+XJ+(

Try it online!

Explanation

The map is kept in the bottom of the stack and gradually filled. The current position of the explorer is stored in clipboard J.

The map uses matrix coordinates, so (1,1) is upper left. In addition, column-major linear indexing is used. This means that the elements of the 8×8 matrix representing the map are accessed with a single index as follows:

1  9 17 25 33 41 49 57
2 10 18 26 34 42 50 58
3 11 19 27 35 43 51 59
4 12 20 28 36 44 52 60
5 13 21 29 37 45 53 61
6 14 22 30 38 46 54 62
7 15 23 31 39 47 55 63
8 16 24 32 40 48 56 64

So for example the element (3,2) of the matrix is the element with linear index 11. Movement towards North, South, East and West respectively corresponds to adding -1, 1, 8 or -8 to the linear index. The array [-1 1 8 -8] serves to encode two different things:

  • The possible displacements of the explorer.
  • The relative positions of features detected with the spyglass. These positions are relative to the current position of the explorer.

The input string is arranged into chunks of 5 characters. Since the first chunk is missing the first character (that which indicates movement), an initial s is arbitrarily included to make all chunks the same size. To compensate for this, the explorer starts at position 7, not 8, so the initial displacement to the South (add 1 to the linear index) leaves them at position 8.

The chunks of 5 characters are processed in a loop. The first character updates the position, and the remaining 4, if different than #, are written into the adequate entries of the matrix that represents the map.

'?'          % push '?'. The map will initially be filled with this
7XJ          % push 7: initial position of the explorer. Copy into clipboard J
Qt           % add 1. Duplicate
X"           % 8x8 matrix containing '?'
'n'jh        % take input string. Prepend 'n'
5e           % reshape into a 5-column matrix
"            % for each column (chunk)
  @          %   push current chunk
  2#1)       %   split chunk into its first char and an array with the other 4
  t35>       %   duplicate. Logical index of chars different than #
  )          %   apply that index to keep characters different than #
  -1l8t_4$h  %   array [-1 1 8 -8]
  9M         %   push logical index again
  )          %   apply that index to keep only relevant relative positions
  b          %   bubble up in stack: move first char of chunk to top
  'nsew'=    %   logical index that tells if that char is 'n', 's', 'e' or 'w'
  8M         %   push array [-1 1 8 -8] again
  *          %   multiply element-wise. Only one of the four results will be nonzero
  s          %   sum of the array. Gives displacement of the explorer
  J+         %   push position of the explorer and add to compute new position
  XJ         %   update position in clipboard J
  +          %   add updated position of explorer to relative positions of features
  (          %   write those fearttures into the indexed entries of the map
             % end for each. Implicitly display
\$\endgroup\$
  • \$\begingroup\$ That's a clever trick ! I will test your program against a few maps to see if it does what I expect. \$\endgroup\$ – user52676 Mar 31 '16 at 10:02
3
\$\begingroup\$

C, 210 208 207 bytes

This one uses printf and scanf to read input, and a linearized array instead of x,y; so I feel it is sufficiently different from millibyte's.

Golfed:

 main(p){char*i,*j,m[80];for(p=73,i=m+p;p--;m[p]=63);for(p=8;scanf("%5s",i)>0;p+=*j=='n'?8:*j=='s'?-8:*j=='e'?1:-1)for(j=i;j-i<4;j++)if(*j^35)m[p+"qajh"[j-i]-'i']=*j;for(p=72;m[p]=0,p-=8;)printf("%s\n",m+p);}

Somewhat-ungolfed:

main(p){
    char*i,*j,m[80];
    for(p=73,i=m+p;p--;m[p]=63);                   // fill with ?
    for(p=8;scanf("%5s",i)>0;
            p+=*j=='n'?8:*j=='s'?-8:*j=='e'?1:-1)  // read 5-at-a-time
        for(j=i;j-i<4;j++)
            if(*j^35)m[p+"qajh"[j-i]-'i']=*j;      // update map positions
    for(p=72;m[p]=0,p-=8;)printf("%s\n",m+p);      // output line-by-line
}

Representation:

  // board: (vertically reversed when printed)
    0  1  2  3  4  5  6  7
    8  9  10 ...
    16 18 19 ...
    ...
    56 57 58 59 60 61 62 63

  // offsets and offset order, or why "qajh": 
    s2      -8       a
  w4  e3  -1 0+1   h i j
    n1      +8       q   <- offset by +'i'

Also, you start at position 8 because this shaves a char or so off the print-loop.

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

Fortran, 263 251 247 235 234 216 bytes

1D version (similar to the one by Don Muesli):

#define R read(*,'(a)',advance='no',eor=1)c
#define F(x)R;if(c/='#')a(x+i)=c
program t
character::a(64)='?',c
integer::k(4)=[8,-8,1,-1],i=57
do
F(-8)
F(8)
F(1)
F(-1)
R
i=i+k(index('snew',c))
enddo
1 print'(8a)',a
end

2D version:

#define R read(*,'(a)',advance='no',eor=1)c
#define F(x,y)R;if(c/='#')a(x+m,y+l)=c
#define G(x,y)j=index(x,c);if(j==2)j=-1;y=y+j
program t
character::a(8,8)='?',c
l=8;m=1
do
F(,-1)
F(,1)
F(1,)
F(-1,)
R
G('sn',l)
G('ew',m)
enddo
1 print'(8a)',a
end

To enable free form and pre-processing, the file needs the extension .F90, e.g. explorer.F90. The input is read from STDIN:

echo "~#~#e~#~~e~#~~e.#~~e^#~~n.~..n~^~.n~.~~n.~~.n.~~*n~.~.n#.~~w#.~~w#.~~s~*..s..*.s*~.~s.~~~s" | ./a.out 
?~~~~~??
?....~??
?.**.~??
?~..~~??
?~~~~~??
??~..~??
~~~.^.??
~~~~~~??
\$\endgroup\$
  • \$\begingroup\$ So does Fortran also have linear indexing? \$\endgroup\$ – Luis Mendo Mar 31 '16 at 11:31
  • \$\begingroup\$ @DonMuesli No, not really. I'm operating on a 1D array directly. For printing the array of characters I'm using the fact that the array is stored contiguously in memory. \$\endgroup\$ – Alexander Vogt Mar 31 '16 at 11:34
2
\$\begingroup\$

C, 265 226 224 bytes

a[8][8];x;y;i;main(c){for(;c=getchar(),c+1;y+=(c=='n')-(c=='s'),x+=(c=='e')-(c=='w'))for(i=5;--i;c=getchar())i&&c-35&&(a[x+(i==2)-(i==1)][y-(i==3)+(i==4)]=c);for(y=8;y--;putchar(10))for(x=0;x<8;)putchar((i=a[x++][y])?i:63);}

The map is 8x8, I didn't notice that before. And here is the 265 bytes solution that works for maps with variable dimensions:

a[99][99];c;x;X;y;i;k;p;main(Y){for(;c=getchar(),c+1;y+=(c=='n')-(c=='s'),x+=(c=='e')-(c=='w'))for(i=5;--i;c=getchar())i&&c-35&&(a[k=x+(i==2)-(i==1),X=X<k?k:X,k][p=y-(i==3)+(i==4),Y=Y<p?p:Y,p]=c);for(y=Y+1;y--;putchar(10))for(x=0;x<=X;)putchar((i=a[x++][y])?i:63);}
\$\endgroup\$
  • \$\begingroup\$ Shouldn't a[8][8] be sufficient? \$\endgroup\$ – Alexander Vogt Mar 31 '16 at 11:16
  • \$\begingroup\$ @Alexander Vogt - Oh, right! Thank you, that reduces two more bytes. \$\endgroup\$ – mIllIbyte Mar 31 '16 at 11:33
  • \$\begingroup\$ I really like how you calculate increments/decrements to x and y. Comparing our C code, static int a[8][8] gets you free map initialization, and use of char m[64] gets me great discounts for map output. Really close counts, though \$\endgroup\$ – tucuxi Mar 31 '16 at 14:39
  • \$\begingroup\$ If you reverse e and w in your map representation, then you can use for(x=8;x--;)putchar((i=a[x][y])?i:63) to shave two bytes on output. \$\endgroup\$ – tucuxi Mar 31 '16 at 14:43
  • \$\begingroup\$ Is c=getchar(),c+1 not equivalent to getchar(),c++ or is there some trickery involved? \$\endgroup\$ – Jonathan Frech May 9 '18 at 21:49
2
\$\begingroup\$

Ruby, 169 147 bytes

Full program. Takes in the input string from STDIN (you probably need to pipe it in from a file to prevent any trailing newlines from messing things up) and outputs the resultant map to STDOUT.

Trimmed a ton by putting all the strings into one and then splitting them later.

m=??*64
d=0
x=56
gets.each_char{|c|d<4?(w=x+(d>2?-1:d>1?1:d<1?-8:d<2?8:0)
m[w]=c if c>?$):x+=c>?v?-1:c<?f?1:c>?q?8:-8
d+=1;d%=5}
puts m.scan /.{8}/

Ungolfed:

m = ?? * 64                 # 64 "?" symbols
                            # y axis counts downwards; 0-7 is top row
d = 0                       # Keep track of which direction we're looking
x = 56                      # Position, bottom left corner (0,7)
gets.each_char do |c|       # For each character from first line of STDIN
    if d < 4                # Looking in a direction
        if    d > 2         # d == 3; looking west
            w = x - 1
        elsif d > 1         # d == 2; looking east
            w = x + 1
        elsif d < 1         # d == 0; looking north
            w = x - 8
        else                # d == 1; looking south
            w = x + 8
        end
        m[w] = c if c > ?$  # Only '#' gets rejected by this step
    else                    # Moving in a direction
        if    c > ?v        # c == 'w'
            x -= 1
        elsif c < ?f        # c == 'e'
            x += 1
        elsif c > ?q        # c == 's'
            x += 8
        else                # c == 'n'
            x -= 8
        end
    end
    d = (d + 1) % 5         # Look in the next direction
end
puts m.scan /.{8}/          # Split map into rows of 8
\$\endgroup\$
1
\$\begingroup\$

Lua, 354 bytes (try it online)

Golfed:

n=(...)r={}y=8x=1q="?"for i=1,8 do r[i]={q,q,q,q,q,q,q,q}end for u in n:gsub("#",q):gmatch(".....")do a,b,c,d,e=u:match("(.)(.)(.)(.)(.)")if a~=q then r[y-1][x]=a end if b~=q then r[y+1][x]=b end if c~=q then r[y][x+1]=c end if d~=q then r[y][x-1]=d end y=y+(("n s"):find(e)or 2)-2x=x+(("w e"):find(e)or 2)-2 end for i=1,8 do print(table.concat(r[i]))end

Slightly ungolfed:

n = "~#~#e~#~~e~#~~e.#~~e^#~~n.~..n~^~.n~.~~n.~~.n.~~*n~.~.n#.~~w#.~~w#.~~s~*..s..*.s*~.~s.~~~s"

r={} y=8 x=1 q="?"
for i=1,8 do r[i]={q,q,q,q,q,q,q,q} end
for u in n:gsub("#",q):gmatch(".....") do
  a,b,c,d,e=u:match("(.)(.)(.)(.)(.)")
  if a~=q then r[y-1][x]=a end
  if b~=q then r[y+1][x]=b end
  if c~=q then r[y][x+1]=c end
  if d~=q then r[y][x-1]=d end
  y=y+(("n s"):find(e)or 2)-2
  x=x+(("w e"):find(e)or 2)-2
end
for i=1,8 do print(table.concat(r[i])) end
\$\endgroup\$
  • \$\begingroup\$ Can x=x+(("w e"):find(e)or 2)-2 end not be x=x-2+(("w e"):find(e)or 2)end? \$\endgroup\$ – Jonathan Frech May 9 '18 at 21:58
1
\$\begingroup\$

Kotlin, 242 bytes

{val m=Array(8){Array(8){'?'}}
var d=7
var i=0
for(c in it)(mapOf('n' to{d--},'s' to{d++},'w' to{d-=8},'e' to{d+=8},'#' to{i++})[c]?:{m[d%8+listOf(-1,1,0,0)[i%4]][d/8+listOf(0,0,1,-1)[i%4]]=c
i++})()
m.forEach{for(c in it)print(c);println()}}

The newlines can be replaced with semicolons if wished.

Try Here

\$\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.