13
\$\begingroup\$

Information

  • Given a non-negative odd integer (let's call it \$n\$), find the number of all possible paths which covers all squares and get from the start to end on a grid.
  • The grid is of size \$n\$×\$n\$.
  • The start of the path is the top left corner and the end is the bottom right corner.
  • You have to count the number of all paths which go from the start to end which covers all squares exactly once.
  • The allowed movements are up, down, left and right.
  • In other words compute A001184, but numbers are inputted as grid size.

Scoring

This is code-golf, write the shortest answer in bytes.

Test cases

1  → 1
3  → 2
5  → 104
7  → 111712
9  → 2688307514
11 → 1445778936756068
13 → 17337631013706758184626
\$\endgroup\$
1

8 Answers 8

5
\$\begingroup\$

Python 3, 109 bytes

f=lambda n,x=0,*s:1-(x in s)and(x==n*n-1==len(s)or sum(f(n,x+a,x,*s)for a in(~x%n>0,x%n//-n,n,-n)if-1<x<n*n))

Try it online!

Port of my answer to Find the shortest route on an ASCII road. Brute forces all paths and returns the number of valid ones. Slow as molasses, though.

-4 bytes thanks to Jakque

-8 bytes thanks to att

\$\endgroup\$
4
  • 1
    \$\begingroup\$ if you move the n*n>x>=0 condition inside the sum using a if, you can save a byte : def f(n,*s):*p,x=0,*s;return{x}-{*p}and sum(f(n,*s,x+a)for a in(-~x%n>0,-(x%n>0),n,-n)if n*n>x>=0)or len({*s})==n*n-1==x \$\endgroup\$
    – Jakque
    Oct 21, 2021 at 10:44
  • 2
    \$\begingroup\$ 112 bytes \$\endgroup\$
    – att
    Oct 21, 2021 at 22:16
  • 1
    \$\begingroup\$ -1 byte because ~x%n>0 is equivalent to -~x%n>0 \$\endgroup\$
    – Jakque
    Oct 22, 2021 at 9:24
  • 1
    \$\begingroup\$ also -1 byte because x%n//-n is equivalent to -(x%n>0) \$\endgroup\$
    – Jakque
    Oct 22, 2021 at 9:33
4
\$\begingroup\$

Jelly, 21 bytes

æịþḶFµḢ;ⱮṖŒ!;€ṪƲIỊẠ€S

Try it online!

Takes forever for n>3 because it tries to generate all permutations of n**2-2 items.

æịþḶFµḢ;ⱮṖŒ!;€ṪƲIỊẠ€S    Monadic link. Input: n
æịþḶF                    Generate complex numbers (1..n)+(0..n-1)i
     µḢ;ⱮṖŒ!;€ṪƲ         Generate all permutations with 1st and last fixed:
      Ḣ;Ɱ                  Chain 1st to each of...
         ṖŒ!;€               Permutations of the middle with...
              ṪƲ               The last chained to the end of each
                IỊẠ€S    Count those whose pairwise distances are all 1
\$\endgroup\$
3
\$\begingroup\$

Python 3, 185 bytes

def f(n):k=range(n);v=[-~x+y*1j for x in k for y in k];return sum(all(abs(z-y)<=1for y,z in zip(x,x[1:]))for x in[[1]+[*q]+[v[-1]]for q in permutations(v[1:-1])])
from itertools import*

Try it online!

@Bubbler's Jelly answer port

-3 thanks to @KevinCruijssen

\$\endgroup\$
4
  • \$\begingroup\$ Shouldn't the <=1 be ==1 (shouldn't make a difference since we're working with non-duplicated integers in the permutation, but still). \$\endgroup\$ Oct 21, 2021 at 8:16
  • \$\begingroup\$ @KevinCruijssen I don't know, my answer is just the Jelly port, it uses <=1 () so I used too \$\endgroup\$
    – Wasif
    Oct 21, 2021 at 8:20
  • \$\begingroup\$ Yeah, I thought so, since Jelly has a convenient builtin for that. :) Since we're working with unique integers in the permutations, z-y can never be 0. Doesn't matter to the byte-count either way though, so whatever. Also, I think (not entirely sure, I'm not too familiar with complex numbers tbh) you can save some bytes by changing [v[0]] to [1], since [v[0]] will always be 1+0j. \$\endgroup\$ Oct 21, 2021 at 8:27
  • 1
    \$\begingroup\$ @KevinCruijssen thanks for the 3 byte save!! (BTW jelly port in 05ab1e ends up 28 bytes) \$\endgroup\$
    – Wasif
    Oct 21, 2021 at 8:37
3
\$\begingroup\$

05AB1E, 27 bytes

LD<⩨¦œε®нš®θªü2€øÆnOtΘP}O

Try it online!

Basic idea is like Bubblers, represent the grid as complex numbers, jumble all the intermediate cells between the first and last, and compute their distances and check if they are adjacent

a byte save thanks to @KevinCruijssen

Explanation (pseudo-code)

range
dup
decrement
cartesian product
copy to register (no pop)
cut tail
behead
permutations
map
  push register
  head
  prepend
  push register
  tail
  append
  cumulative pairs
  map
    zip
  deltas
  square
  sum
  square root
  equals 1?
  product
end map
sum
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I knew 05AB1E lacked complex numbers, so I didn't even tried to port it. But using pairs like that to pretend they're complex numbers is pretty nice. +1 from me. \$\endgroup\$ Oct 21, 2021 at 8:51
  • 1
    \$\begingroup\$ -1 byte changing ε`-} to €øÆ \$\endgroup\$ Oct 21, 2021 at 8:56
  • \$\begingroup\$ @KevinCruijssen thanks!! (And thanks for the earlier ==1 pointer, it saves a byte here since 05ab1e lacks less than or equal builtin) \$\endgroup\$
    – Wasif
    Oct 21, 2021 at 9:05
  • \$\begingroup\$ If you're checking that the square root of the sum equals 1, can't you just check that the sum equals 1, and remove the square root? \$\endgroup\$ Oct 21, 2021 at 22:10
  • \$\begingroup\$ @cairdcoinheringaahing The square + square root is because values can be negative, but you're implicitly right that summing the absolute values is possible and 1 byte shorter: nOt to ÄO. \$\endgroup\$ Oct 25, 2021 at 9:58
3
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

-3 bytes thanks to @att.

Length@FindPath[GridGraph@{#,#},1,#^2,{#^2-1},All]/. 0->1&

n = 7 takes 3 minutes on my computer.

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 58 bytes \$\endgroup\$
    – att
    Oct 21, 2021 at 18:49
  • \$\begingroup\$ When using the right tool for the job feels like cheating :P \$\endgroup\$
    – Kaddath
    Oct 22, 2021 at 9:56
2
\$\begingroup\$

05AB1E, 36 33 bytes

nÍLœε0šZ>ªü2εDI÷ËiÆëI‰ø`ËsÆ*]ÄPΘO

Brute-force approach generating permutations of the grid (minus first and last item), so times out for anything \$n>3\$ (\$n=3\$ takes about 5 seconds).

Try it online.

Explanation:

Step 1: Generate all permutations of the list \$[1,n^2-2]\$, and prepend a leading \$0\$ and trailing \$n^2-1\$ to each:

n                 # Push the square of the (implicit) input-integer
 Í                # Decrease it by 2
  L               # Push a list in the range [1,n²-2]
   œ              # Pop and push all permutations of this list
    ε             # Map each permutation-list to:
     0š           #  Prepend a leading 0
       Z          #  Push the maximum (without popping the list)
        >         #  Increase it by 1
         ª        #  And append it as trailing item

Try just the first step.

Step 2: Check for each list whether it's a valid path:

ü2               #  Create overlapping pairs of the current list
  ε              #  Inner map the list of pairs to:
   D             #   Duplicate the current pair
    I÷           #   Integer-divide both integers in this copy by the input-integer
      Ëi         #   If both are the same (they're in the same row of the grid):
        Æ        #    Reduce the current pair by subtracting
       ë         #   Else:
        I‰       #    Divmod both integers in the current pair by the input-integer
          ø      #    Zip/transpose; swapping rows/columns
           `     #    Pop and push both pairs separated to the stack
            Ë    #    Check if the top pair (the [a%input,b%input]) are both the same
             s   #    Swap to get the other pair (the [a//input,b//input])
              Æ  #    Reduce it by subtracting
               * #    Multiply it to the a%input==b%input check
]                # Close the if-else statement and nested maps
 Ä               # Take the absolute value of each innermost integer
  P              # Taking the product of each inner list
   Θ             # Check for each if it's equal to 1 (1 if 1; 0 if not)

The I÷Ë checks if the integers in the current pair are in the same row of the grid, and with Æ + Ä it checks if their absolute difference is 1.
For any remaining pair that are not in the same row, the I‰ø`ËsÆ* + Ä checks if the two integers are in the same column and their absolute (vertical) difference is also 1.
The P after the map then checks if this was truthy for all of the pairs in the list.

Try the first two steps.

Step 3: Check how many valid paths were valid after the map, and output it as result:

O                 # Pop and sum to get the amount of valid paths
                  # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 82 bytes

NθUOθ#J⊖θ⊖θP0⊞υ⌕AKV#≔⁰ηWυ«≔⊟υι¿ι«⊞υι≔⊟ιιM✳⁻χ⊗ιPIι⊞υ⌕AKV#»«≧⁺¬∨∨ⅈⅉ№KA#η✳⁻⁶⊗KK#»»⎚Iη

Try it online! Link is to verbose version of code. Will do n=5 on TIO but larger numbers are probably too slow. Explanation: Works by counting the paths from the bottom right corner back to the top left corner of an n×n square drawn on the canvas.

Nθ

Input n.

UOθ#

Draw an n×n square of #s.

J⊖θ⊖θP0

Start at the bottom right corner. (Any digit works here, it's just a placeholder showing that the square has been visited.)

⊞υ⌕AKV#

Start with the possible moves from the corner. (This is empty for n=1 of course.)

≔⁰η

Start with 0 paths found.

Wυ«

Repeat until all paths have been attempted.

≔⊟υι

Pop the remaining moves to try from the current cell from the stack.

¿ι«

If there are any moves left, then:

⊞υι

Push the moves back to the stack again.

≔⊟ιι

Pop the next move to try.

M✳⁻χ⊗ι

Move in that direction.

PIι

Overwrite the current cell with the direction, so that we can find our way back, and also so that we don't try to re-enter the cell.

⊞υ⌕AKV#

Push the available moves from this cell to the stack.

»«

Otherwise:

≧⁺¬∨∨ⅈⅉ№KA#η

If the current cell is at the top left and there are no #s left indicating that we've covered all of the squares, then increment the count of paths found.

✳⁻⁶⊗KK#

Overwrite the current cell with a # and move back to the previous cell.

»»⎚Iη

Clear the canvas and output the number of paths found.

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

Python 3, 138 bytes

f=lambda n,a={0},x=0,y=0:n==len(a)/n<x+2<y+3or sum(f(n,a|{(x,y)},i,j)for i in range(n)for j in range(n)if(x-i)**2+(y-j)**2==1and{(i,j)}-a)

Try it online!

returns True for f(1)

How it works :

take as input :

  • n the size of the grid
  • a={0} the set of all visited positions initialized with a 0 to avoid typing set()
  • x=0,y=0 the current position in the grid

then :

  • n==len(a)/n<x+2<y+3 verify if we visited all positions and if we are in the bottom right of the grid

  • f(n,a|{(x,y)},i,j)for i in range(n)for j in range(n) if recursively call f with all the position verifying

    • (x-i)**2+(y-j)**2==1 the position is at distance 1 of (x,y)
    • {(i,j)}-a the position is unvisited
\$\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.