PianoWow

So last night my computer completely crashed. Nothing was responding, even after several minutes of waiting. I performed a hard reboot. It had to be restarted several times. When it finally came up, I wasn’t worried. But after a few minutes it froze yet again, and I began to worry. I rebooted it and went to bed.

I’m writing this from my iPhone. My PC I built two years ago has died. I might be able to fix it by reinstalling windows, but if I have to start over, I would rather start with a new Mac.

Really, I’m sad about this and happy at the same time. Sad because I’ll be leaving the familiar world of windows. Happy because I’ve been wanting a mac for a while. Also sad because I’ll have to use credit. I haven’t used a credit card to buy anything in like a year.

It started with my desire to build applications for my iPhone. I have ideas for apps that don’t exist in the app store. Even if they don’t sell, I’d want them on my own phone. But, it seems the only way to build iPhone apps is on a computer with OS X Leopard on it. My attempts at installing OS X on my current hardware have failed. But I think I’d rather have a legitimate Mac anyway.

I’ll be going today to purchase one.

Problem 96 asks you to write an algorithm to solve 50 sudoku puzzles.  I decided early on to make the problem slightly more difficult for myself by not using any backtracking (guess and check) in my algorithm.  Forcing myself to write logical algorithms only made the solution both more difficult and more efficient.  I probably spent 16 hours total writing and rewriting my solution, over a period of nearly two months.  The first version of my problem didn’t save clues, only numbers that had been filled in.  I only got the first 40 solved without saving the clues.

When discussing my solution to problem 96, I’ll be using terms from sudocue.net’s solving guide.  A grid is made up of rows, columns, boxes (collectively: houses).  A puzzle starts with givens.  Possible numbers for a square are called candidates.

The first three methods I wrote were to find all candidates, fill in naked singles, and fill in hidden singles.  The method to find all candidates eliminates the givens and other filled-in squares from the local box, the row and the column (peers).  The method to fill in naked singles fills in the square if there is only one candidate in that square.  The method to fill in hidden singles examines each house and fills a number in if it can only go in one place in that house, using squeezing and cross-hatching.

These three methods alone solved the easy/medium problems, 40 to be exact.  But still 10 remained.  I consulted with my mom heavily at this point, needing to understand what types of logic could be used to fill in other numbers in the un-solved puzzles.  With her help I wrote my fourth algorihm, which looks for naked pairs.  If two squares in a house have the same two candidates, no other square in that house can use those candidates, which can be eliminated.  This helped me solve 4 more, so I was up to 44.

After further consultation, I wrote my fifth method.  This method looks for locked candidates in a box, and eliminates that candidate from other squares in the same row or column.  I had solved two more with this method.  46!  The sixth method looks for something not completely described on the sudocue guide page.  It looks for a third type of locked candidate, where two adjacent boxes have a candidate confined to the same two lines.  Because that candidate is locked to those two lines, the third box can have the candidate only in the third line.  I was now up to 48 solved, leaving 2 difficult puzzles left.

At this point, Mom was getting frustrated and so was I.  I decided to do some Internet research to help out.  I found a technique called the x-wing, and implemented it.  It was enough to solve all 50 puzzles.  So I had solved the Project Euler problem.

While doing my research I came across a set of puzzles that have been proven to have only one solution each, but only have 17 givens.  I took ten of those and gave them to my program… it solved all but one in less than a few seconds!  I was very proud of this.  17 givens is considered the minimum amount of clues, i.e., the most difficult of puzzles.  Perhaps soon, I’ll figure out how to solve the one it did not complete.

If anyone is interested in my code, contact me with the answer to problem 96 (the sum of the first three numbers of each grid), and I’ll send my code.  Do not post the answer as a comment.  Email me, using the contact info on the left sidebar.

I chat on ICQ with a friend of mine in Ukraine.  She’s from east Ukraine, so she speaks Russian and types in Russian.  She also chats in English, often to two people in two different languages at the same time.  Occasionally, she’ll forget to change the input language, and will type in English using Russian characters.  Basically, what happens is the standard English alphabet:

abcdefghijklmnopqrstuvwxyz

becomes

фисвуапршолдьтщзйкыегмцчня

So, she’ll type something like, “ш туув ещ пщ пуе куфвн” which looks like absolute gibberish if you speak Russian.  But she really means “i need to go get ready”.

Now, if she’s on the ball, she’ll just change the input language and re-type it.  No problem there.  But if she’s busy, or in the “i need to go” message above, she’ll sign off or quickly divert her attention before noticing the language was wrong.  Even worse, by the time she notices, she forgot what she meant to say, and the message is lost.

Text processing is at least 50% of a programmer’s life, so I knew that it would be very easy to design a script that “translates” her gibberish into what she really meant.  I simply have never gotten around to it, until today, that is.

I decided to write a short python script that would translate the standard russian keyboard layout to the english one. I haven’t included very many special characters, only question mark, period, and comma.

It’s written in Python 3.0, and requires installation of Python 3.0 to run.

english = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz?.,'
russian = [1060, 1048, 1057, 1042, 1059, 1040, 1055, 1056, 1064, 1054,
           1051, 1044, 1068, 1058, 1065, 1047, 1049, 1050, 1067, 1045,
           1043, 1052, 1062, 1063, 1053, 1071, 1092, 1080, 1089, 1074,
           1091, 1072, 1087, 1088, 1096, 1086, 1083, 1076, 1100, 1090,
           1097, 1079, 1081, 1082, 1099, 1077, 1075, 1084, 1094, 1095,
           1085, 1103, 46,   1102, 1073]
print ('Copy the Russian text and press enter.  Enter alone will exit.')
s = input()
while s != '':
    for i,r in enumerate(russian):
        s = s.replace(chr(r),english[i])
    print (s)
    s = input()

I asked her to purposefully type all the English letters using Russian input so I would know where everything was on the Russian keyboard.  Then I found out the ord() values of each of the Russian characters and stored them in a list.  Finally I used chr() to replace these values in the input text with the appropriate English letters.

Here’s an example of the script in action:

>>>
Copy the Russian text and press enter.  Enter alone will exit.
ыщ тщц нщг сфт куфв црфе ш ензу шт ьн ыекфтпу дфтпгфпу Ж),
so now you can read what i type in my strange language Ж),
дщд
lol