Monday, July 30, 2007

Connection - A Google Suggest Game

A few days ago I was searching for a string method in Google. As soon as I had typed in "string", Google Suggest popped in with the following suggestions:

string cheese
string theory
string bikini

I was amused. Then I thought, what if there were a game where you had to go from cheese, theory, bikini back to "string"? After finding Google's convinient Suggest API, I wrote it in about 25 minutes. The game picks a common word and displays the suggest results - you have to find the connection between them. It's pretty fun. Here are some examples (find the missing word).

1)
***back machine
***ne state university
*** back into love lyrics
*** back into love
***ne rooney
*** back machine
***back
***ne gretzky
***nes world

2)
***s inn
***s of our lives
***s of our lives spoilers
***ton daily news
***tona beach
*** of the dead
***spring
***light savings time
***s inn hotels

3)
***** map
***** of warcraft
***** clock
***** time
***** war 2
***** weather
***** market
***** series of poker
***** bank

4)
**** zones
**** warner cable
**** warner
**** zone
**** magazine
**** out


Python Code:
I have some ideas for improvements, but this is the half-hour version.
You'll need a word list. The nouns in http://en.wikipedia.org/wiki/Most_common_words_in_English worked well.
Enter q to quit, or n for the next word if you give up.
# Works in Python 2.5, needs internet connection
import urllib
import re
import random

g_restr = re.compile('<suggestion data="([^"]+)"/>')
astrWords = 'fact,child,problem,part,hand,case'.split(',')
# Put another word list, separated by commas,into the above string.

def main():
    random.shuffle(astrWords)
    i =0
    while True:
        res = nextword(astrWords[i])
        if res == False: return
        i+=1
    
def nextword(strWord):
    strUrl = 'http://google.com/complete/search?output=toolbar&q=' + strWord
    f = urllib.urlopen(strUrl)
    strXml = f.read()
    f.close()
    
    strBlank = '*' * len(strWord)
    
    for match in g_restr.findall(strXml):
        print match.replace(strWord, strBlank)
    
    while True:
        strGuess = raw_input(':')
        if strGuess.lower() == strWord.lower():
            print 'Win!'
            return True
        if strGuess == 'q':
            print 'Exiting...'
            return False
        elif strGuess == 'n':
            print 'You gave up.'
            return True
main()
Answers to the examples are "way", "day", "world", and "time." Have fun!

Thursday, July 26, 2007

DHTML Pizza, cooked up in 30 Minutes

Here's an amusing piece of dhtml I put together a while ago (March 2006). I was experimenting with setTimeout callbacks.

The code is ugly, but the results are fun.

Pizza

If you run it in IE, you can click and re-form the pizza. It could stand some improvements, but I don't feel like working on it now. Don't take it too seriously.

Wednesday, July 25, 2007

Preview Webpage Links

Both "Open link in new Window" and "Open link in new tab" are very useful. They make my web surfing experience a LIFO stack. Where would I be without Shift-click and control-click?

However, there are other cases when you need other functionality. For example, many FAQ sites consist of several links to other pages. Or, you're lost in an extensive site map. When you don't know which link you want, it's slow to have to repeatedly open/close new tabs or windows, and especially slow to go back and forth between pages.

So, I wrote a javascript tidbit to redirect all links to open the page in one specific window. It's like "Open link in Window x" instead of "Open link in new window." (It changes the target attribute of the a tag).


javascript:var thehtml = document.body.innerHTML;thehtml = thehtml.replace(/href="([^"]+)"/gi,'href="$1" target="mynew"');document.write(thehtml);

Try it by going to a webpage with some links (like Wikipedia), copying the code, pasting it into the URL bar, and pressing Enter. It probably will make the page look ugly, but all the links will open in the same window, without you even having to press control or shift.

Below is a more fancy version of the same idea. It lets you "preview" the next webpage in an iframe, in the same window. Not pretty, but it's handy!


javascript:var thehtml = document.body.innerHTML;thehtml = thehtml.replace(/href="([^"]+)"/gi,'href="#" onclick="javascript:document.getElementById(\'ifff\').src=\'$1\';return false"');thehtml = '<div style="float:right; width:600px; height:600px"><iframe style="float:right" src ="'+window.location.href+'" id="ifff" width="100%" height="100%" ></iframe></div>' + thehtml;document.write(thehtml);

Tuesday, July 24, 2007

BidirectionalDictionary

Common C# problem: you need a two-way dictionary. In many cases you need to set up a 1-1 mapping. Say you have an enumeration where each value has a corresponding string, and you need to be able to go from the enum value to the string, and vice versa. Wouldn't it be nice if this were handled by one object?

So, today I wrote the BidirectionalDictionary. It wraps two dictionaries (yay generics!). It's not that full-featured, but I put it together in 30 minutes, and it's solid code.

I decided to still label a "key" and "value", because in most cases you are still thinking in terms of a Dictionary, just one you can "reverse" back to the key.

Sample Usage

BidirectionalDict<int, string> map = new BidirectionalDict<int, string>
(
 new int[] { 1, 2, 3, 4 },
 new string[] { "a", "b", "c", "d" }
);
// Wasn't that syntax beautiful? (Much better than .Add, .Add ...)

map.Add(5, "e");
Console.WriteLine(map[1]);
Console.WriteLine(map.ValueToKey("d"));

Dictionary<int, string> a = new Dictionary<int, string>();
foreach(int key in map.Keys())
 Console.WriteLine(key);

foreach (KeyValuePair<int, string> pair in map.Pairs())
 Console.WriteLine(pair.Key.ToString() + "," + pair.Value);

Inspired by Python, I also added a TryKeyToValue(key, defaultValue) that lets you specify a default value if the key is not in the dict.

Note that there might be a slight performance benefit because the dictionaries can be initialized with a length.

Code

class BidirectionalDict<typeKey, typeValue>
{
 private Dictionary<typeKey, typeValue> m_dictKeyToValue;
 private Dictionary<typeValue, typeKey> m_dictValueToKey;

 public BidirectionalDict(typeKey[] arKeys, typeValue[] arValues)
 {
  if (arKeys.Length != arValues.Length)
   throw new FormatException();

  int nLength = arKeys.Length;
  m_dictKeyToValue = new Dictionary<typeKey, typeValue>(nLength);
  m_dictValueToKey = new Dictionary<typeValue, typeKey>(nLength);

  for (int i = 0; i < nLength; i++)
  {
   m_dictKeyToValue.Add(arKeys[i], arValues[i]);
   m_dictValueToKey.Add(arValues[i], arKeys[i]);
  }
 }
 public BidirectionalDict(KeyValuePair<typeKey, typeValue>[] pairs)
 {
  int nLength = pairs.Length;
  m_dictKeyToValue = new Dictionary<typeKey, typeValue>(nLength);
  m_dictValueToKey = new Dictionary<typeValue, typeKey>(nLength);
  foreach (KeyValuePair<typeKey, typeValue> pair in pairs)
  {
   m_dictKeyToValue.Add(pair.Key, pair.Value);
   m_dictValueToKey.Add(pair.Value, pair.Key);
  }
 }
 public void Add(typeKey key, typeValue value)
 {
  m_dictKeyToValue.Add(key, value);
  m_dictValueToKey.Add(value, key);
 }

 public typeValue this[typeKey index]
 {
  get {return m_dictKeyToValue[index]; }
 }
 public typeKey ValueToKey(typeValue value)
 {
  return m_dictValueToKey[value];
 }
 public bool ContainsKey(typeKey key)
 {
  return m_dictKeyToValue.ContainsKey(key);
 }
 public bool ContainsValue(typeValue value)
 {
  return m_dictValueToKey.ContainsKey(value);
 }
 public typeValue TryKeyToValue(typeKey key, typeValue defaultValue)
 {
  typeValue result;
  return m_dictKeyToValue.TryGetValue(key, out result) ? result : defaultValue;
 }
 public typeKey TryValueToKey(typeValue value, typeKey defaultKey)
 {
  typeKey result;
  return m_dictValueToKey.TryGetValue(value, out result) ? result : defaultKey;
 }

 public IEnumerable<typeKey> Keys()
 {
  foreach (typeKey key in m_dictKeyToValue.Keys)
   yield return key;
 }
 public IEnumerable<typeValue> Values()
 {
  foreach (typeValue value in m_dictValueToKey.Keys)
   yield return value;
 }
 public IEnumerable<KeyValuePair<typeKey, typeValue>> Pairs()
 {
  foreach (KeyValuePair<typeKey, typeValue> pair in m_dictKeyToValue)
         yield return pair;
 }
}

Got to go! Comments and criticism welcome.

"Big" Recursion

I was thinking about recursion. The classic example of an elegant recursive algorithm is:

def factorial(n):
 if (n<=1):
  return 1
 else:
  return n * factorial(n-1)

This is an example of a function that calls itself, eventually returning the correct answer.

I thought, why stop at the function level? I want to have "bigger recursion" - how about a whole program that calls itself? Of course, this would be really impractical in terms of memory, but it sounded like fun.

The Hack: "Big" recursion

So, during my lunch at work, I put the following together. (C# 2.0)
If you run the program, it will compute a factorial for you... in a non-standard way.

static void Main(string[] args)
{
 if (args.Length == 0)
 {
  Console.WriteLine("Enter number:");
  string strNum = Console.ReadLine();
  int nInput = int.Parse(strNum);

  string strLoc = System.Reflection.Assembly.GetExecutingAssembly().Location;
  int nReturn = int.Parse(ExecuteAndWait(strLoc, (nInput).ToString()));
  Console.WriteLine("The answer is: "+ nReturn);
 }
 else
 {
  int nInput = int.Parse(args[0]);
  Recurse(nInput);
 }
}

private static void Recurse(int nInput)
{
 if (nInput <= 1)
  Console.Write("1");
 else
 {
  string strLoc = System.Reflection.Assembly.GetExecutingAssembly().Location;
  int nReturn = int.Parse(ExecuteAndWait(strLoc, (nInput - 1).ToString()));
  Console.Write(nInput * nReturn);
 }
}
By renaming variables and methods, this code could be obfuscated pretty nicely.
The ExecuteAndWait method runs an executable and redirects the stdout to a string. See http://forums.hostrocket.com/archive/index.php/t-15099.html.

Although this was fun, it wasn't extreme enough. I wanted something even bigger, more impractical, and more hacky. So, I invented "bigger" recursion. Have fun understanding what this next one does.

"Bigger" Recursion

(Warning: the following code will compile but is not guaranteed to work on your machine. It's extremely fragile, for reasons that should be clear. I used Visual Studio 2005, c# console app.)
Hint 1: The byte 0xE2 is not commonly found in C# executables.
Hint 2: If you change any line of code, it probably won't work.
Hint 3: this is my directory listing after I run the program and find the factorial of 5:
Bigger2.exe
Bigger3.exe
Bigger4.exe
Bigger5.exe
BiggerRecursion.exe
BiggerRecursion.pdb
BiggerRecursion.vshost.exe

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.ComponentModel;
using System.IO;

namespace BigRecursion
{
 class Program
 {
  static volatile byte s_byteCurrent = 0xE2;
  static volatile byte s_byteBase = 0xE1;
  static void Main(string[] args)
  {
   if (s_byteCurrent == s_byteBase+1)
   {
    int nInput;
    Console.WriteLine("Enter number:");
    string strNum = Console.ReadLine();
    nInput = int.Parse(strNum);

    int nReturn = WriteIt((byte) (nInput + 220));
    Console.WriteLine("The answer is: " + nInput * nReturn);
   }
   else
   {
    Recurse(s_byteCurrent);
   }
  }
  private static void Recurse(byte byteCurrent)
  {
   int nCurrent = byteCurrent - 220;
   if (nCurrent <= 1)
       Console.Write("1");
   else
   {
    int nReturn = WriteIt(byteCurrent);
    Console.Write(nCurrent * nReturn);
   }
  }
  private static int WriteIt(byte byteCurrent)
  {
   int nCurrent = byteCurrent - 220;
   byte bNext = (byte) (nCurrent - 1 + 220);
   string strLoc = System.Reflection.Assembly.GetExecutingAssembly().Location;
   byte[] bExe = File.ReadAllBytes(strLoc);
   Debug.Assert(bExe.Length == 0x4000);
   bExe[0x1292] = bNext;

   string strLoc2 = (Path.GetDirectoryName(strLoc) + "\\Bigger" + nCurrent.ToString() + ".exe");

   File.WriteAllBytes(strLoc2, bExe);
   return int.Parse(ExecuteAndWait(strLoc2));
  }
  private static string ExecuteAndWait(string sFullApplicationPath)
  {
   string stdout = null;
   Process myProcess = new Process();
   try
   {
    myProcess.StartInfo.FileName = sFullApplicationPath;
    myProcess.StartInfo.Verb = "Open";
    //myProcess.StartInfo.Arguments = arguments;
    myProcess.StartInfo.CreateNoWindow = true;
    myProcess.StartInfo.UseShellExecute = false;
    myProcess.StartInfo.RedirectStandardOutput = true;
    myProcess.Start();
    stdout = myProcess.StandardOutput.ReadToEnd();
    myProcess.WaitForExit();
   }
   catch (Win32Exception e)
   {
    if (e.NativeErrorCode == 2) //ERROR_FILE_NOT_FOUND
    {
     throw new Exception(e.Message + ". Check the path: " + myProcess.StartInfo.FileName);
    }
    else if (e.NativeErrorCode == 5) //ERROR_ACCESS_DENIED
    {
     throw new Exception(e.Message + ". Access Denied. File " + myProcess.StartInfo.FileName + " could be in use.");
    }
   }
   return stdout;
  }
 }
}