16
\$\begingroup\$

A Knight in chess moves two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of a capital L)


Given a Knight current square in a chess board and an array of unavailable squares, calculate the minimum number of valid jumps required to reach a target square. If no route is available to reach the required target return 0.

A valid jump is a move that:

  • Does not go out of the board (8x8 square board)
  • Does not overlap with another piece
  • Follows the Knight L shape move pattern

Input

Knight square, array of occupied squares, target square. Input might look like:

f("b3", ["c4", "h7", "g5", "a8"], "b7")
  • You can use a set of coordinates instead of chess algebraic notation. It can be 0 or 1-index. Example: b3 -> (2,3) or b3 -> (1,2)

  • You can assume that Knight Square != Target Square for every input.

  • You can assume every input square is valid and non overlapping

  • Input values can be taken in any order you'd like

Output

Minimal number of valid jumps to reach a square, or 0 in case no route can be found


Test Cases

"e3", [], "f5" -> 1
"e3", [], "f6" -> 2
"c4", [], "f6" -> 3
"g1", ["f3", "g3"], "h4" -> 4
"c4", ["d6", "b6", "e5", "e3", "e4"], "f6" -> 5
"a1", [], "h8" -> 6
"g1", ["h3","h5","g2","g3","g6","f3", "e5", "e6", "d4", "d5", "c1", "c3", "c5", "b2"], "b7" -> 7
"h1", ["f2", "g3"], "h3" -> 0
"d4", ["b3", "b5", "c2", "c6", "e2", "e6", "f3", "f5"], "a8" -> 0
\$\endgroup\$
8
  • \$\begingroup\$ Pretty much related \$\endgroup\$ Aug 29, 2023 at 13:49
  • \$\begingroup\$ Can we take input as [x,y] tuples instead of strings? \$\endgroup\$
    – mousetail
    Aug 29, 2023 at 13:49
  • 1
    \$\begingroup\$ are you sure about the 6th test-case g1,e2,c1,b3,a5,b7 seems to be a valid path in only 5 jumps \$\endgroup\$
    – bsoelch
    Aug 29, 2023 at 14:12
  • 1
    \$\begingroup\$ @bsoelch my mistake, I was missing one unavailable square. Should be fine now \$\endgroup\$ Aug 29, 2023 at 14:17
  • 1
    \$\begingroup\$ b3 should be (2,3) when 1-indexed and (1,2) when 0-indexed. \$\endgroup\$
    – Value Ink
    Sep 1, 2023 at 2:13

9 Answers 9

5
\$\begingroup\$

Python, 154 bytes

-17 bytes, thanks to The Thonnu

def f(s,b,t,k=0):
 p=s,
 while(t in p)*64<64>k:p=[[u,v]for i in range(64)if([u:=i//8,v:=i%8]in b)<any((x-u)**2+(y-v)**2==5for x,y in p)];k+=1
 return k%64

Attempt This Online!

Goes through all reachable fields until target is reached, aborts after 64 steps and returns 0

\$\endgroup\$
2
  • \$\begingroup\$ 163 bytes \$\endgroup\$
    – The Thonnu
    Aug 29, 2023 at 15:52
  • \$\begingroup\$ 64 steps are more than needed but I guess cutting this by a few doesn't help with golfing as long as it is still a 2-digit number and one can create examples where the minimal number of jumps is bigger than 10. \$\endgroup\$
    – quarague
    Aug 30, 2023 at 7:03
4
\$\begingroup\$

JavaScript (Node.js), 143 bytes

Expects [source, target, occupied_0, occupied_1, ...] where each square is a pair of 0-indexed coordinates.

f=(a,n)=>(g=(n,s)=>(i=b.indexOf(s))>1|s&136?0:i>0|Buffer(' "/3OS`b').some(v=>n&&g(n-1,s+v-65)))(n,...b=a.map(([x,y])=>x|y<<4))?n:n>9?0:f(a,-~n)

Try it online!

How?

This is internally using the 0x88 encoding. Converting the input to this format is a bit costly, but it makes basically everything else easier and shorter (moves, square comparisons and out-of-board detections).

\$\endgroup\$
2
  • \$\begingroup\$ Out of curiosity: is this really shorter than using your answer to the other challenge for the first input and then indexing with the second input? \$\endgroup\$
    – Luis Mendo
    Aug 30, 2023 at 10:31
  • 1
    \$\begingroup\$ @LuisMendo Good question. :-) I'll have a look later. \$\endgroup\$
    – Arnauld
    Aug 30, 2023 at 11:42
3
\$\begingroup\$

Excel, 236 bytes

Define z as:

=LAMBDA(p,q,
    LET(
        a,OFFSET(
            INDIRECT(p),
            {-2,-2,-1,-1,1,1,2,2},
            {-1,1,-2,2,-2,2,-1,1}
        ),
        b,ROW(a),
        c,COLUMN(a),
        d,TOCOL(IF((b<9)*(c<9),ADDRESS(b,c,4),NA()),2),
        e,FILTER(d,ISNA(XMATCH(d,$B1#))),
        IF(SUM(N(e=$C1))>0,q+1,z(e,q+1))
    )
)

Within the worksheet:

=IFERROR(z($A1,),)

Knight square in cell A1, target square in cell C1 and occupied squares in spilled, vertical range B1#.

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

Charcoal, 59 bytes

F…β⁸F⁸⊞υ⁺ι⊕κ≔⟦θ⟧θW∧¬№θζΦ⁻υ⁺θη⊙θ⁼⁵ΣXEμ⁻℅ξ℅§κπ²«→≔⁺θιθ»I∧№θζⅈ

Try it online! Link is to verbose version of code. Explanation:

F…β⁸F⁸⊞υ⁺ι⊕κ

Create a list of all valid chess board squares.

≔⟦θ⟧θ

Start with one reachable square.

W∧¬№θζΦ⁻υ⁺θη⊙θ⁼⁵ΣXEμ⁻℅ξ℅§κπ²«

While the target has not been reached and there are still more squares that can be reached...

... increment the count of jumps, and...

≔⁺θιθ

... append the newly reachable squares to the list of reachable squares.

»I∧№θζⅈ

Output the count of jumps or 0 if the target was not reached.

51 bytes by taking input as Gaussian integers:

≔⟦θ⟧θW∧¬№θζΦ⁻ΣE⁸E⁸⁺κ×μI1j⁺θη⊙θ⁼₂⁵↔⁻μκ«→≔⁺θιθ»I∧№θζⅈ

Attempt This Online! Link is to verbose version of code.

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

Scala, 378 336 bytes

Port of @bsoelch's Python answer in Scala.

Saved 42 bytes thanks to the comment of @Kjetil S


Golfed version. Try it online!

def f(s:(Int,Int),b:Seq[(Int,Int)],t:(Int,Int),K:Int=0)={var p=Seq(s);var k=K;while(!p.contains(t)&&k<64){p=(for(i<-0 until 64;u=i/8;v=i%8;if !b.contains((u,v))&&p.exists{case(x,y)=>(x-u)*(x-u)+(y-v)*(y-v)==5})yield(u,v)).toList;k+=1};k%64}
def C(s:String)=(s(0)-97,s(1)-49)
def h(a:String,b:List[String],c:String)=f(C(a),b.map(C),C(c))

Ungolfed version. Try it online!

object Main {
  def f(s: (Int, Int), b: List[(Int, Int)], t: (Int, Int), k: Int = 0): Int = {
    var p = List(s)
    var kVar = k
    while (!p.contains(t) && kVar < 64) {
      p = (for (i <- 0 until 64; 
                u = i / 8; 
                v = i % 8; 
                if !b.contains((u, v)) && p.exists { case (x, y) => (x - u) * (x - u) + (y - v) * (y - v) == 5 }) 
            yield (u, v)).toList
      kVar += 1
    }
    kVar % 64
  }

  def coord(s: String): (Int, Int) = {
    ("abcdefgh".indexOf(s.charAt(0)), s.charAt(1).asDigit - 1)
  }

  def helper(a: String, b: List[String], c: String): Int = {
    f(coord(a), b.map(coord), coord(c))
  }
  
  def main(args: Array[String]): Unit = {
    println(helper("e3", List(), "f5")) //-> 1
    println(helper("e3", List(), "f6")) //-> 2
    println(helper("c4", List(), "f6")) //-> 3
    println(helper("g1", List("f3", "g3"), "h4")) //-> 4
    println(helper("c4", List("d6", "b6", "e5", "e3", "e4"), "f6")) //-> 5
    println(helper("a1", List(), "h8")) //-> 6
    println(helper("g1", List("h3","h5","g2","g3","g6","f3", "e5", "e6", "d4", "d5", "c1", "c3", "c5", "b2"), "b7")) //-> 7
    println(helper("h1", List("f2", "g3"), "h3")) //-> 0
    println(helper("d4", List("b3", "b5", "c2", "c6", "e2", "e6", "f3", "f5"), "a8")) //-> 0
  }
}
\$\endgroup\$
2
  • \$\begingroup\$ You can shave off 24 bytes by replacing "abcdefgh".indexOf(s(0)) with s(0)-97 and s(1).asDigit-1 with s(1)-49 \$\endgroup\$
    – Kjetil S
    Sep 1, 2023 at 20:17
  • \$\begingroup\$ ...and 18 bytes by removing return type :(Int,Int) and :Int twice. \$\endgroup\$
    – Kjetil S
    Sep 1, 2023 at 20:29
2
\$\begingroup\$

K (ngn/k), 62 bytes

{0^*&~^?[;z]'64{?,/x@y}[i!i@&'(4=*/4#)''i-\:/:i:(+!8 8)^y]\,x}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

J, 59 bytes

1 :'1{.[:I.[e."1(u-.~,j./~i.8)(]~.@,&;[<@#~2j1=&|-/~)^:a:]'

Attempt This Online!

Takes input as complex numbers.

To handle all 3 args, we use a J adverb which modifies the list of illegal positions, and takes the target and start positions as the left and right args, respectively.

  • (u-.~,j./~i.8) Generate the full board minus the illegal spaces
  • (]~.@,&;[<@#~2j1=&|-/~)^:a:] Collecting each step's results until you reach a fixed point, starting the initial square, find all legal spaces that are \$\sqrt{5}\$ away from the current positions. In this way, we spider out stepwise to every reachable position
  • [e."1 For each steps results, is the target position in that list? Now our list of lists (the step results) will become a single 0-1 list, with the first 1 representing the index we seek
  • [:I. All 1 indexes. Returns empty list for no matches.
  • 1{. Take the first. Exactly what we need, and since taking 1 from the empty list returns 0, it also handles the no match case.
\$\endgroup\$
1
\$\begingroup\$

Haskell, 192 bytes

n=99
q=[-1,1]
(#)=elem
g a b p c=last$last(1+g[w|s<-a,x<-[1,2],y<-q,z<-q,w<-[zipWith(+)s[y*x,z*(3-x)]],all(`elem`[0..7])w&&not(w#b)]b(p++a)c:[n|all(#p)a]):[0|c#a]
f a b c= min(g[a]b[]c)n`mod`n

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 166 bytes

sub{($s,$e,%o)=@_;@w=(0,$s);while(($n,$s,@w)=@w){$s-$e||last,push@w,map{$n+1,$_}grep{($a,$b,$c,$d)=map{$_>>3,$_%8}$s,$_;!(($a-$c)**2+($b-$d)**2-5||$o{$_}++)}0..63}$n}

Try it online!

sub steps {
  ($s,$e,%o)=@_;        #start, end, occupied set as hash from input args in @_
  @w=(0,$s);            #initial work (steps,square)
  while(($n,$s,@w)=@w){ #while work left to be done
    $s-$e||last,        #bail if current square $s equals $e end square
    push@w,             #register new work/new squares to be checked
      map{$n+1,$_}      # (new steps, new square)
      grep{                       #filter
        ($a,$b,$c,$d)             #coords of current square ($a,$b)
          =map{$_>>3,$_%8}$s,$_;  #...and potential new square ($c,$d)
        !(($a-$c)**2+($b-$d)**2-5 #pythagorean horsyness check of new vs current
          ||$o{$_}++)             #...non-occupied new squares
                                  #...and register new square as occupied
                                  #...with ++ to not enter it again
      }
      0..63                       #loop through potential new squares
  }
  $n                              #return n steps from last work
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.