epsilon_573's blog

Matt Parker's Coding Challenge
By epsilon_573, history, 19 months ago, In English

I recently watched a video by Matt Parker, who you might have seen a lot on the Numberphile Channel.

He shared an interesting problem in the video, which has attracted many coders to come up with faster solutions for the same or you can say speedrun?

He also made another video detailing the problem. Here's the podcast for the same.

For those of you lazy enough to go through the videos, here is the text version.

Problem:
Example:

I would like to see how the CP Community tackles this. As for the accepted wordlist, you can use any famous ones you can find such as this one.

Feel free to discuss approaches, and share your codes/times.

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
19 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Bitmask DP :P

UPD: Wait, do you mean valid english words? We might like some heuristics to get it faster in this case.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is debatable. But for the sake of the problem let's say a word that is defined on the following dictionary.

    → Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

edit: seems like the word list is fixed. so the best solution is to use some heuristics. for example, you know a 5-tuple of word only works if it appears in your precomputed solution list.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    As the heuristics, I believe we could use some pruning, to prevent searching words with impossible substrings such as "ghj" and "zwx".

    → Reply