[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](https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods) as usual. [Programs or functions](http://meta.codegolf.stackexchange.com/a/2422/36398) are allowed, in any [programming language](https://codegolf.meta.stackexchange.com/questions/2028/what-are-programming-languages/2073#2073). [Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) 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]
# [Haskell](https://www.haskell.org/), ~~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!](https://tio.run/##RY0xDgIhEAC/QmEBEU7pLHbvB/cCJBcgehK5DRFNKPg7SmUz1WTm4crzllLvG6PmQJXgKPGjOMNh3l1e@HVVs9FSaUlSkRVGTxNZLJ/d6FZBOWl886CqDAMeMVjEak9/w/bdRWLIRnBl@RXpzfk9xcylQIBN/Gaje7GifwE "Haskell – 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]
# [Python 2](https://docs.python.org/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!](https://tio.run/##FY0xDoMwEATr8IorbXFO4oQqkvkEpeXCkbGCBAsCp8jrnaPd3ZndfuWz4lFrdnNc3ikSeHD@Hl7o3TxCDToi0fFdVFZStX7wxoY2BZ3XnRJN8AZsLFtG0LfuKunJHWMRVveo5w6yI//kjq2om8u2TyhyRSLVTf0D "Python 2 – Try It Online")
A recursive approach inspired by [flawr's lovely Haskell answer](https://codegolf.stackexchange.com/a/197382/69880). Outputs a float.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~15~~ 12 bytes
```
‘ı×Ƭ¤ṗÄQƑ€Æm
```
[Try it online!](https://tio.run/##ATkAxv9qZWxsef//4oCYxLHDl8aswqThuZfDhFHGkeKCrMOGbf874oCcIC0@IOKAnTvDhwrDh@KCrFn//zg "Jelly – 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]
# [MATL](https://github.com/lmendo/MATL), 16 bytes
Done with a lot of help from [Luis Mendo](https://codegolf.stackexchange.com/users/36398/luis-mendo) in [MATL CHATL](https://chat.stackexchange.com/rooms/39466/matl-chatl).
```
QJ4:!^Z^!YsSdAYm
```
[Try it at MATL Online!](https://matl.io/?code=QJ4%3A%21%5EZ%5E%21YsSdAYm&inputs=4&version=22.1.0)
Alternative:
```
Q8BPZFZ^!YsSdAYm
```
[Try it at MATL Online!](https://matl.io/?code=Q8BPZFZ%5E%21YsSdAYm&inputs=4&version=22.1.0)
## 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](https://chat.stackexchange.com/transcript/message/53024041#53024041).
[Answer]
# [R](https://www.r-project.org/) + gtools, ~~111~~ 88 bytes
```
mean(!apply(diffinv(t(expand.grid(rep(list(c(1,-1,n<-scan(),-n)),n)))),2,anyDuplicated))
```
[Try it online!](https://tio.run/##Dcs9CoAwDEDhs7glkAoKbo5eJPRHAjWEtoqevnZ43/ZK71dkhYnN8gdBUhJ9oEF8jTXMZ5EAJRpkqQ08LOQW0t1VPyYkp4g0Gq7E@h23ZfHcYkDsW/8B "R – Try It Online")
[Test suite](https://tio.run/##VY7NCsIwEITvfYo1UNjARqgnKfXmY3gJ@ZFAXUOTSoP47DHFk4cZhjl8M0v1MCnwK5scnoybhHeXjOa/Vm714TTjQcc4F7TB@8AvzOi2qNke70uwuLiIc0gZDQ6kBuJJ7SCUpFhKamp@Is3lusY5GJ2dlbJ@upYwxSVw9ih6O0KfBEHZHwzjmSD9Vgv5BkguwgXEjYWsXw)
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]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 16 bytes
Uses [flawr's method](https://codegolf.stackexchange.com/a/197382/59487) of reducing to 1D.
```
1‚D(«Iãε.¥DÙQ}ÅA
```
[Try it online!](https://tio.run/##ASMA3P9vc2FiaWX//zHigJpEKMKrScOjzrUuwqVEw5lRfcOFQf//NQ "05AB1E – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), 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!](https://tio.run/##DctBDsIgEADAe1/RgyS7EdqSeDAG/IEvQNKQVpR0IRvRm28Xnfs8Qt1uRC3aawPhPHZKi9nqrgiy9Z0dFKVR5MCwXxGmE@FnNcppqbTkJBUnLwMRjHZC8uOh5ZBKb/v/uMw9P1N5AURKDBKtMRHN7uz0MBw9tu8SKdxrUwvzDw "Haskell – Try It Online")
Uses a similar idea to [flawr's solution](https://codegolf.stackexchange.com/a/197382/20260) 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]
# [Python 3](https://docs.python.org/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!](https://tio.run/##K6gsycjPM/7/P802JzE3KSVRIU@nwNZARyvYKs/GML9Iobg0VyNNI0/XUKdQpwAorJkGFCxUyMyrLgCKFWgDsa5hFoiRVatbrRVcq6lv8h@kJg@oRqEoMS89VcNQx1LTiouzoCgzr0QjT0cBaJ6m5n8A "Python 3 – Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~56~~ 52 bytes
```
Ｎθ≔⁰η⊞υ⟦⁰⟧ＦυＦΦ⁺⟦¹θ±¹±θ⟧§ι±¹¬№ικ¿⁼Ｌιθ≦⊕η⊞υ⁺ι⟦κ⟧Ｉ∕ηＸ⁴θ
```
[Try it online!](https://tio.run/##TY5NSwMxEIbv/oo5TiBCC715KlVhQUvvyx7i7nQTmiZNMqn@@zi7qHiar2dentGaPEbjW@vCrfKxXj8oY1JPD/tS3Bxwo8HKdKrFYtXQbwaZzjEDVgVrfXWe5efka8F@qyFpONJsmHCr/tqkBg177sJEX@j@EWphIuMh1sDL5SIrcGfAl1SNL/hGYWaLTrgkl3dz@zHrwpjpSoFpWh2BfCH4FV11JK6/DGrxz07iD6YwPru7mwitMPFTxHdrsECt7drj3X8D "Charcoal – 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.
]