29
\$\begingroup\$

I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021.

Would be super great to get a couple more terms for [...] A049021. Kind of thing [...] team golf would excel at.

As I found out the hard way with the help of user202729, the definition of A049021 is... slippery. Instead, this challenge will have you compute a similar sequence.

(If, separate from this challenge, you're interested in computing more terms of A049021, I encourage it!)

Definition

This challenge will have you counting topologically distinct ways of partitioning a square into \$n\$ rectangles.

Two partitions are called topologically distinct if there's no homeomorphism \$A \rightarrow B\$ with the additional property that the corners of \$A\$'s square map surjectively to the corners of \$B\$'s square. The less fancy way of saying this is that if partitions \$A\$ and \$B\$ are topologically equivalent, there is a map from \$A \rightarrow B\$ and a map from \$B \rightarrow A\$ such that all nearby points stay nearby, and every corner of \$A\$ is sent to a distinct corner of \$B\$.

Examples of homeomorphisms are rotating the square, flipping the square, and "slightly" moving the boundaries of the rectangles.

When \$n = 4\$ there are seven topologically distinct partitions:

The seven topologically distinct ways of dissecting a square into 4 rectangles.

As user202729 pointed out, sometimes these equivalences are somewhat surprising; in particular, the following partitions are equivalent by homeomorphism: An example of two partitions that are homeomorphism.

Challenge

This challenge will have you write a program that computes as many terms of this new sequence as possible. In case of a close call, I will run submissions on my machine, a 2017 MacBook Pro with 8 GB of RAM.

(Be aware that some of these square partitions are more complicated then just putting two smaller partitions side-by-side.)

\$\endgroup\$
40
  • 6
    \$\begingroup\$ I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021 This must be the first time a challenge asks to write useful code \$\endgroup\$
    – Luis Mendo
    Mar 1 at 23:29
  • 1
    \$\begingroup\$ @user202729 The second and 3rd are homeomorphic, however the corner mapping cannot be surjective. The four corners of A map to only 2 corners of B. \$\endgroup\$
    – Grain Ghost
    Mar 2 at 12:58
  • 2
    \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – Grain Ghost
    Mar 2 at 15:39
  • 1
    \$\begingroup\$ This configuration can't be generated by the algorithm used by the OEIS sequence. \$\newcommand{\x}[1]{\color{#1}{\blacksquare}} \newcommand{\r}{\x{red}} \newcommand{\g}{\x{green}} \newcommand{\b}{\x{blue}} \newcommand{\y}{\x{yellow}} \newcommand{\c}{\x{cyan}} \newcommand{\m}{\x{magenta}} \begin{matrix} \r\b\b\b\r\r\b\b\b\b\b\\ \r\g\y\y\r\r\g\g\g\g\y\\ \r\g\y\y\m\m\m\m\m\m\y\\ \r\g\y\y\c\c\c\r\r\b\b\\ \m\m\y\y\c\c\c\r\r\b\b\\ \m\m\y\y\c\c\c\r\r\g\y\\ \r\b\b\b\b\b\b\r\r\g\y\\ \r\g\g\g\g\y\y\r\r\g\y\\ \m\m\m\m\m\y\y\m\m\m\y\\ \end{matrix}\$ \$\endgroup\$
    – DELETE_ME
    Mar 3 at 7:02
  • 2
    \$\begingroup\$ Voting to close because of the edit "as user 202729 pointed out..." It looks to me that to get from one to the other you have to slide through the point where the Northwest rectangle forms a 4-way corner with the rectangles East, South and Southeast of it. Also, if these two are equivalent, why aren't the 5th and 2nd examples for n=4 equivalent? Extend the west rectangle till it fills the whole west side, then rotate 90 deg. I think this needs clearer definition. \$\endgroup\$ Mar 3 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.