Generate a message out of cutout magazine characters (interview question)

views:

117

answers:

+2 Q:

Generate a message out of cutout magazine characters (interview question)

This problem comes out of the dynamic programming chapter in The Algorithm Deisgn Manual by Skiena.

Give an algorithm to determine whether you can generate a given string by pasting cutouts from a magazine. You are given a function that will identify the character and its position on the reverse side of the page for any given character position.

I solved this with with backtracking, but since it's in the dynamic programming chapter I think there must be a recurrence I can't figure out. Can anyone give me a hint?

+1 A:

You can solve it with maximum bipartite matching.

Each character L of the given string forms the left set. (Note, you repeat the characters if the string has repeated characters).

Each pair of characters (R1,R2) of the magazine forms the right set.

L is connected to (r1,r2) iff L=R1 or L=R2.

Find a maximum matching in the resulting graph. If all left vertices are part of the matching, you have the answer. If not, such a string is not possible.

See Maximum Bipartite Matchings for an algorithm.

Not sure if this is optimal though and sorry for not answering exactly as asked.

Moron 2010-08-10 03:19:58

With this approach you can form a message with more characters than the magazine :)

Tom Sirgedas 2010-08-10 03:52:55

@Tom: No, the size of matching is bounded by the number of nodes in the right set (and the left set), which can never exceed the characters in the magazine. Or did I misunderstand you?

Moron 2010-08-10 05:26:24

@Moron: I assumed that a single character one side of the page might overlap multiple characters on the reverse. In an extreme case, you could have 10 characters on each side all overlapping (giving 100 pairs). Maybe that's not allowed?

Tom Sirgedas 2010-08-10 14:58:23

@Tom: According to the question, given a position you get the character and the character on the reverse. Maybe i misread. In any case, instead of pair, you can have a set of characters.

Moron 2010-08-10 15:05:23

@Moron: OK, I think you're right, though I'm still confused by the wording

Tom Sirgedas 2010-08-10 15:51:24

@TOm: I agree, the wording is very weird.

Moron 2010-08-10 16:51:47

@Moron: This is a really nice solution. There must be a dynamic programming approach too since it was in that chapter. @Tom: the way I understand it is that one character maps to one character on the reverse side, not multiple characters.

Rich 2010-08-10 17:10:52

I see, there's a linear programming algorithm for maximal flow. That's a complicated interview question.

Rich 2010-08-11 02:02:05

+1 A:

If you have a recursive backtracking solution, you may be able to apply memoization, which is one way to do dynamic programming.

Tom Sirgedas 2010-08-10 03:33:27

Thanks for the suggestion. I was thinking about this, but my backtracking solution was a depth first search that didn't ever need to recalculate a previously calculated smaller solution. I'm sure I must have formulated it poorly.

Rich 2010-08-10 17:12:46

ansaurus

tags:

views:

answers:

Generate a message out of cutout magazine characters (interview question)

related questions