Login

***goldenglutes*** · 04-05-2019, 10:16 PM

NOTE: For people looking to just find out the answer to the #Scrambled-Izzy puzzle, you won't find an easy answer here (Izzy only let me post this if I didn't explicitly include the answers). However, you can try running the code yourself and getting the answers.

Python Version: 3.6
Word Count: 1226 + coding effort

Hey everyone! I thought I'd cash in on some free SHL money by showing how I solved the #Scrambled-Izzy puzzle with Python. This isn't really going to be a coding tutorial or anything -- I'm just going to assume that whoever wants to read this already has at least a beginner background in programming. I'm going to outline two methods that could be used: one more naive and inefficient, the other uglier but more efficient. I'm going to be using a bit of big O notation in this post, so if you're not sure what that is and would like to read up on it, this is an excellent post that outlines it in plain-ish english (though I think this article should still be understandable without that knowledge -- just know that O is a theoretical measure of how efficient an algorithm is).

Anywho, moving on. First, I needed to compile a list of all players in the finals. Here's what I grabbed from the playoffs index:

Code:
players = [

   "Dermot Lavelle",

   "Oliver Konig",

   "Brock Becker",

   "Hippo Passamus",

   "Conor McGregor",

   "Viktor Marius",

   "Kevin Hamilton",

   "TJ Bayley",

   "Finn McCool",

   "Leafer Rielly",

   "Alexander Selich",

   "Konstantin Kostoyevskiy",

   "Tatu Makela",

   "Alexis Metzler",

   "GOD McZehrl",

   "Charles Walker",

   "Quick Mafs",

   "Cassius Darrow",

   "Samuel Jalopski",

   "Cedric Robinson",

   "Kyle Davis",

   "DeMaricus Smyth",

   "Alex Andani",

   "Soren Kierkegaard",

   "Joe Kurczewski",

   "Oisin Fletcher",

   "Nicholas Williams",

   "Krists Zommers",

   "Chuck Bernstein",

   "Roman Augustus",

   "Piotr Czerkawski",

   "Xavier Paquette",

   "Vasily Horvat",

   "Clint Eastwood",

   "Richard Physt",

   "Karl Hefeweizen",

   "Adam Kaiser",

   "Sean Stevenson Jr",

   "Patrick Brumm Jr",

   "Aleister Cain",

   "Mike Hunt",

   "Nathan Cosco"

]

Next, we'll need to put the scrambled names in another list:

Code:
scrambled = ["pusesmakajolil", "noewtdicatslo", "lkgvironeoi", "ihoswlilmlncsaai"]

Now, here's the first method that I talked about, which tackles the problem in a somewhat naive way:

Code:
def method1(players, scrambled):

   outDict = {}

   for s in scrambled:

       scrambledAlphabet = [0 for i in range(26)]

       for c in s:

           number = ord(c) - 97

           scrambledAlphabet[number] += 1

       for player in players:

           playerAlphabet = [0 for i in range(26)]

           playerCleaned = player.lower().replace(" ", "")

           for c in playerCleaned:

               number = ord(c) - 97

               playerAlphabet[number] += 1

           if scrambledAlphabet == playerAlphabet:

               outDict[s] = player

               break

   assert(len(outDict) == len(scrambled))

   return outDict

I'll try to explain the code in plain english. This function loops through the list of scrambled names, and for each scrambled name, it tries to match it up with a player in the list of players. If we try to frame this matching process as a programming problem, we can describe it as a permutations problem, or: "Given a word, determine whether another word is a permutation of the given word". My solution to this matching process relies on the scrambled name and the matching player name having the same number of each letter in the alphabet. In other words, "abcde" and "edabc" will both have the same number of a's, b's, c's, etc., and that's how we can determine whether two words are scrambled versions of each other. There are other ways to handle the matching, but I believe this is a best trade-off between efficiency and intuitiveness. Now, as soon as we've found a match for the scrambled name, we add the scrambled/player combo to the outDict, which is the dict (or Hashtable for those who don't Python) that eventually gets returned as the solution. We then move onto the next scrambled name and loop through the players again until we find a match, until eventually we find a match for each scrambled name.

Now, this code has a computational complexity of O(M*N), where M is the number of scrambled names, and N is the number of players. This is because we loop through the number of scrambled names, and for each name, we loop through every player.

Now, for the uglier but more efficient method:

Code:
def method2(players, scrambled):

   outDict = {}

   scrambledAlphabets = {}

   for s in scrambled:

       alphabet = [0 for i in range(26)]

       for c in s:

           number = ord(c) - 97

           alphabet[number] += 1

       scrambledAlphabets["".join(str(i) for i in alphabet)] = s

   for player in players:

       playerCleaned = player.lower().replace(" ", "")

       alphabet = [0 for i in range(26)]

       for c in playerCleaned:

           number = ord(c) - 97

           alphabet[number] += 1

       alphabetAsString = "".join(str(i) for i in alphabet)

       if alphabetAsString in scrambledAlphabets:

           outDict[scrambledAlphabets[alphabetAsString]] = player

           if len(outDict) == len(scrambled):

               break

   assert(len(outDict) == len(scrambled))

   return outDict

The key difference between these two methods is as follows:

While the first method iterates through all scrambled names, and for each scrambled name, it iterates through all player names, it has to do (in the worst case) 4 * 40-ish computations.
The second method iterates through the scrambled names, then AFTER it finishes that, it then iterates through all player names just once. This means it only has to do (in the worst case) 4 + 40-ish computations.
The second method uses a dict (or Hashtable) to store the "alphabet encodings" (or the number of each letter in the word) of the scrambled names, which can be accessed and used for the matching algorithm in O(1) time, or constant time.

To break down the second method, I won't go too much into the nitty gritty of everything, since I do a bit of black magic fuckery like converting lists of integers into strings. First, we iterate through all of the scrambled names, and enter their "alphabet encoding" into a scrambledAlphabets dict. Next, we iterate through the normal names, and get their "alphabet encoding". For each name, we check to see if this alphabet encoding exists in the scrambledAlphabets dict, and if so, we've got a match! We add that to the outDict and keep on chugging until we've found all 4 matches. Overall, because we iterate through the scrambled names and then we iterate through the players, our method has a computational complexity of O(M+N), where M is the number of scrambled names and N is the number of players.

Now, at the end of all of this, you might ask how much better method 2 is over method 1. Is it worth writing messier and harder to understand code just for the performance benefits? I timed the running of both methods (using time.time()), and here were the results:

Code:
Method 1 Time Taken: 0.0009999275207519531s

Method 2 Time Taken: 0.0s

So, while my timer seems to think method 2 is infinitely faster than method 1, at the end of the day it's only an improvement of < 0.001 seconds. Now, if our problem had many many more scrambled names and players (think in the millions or billions), method 1 may take significantly longer than method 2. However, knowing we only have a few names and players, the complexity of O(M*N) is generally quite acceptable and fast, and for the trade-off of much tidier code, I think method 1 is preferable in this situation.

Thanks for listening to my code breakdown for SHL moneys. I'm happy to answer any questions you may have, as well as discuss better ways to solving the problem!

On an unrelated note, Dom Montgomery is very cool and really, really, really ridiculously good looking.

Signatures by Vulfzilla, Jepox, Jess, rum_ham, Ragnar, and myself
[Image: 9vAsr7c.png]

***luke*** · 04-05-2019, 10:17 PM

Needs more comments

***goldenglutes*** · 04-05-2019, 10:20 PM

04-05-2019, 10:17 PMluketd Wrote: Needs more comments

hush I wrote the code in the middle of the night just because I was too lazy to manually solve the problem

Signatures by Vulfzilla, Jepox, Jess, rum_ham, Ragnar, and myself
[Image: 9vAsr7c.png]

bilbo · 04-05-2019, 10:20 PM

So even when I go back and read this seriously later, I doubt I'll understand it all the way, but for some reason this article is the BEST one you've ever written. Keep 'em comin.

*performs matt's ritual*

But actually this is v cool. Good job.

***luke*** · 04-05-2019, 10:21 PM

04-05-2019, 10:20 PMgoldenglutes Wrote:
04-05-2019, 10:17 PMluketd Wrote: Needs more comments

hush I wrote the code in the middle of the night just because I was too lazy to manually solve the problem

Just do what I do and get it off of discord like the rest of us plebs

***goldenglutes*** · 04-05-2019, 10:22 PM

04-05-2019, 10:21 PMluketd Wrote:
04-05-2019, 10:20 PMgoldenglutes Wrote: hush I wrote the code in the middle of the night just because I was too lazy to manually solve the problem

Just do what I do and get it off of discord like the rest of us plebs

no one posted the answers in any of the discords I'm in :feelsbadman:

Signatures by Vulfzilla, Jepox, Jess, rum_ham, Ragnar, and myself
[Image: 9vAsr7c.png]

***luke*** · 04-05-2019, 10:30 PM

04-05-2019, 10:22 PMgoldenglutes Wrote:
04-05-2019, 10:21 PMluketd Wrote: Just do what I do and get it off of discord like the rest of us plebs

no one posted the answers in any of the discords I'm in :feelsbadman:

haha, youre code works well.

5ympathies · 04-05-2019, 11:29 PM

graders you need to pay him extra, the work put into this was crazy

Thanks to JSS for the signature

*Scrufdaddy* · 04-06-2019, 01:19 AM

did you try searching stack overflow first for the code to solve this?

***goldenglutes*** · 04-06-2019, 02:47 AM

04-06-2019, 01:19 AMScrufdaddy Wrote: did you try searching stack overflow first for the code to solve this?

why steal when you can make your own?

Signatures by Vulfzilla, Jepox, Jess, rum_ham, Ragnar, and myself
[Image: 9vAsr7c.png]

5ympathies · 04-06-2019, 03:27 AM

04-06-2019, 02:47 AMgoldenglutes Wrote:
04-06-2019, 01:19 AMScrufdaddy Wrote: did you try searching stack overflow first for the code to solve this?

why steal when you can make your own?

if you're not cheating, you're not trying hard enough

Thanks to JSS for the signature

DeletedAtUserRequest · 04-06-2019, 08:29 AM

I've sent this post over to little Tammy (who is currently in rehab).. she would be happy to know that her task replacement has sparked great coding through its virtual endeavours...

Ilike

|

|

|

|

SlashACM · 04-06-2019, 09:32 AM

You know this is called the *casual member special* right??

Navigation

Extra Menu

About us