x86 32-bit machine code, 26 bytes

B6 80 8A 01 41 D4 05 92 28 D0 28 F4 70 F4 F6 EC 04 02 A8 FB 74 EC F6 DE D6 C3

Try it online!

Following the fastcall calling convention, this function takes the address of a null-terminated byte string in ECX and returns an 8-bit integer in AL, which is 0 if the string is a valid knight's tour and -1 if it is not.

The basic method is to divmod each ASCII code by 5 to get coordinates, and take differences; the valid knight's moves of (±1, ±2) and (±2, ±1) are characterized by the product of the two coordinates being ±2.

In assembly:

f:	mov dh, -128    # Set DH to -128.
r:	mov al, [ecx]   # Load a byte from the string into AL.
	inc ecx         # Advance the pointer.
	aam 5           # Divide by 5; quotient in AH, remainder in AL.
	xchg edx, eax   # Exchange registers, putting those in DH and DL.
	sub al, dl      # Subtract DL from AL (this and prev remainders).
	sub ah, dh      # Subtract DH from AH (this and prev quotients).
	jo r            # Jump back if signed overflow (occurs 1st time).
	imul ah         # Multiply the two differences.
	add al, 2       # Add 2 to the product.
	test al, ~4     # In the result, look at all except the 4s bit.
	jz r            # Jump back if those bits are zero (from 0 or 4).
	neg dh          # Negate DH (the quotient from the last byte).
	                #  CF becomes 1 if DH is nonzero, 0 if zero;
	                #  DH is nonzero for letters, zero for the null.
	.byte 0xD6      # Undocumented SALC instruction: set AL to -CF.
	ret             # Return.

posted 3 months ago

CC BY-SA 4.0

m90‭

401 reputation 0 16 40 2

Perl 5, 93 bytes

I am disappointed to discover that just doing the obvious coordinate calculations requires fewer bytes than my lookup table approach. 😢

Reads a string from stdin. Exits 0 if valid tour, 1 if invalid.

-6 bytes from @m90.

perl -ne'map{$_=ord;$x=$_%5;$y=int$_/5;exit 1if$i++&&2-abs(($x-$X)*($y-$Y));$X=$x;$Y=$y}/./g'

echo 'MJCFQXODGPWTIBKVSHENYRULA' | perl -ne'
    # walk the positions
    map {
        # convert character to ascii ordinal value.
        # conveniently A is 65 which is a multiple of 5
        #   so no offset is needed for modulo to work
        $_ = ord;

        # derive x/y coordinates
        $x = $_%5;
        $y = int $_/5;

        # after the first move, abort if not a legal move
        # a legal move differs by 1 or 2 in x and 2 or 1 in y
        #   from the previous position
        # borrowing @m90's observation, if we multiply together
        #   we just need to check for +/- 2
        exit 1 if $i++ && 2 - abs(($x-$X)*($y-$Y));

        # current position becomes previous position
        $X = $x;
        $Y = $y
    } /./g
'

Try it online!

posted 3 months ago

CC BY-SA 4.0

3mo ago

jhnc‭

581 reputation 0 46 58 98

Uiua, 27 bytes*

Function definition. Takes string as argument, returns 0/1 for false/true.

≍♭1◴⧈(≍⇡₁2⍆⌵-)⍉⊟⊃◿₅(⌊÷₅)-@A

Uiua pad this online

*: assuming a single-byte coding scheme (SBCS) is acceptable.

Explanation

≍♭1◴⧈(≍⇡₁2⍆⌵-)⍉⊟⊃◿₅(⌊÷₅)-@A
                         -@A subtract letter 'A' to yield numeric
                             alphabet positions [0-24]
                 ⊃           fork both
                  ◿₅          x and
                    (⌊÷₅)     y coordinate calculations
                             which yields two 1-dimensional arrays
                ⊟            coupled to a wide 2xN array and
               ⍉            transposed to a tall Nx2 array of [x y] rows
    ⧈(       )               stencil to operate on row pairs
            -                 calculate differences
           ⌵                  drop any negative signs
          ⍆                   sort coordinate pair ascending
      ≍⇡₁2                    compare against the only good [1 2] pair
                             which yields an array of matches
   ◴                         deduplicate the matches
≍♭1                          and compare against the array [1]

posted 3 months ago

CC BY-SA 4.0

ojdo‭

71 reputation 0 7 7 2

Perl 5, 121 bytes

Reads a string from stdin. Exits 0 if valid tour, 1 if invalid.

perl -ne'map{$h=~y/7-^/<-c/;$h.=q|A8>HL B79?IKM C8:<@FJLN D9;=GMO E:>HN |}1..5;map{exit(1)if$p&&$h!~/$_\S*$p/;$p=$_}/./g'

echo 'ALURYNEHSVKBITWPGDOXQFCJM' | perl -ne'
    # extend board:
    #     789:;
    #     <=>?@
    #     ABCDE
    #     FGHIJ
    #     KLMNO
    #     PQRST
    #     UVWXY
    #     Z[\]^
    #     _`abc

    # using ABCDE row as examplar, encode lookup data as
    #   space-terminated list of move followed by valid
    #   previous positions
    # generate string containing data for all five rows
    #   by repeatedly translating ascii+5
    map {
        $h =~ y/7-^/<-c/;
        $h .= q|A8>HL B79?IKM C8:<@FJLN D9;=GMO E:>HN |
    } 1..5;

    # walk the moves
    map {
        # after first move, do regex match to check if
        #   the actual previous position of current move
        #   is present in the lookup data and abort if not
        exit(1) if $p && $h !~ /$_\S*$p/;
        $p = $_
    } /./g

    # if we get here, assume valid and exit(0)
'

Try it online!

posted 3 months ago

CC BY-SA 4.0

3mo ago

jhnc‭

581 reputation 0 46 58 98