Snack Break Problem #23

Last Challenge

The last snack break asked you to create an algorithm for solving Tic-Tac-Toe boards and puzzles. The advanced challenge was to create a perfect algorithm that could never lose a game of Tic-Tac-Toe.

Solutions:

OldPalHappy - Solution

Kingdom5 - Solution

Advanced Solutions:

Spongocardo - Solution

superalp1111 - Solution

This week's challenge

This week's challenge was suggested by BlueTaslem. There is a problem in computer science that asks if strings from one table can be concatenated together to match the strings of another table. This problem is called the Post correspondence problem.

If you're confused on the problem like I was, this video explains the problem very well.

You're required to make a function that returns the string that can be made from both tables. Example:

local function PostCorrespondence(table1, table2)
    -- You could return aaaab, because using the block aaaa & aa from the first index of the tables, and then using the second index of both tables, you get aaaa..b for the first table, and aa..aab for the second, which makes a matching string.
end

PostCorrespondence({"aaaa", "b"}, {"aa", "aab"})

This problem is an undecidable decision problem, but extra points to you if you wish to return false to some solutions that you know can't be combined to make a matching string.

Submission

In order to submit your attempt, simply message me, OldPalHappy, here with the model or place, open sourced. If you would like, you can also message me on discord or via the forum messaging system with a link to your code.