Challenge #75: Scrabble Word Finder

[JoeM]

Welcome to Week 75!! We have a few people vying for a new shiny badge!!

This challenge is based off the word game Scrabble. In the game of Scrabble, you are given 7 tiles with a letter printed on them. Additionally, a point value is assigned to the letters. The player tries to find the word that is worth the most points. For example, a player may draw the following 7 tiles: G (2 points), A (1 point), R (1 point), E (1 point), T (1 point), V (4 point). It is important to note that the longest word assembled is not always the best word – for example the word of ‘parget’ is worth less then ‘paver’.

The challenge this week is to find the best word (from a provided text file) that can be assembled from 7 provided letters. Use the workflow and the files attached to get to your solution.

Advanced Users and Challenge 75 Racers: The game of Scrabble also provides a max of 2 blank tiles. These tiles are a wildcard and can be used as any letter, but are worth 0 points. While it is unlikely that a single player has both blanks at a single time, we must be prepared for when it takes place. Try to find the highest scoring word using the blank tiles – but be sure that they are not scored!

[NicoleJohnson]

Question... you say to make a word from the 7 tiles provided... but there are 8 tiles in the workflow? :)

[JoeM]

Good call @NicoleJohnson. I just updated the file!

[patrick_digan]

Solution attached for the no wildcards case. I'm trying to think about how to attack the wildcards...

Spoiler

I used a very brute force method. I used the append tools get all the permutations. I also tried out a new tool I've built to reference different columns dynamically at the end. This made it slightly easier at the end with less transposing and crosstabbing.

[patrick_digan]

Solution attached for the wildcards case.

Spoiler

I just tweaked it a little so that if you have a blank or two (which you would just only enter the 5 or 6 tiles you had into the app), it just adds in all 26 letters. The app really slows down if you have 2 blanks (over 4 minutes on my machine) since it's going through so many appends with a lot of possible letters for those blanks.

2 wildcards case (v,q,t,r,blank,blank,p)


1 wildcard case (b,a,o,blank,t,q,u):


no wildcards case (e,d,g,c,r,a,l)

[SeanAdams]

Very very messy solution, but it is working :-)

Spoiler

Step 1: Create static combinations
The core of the approach is to build a combination set up-front which just uses numbers as indices so that it will work with any tile-set.
The combination set looks like:
- 12
- 13
- 14 ...
- 23
- 24
These sets are always created so that numbers earlier in the list are always smaller than numbers later in the list (this is important later)



Step 2: Change the dictionary words
Take all the dictionary words provided, and create a second version of the dictionary word with all the letters in sorted order (makes it easier to find matches).   So - cat becomes atc


Step 3: Brute-force combination of tiles
Combine the tiles in every combination that we've pre-computed, bringing in the score from the inputs



The fact that the generated words, and the dictionary words are all re-sorted in letter order makes the search really quick - it's just a join

Blank Tiles:
For one blank tile -very similar approach - just had a slightly more complex combination generator, which took the original one, and wherever tile 7 was used, it exploded out 26 letter combinations.
For 2 blank tiles - took the output from the 1-blank tile combinator and exploded out everywhere that tile 6 was used.


Would I do it the same next-time?
Same method, less messy.   I'm pretty sure that with time it would be possible to figure out a far more elegant combination generator that has parameters for how many blanks etc.  

For now, it's late and I'm going to get some sleep!

[LordNeilLord]

My word that was difficult @JoeM!

I went for the one macro to rule them all approach, it is a horrible workflow and I'm not sure I could explain it back to anyone...just take my word for it...it works!

Spoiler

Part 1Part 2Results

@SeanAdams I tip my hat to you sir, congratulations on being the first to get the 75 badge! Well played

*anxiously awaits 75 badge*

[NicoleJohnson]

Darn it, @SeanAdams!! :)

But I made it. With a detour to fix my payroll system and to pick up my car from the shop whilst trying to solve it. So, you know. Monday as usual.

Thanks for the killer challenge, @JoeM! Looking forward to see where the climb takes us for Challenge #100 :)

Spoiler

1. I probably made this extra hard on myself by trying to convert that random text file containing letter points into the workflow without just manually inputting them. So that was step 1. And then I had leave to go fix our payroll system.

2. I initially solved for no blanks, and then 1 blank... but figured that I should be able to get to all 3 answers if I did the two blanks the right way, so that's the solution I ended up posting. Dealt with the blanks by appending the existing hand to each of the letters from step 1, using a formula (ReplaceFirst) to replace the first "blank" with the letter it was appended to, and then doing those two steps again for the second blank. And then I had to leave for 30 minutes for an "emergency" team meeting. Suspect @SeanAdams of sabatoge

3. Tokenize Scrabble words & count number of each letter in word. At this point I discovered it was going to take 5+ minutes to run anything beyond this, and I am a frequest-workflow-tester, so that simply wouldn't do... so I added a random sample tool to just give me 1% of the possible words while I was building it out. I also filtered out anything over 7 letters to shorten the list a bit.

4. Joined by letter from Hand source & Word source. Filtered out anything where the count of that letter in the hand was less than the count of that letter in the word. Then I summarized that list (group by ID's, concatenate the letters with no delimiter) to a list of the words that had also been sorted so the letters in the word were sorted alphabetically. This gave me the word Record ID's that had matches based on hand Record ID. I then used Find & Replace based on word Record ID to determine the original word. I then had to leave for 45 minutes to go pick up my car from the shop. #curses

5. To finish it up, I took the matching words, tokenized them by letter, matched the letters to the values in the letter points value datasource, then summarized them, sorted by descending total points, and selected the top 5.

6. Re-read instructions and realize that the blanks don't count for points. Insert new logic at end to only count non-blank letters that were in the original hand. #morecurses

7. Run workflow. Wait 2:29. Marvel that despite an unpleasant number of joins & appends, it was still sub-3 minutes. Ta da!! :)

[Ned]

Fun problem.  I have a solution that runs sub second even with the blanks if you allow me to pre-compute a few tables.  Of course it is taking advantage of awful stuff like regex.  One example is:

regex_replace(hand, "(.)(.)(.)(.)(.)(.)(.)", regex_replace(p, "(.)", "$$$1"))

another:

regex_replace([Field_1], "(?<=^.{" + tostring(tonumber(left(p,1))-1) + "}).", ".")

I'll post in a few days if no one else comes up with a super fast solution...

[MarqueeCrew]

Congrats @SeanAdams on your new shiny badge!

Climbing to the summit alone however could lead to a dangerous selfie situation.  Hopefully your team will catch you soon.

Cheers,

Mark