← Blog Home

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.

Commentary

Leave a Comment

AlphaGamer150 says: April 18, 2017
Please try setting a chalenge, THAT IS ACTUALLY POSSIBLE!
SuperLol211 says: April 19, 2017
Alpha, it is possible, but it's just quite challenging, hence the name challenge.
auwv says: April 28, 2017
I did it in under 40 minutes.
MICHEAL1988351 says: July 5, 2017
local function concat_the_tables(...) local arg = {...}; local s = ""; for i = 1, #arg do s = (s..table.concat(arg[i])); end return s; end If you are trying to do something else that is not working then it is probably because tables are not immutable in Lua. (i.e. you can create pointers to tables in Lua)
MICHEAL1988351 says: July 6, 2017
Oops, please disregard my previous comment; I did not fully understand what you were talking about and assumed you mean concatenation. Either way a simple solution would be to store every single combination for table1[1], table2[1], ... and so on, and do the same for table2[1], table2[2], ... and then compare every single concatenation to see if the resulting string is equal.
Ad