Show us your stuff!

Crossword (id: challenge-01)

A local newspaper hires you to generate crossword puzzles for their daily paper. They have a list of words for you to turn into a crossword puzzle. The paper varies the size of the crossword from day-to-day, so they require you to fit it within a given set of dimensions.

Words in a crossword are always written from left-to-right or top-to-bottom. Words cannot be placed side-by-side unless the paired letters correctly spell words in the set. Words may only intersect perpendicularly (die: you cannot have a horizontal word that overlaps the end of another horizontal word, or lives entirely within the other word). Each word placed (beyond the first word) must be placed on at least one other existing word so that all the spaces in the completed puzzle are connected.

Input

The input consists of a line with the maximum crossword dimensions (width, then height), followed by one line for each of the words that must exist in the crossword. The words will be input as mixed case.

Example 1

10 10
Boats
Toad

Example 2

3 3
Age
Ago
Beg
Cab
Cad
Dog

Example 3

10 10
Bleh
Oops

Output

Your program must output the answer to crossword with the smallest area. The output characters must be written in uppercase.

If two or more crosswords have the same area, output the one that sorts lexicographically greatest when concatenating all of the crossword rows together (including trailing spaces required to pad out to the square).

If the crossword is impossible to solve within the given bounds, or the words cannot be fit together, print the string IMPOSSIBLE.

Example 1

BOATS
O
A
D

Example 2

CAD
AGO
BEG

Example 3

IMPOSSIBLE

Switch Logic (id: challenge-02)

One of the server rooms in your employer's building has a set of switches that, when set to certain positions, turn on the lights in the server room. The logic behind the switches has been lost to time, but your employer had an intern dutifully brute force all of the switch positions that cause the lights to turn on.

Your employer now wants you to write a description of how to turn the lights on.

Notes from the original designer of the building indicate that the logic behind the lights consists of some very simple rules for each switch:

  • Some switches are not hooked up
  • Some switches must always be up
  • Some switches must always be down
  • Some switches are part of a group, where one or more of them must be on
  • Some switches are linked to another switch, such that either:
    • this switch must always be in the same position as the other switch, OR
    • this switch must always be in the opposite position of the other switch

Input

The input to your program will be a complete set of switch positions the turn on the lights (switch 1 is the left-most character), where U means that the switch is up and D means that the switch is down:

Example

DUUDDDDUU
DUUDDUDDU
DUUDDUDUU
DUUUUDDUU
DUUUUUDDU
DUUUUUDUU
UDDDDDDUU
UDDDDUDDU
UDDDDUDUU
UDDUUDDUU
UDDUUUDDU
UDDUUUDUU

Output

Your program's output should list logic behind the switches in plain English. List the switches from left to right and whether the switch must be:

  • In any position (print "any position")
  • Always up (print "up")
  • Always down (print "down")
  • Same as one of the other switches to its left (print "same as n")
  • Part of a group (print "At least one of n1, n2[, ... nN])
  • Opposite of one of the switches to its left (print "opposite of n")

To simplify the instructions, only print a switch's relationship with switches to its left. If a switch depends on more than one switch to its left, print the relationship with the switch that is closest. For those switches part of a group, print the description of the group for the first switch in the group.

Example

1 any position
2 opposite of 1
3 same as 2
4 any position
5 same as 4
At least of of 6, 8
7 down
9 up