14
\$\begingroup\$

A convenient and useful way to represent topological surfaces is with a fundamental polygon. Each side on a polygon matches to another side and can be either parallel or anti-parallel. For instance the here is the fundamental polygon of a torus:

Torus

To figure out why this is a torus we could imagine our polygon being a sheet of paper. To make the proper surface we want to bend our paper so that the corresponding edges line up with their arrows going the same way. For our torus example we can start by rolling the paper into a cylinder so that the two blue edges (labeled b) are connected. Now we take our tube and bend it so that the two red edges (labeled a) connect to each other. We should have a donut shape, also called the torus.

This can get a bit trickier. If you try to do the same with the following polygon where one of the edges is going in the opposite direction:

Klein Bottle

you might find yourself in some trouble. This is because this polygon represents the Klein bottle which cannot be embedded in three dimensions. Here is a diagram from wikipedia showing how you can fold this polygon into a Klein bottle:

Folding a Klein Bottle


As you may have guessed the task here is to take a fundamental polygon and determine which surface it is. For four sided polygons (the only surfaces you will be required to handle) there are 4 different surfaces.

They are

  • Torus

  • Klein Bottle

  • Sphere

  • Projective plane

Now this is not so I don't expect you to take an image as input instead we will use a convenient notation to represent the fundamental polygon. You may have noticed in the two examples above that I named corresponding edges with the same letter (either a or b), and that I gave the twisted edge an additional mark to show its twisted. If we start at the upper edge and write down the label for each edge as we go clockwise we can get a notation that represents each fundamental polygon.

For example the Torus provided would become abab and the Klein Bottle would become ab-ab. For our challenge we will make it even simpler, instead of marking twisted edges with a negative we will instead make those letters capitalized.

Task

Given a string determine if it represents a fundamental polygon and output a value that corresponding to the proper surface of it is. You do not need to name the surfaces exactly, you just need 4 output distinct values each representing one of the 4 surfaces with a fifth value representing improper input. All of the basic cases are covered in the Simple Tests section, every car will be isomorphic to one of the or invalid.

Rules

  • Sides will not always be labeled with a and b, but they will always be labeled with letters.

  • Valid input will consist of 4 letters, two of one type and two of another. You must always output the correct surface for valid input.

  • You should reject (not output any of the 4 values representing surfaces) invalid input. You may do anything when rejecting an input, as long as it is distinguishable from the 4 surfaces

  • This is so the goal is to minimize the number of bytes in your source code.

Tests

Simple Tests

abab Torus
abAb Klein Bottle
abaB Klein Bottle
abAB Projective Plane
aabb Klein Bottle
aAbb Projective Plane
aabB Projective Plane
aAbB Sphere
abba Klein Bottle
abBa Projective Plane
abbA Projective Plane
abBA Sphere

Trickier Tests

ABAB  Torus
acAc  Klein Bottle
Emme  Projective Plane
zxXZ  Sphere
aaab  Bad input
abca  Bad input
abbaa Bad input
ab1a  Bad input
\$\endgroup\$
  • \$\begingroup\$ Why is abab a torus and aabb a Klein bottle? \$\endgroup\$ – Neil May 20 '17 at 20:57
  • \$\begingroup\$ @Neil abab is the example in the first paragraph, you can look there for an explanation. Here is an image showing why aabb is the same as abAb which is a Klein bottle. \$\endgroup\$ – Sriotchilism O'Zaic May 20 '17 at 21:00
  • 1
    \$\begingroup\$ What bad inputs do we have to handle and identify as bad? All possible strings? Printable ASCII? Any limits on length? If we write a function, might it be passed a non-string object? Really, this whole input processing business strikes me as a chameleon challenge. \$\endgroup\$ – xnor May 21 '17 at 7:29
  • 1
    \$\begingroup\$ @WheatWizard In that case, can you please make that clear in the title and body? It reads like math all the way until Rules, and even there it's easy to miss the gamechanging requirement to validate rather than just classify. \$\endgroup\$ – xnor May 21 '17 at 7:39
  • 2
    \$\begingroup\$ Separately, I think an explanation is missing of what makes a string be classified into a given category, since you seem not to expect people to do out the math behind the classification. I think I could puzzle out the rules from test cases, but that's far from ideal. \$\endgroup\$ – xnor May 21 '17 at 7:43
6
\$\begingroup\$

Retina, 123 bytes

i`(.)(\1..)
$2$1
iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$
(..)\1
T
.*(.).\1.*|(.)(.)\3\2
B
(.)..\1|.(.)\2.
P
i`(.)..\1
S
....
P

Try it online! Thanks to @JonathanAllen for pointing out a bug in my code and also how to save some bytes; I also golfed some more bytes myself so I can't credit him for a specific figure. Explanation:

i`(.)(\1..)
$2$1

If the first two letters are the same (ignoring case), move the first letter to be fourth. This reduces the number of cases that I need to test.

iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$

If there are not exactly four letters, or the first two letters are the same, or the last two letters do not duplicate the first two, then delete everything.

(..)\1
T

The torus is the easy case: a pair of letters, repeated matching case.

.*(.).\1.*|(.)(.)\3\2
B

If one of the pair matches case (in which case other of the pair must mismatch case), then that is a Klein bottle. Alternatively, if the pair matches case but is reversed, then it is also a Klein bottle.

(.)..\1|.(.)\2.
P

If on the other hand the pair is reversed, but only one of the pair matches case, then that is a projective plane.

i`(.)..\1
S

And if the pair is reversed but neither matches case, then that is a sphere. (i`.(.)\1. would also work.)

....
P

Everything else is a projective plane.

\$\endgroup\$
  • 1
    \$\begingroup\$ @JonathanAllan Thanks for the tip; hopefully this version has better validation. \$\endgroup\$ – Neil May 21 '17 at 0:03
  • \$\begingroup\$ If only I could work out the logic myself :p \$\endgroup\$ – Jonathan Allan May 21 '17 at 0:05
1
\$\begingroup\$

Jelly, 52 51 58 bytes

+7 bytes, I found that the mapping I'd used did not work for some (off example) case change scenarios.

“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€
,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeЀ¢TṪ’:3,8

A monadic link taking a string and returning the following five distinct, consistent values:

  • [-1,-1] - invalid input
  • [0,0] - projective plane
  • [1,0] - Klein bottle
  • [2,0] - sphere
  • [2,1] - torus

Try it online! or see the test suite.

How?

Any fundamental polygon is:

  • unchanged under rotation - one may turn the paper like a steering wheel
  • unchanged under reflection - one may turn the paper over
  • unchanged under case reversal - one may swap as and As and/or swap bs and Bs with no effect - since we want to match the directions the actual label is inconsequential.

As such there are nine equivalence classes. The code creates lists of four integers each representing an example of one of the nine equivalence classes, creates the four rotations of each, reflects each of those and then checks if a translated form of the input exists in each list. The classes are ordered P,P,P,K,K,K,S,S,T, so taking the 0-based index integer divided by each of [3,8] yields the four valid outputs (indexing is 1-based and the atom e returns 0 for non-existence, so subtracting 1 and integer dividing by each of [3,8] yields [-1,-1] for the invalid case).

“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€ - Link 1, symmetries of the 9 equivalence classes: no arguments
“nḲ⁾⁶ƥ¦ṃṗḋ’              - base 250 number                 1704624888339951310984
           b4            - convert to base 4               [1,1,3,0,1,2,2,0,1,2,3,0,0,2,2,0,1,3,1,0,2,1,2,0,2,3,1,0,3,1,2,0,2,0,2,0]
             s4          - split into 4s                   [[1,1,3,0],[1,2,2,0],[1,2,3,0],[0,2,2,0],[1,3,1,0],[2,1,2,0],[2,3,1,0],[3,1,2,0],[2,0,2,0]]
               ‘         - increment (vectorises)          [[2,2,4,1],[2,3,3,1],[2,3,4,1],[1,3,3,1],[2,4,2,1],[3,2,3,1],[3,4,2,1],[4,2,3,1],[3,1,3,1]]
                µ     µ€ - for €ach:                       ...e.g. [2,2,4,1]:
                  J      -   range of length               [1,2,3,4]
                 ṙ       -   rotate left by (vectorises)   [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1]]
                     $   -   last two links as a monad:
                    U    -     upend (reverse each)        [[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]
                   ;     -     concatenate                 [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1],[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]

,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeЀ¢TṪ’:3,8 - Main link: string s      e.g. "xOxO"
 Œs                               - swap case                     "XoXo"
,                                 - pair with s                   ["xOxO","XoXo"]
    Þ                             - sort by:
   Ṣ                              -   sort                        ["xOxO","XoXo"]
     Ṫ                            - tail                          "XoXo"
      µ                           - monadic chain separation, call that v
       Œl                         - convert to lowercase          "xoxo"
         Ġ                        - group indices by value        [[2,4],[1,3]]
          L€                      - length of each                [2,2]
             2,2                  - 2 pair 2                      [2,2]
            ⁼                     - equal? (1 if so, 0 if not)    1
                 ⁸                - link's left argument, v       "XoXo"
                ȧ                 - and (v if equal, 0 if not)    "XoXo"
                     Ṣ            - sort v                        "XoXo"
                  i@€             - first index for €ach          [1,3,1,3]
                         ¢        - call the last link (1) as a nilad
                       Ѐ         - map over right:
                      e           -   exists in?                  [0,0,0,0,0,0,0,0,1]
                          T       - truthy indexes                [                9]
                           Ṫ      - tail (empty list yields 0)    9
                            ’     - decrement                     8
                              3,8 - 3 pair 8                      [3,8]
                             :    - integer division (vectorises) [2,1]

Note: 11 bytes (ŒlĠL€⁼2,2ȧ⁸) only validate the input string as being of the correct form - without this code every example case passes except that ab1a is evaluated as if it were abBa, a projective plane.

\$\endgroup\$

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.