Part I was relatively easy because there were no "confusing edges" (e.g. edges shared by more than 2 tiles). With the corners identified, I decided to pick one corner and start growing the board from that.
Pick one tile, get the matching tile, then go across and get the next tile and so on. I was trying to keep track of thinks like...
If tile A is not flipped, and the edge at Row_01 is matching tile B, not flipped, at Row_10, then tile B does not need to be rotated.
If tile A is not flipped, and the edge at Row_01 is matching tile B, flipped, at Col_01, then tile B needs to be flipped and rotated 3 times (or -1, but I sticked to +ve).
But I was doing something wrong (don't know what yet) and, although the array with the positions was correct, the orientation wasn't, so it was failing when building the big puzzle.Some colour coded tiles (the sample input)
I eventually decided to stop sinking more time debugging that and chose to use the array with the positions to grow the board once more. This time, starting wtih one corner, then getting the adjacent tile with no prior information, get all the possible rotations and choose the rotation that fits. This makes it rather slow (~ 1min), but still faster than debugging the whole thing.
In order to find the seamonsters...
I took one seamonster (length 20), rotated it and flipped it to all possible orientations, chose one "#" at random and decided that was the "origin" of the seamonster. Then calculated offset in rows/columns for all the remaining parts of the seamonster.
I then evaluated whether each '#' in the map was a potential origin for a seamonster (that is, all the corresponding offseted rows and columns contain a # as well).
The only thing is... there's still something not quite completely working, meaning that it DOES matter which corner you start building from (in other words, I needed to run it a couple of times to make sure that seamonsters were found!