May the wind be always at your back

Question

You are Odysseus, and are finally free from Calypso (who has kept you captive for many years) after you drugged her while she was sleeping¹. 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 code-golf, so the shortest solution in bytes in each language wins.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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()

Answer 6

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!

Answer 7

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=="^"))))
}

Answer 8

Scala, 319 bytes

It can be golfed more.

A port of @gsitcia's answer.

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!")
    }
  }
}