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

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.