13
\$\begingroup\$

Imagine a straight river and a road that goes across the river n times through bridges. The road does not loop on itself and is infinitely long. This road would be considered an open meander. An open meander is an open curve, that does not intersect itself and extends infinitely at both ends, which intersects a line n times.

A valid meander may be described entirely by the order of the intersection points it visits.

The number of distinct patterns of intersection with n intersections a meander can be is the nth meandric number. For example, n = 4:

The first few numbers of this sequence are:

1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954...

This is OEIS sequence A005316.

Challenge

Write a program/function that takes a positive integer n as input and prints the nth meandric number.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • Your solution can either be 0-indexed or 1-indexed but please specify which.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
  • Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

These are 0-indexed. Note that you need not handle numbers this big if your language cannot by default.

Input      Output

1          1
2          1
11         1828
14         30694
21         73424650
24         1649008456
31         5969806669034

In a few better formats:

1 2 11 14 21 24 31
1, 2, 11, 14, 21, 24, 31
\$\endgroup\$
  • 1
    \$\begingroup\$ You define a meander to be a closed curve, but the OEIS sequence you have is for meanders by open curves. Did you mean A005315 instead? \$\endgroup\$ – Not a tree Jul 20 '17 at 23:58
  • 7
    \$\begingroup\$ this is Project-Euler level... \$\endgroup\$ – J42161217 Jul 21 '17 at 0:10
  • 1
    \$\begingroup\$ @Notatree Oh, there's my big screw-up of the day... Was looking for it. Will fix, thanks for letting me know! \$\endgroup\$ – totallyhuman Jul 21 '17 at 0:10
  • 3
    \$\begingroup\$ combinatorics.org/ojs/index.php/eljc/article/view/v19i2p43/pdf \$\endgroup\$ – J42161217 Jul 21 '17 at 0:16
  • 1
    \$\begingroup\$ One more quibble (sorry…): an open curve is allowed to have endpoints, but I think an open meander has to extend to infinity at both ends. (If endpoints are allowed, you can have curves that do things like so the meandric numbers would be bigger.) \$\endgroup\$ – Not a tree Jul 21 '17 at 0:56
11
\$\begingroup\$

Python 3, 208 188 187 184 180 177 171 bytes

lambda n:sum(all(i-j&1or(x<a<y)==(x<b<y)for(i,(a,b)),(j,(x,y))in d(enumerate(map(sorted,zip((0,)+p,p+(n,)))),2))for p in d(range(n)))
from itertools import*;d=permutations

Try it online!

Now 1-indexed (was previously 0-indexed but 1-indexing saved a byte due to a lucky quirk regarding the behavior of meanders).

Explanation

This may be the same as the link posted by Jenny_mathy, but I didn't end up reading the paper, so this is just the logic behind my method.

I will be using the following illustration provided on OEIS in order to visualize the results.

enter image description here

Each valid meander may be described entirely by the order of the intersection points it visits. This may be trivially observed in the image; the entry segment is always on the same side (otherwise the number would be double). We can represent the tendency of both the entry and exit segments to their respective infinities by simply adding to every order a point on either side - that is to say, the order (2, 1, 0) would become (-1, 2, 1, 0, 3).

With this in mind, the task is to find the number of orders, or permutations of the range up to n, which do not intersect with themselves. Intersections are only an issue between pairs of points for which the connecting segment lies on the same side. For any two pairs of consecutive points in a permutation whose segments share a side, whether or not they intersect is equivalent to whether one, and only one, of the points of one pair is between the two elements of the other pair. As such, we can determine if an order is valid by whether there are no pairs with one point contained by another pair with a segment on the same side.

Finally, having determined the validity of each permutations, the output of the function comes down to the number of permutations found to be valid.

\$\endgroup\$
  • 1
    \$\begingroup\$ Did you already have this done for a combinatorics class? Or did you just FGITW exceptionally hard? \$\endgroup\$ – Magic Octopus Urn Jul 21 '17 at 1:06
  • 2
    \$\begingroup\$ @MagicOctopusUrn Honestly, I've been bashing my head against this for about two hours - so I guess the latter. \$\endgroup\$ – notjagan Jul 21 '17 at 1:08
  • \$\begingroup\$ Would you mind if I used some of your explanation in the question? 'Cause my explanation currently... is not... great. \$\endgroup\$ – totallyhuman Jul 21 '17 at 10:37
  • 1
    \$\begingroup\$ @totallyhuman Feel free to use anything that seems useful, although I imagine it's not too much since a lot is specific to my method in particular. \$\endgroup\$ – notjagan Jul 21 '17 at 17:39
5
\$\begingroup\$

Haskell, 199 bytes

1!x=x
-1!(-1:x)=1:x
n!(i:x)=i:(n-i)!x
0#([],[])=1
0#_=0
n#(a,b)=sum$((n-1)#)<$>(-1:a,-1:b):[(a,-i:b)|i:a<-[a]]++[(-j:a,b)|j:b<-[b]]++[(j!a,i!b)|i:a<-[a],j:b<-[b],i+j>=0]
f n=n#([],[-1,1])+n#([1],[1])

Try it online!

Based on an extension of the ideas in Iwan Jensen, Enumerations of plane meanders, 1999 to the case of open meanders. This runs through n = 1, …, 16 in about 20 seconds on TIO.

\$\endgroup\$
  • \$\begingroup\$ Have you seen arxiv.org/abs/cond-mat/0008178 ? \$\endgroup\$ – Peter Taylor Jul 21 '17 at 17:35
  • \$\begingroup\$ @PeterTaylor I hadn’t. It looks like a newer version of the same paper, updated with a strategy for dealing with open meanders that’s probably easier to explain than my strategy, but that requires many more special cases in the code. \$\endgroup\$ – Anders Kaseorg Jul 21 '17 at 18:53
0
\$\begingroup\$

APL (Dyalog Classic), 127 115 bytes

⊃⊃⌽{↓⍉(⊃,/c),∘(+/)⌸(≢¨c←{1↓¨⍳¨⍨0,¨((×2↑¯1⌽⍵)/¯1 1⌽¨⊂⍵),(⊂∊#⍵#),(××/m,≠/m)/⊂1↓¯1↓(⊢-⍵×~)⍵∊m←2↑¯1⌽⍵}¨⊃⍵)/⊃⌽⍵}⍣⎕⌽1,⊂⍳2

Try it online!

\$\endgroup\$
  • \$\begingroup\$ How does this work? \$\endgroup\$ – lirtosiast Nov 30 '18 at 22:56
  • \$\begingroup\$ @lirtosiast basically this but encoding matching loop ends with matching integer ids instead of 0/1 \$\endgroup\$ – ngn Dec 1 '18 at 11:33

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.