18
\$\begingroup\$

You are Odysseus, and are finally free from Calypso (who has kept you captive for many years) after you drugged her while she was sleeping1. You wish to return to your homeland of Ithaca, but the ship you've stolen is a bit damaged and cannot steer. However, you have also stolen a map which contains the location of Calypso’s island as well as the locations of Ithaca and the small islands that lie in between, as well as information about the wind currents of the area. Your ship can only sail by the wind currents, but you get to choose the direction you start in (north, south, east, west). If the currents bring you to another island, you also get to choose the direction in which you depart that island.

Can you get home to Ithaca?

[1] Because that definitely happens in the epic.

Input Format

The input consists of:

  • positive integers w and h
  • a w-by-h grid of characters representing the map, where:
    • ~ denotes calm sea
    • ^ denotes a wind blowing north
    • v denotes a wind blowing south
    • < denotes a wind blowing west
    • > denotes a wind blowing east
    • c denotes Calypso's island, your starting point
    • i denotes Ithaca, the destination
    • * denotes an intermediate island

Each “wind” character moves you one cell in the direction of the wind, and winds never form loops (i.e. there is no way to get trapped in a cycle of winds).

You may take input however you want (reading a file, from STDIN, as function parameters etc.)

Output

Output a truthy value if it is possible to get to Ithaca, and a falsy value if that is not possible.

Test Cases

w=10, h=5
~^~~~~~~~~
~c>>*>>v~~
~v~~v~~v~~
~>>*<~~*>i
~~~v~~~~~~
Expected Output: True
Explanation: Go east, then east again, then east again
w=8, h=5
~~~~~~~~
~~>>v~~~
<<c~~~~~
~~>~i~~~
~~~~~~~~
Expected Output: False
Explanation: There are two paths that lead to cells neighboring Ithaca,
but there is no wind on those cells.
w=5, h=2
<c>>>
~v~~i
Expected Output: False
Explanation: Although you can get to a distance of one cell away from
Ithaca, the wind on that cell is eastward which pushes Odysseus
off the map instead of to Ithaca.
w=20, h=6
~~~~~~~~~~~~~~~~~~~~
~~v<<<<<<*<<>>>v>~~~
~~i~<<*<<<<c~~~*~~~~
~~~~~~^~~~~v~~~^~~~~
~~~~~~<<*>>>>>>^~~~~
~~~~~~~~~~~~~~~~~~~~
Expected Output: True
Explanation: North, then West
w=20, h=6
~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~*<<>>>v>~~~
~~i<v<*<<<<c~~~*~~~~
~~~~v~^~~~~v~~~^~~~~
~~~~v~<<*>>>>>>^~~~~
~~~~v~~~~~~~~~~~~~~~
Expected Output: False
Explanation: Although there is a wind leading to Ithaca, it is inaccessible.

Standard loopholes are prohibited. This is , so the shortest solution in bytes in each language wins.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Probably a bit late now, but it would have been cool if we had the option accept the map in the form of emoticons for sea, wind and islands (assuming that they exist)... \$\endgroup\$ – Dominic van Essen Apr 26 at 5:28
  • 2
    \$\begingroup\$ @DominicvanEssen There's 🏝️, 🌊, and 💨, but the wind only goes in one direction. You'd probably have to use one of the various arrow emoji sets to handle that... \$\endgroup\$ – Darrel Hoffman Apr 26 at 16:38
  • \$\begingroup\$ For Calypso and Ithaca, there's 🏰 and 🏘️, but parsing Emoji is very hard (at least from my experience). \$\endgroup\$ – knosmos Apr 26 at 16:41
8
\$\begingroup\$

Python 3.8 (pre-release), 176 bytes

lambda w,h,b:b.find('i')in(r:={b.find('c')})|{r.update(*([{(d:={'<':i-1,'>':i+1,'^':i+~w,'v':i-~w}).get(b[i],i)},{*d.values()}][b[i]in'*c']for i in r if-1<i<len(b)))for _ in b}

Try it online!

Ungolfed

def f(w,h,b):
  r = {b.find('c')}
  for _ in b:
    for i in list(r):
      if 0 <= i < len(b):
        d = {'<':i-1,'>':i+1,'^':i-w-1,'v':i+w+1}
        if b[i] in '*c':
          r.update(d.values())
        r.add(d.get(b[i],i))
  return b.find('i') in r
\$\endgroup\$
2
  • \$\begingroup\$ Can you switch len(b) to w*h to save 3 bytes...? \$\endgroup\$ – Dominic van Essen Apr 26 at 7:14
  • \$\begingroup\$ @DominicvanEssen I don't think so - because b uses newlines as some off-map locations so is longer than w*h (I think if-h<i-h+1<w*h would work for the same byte count, maybe that's golfable?). \$\endgroup\$ – Jonathan Allan Apr 26 at 12:35
7
\$\begingroup\$

JavaScript (Node.js), 178 173 171 168 bytes

s=>!/i/.test(s.map((_,i)=>_.map((_,j)=>_=='c'&&g(j,i,668)),g=(x,y,w)=>w--&&g(x,y,w>>3,w%=8,x+=--w%2,b=s[y+=--w%2]||0,b[x]=c='*<^>v'.indexOf(b[x]),~c&&g(x,y,c||668)))+s)

Try it online!

Treat destination as glory hole

\$\endgroup\$
5
\$\begingroup\$

Charcoal, 59 bytes

WS⊞υιυW№KAiFLυFL§υ⁰«Jλκ¿⁼iKK«UMKV⎇№⁺c*§v<^>νμiμ~»»≔¬№KAcθ⎚θ

Try it online! Link is to verbose version of code. Doesn't bother with the dimensions, just takes a newline terminated list of strings for the map. Explanation:

WS⊞υιυ

Input the map and print it to the canvas.

W№KAi

Repeat while there are still potential source squares.

FLυFL§υ⁰«

Loop over all squares of the map.

Jλκ¿⁼iKK«

If the current square is a potential source square, then...

UMKV⎇№⁺c*§v<^>νμiμ

... mark adjacent squares that can move to the current square as potential source squares, and...

~»»

... mark this square as seen.

≔¬№KAcθ

Record whether the initial square was found to be a potential source square.

⎚θ

Clear the canvas and output the result.

\$\endgroup\$
5
\$\begingroup\$

Python 3, 361 bytes

e=enumerate
d={"^":(0,-1),"v":(0,1),"<":(-1,0),">":(1,0),"~":(0,0)}
def f(g,x=e,y=0,V=[]):
	if x==e:x,y=[(x,y)for y,r in e(g)for x,c in e(r)if c=="c"][0]
	if(x,y)in V or x<0 or x>=len(g[0])or y<0 or y>=len(g):return 0
	v=g[y%len(g)][x%len(g[0])]
	if v in d:a,b=d[v];return f(g,x+a,y+b,V+[(x,y)])
	return v=="i"or any(f(g,x+j,y+k,V+[(x,y)])for j,k in d.values())

Try it online!

-26 bytes thanks to l4m2

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 366 \$\endgroup\$ – l4m2 Apr 25 at 17:23
  • \$\begingroup\$ @l4m2 Ah, I didn't need that line. Thanks :) \$\endgroup\$ – hyper-neutrino Apr 25 at 17:24
  • \$\begingroup\$ def f(g,x=e,y=0,V=[]): if x==e: save another byte \$\endgroup\$ – l4m2 Apr 25 at 17:32
  • \$\begingroup\$ return v=="i"or any(f(g,x+j,y+k,V+[(x,y)])for j,k in d.values()) \$\endgroup\$ – l4m2 Apr 25 at 17:33
5
\$\begingroup\$

JavaScript (ES6), 114 bytes

As suggested by @tsh, we can save many bytes if we take the grid as an array of characters (with line-feeds) along with its width.

Expects (width)(grid). Returns 0 or 1.

w=>g=(m,p=m.indexOf('c'),c=m[p])=>c=='i'|[m[p]=0,1,2,3].some(i=>"<^>v"[i]==c|c=='*'|c=='c'&&g(m,--i%2+p-~-i%2*~w))

Try it online!


JavaScript (ES6),  148  143 bytes

Saved 5 bytes thanks to @l4m2

Expects a matrix of characters. The dimensions are ignored. Returns 0 or 1.

f=(m,y=m.findIndex(r=>i=~r.indexOf('c')),x=~i,c=(r=m[y]||0)[x])=>c=='i'|[r[x]=0,1,2,3].some(i=>"^<v>"[i]==c|c<'+'|c=='c'&&f(m,y+--i%2,x+~-i%2))

Try it online!

Commented

f = (                     // f is a recursive function taking:
  m,                      //   m[] = input matrix
                          //   (x, y) = current position with:
  y = m.findIndex(r =>    //     y initialized to the index of the row r[] ...
    i = ~r.indexOf('c')   //     ... which contains 'c' at position ~i
  ),                      //     
  x = ~i,                 //     x initialized to ~i
  c = (                   //   c = character at (x, y),
    r = m[y] || 0         //       or undefined if we're out of bounds
  )[x]                    //
) =>                      //
  c == 'i' |              // success if c == 'i'
  [r[x] = 0, 1, 2, 3]     // invalidate r[x]
  .some(i =>              // for i = 0 to i = 3:
    "^<v>"[i] == c |      //   if c is equal to the character for this direction
    c < '+' |             //   or c is '*' (intermediate island)
    c == 'c' &&           //   or c is 'c' (starting point):
      f(                  //     do a recursive call:
        m,                //       pass m[]
        y + --i % 2,      //       add dy to y
        x + ~-i % 2       //       add dx to x
      )                   //     end of recursive call
  )                       // end of some()
\$\endgroup\$
8
  • \$\begingroup\$ Switch to ES2021 use c=m[y]?.[x] and m[y][x]=0 would save 2 bytes. \$\endgroup\$ – tsh Apr 26 at 1:57
  • \$\begingroup\$ y=m.findIndex(r=>i=~r.indexOf('c')),x=~i \$\endgroup\$ – l4m2 Apr 26 at 4:49
  • \$\begingroup\$ 144 \$\endgroup\$ – l4m2 Apr 26 at 4:56
  • \$\begingroup\$ Maybe take the grid as a string with "\n" as an array of characters: w=>g=(m,p=m.indexOf('c'),c=m[p])=>c=='i'||[m[p]=0,1,2,3].some(i=>"^<v>"[i]==c|c<'+'|c=='c'&&g(m,p+--i%2*-~w+--i%2)) \$\endgroup\$ – tsh Apr 26 at 6:28
  • 1
    \$\begingroup\$ I had edited the post to fix the issue DominicvanEssen pointed out. Fell free to roll it back or edit to something else if i massed something up. \$\endgroup\$ – tsh Apr 26 at 8:22
4
\$\begingroup\$

Python 2, 234 201 198 bytes

Full program, outputs by exit code. Started out as a golf of hyper-neutrino's answer.

-9 bytes thanks to l4m2!

g=input()
W=len(g[0])
a=[divmod(`g`.find("c")-2,W+4)]
for y,x in a:A,B,C,D,E,F=map(((g+["~"*W])[y]+"~")[x].__eq__,"><v^~i");a+={(y+a%3+1/~-F,x+a/3-1)for a in{3+3*A-3*B-~C-D}-{4-E}or[3,5,1,7]}-set(a)

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 225 \$\endgroup\$ – l4m2 Apr 25 at 19:19
  • \$\begingroup\$ @l4m2 thanks a lot, the way you handled ~ with 4-E is really nice. I was able to simplify this a bit further by keeping a unique. \$\endgroup\$ – ovs Apr 25 at 20:44
  • \$\begingroup\$ What's W+4? \$\endgroup\$ – l4m2 Apr 26 at 2:35
4
\$\begingroup\$

R, 232 230 203 198 bytes

f=function(m,p=which(m=="c",T))`if`(sd(!p|p>dim(m)),F,{x=regexpr(m[p],"><^v*c~i",f=T)
m[p]="~"
d=matrix(c(1:-1,0,0,-1:1),2)
`if`(x>6,x-7,`if`(x>4,any(apply(d,2,function(e)f(m,p+e))),f(m,p+d[,x])))})

Try it online!

Recursive function expecting the map as a character matrix.

How?

possible_to_get_to_ithaca=
f=function(m,               # recursive function f, m=map as a matrix
    p=which(m=="c",T)){     # p=current position, initialized to position of 'c'
    if(any(p<1|p>dim(m)))   # if p is off the map, return FALSE
      return(F)
    x=m[p]                  # set x to contents of current position
    m[p]="~"                # and set the current position to "~" to stop backtracking
    if(x=="i")return(T)     # if x is "i" then we've arrived: return TRUE
    if(x=="~")return(F)     # if x is "~" then we're becalmed: return FALSE
    if(x=="*"|x=="c"){      # if x is an island, try all 4 directions
      return(any(
        apply(cbind(a<-c(0,0,1,-1),rev(a)), # matrix of all 4 possible offsets
          1,function(b)     # try each offset b
          f(m,p+b))))       # recursive call to f with new position p
    } else                  # else move with the wind
      return(               # recursive call to f with p offset by wind
        f(m,p+c((x==">")-(x=="<"),(x=="v")-(x=="^"))))
}
\$\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.