Proportion of self-avoiding walks on a square lattice

Question

The challenge

Given a positive integer N, compute the proportion of N-step walks on a plane that don't intersect themselves.

Each step can have any of the 4 possible directions North, East, South, West.

A walk intersects itself if it visits a previously visited point.

Examples

• N=1: a single-step walk obviously doesn't intersect itself. So the result is 1.
• N=2: given the first step in any direction, there are 3 possible directions that avoid intersection, and one that goes back to the origin, causing intersection. So the result is 3/4 = 0.75.
• N=3: if the second step doesn't cause intersection, which happens 3/4 of the times, the third step will not cause intersection with probability again 3/4. So the result is (3/4)^2 = 0.5625.
• N=4: things become more interesting because proper loops can be formed. A similar computation as above gives (3/4)^3 - 8/4^4 = 0.390625, where the second term accounts for the 8 proper loops out of the 4^4 possible paths (these are not excluded by the first term).

Additional rules

• Output can be floating-point, fraction, or numerator and denominator.
• If floating point, the result should be accurate up to at least the fourth decimal.
• Input and output are flexible as usual. Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
• Shortest code in bytes wins.

Test cases

1  -> 1
2  -> 0.75
3  -> 0.5625
4  -> 0.390625
5  -> 0.27734375
6  -> 0.1904296875
7  -> 0.132568359375
8  -> 0.09027099609375
9  -> 0.0620574951171875
10 -> 0.042057037353515625
11 -> 0.02867984771728515625
12 -> 0.0193674564361572265625

Answer 1

Haskell, 153 149 144 140 126 118 92 bytes

Here we represent the 2d coordinates as a single integer: We start at 0, and the directions N,E,S,W correspond to adding +n,+1,-n,-1 where n is the input (we could also use any larger number). Using this we generate all possible paths, and then just check for duplicate numbers in those paths.

Thanks @H.PWiz for -26 bytes!

g n|a<-scanl(+)0<$>mapM(\_->[1,-1,n,-n])[1..n]=sum[1|x<-a,[b|b<-x,c<-x,b==c]==x]/sum[1|x<-a]

Try it online!

Explanation

--generate all possible paths
    a<-scanl(+)0<$>mapM(\_->[1,-1,n,-n])[1..n]
--count the non-self intersecting paths, compute the ratio to the total
g n|a<- ... =sum[1|x<-a,[b|b<-x,c<-x,b==c]==x]/sum[1|x<-a]

Answer 2

Python 2, 89 bytes

f=lambda n,S=[0]:n>=len(S)and sum(f(n,S+[S[-1]+d])for d in[-n,-1,1,n])/4.or len(set(S))>n

Try it online!

A recursive approach inspired by flawr's lovely Haskell answer. Outputs a float.

Answer 3

Jelly, 15 12 bytes

‘ı×Ƭ¤ṗÄQƑ€Æm

Try it online!

A monadic link taking N as its argument and returning a float representing the proportion of non-self-intersecting walks of length N. Generates all walks of that length and then checks for intersections, using complex numbers to represent the 2D coordinates.

Thanks to @LuisMendo for saving a byte, and @Mr.XCoder for saving 2 more!

Explanation

‘            | Increment by 1
    ¤        | Following as a nilad
 ı           | - 1i
  ×Ƭ         | - Multiply (by 1i) until no new values, returning all intermediate values
     ṗ       | Cartesian power (with N+1)
      Ä      | Cumulative sums of innermost lists
       QƑ€   | Check whether each list is invariant when uniquified
          Æm | Arithmetic mean

Answer 4

MATL, 16 bytes

Done with a lot of help from Luis Mendo in MATL CHATL.

QJ4:!^Z^!YsSdAYm

Try it at MATL Online!

Alternative:

Q8BPZFZ^!YsSdAYm

Try it at MATL Online!

Explanation

QJ4:!^Z^!YsSdAYm    – Full program. Receives an integer N as input.
  4:                – Range 1...4.
 J  !^              – Raise J (imaginary unit) to those powers*. Yields j, -1, -j, 1.
Q     Z^            – Cartesian power N+1.
        !Ys         – Transpose and take the cumulative sums.
           Sd       – Sort and get the deltas (consecutive differences).
             A      – All. For each column, if it contains 0, then 0, else 1.
              Ym    – Arithmetic mean.

^{_{(*): ! is needed there because Octave is weird.}}

Answer 5

R + gtools, 111 88 bytes

mean(!apply(diffinv(t(expand.grid(rep(list(c(1,-1,n<-scan(),-n)),n)))),2,anyDuplicated))

Try it online!

Test suite

Reads N from STDIN and implicitly prints the answer as a float.

Thanks to @LuisMendo for a fab challenge and saving 6 bytes! Thanks to @Mr.XCoder for saving 3 bytes (indirectly via my Jelly answer). Thanks to @Giuseppe for saving 10 bytes with an excellent suggestion partially inspired by @flawr’s Haskell answer!

Answer 6

05AB1E, 16 bytes

Uses flawr's method of reducing to 1D.

1‚D(«Iãε.¥DÙQ}ÅA

Try it online!

Answer 7

Haskell, 69 bytes

(%[])
-1%_=1
n%l=sum[(n-1)%map(+d)(0:l)|d<-[1,-1,pi,-pi],all(/=0)l]/4

Try it online!

Uses a similar idea to flawr's solution of storing 2D coordinates as 1D values: \$(x,y)\$ is represented as \$x+\pi y\$. Maybe this is unfair because finite precision means that eventually two different coordinates will be represented as the same value. This will take an extremely large input though because toRational pi equals 884279719003555 % 281474976710656.

Instead of updating the position after each move, we map the position change onto the list of previously visited coordinates. That way, we can detect a collision by seeing a 0 among the previous coordinates. Because we only check a coordinate the loop after it's added, one extra loop is done, for n+1 total.

Answer 8

Python 3, 76 bytes

f=lambda n,p=0,*S:n<1or sum(f(n-1,q,p,*S)for q in{p-1,p+1,p-1j,p+1j}-{*S})/4

Try it online!

Answer 9

Charcoal, 56 52 bytes

Ｎθ≔⁰η⊞υ⟦⁰⟧ＦυＦΦ⁺⟦¹θ±¹±θ⟧§ι±¹¬№ικ¿⁼Ｌιθ≦⊕η⊞υ⁺ι⟦κ⟧Ｉ∕ηＸ⁴θ

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

Ｎθ

Input N.

≔⁰η

Initialise the number of paths to 0.

⊞υ⟦⁰⟧

Start off with a path with no steps.

Ｆυ

Perform a breadth-first search of the paths.

ＦΦ⁺⟦¹θ±¹±θ⟧§ι±¹¬№ικ

Take @flawr's list 1, N, -1, -N and add the last position on the current path to each value. Filter out results that already appear in that path, and loop over the remaining self-avoiding values.

¿⁼Ｌιθ

If this path already has N steps...

≦⊕η

... then increment the count of found paths.

⊞υ⁺ι⟦κ⟧

... otherwise construct a new path and add it to the search list.

Ｉ∕ηＸ⁴θ

Print the proportion of self-avoiding paths.