# May the wind be always at your back

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.

• 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)... Apr 26, 2021 at 5:28
• @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... Apr 26, 2021 at 16:38
• For Calypso and Ithaca, there's 🏰 and 🏘️, but parsing Emoji is very hard (at least from my experience). Apr 26, 2021 at 16:41

# 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())
return b.find('i') in r
• Can you switch len(b) to w*h to save 3 bytes...? Apr 26, 2021 at 7:14
• @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?). Apr 26, 2021 at 12:35

# JavaScript (Node.js), 178173171 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

# Charcoal, 59 bytes

ＷＳ⊞υιυＷ№ＫＡiＦＬυＦＬ§υ⁰«Ｊλκ¿⁼iＫＫ«ＵＭＫＶ⎇№⁺c*§v<^>νμiμ~»»≔¬№ＫＡcθ⎚θ

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:

ＷＳ⊞υιυ

Input the map and print it to the canvas.

Ｗ№ＫＡi

Repeat while there are still potential source squares.

ＦＬυＦＬ§υ⁰«

Loop over all squares of the map.

Ｊλκ¿⁼iＫＫ«

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

ＵＭＫＶ⎇№⁺c*§v<^>νμiμ

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

~»»

... mark this square as seen.

≔¬№ＫＡcθ

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

⎚θ

Clear the canvas and output the result.

# 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

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

# 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()
• Switch to ES2021 use c=m[y]?.[x] and m[y][x]=0 would save 2 bytes.
– tsh
Apr 26, 2021 at 1:57
• y=m.findIndex(r=>i=~r.indexOf('c')),x=~i
– l4m2
Apr 26, 2021 at 4:49
• 144
– l4m2
Apr 26, 2021 at 4:56
• 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))
– tsh
Apr 26, 2021 at 6:28
• 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.
– tsh
Apr 26, 2021 at 8:22

# Python 2, 234201 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!

• 225
– l4m2
Apr 25, 2021 at 19:19
• @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.
– ovs
Apr 25, 2021 at 20:44
• What's W+4?
– l4m2
Apr 26, 2021 at 2:35

# R, 232230203 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=="^"))))
}

# Scala, 319 bytes

It can be golfed more.

Try it online!

def f(w:Int,h:Int,b:String)={val r=mutable.Set(b.indexOf('c'));b.foreach(_=>r++=r.toList.filter(i=> 0<=i && i<b.length).flatMap(i =>{val d = Map('<' -> (i - 1), '>' -> (i + 1), '^' -> (i - w - 1), 'v' -> (i + w + 1)); if (b(i) == '*' || b(i)== 'c') d.values else List(d.getOrElse(b(i),i))}));r.contains(b.indexOf('i'))}

Ungolfed version:

import scala.collection.mutable

object TestCases {
val cases = List(
(10, 5, """\
|~^~~~~~~~~
|~c>>*>>v~~
|~v~~v~~v~~
|~>>*<~~*>i
|~~~v~~~~~~""".stripMargin, true),
(8, 5, """\
|~~~~~~~~
|~~>>v~~~
|<<c~~~~~
|~~>~i~~~
|~~~~~~~~""".stripMargin, false),
(5, 2, """\
|<c>>>
|~v~~i""".stripMargin, false),
(20, 6, """\
|~~~~~~~~~~~~~~~~~~~~
|~~v<<<<<<*<<>>>v>~~~
|~~i~<<*<<<<c~~~*~~~~
|~~~~~~^~~~~v~~~^~~~~
|~~~~~~<<*>>>>>>^~~~~
|~~~~~~~~~~~~~~~~~~~~""".stripMargin, true),
(20, 6, """\
|~~~~~~~~~~~~~~~~~~~~
|~~~~~~~~~*<<>>>v>~~~
|~~i<v<*<<<<c~~~*~~~~
|~~~~v~^~~~~v~~~^~~~~
|~~~~v~<<*>>>>>>^~~~~
|~~~~v~~~~~~~~~~~~~~~""".stripMargin, false),
(2, 2, """\
|ci
|>>""".stripMargin, true)
)
}

object Main {
def f(w: Int, h: Int, b: String): Boolean = {
val r = mutable.Set(b.indexOf('c'))
for (_ <- b) {
for (i <- r.toList) {
if (0 <= i && i < b.length) {
val d = Map('<' -> (i - 1), '>' -> (i + 1), '^' -> (i - w - 1), 'v' -> (i + w + 1))
if (b(i) == '*' || b(i) == 'c') {
r ++= d.values
}
r += d.getOrElse(b(i), i)
}
}
}
r.contains(b.indexOf('i'))
}

def main(args: Array[String]): Unit = {
var success = true

for ((w, h, b, c) <- TestCases.cases) {
if (f(w, h, b) != c) {
if (!success) println()
println("Test Failed!")
println(s"w=$w, h=$h, \$c")
println(b)
success = false
}
}
if (success) {
println("All tests passed!")
}
}
}