20
\$\begingroup\$

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

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
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Related: OEIS A001411 \$\endgroup\$
    – Luis Mendo
    Dec 23, 2019 at 20:14
  • 3
    \$\begingroup\$ @Downvoter How can I improve this challenge, or future challenges? Any advice you’d like to share? \$\endgroup\$
    – Luis Mendo
    Dec 24, 2019 at 11:52
  • 6
    \$\begingroup\$ I guess the downvoter tripped over their own path when reading this challenge. \$\endgroup\$
    – flawr
    Dec 24, 2019 at 14:34
  • \$\begingroup\$ why not allow the output to be the number of paths (like in OEIS)? \$\endgroup\$
    – qwr
    Dec 26, 2019 at 22:37
  • \$\begingroup\$ @qwr That was the other option I considered. I settled down on proportion rather than number because proportion has a clearer meaning. ("There are 5916 non-intersecting paths of length 8. Is that a lot? Well, it's a fraction 0.09 of all exiting paths"). Anyway it's too late to change now... \$\endgroup\$
    – Luis Mendo
    Dec 26, 2019 at 22:52

9 Answers 9

14
\$\begingroup\$

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]
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Very clever way to reduce to 1D! \$\endgroup\$
    – Luis Mendo
    Dec 23, 2019 at 22:24
  • \$\begingroup\$ 92 bytes. I think it can be shorter \$\endgroup\$
    – H.PWiz
    Dec 24, 2019 at 15:46
  • \$\begingroup\$ thanks, I feel stupid that I didn't notice the mapM opportunity, and the uniqueness check is neat, maybe something to add for the tips! \$\endgroup\$
    – flawr
    Dec 24, 2019 at 15:55
  • \$\begingroup\$ @H.PWiz Sorry, I mistakenly attributed your suggestion to another wizard! \$\endgroup\$
    – flawr
    Dec 24, 2019 at 19:26
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Good idea :-) I also used complex numbers in my code to generate the test cases \$\endgroup\$
    – Luis Mendo
    Dec 23, 2019 at 22:25
  • 1
    \$\begingroup\$ @LuisMendo thanks. Nice challenge! \$\endgroup\$ Dec 23, 2019 at 22:27
  • 1
    \$\begingroup\$ 12 bytes with ‘ı×Ƭ¤ṗÄQƑ€Æm. \$\endgroup\$
    – Mr. Xcoder
    Dec 24, 2019 at 9:03
  • \$\begingroup\$ @Mr.Xcoder thanks! You also brought my R answer under 100 bytes. \$\endgroup\$ Dec 24, 2019 at 9:11
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ any(duplicated(...)) -> anyDuplicated(...)? \$\endgroup\$
    – Giuseppe
    Dec 24, 2019 at 14:11
  • \$\begingroup\$ Or doing the 1-d reduction inspired by flawr, you can get to 91 bytes \$\endgroup\$
    – Giuseppe
    Dec 24, 2019 at 14:19
  • \$\begingroup\$ @Giuseppe thanks. The 1-d reduction fails for N=1; I can’t see an obvious way around that that costs fewer than 5 bytes. \$\endgroup\$ Dec 24, 2019 at 18:30
  • 2
    \$\begingroup\$ perhaps a nice base R expand.grid will work: 88 bytes \$\endgroup\$
    – Giuseppe
    Dec 24, 2019 at 18:49
  • \$\begingroup\$ @Giuseppe thanks, I’d not used diffinv or anyDuplicated before; both very handy! \$\endgroup\$ Dec 24, 2019 at 19:41
3
\$\begingroup\$

05AB1E, 16 bytes

Uses flawr's method of reducing to 1D.

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

Try it online!

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

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.

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

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!

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

Charcoal, 56 52 bytes

Nθ≔⁰η⊞υ⟦⁰⟧FυFΦ⁺⟦¹θ±¹±θ⟧§ι±¹¬№ικ¿⁼Lιθ≦⊕η⊞υ⁺ι⟦κ⟧I∕ηX⁴θ

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

Nθ

Input N.

≔⁰η

Initialise the number of paths to 0.

⊞υ⟦⁰⟧

Start off with a path with no steps.

Fυ

Perform a breadth-first search of the paths.

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

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.

¿⁼Lιθ

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.

I∕ηX⁴θ

Print the proportion of self-avoiding paths.

\$\endgroup\$

Your Answer

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

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