As you most probably now, there are 2339 solutions to pentomino puzzle in a 6x10 grid. There are different labeling schemes for the 12 pentominoes, two of them are shown on the image below:

enter image description here

Image credit: Wikipedia

For the purposes of the current task we will say that a normalized pentomino solution is a solution that uses the second labeling scheme (Conway’s).

Example:

O O O O O S S S Z Z
P P R R S S W W Z V
P P P R R W W Z Z V
U U X R T W Y V V V
U X X X T Y Y Y Y Q
U U X T T T Q Q Q Q

The piece with 5 squares in a row is denoted with letters O, according to the scheme. The same is true for all pieces.

Task:

Given a solution to the 6x10 pentomino in which the pieces are labeled with a random sheme, normalize it so that all pieces are labeled in Conway’s labeling scheme. You need to recognize the pieces and mark each square of a particular piece with the symbol of the piece.

Input:

The solution to be normalized, in any format that is convenient for you, for example:

  • A multiline string

  • A list of strings

  • A list of lists of characters

and so on

Output:

The same solution (all the pieces positions and orientation preserved), but each piece labeled according to Conway’s labeling scheme. Note: The output MUST be PRINTED as a 6x10 grid of characters. Leading and trailing newlines and spaces are permitted. You can also print a space between the characters (but not empty lines), as in the example above.

Test cases:

1. Input:

6623338888
6222344478
66A234BB70
1AAA94B770
11A99BB700
1199555550

Output:

UURTTTQQQQ
URRRTVVVSQ
UUXRTVZZSY
PXXXWVZSSY
PPXWWZZSYY
PPWWOOOOOY

2. Input:

45ookkkk00
455ooogk00
4a55gggdd0
4aaa3gnnd.
4am333ndd.
mmmm3nn...

Output:

OWSSQQQQPP
OWWSSSRQPP
OTWWRRRUUP
OTTTXRZZUV
OTYXXXZUUV
YYYYXZZVVV

Winning criteria:

The shortest solution in bytes in each language wins. Don’t be discouraged by the golfing languages. Explanations of the algorithms and implementations are welcome.

APL (Dyalog Classic), 54 53 50 bytes

⍴⍴{'OXRYTPZQUWSV'[⌊5÷⍨⍋⍋,{×/+⌿↑|(⊢-+/÷≢)⍸⍵}¨⍵=⊂⍵]}

Try it online!

Compute an invariant for each pentomino in the input: measure (∆x,∆y) from each of its squares to its centre of gravity, take abs(∆x) and abs(∆y), sum the x components and separately the y components, and multiply the two sums. This gives 12 distinct results. Then, find the index of each pentomino's invariant in the sorted collection of all invariants. Replace 0 with 'O', 1 with X, 2 with R, etc.

  • Thank you for the fast answer and the explanation, +1 from me! I meant the solution to be explicitly printed as a 6x10 grid. I changed the descrition, please update your solution - I'm sorry for the inconvenience. – Galen Ivanov Oct 12 at 10:26
  • @GalenIvanov but... it is a grid. My tests output "ok" instead of printing the result - maybe that's too confusing? – ngn Oct 12 at 10:29
  • Yes, I was confused by the tests. – Galen Ivanov Oct 12 at 10:36
  • 3
    now they print the result before validating it – ngn Oct 12 at 10:50

Jelly, 37 bytes

ŒĠZÆmạƊ€ḅı§AỤỤị“æṂ⁾+’Œ?¤+78Ọ,@FQṢƊyⱮY

A full program taking a list of strings (because we must print - otherwise remove the trailing Y and you have a monad taking a list of lists of numbers or characters which returns a list of lists of characters).

Try it online!

How?

I believe this works using the same categorisation of pentominos as ngn's APL solution, albeit in a slightly different way (I also don't know APL so I'm not that sure how similar the method is beyond the categorisation).

(Note that “æṂ⁾+’Œ?¤+78Ọ is only a one-byte save over “XRPTZWUYSVQO”!)

ŒĠZÆmạƊ€ḅı§AỤỤị“æṂ⁾+’Œ?¤+78Ọ,@FQṢƊyⱮY - Main Link: list of lists of characters L
ŒĠ                                    - group multidimensional indices by value
      Ɗ€                              - last three links as a monad for €ach i.e. f(x):
  Z                                   -   transpose x
   Æm                                 -   mean (vectorises) (i.e. the average of the coordinates)
     ạ                                -   absolute difference with x (vectorises) (i.e. [dx, dy])
         ı                            - square root of -1 (i)
        ḅ                             - convert from base (vectorises) (i.e a list of (i*dx+dy)s)
          §                           - sum each
           A                          - absolute value (i.e. norm of the complex number)
            Ụ                         - grade up (sort indices by value)
             Ụ                        - grade up (...getting the order from the result of A back,
                                      -              but now with one through to 12)
                       ¤              - nilad followed by links as a nilad:
               “æṂ⁾+’                 -   base 250 literal = 370660794
                     Œ?               -   permutation@lex-index = [10,4,2,6,12,9,7,11,5,8,3,1]
              ị                       - index into
                        +78           - add seventy-eight
                           Ọ          - cast to characters (character(1+78)='O', etc...)
                                 Ɗ    - last three links as a monad (i.e. f(L)):
                              F       -   flatten
                               Q      -   de-duplicate
                                Ṣ     -    sort
                            ,@        - pair (with sw@pped @rguments) (giving a list of 2 lists)
                                   Ɱ  - Ɱap across L with:
                                  y   -   translate i.e. swap the letters as per the the pair)
                                    Y - join with new lines
                                      - implicit print

Wolfram Language (Mathematica), 103 bytes

""<>Riffle[(t=#)/.Thread[SortBy[Union@@t,Tr@Kurtosis@Position[t,#]&]->Characters@"UPSWZVRTQXYO"],"\n"]&

Takes input as a list of lists of characters.

Try it online!

The main idea here is that for each character in the input, we find the coordinates where it occurs, take the kurtosis and sum its coordinates. This gives us an invariant for each piece.

(The kurtosis is some mostly-irrelevant operator from statistics - the key is that it's invariant under translation, while reflection and rotation might switch the order of coordinates at most. We sum the coordinates, so the invariant never changes.)

Anyway, apart from the weird invariant, this solution is similar to the others: we sort the characters and the pieces by each invariant, then replace each character by the corresponding character of "UPSWZVRTQXYO": the pieces, sorted by kurtosis sum.

Finally, ""<>Riffle[...,"\n"] is the print-as-a-grid code.

  • +1 for knowing an operation that I never even heard of and putting it to good use – Black Owl Kai Oct 24 at 19:37
  • My first attempt at a solution had Sort@Variance in place of Tr@Kurtosis, and probably more people have heard of variance. But Tr@Variance doesn't work because several pentominoes (such as P and X) have the same sum of x-variance and y-variance. So I went looking through Mathematica's documentation for something fancier. – Misha Lavrov Oct 24 at 21:24

Python 2, 191 bytes

def y(o):print"".join(['XPRTWZUYSVQO\n'[[w for v,w in sorted([sum(abs(u-sum(t)/5)for t in[[complex(r%11,r/11)for r,q in enumerate(o)if q==p]]for u in t),p]for p in o)].index(x)/5]for x in o])

Try it online!

Takes a multi-line string with a trailing newline and does six nested list comprehensions.

Ungolfed Version

def pentomino_normalizer(input_string):
    # input_string is a multi-line string with a trailing newline

    results = []  # For saving the results of the for loop
    for current_char in input_string:
        # current_char = p in the golfed version

        # The python data type complex stores a real and a imaginary value and
        # is used for storing the x and y coordinates.
        # In the end, the positions list contains a complex number for every
        # occurence of current_char in the string
        # positions_list = t in the golfed version
        positions_list = [complex(i % 11, i / 11) for i, c
                          in enumerate(input_string) if c == current_char]
        # average_pos is the midpoint of all occurences of current_char, 
        # to get rid of translations
        average_pos = sum(positions_list)/5
        # Calculates a value for each tile that is invariant under 
        # translations and rotations,
        # simply the sum of all the distances between the midpoint
        # and the positions
        invariant = sum(abs(pos - average_pos) for pos in positions_list)

        # Saves the invariant value to a list
        results.append(invariant, current_char)

    # This new list contains the characters occuring in the string, sorted
    # by the invariant value. Because this was done with each char in the 
    # input string, this lists contains every value five times and also 
    # contains six newlines
    # at the end of the list
    sorted_results = [w for v, w in sorted(results)]

    # This code snippet maps each char from the input string to its according
    # output and prints to stdout
    chars = ['XPRTWZUYSVQO\n'[sorted_results.index(c)/5] for c in input_string]
    print "".join(chars)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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