Merge https://github.com/yenatch/pokecrystal

6 files changed, 962 insertions, 26 deletions

diff --git a/extras/chars.py b/extras/chars.py
index 28f37cb84..1bc25dbe7 100644
--- a/extras/chars.py
+++ b/extras/chars.py
@@ -98,6 +98,8 @@ chars = {
     0xE9: "&",
     0xEA: "é",
     0xEB: "→",
+    0xED: "▶",
+    0xEE: "▼",
     0xEF: "♂",
     0xF0: "¥",
     0xF1: "×",
diff --git a/extras/crystal.py b/extras/crystal.py
index b3f29a12f..c7b09397e 100644
--- a/extras/crystal.py
+++ b/extras/crystal.py
@@ -1471,7 +1471,7 @@ ScriptPointerLabelAfterBank.parse = _parse_script_pointer_bytes
 class PointerLabelToScriptPointer(PointerLabelParam):
     def parse(self):
         PointerLabelParam.parse(self)
-        address = calculate_pointer_from_bytes_at(self.address, bank=self.bank)
+        address = calculate_pointer_from_bytes_at(self.parsed_address, bank=self.bank)
         address2 = calculate_pointer_from_bytes_at(address, bank="reverse") # maybe not "reverse"?
         self.script = parse_script_engine_script_at(address2, origin=False, map_group=self.map_group, map_id=self.map_id, force=self.force, debug=self.debug)
 
@@ -2912,7 +2912,7 @@ music_command_enders = [0xEA, 0xEB, 0xEE, 0xFC, 0xFF,]
 # special case for 0xFD (if loopchannel.count = 0, break)
 
 def create_music_command_classes(debug=False):
-    klasses = [GivePoke]
+    klasses = []
     for (byte, cmd) in music_commands_new.items():
         cmd_name = cmd[0].replace(" ", "_")
         params = {"id": byte, "size": 1, "end": byte in music_command_enders, "macro_name": cmd_name}
@@ -2938,6 +2938,221 @@ def create_music_command_classes(debug=False):
     return klasses
 music_classes = create_music_command_classes()
 
+
+
+effect_commands = {
+	0x1: ['checkturn'],
+	0x2: ['checkobedience'],
+	0x3: ['usedmovetext'],
+	0x4: ['doturn'],
+	0x5: ['critical'],
+	0x6: ['damagestats'],
+	0x7: ['stab'],
+	0x8: ['damagevariation'],
+	0x9: ['checkhit'],
+	0xa: ['effect0x0a'],
+	0xb: ['effect0x0b'],
+	0xc: ['effect0x0c'],
+	0xd: ['resulttext'],
+	0xe: ['checkfaint'],
+	0xf: ['criticaltext'],
+	0x10: ['supereffectivetext'],
+	0x11: ['checkdestinybond'],
+	0x12: ['buildopponentrage'],
+	0x13: ['poisontarget'],
+	0x14: ['sleeptarget'],
+	0x15: ['draintarget'],
+	0x16: ['eatdream'],
+	0x17: ['burntarget'],
+	0x18: ['freezetarget'],
+	0x19: ['paralyzetarget'],
+	0x1a: ['selfdestruct'],
+	0x1b: ['mirrormove'],
+	0x1c: ['statup'],
+	0x1d: ['statdown'],
+	0x1e: ['payday'],
+	0x1f: ['conversion'],
+	0x20: ['resetstats'],
+	0x21: ['storeenergy'],
+	0x22: ['unleashenergy'],
+	0x23: ['forceswitch'],
+	0x24: ['endloop'],
+	0x25: ['flinchtarget'],
+	0x26: ['ohko'],
+	0x27: ['recoil'],
+	0x28: ['mist'],
+	0x29: ['focusenergy'],
+	0x2a: ['confuse'],
+	0x2b: ['confusetarget'],
+	0x2c: ['heal'],
+	0x2d: ['transform'],
+	0x2e: ['screen'],
+	0x2f: ['poison'],
+	0x30: ['paralyze'],
+	0x31: ['substitute'],
+	0x32: ['rechargenextturn'],
+	0x33: ['mimic'],
+	0x34: ['metronome'],
+	0x35: ['leechseed'],
+	0x36: ['splash'],
+	0x37: ['disable'],
+	0x38: ['cleartext'],
+	0x39: ['charge'],
+	0x3a: ['checkcharge'],
+	0x3b: ['traptarget'],
+	0x3c: ['effect0x3c'],
+	0x3d: ['rampage'],
+	0x3e: ['checkrampage'],
+	0x3f: ['constantdamage'],
+	0x40: ['counter'],
+	0x41: ['encore'],
+	0x42: ['painsplit'],
+	0x43: ['snore'],
+	0x44: ['conversion2'],
+	0x45: ['lockon'],
+	0x46: ['sketch'],
+	0x47: ['defrostopponent'],
+	0x48: ['sleeptalk'],
+	0x49: ['destinybond'],
+	0x4a: ['spite'],
+	0x4b: ['falseswipe'],
+	0x4c: ['healbell'],
+	0x4d: ['kingsrock'],
+	0x4e: ['triplekick'],
+	0x4f: ['kickcounter'],
+	0x50: ['thief'],
+	0x51: ['arenatrap'],
+	0x52: ['nightmare'],
+	0x53: ['defrost'],
+	0x54: ['curse'],
+	0x55: ['protect'],
+	0x56: ['spikes'],
+	0x57: ['foresight'],
+	0x58: ['perishsong'],
+	0x59: ['startsandstorm'],
+	0x5a: ['endure'],
+	0x5b: ['checkcurl'],
+	0x5c: ['rolloutpower'],
+	0x5d: ['effect0x5d'],
+	0x5e: ['furycutter'],
+	0x5f: ['attract'],
+	0x60: ['happinesspower'],
+	0x61: ['present'],
+	0x62: ['damagecalc'],
+	0x63: ['frustrationpower'],
+	0x64: ['safeguard'],
+	0x65: ['checksafeguard'],
+	0x66: ['getmagnitude'],
+	0x67: ['batonpass'],
+	0x68: ['pursuit'],
+	0x69: ['clearhazards'],
+	0x6a: ['healmorn'],
+	0x6b: ['healday'],
+	0x6c: ['healnite'],
+	0x6d: ['hiddenpower'],
+	0x6e: ['startrain'],
+	0x6f: ['startsun'],
+	0x70: ['attackup'],
+	0x71: ['defenseup'],
+	0x72: ['speedup'],
+	0x73: ['specialattackup'],
+	0x74: ['specialdefenseup'],
+	0x75: ['accuracyup'],
+	0x76: ['evasionup'],
+	0x77: ['attackup2'],
+	0x78: ['defenseup2'],
+	0x79: ['speedup2'],
+	0x7a: ['specialattackup2'],
+	0x7b: ['specialdefenseup2'],
+	0x7c: ['accuracyup2'],
+	0x7d: ['evasionup2'],
+	0x7e: ['attackdown'],
+	0x7f: ['defensedown'],
+	0x80: ['speeddown'],
+	0x81: ['specialattackdown'],
+	0x82: ['specialdefensedown'],
+	0x83: ['accuracydown'],
+	0x84: ['evasiondown'],
+	0x85: ['attackdown2'],
+	0x86: ['defensedown2'],
+	0x87: ['speeddown2'],
+	0x88: ['specialattackdown2'],
+	0x89: ['specialdefensedown2'],
+	0x8a: ['accuracydown2'],
+	0x8b: ['evasiondown2'],
+	0x8c: ['statmessageuser'],
+	0x8d: ['statmessagetarget'],
+	0x8e: ['statupfailtext'],
+	0x8f: ['statdownfailtext'],
+	0x90: ['effectchance'],
+	0x91: ['effect0x91'],
+	0x92: ['effect0x92'],
+	0x93: ['switchturn'],
+	0x94: ['fakeout'],
+	0x95: ['bellydrum'],
+	0x96: ['psychup'],
+	0x97: ['rage'],
+	0x98: ['doubleflyingdamage'],
+	0x99: ['doubleundergrounddamage'],
+	0x9a: ['mirrorcoat'],
+	0x9b: ['checkfuturesight'],
+	0x9c: ['futuresight'],
+	0x9d: ['doubleminimizedamage'],
+	0x9e: ['skipsuncharge'],
+	0x9f: ['thunderaccuracy'],
+	0xa0: ['teleport'],
+	0xa1: ['beatup'],
+	0xa2: ['ragedamage'],
+	0xa3: ['effect0xa3'],
+	0xa4: ['allstatsup'],
+	0xa5: ['effect0xa5'],
+	0xa6: ['effect0xa6'],
+	0xa7: ['effect0xa7'],
+	0xa8: ['effect0xa8'],
+	0xa9: ['clearmissdamage'],
+	0xaa: ['wait'],
+	0xab: ['hittarget'],
+	0xac: ['tristatuschance'],
+	0xad: ['supereffectivelooptext'],
+	0xae: ['startloop'],
+	0xaf: ['curl'],
+	0xfe: ['endturn'],
+	0xff: ['endmove'],
+}
+
+effect_command_enders = [0xFF,]
+
+def create_effect_command_classes(debug=False):
+    klasses = []
+    for (byte, cmd) in effect_commands.items():
+        cmd_name = cmd[0].replace(" ", "_")
+        params = {
+            "id": byte,
+            "size": 1,
+            "end": byte in effect_command_enders,
+            "macro_name": cmd_name
+	}
+        params["param_types"] = {}
+        if len(cmd) > 1:
+            param_types = cmd[1:]
+            for (i, each) in enumerate(param_types):
+                thing = {"name": each[0], "class": each[1]}
+                params["param_types"][i] = thing
+                if debug:
+                    print "each is: " + str(each)
+                    print "thing[class] is: " + str(thing["class"])
+                params["size"] += thing["class"].size
+        klass_name = cmd_name+"Command"
+        klass = classobj(klass_name, (Command,), params)
+        globals()[klass_name] = klass
+        klasses.append(klass)
+    # later an individual klass will be instantiated to handle something
+    return klasses
+
+effect_classes = create_effect_command_classes()
+
+
+
 def generate_macros(filename="../script_macros.asm"):
     """generates all macros based on commands
     this is dumped into script_macros.asm"""
@@ -6201,7 +6416,7 @@ def parse_map_header_by_id(*args, **kwargs):
     elif len(args) == 1 and type(args[0]) == str:
         map_group = int(args[0].split(".")[0])
         map_id = int(args[0].split(".")[1])
-    else:
+    elif map_group == None and map_id == None:
         raise Exception("dunno what to do with input")
     offset = map_names[map_group]["offset"]
     map_header_offset = offset + ((map_id - 1) * map_header_byte_size)
diff --git a/extras/gfx.py b/extras/gfx.py
index 3aa98b3ca..3d8e950bc 100644
--- a/extras/gfx.py
+++ b/extras/gfx.py
@@ -1436,8 +1436,8 @@ def mass_to_colored_png(debug=False):
 			for name in files:
 				if debug: print os.path.splitext(name), os.path.join(root, name)
 				if os.path.splitext(name)[1] == '.2bpp':
-					if name[:5]+'.pal' in files:
-						to_png(os.path.join(root, name), None, os.path.join(root, name[:-5]+'.pal'))
+					if os.path.splitext(name)[0]+'.pal' in files:
+						to_png(os.path.join(root, name), None, os.path.join(root, os.path.splitext(name)[0]+'.pal'))
 					else:
 						to_png(os.path.join(root, name))
 	
@@ -1459,26 +1459,26 @@ def mass_to_colored_png(debug=False):
 
 def mass_decompress(debug=False):
 	for root, dirs, files in os.walk('../gfx/'):
-		for file in files:
-			if 'lz' in file:
+		for name in files:
+			if 'lz' in name:
 				if '/pics' in root:
-					if 'front' in file:
+					if 'front' in name:
 						id = root.split('pics/')[1][:3]
 						if id != 'egg':
-							with open(root+'/'+file, 'rb') as lz: de = Decompressed(lz.read(), 'vert', sizes[int(id)-1])
+							with open(os.path.join(root, name), 'rb') as lz: de = Decompressed(lz.read(), 'vert', sizes[int(id)-1])
 						else:
-							with open(root+'/'+file, 'rb') as lz: de = Decompressed(lz.read(), 'vert', 4)
-						to_file(root+'/'+'front.2bpp', de.pic)
-						to_file(root+'/'+'tiles.2bpp', de.animtiles)
-					elif 'back' in file:
-						with open(root+'/'+file, 'rb') as lz: de = Decompressed(lz.read(), 'vert')
-						to_file(root+'/'+'back.2bpp', de.output)
+							with open(os.path.join(root, name), 'rb') as lz: de = Decompressed(lz.read(), 'vert', 4)
+						to_file(os.path.join(root, 'front.2bpp'), de.pic)
+						to_file(os.path.join(root, 'tiles.2bpp'), de.animtiles)
+					elif 'back' in name:
+						with open(os.path.join(root, name), 'rb') as lz: de = Decompressed(lz.read(), 'vert')
+						to_file(os.path.join(root, 'back.2bpp'), de.output)
 				elif '/trainers' in root or '/fx' in root:
-					with open(root+'/'+file, 'rb') as lz: de = Decompressed(lz.read(), 'vert')
-					to_file(root+'/'+file[:-3]+'.2bpp', de.output)
+					with open(os.path.join(root, name), 'rb') as lz: de = Decompressed(lz.read(), 'vert')
+					to_file(os.path.join(root, os.path.splitext(name)[0]+'.2bpp'), de.output)
 				else:
-					with open(root+'/'+file, 'rb') as lz: de = Decompressed(lz.read())
-					to_file(root+file[:-3]+'.2bpp', de.output)
+					with open(os.path.join(root, name), 'rb') as lz: de = Decompressed(lz.read())
+					to_file(os.path.join(root, os.path.splitext(name)[0]+'.2bpp'), de.output)
 
 def append_terminator_to_lzs(directory):
 	# fix lzs that were extracted with a missing terminator
diff --git a/extras/vba.py b/extras/vba.py
index 8ed0d7b5a..317f70540 100644
--- a/extras/vba.py
+++ b/extras/vba.py
@@ -104,6 +104,11 @@ Gb.loadVBA()
 
 from vba_config import *
 
+try:
+    import vba_keyboard as keyboard
+except ImportError:
+    print "Not loading the keyboard module (which uses networkx)."
+
 if not os.path.exists(rom_path):
     raise Exception("rom_path is not configured properly; edit vba_config.py?")
 
@@ -163,10 +168,14 @@ def button_combiner(buttons):
             buttons.replace("select", "")
             result |= button_masks["select"]
 
+    if isinstance(buttons, list):
+        if len(buttons) > 9:
+            raise Exception("can't combine more than 9 buttons at a time")
+
     for each in buttons:
         result |= button_masks[each]
 
-    print "button: " + str(result)
+    #print "button: " + str(result)
     return result
 
 def load_rom(path=None):
@@ -434,6 +443,69 @@ def press(buttons, steplimit=1):
     for step_counter in range(0, steplimit):
         Gb.step(number)
 
+def get_buttons():
+    """
+    Returns the currentButtons[0] value (an integer with bits set for which
+    buttons are currently pressed).
+    """
+    return Gb.getCurrentButtons()
+
+class State(RomList):
+    name = None
+
+class Recording:
+    def __init__(self):
+        self.frames = []
+        self.states = {}
+
+    def _get_frame_count(self):
+        return len(self.frames)
+
+    frame_count = property(fget=_get_frame_count)
+
+    def save(self, name=None):
+        """
+        Saves the current state.
+        """
+        state = State(get_state())
+        state.name = name
+        self.states[self.frame_count] = state
+
+    def load(self, name):
+        """
+        Loads a state by name in the state list.
+        """
+        for state in self.states.items():
+            if state.name == name:
+                set_state(state)
+                return state
+        return False
+
+    def step(self, stepcount=1, first_frame=0, replay=False):
+        """
+        Records button presses for each frame.
+        """
+        if replay:
+            stepcount = len(self.frames[first_name:])
+
+        for counter in range(first_frame, stepcount):
+            if replay:
+                press(self.frames[counter], steplimit=0)
+            else:
+                self.frames.append(get_buttons())
+            nstep(1)
+
+    def replay_from(self, thing):
+        """
+        Replays based on a State or the name of a saved state.
+        """
+        if isinstance(thing, State):
+            set_state(thing)
+        else:
+            thing = self.load(thing)
+        frame_id = self.states.index(thing)
+        self.step(first_frame=frame_id, replay=True)
+
 class Registers:
     order = [
         "pc",
@@ -564,6 +636,66 @@ def call(bank, address):
     else:
         registers["pc"] = address
 
+class cheats:
+    """
+    Helpers to manage the cheating infrastructure.
+
+    import vba; vba.load_rom(); vba.cheats.add_gameshark("0100CFCF", "text speedup 1"); vba.cheats.add_gameshark("0101CCCF", "text speedup 2"); vba.go()
+    """
+
+    @staticmethod
+    def enable(id):
+        """
+        void gbCheatEnable(int i)
+        """
+        Gb.cheatEnable(id)
+
+    @staticmethod
+    def disable(id):
+        """
+        void gbCheatDisable(int i)
+        """
+        Gb.cheatDisable(id)
+
+    @staticmethod
+    def load_file(filename):
+        """
+        Loads a .clt file. By default each cheat is disabled.
+        """
+        Gb.loadCheatsFromFile(filename)
+
+    @staticmethod
+    def remove_all():
+        """
+        Removes all cheats from memory.
+
+        void gbCheatRemoveAll()
+        """
+        Gb.cheatRemoveAll()
+
+    @staticmethod
+    def remove_cheat(id):
+        """
+        Removes a specific cheat from memory by id.
+
+        void gbCheatRemove(int i)
+        """
+        Gb.cheatRemove(id)
+
+    @staticmethod
+    def add_gamegenie(code, description=""):
+        """
+        void gbAddGgCheat(const char *code, const char *desc)
+        """
+        Gb.cheatAddGamegenie(code, description)
+
+    @staticmethod
+    def add_gameshark(code, description=""):
+        """
+        gbAddGsCheat(const char *code, const char *desc)
+        """
+        Gb.cheatAddGameshark(code, description)
+
 class crystal:
     """
     Just a simple namespace to store a bunch of functions for Pokémon Crystal.
@@ -767,6 +899,25 @@ class crystal:
         return output
 
     @staticmethod
+    def keyboard_apply(button_sequence):
+        """
+        Applies a sequence of buttons to the on-screen keyboard.
+        """
+        for buttons in button_sequence:
+            press(buttons)
+            nstep(2)
+            press([])
+
+    @staticmethod
+    def write(something="TrAiNeR"):
+        """
+        Uses a planning algorithm to type out a word in the most efficient way
+        possible.
+        """
+        button_sequence = keyboard.plan_typing(something)
+        crystal.keyboard_apply([[x] for x in button_sequence])
+
+    @staticmethod
     def set_partymon2():
         """
         This causes corruption, so it's not working yet.
@@ -836,6 +987,14 @@ class TestEmulator(unittest.TestCase):
 
         self.assertTrue("TRAINER" in text)
 
+class TestWriter(unittest.TestCase):
+    def test_very_basic(self):
+        button_sequence = keyboard.plan_typing("an")
+        expected_result = ["select", "a", "d", "r", "r", "r", "r", "a"]
+
+        self.assertEqual(len(expected_result), len(button_sequence))
+        self.assertEqual(expected_result, button_sequence)
+
 if __name__ == "__main__":
     unittest.main()
 
diff --git a/extras/vba_config.py b/extras/vba_config.py
index 8377c8818..4433f16c0 100644
--- a/extras/vba_config.py
+++ b/extras/vba_config.py
@@ -2,13 +2,10 @@
 # -*- encoding: utf-8 -*-
 import os
 
-# by default we assume the user has things in their $HOME
-home = os.path.expanduser("~") # or System.getProperty("user.home")
+# by default we assume the user has vba in pokecrystal/extras
+project_path = os.path.abspath(os.path.join(os.path.dirname( __file__ ), '..'))
 
-# and that the pokecrystal project folder is in there somewhere
-project_path = os.path.join(home, os.path.join("code", "pokecrystal"))
-
-# save states are in ~/code/pokecrystal/save-states/
+# save states are in pokecrystal/save-states/
 save_state_path = os.path.join(project_path, "save-states")
 
 # where is your rom?
diff --git a/extras/vba_keyboard.py b/extras/vba_keyboard.py
new file mode 100644
index 000000000..bbe85b051
--- /dev/null
+++ b/extras/vba_keyboard.py
@@ -0,0 +1,563 @@
+# -*- encoding: utf-8 -*-
+"""
+This file constructs a networkx.DiGraph object called graph, which can be used
+to find the shortest path of keypresses on the keyboard to type a word.
+"""
+
+import itertools
+import networkx
+
+graph = networkx.DiGraph()
+
+graph_data = """
+A a select
+A B r
+A I l
+A lower-upper-column-1 u
+A J d
+
+B b select
+B A l
+B C r
+B lower-upper-column-2 u
+B K d
+
+C c select
+C D r
+C B l
+C lower-upper-column-3 u
+C L d
+
+D d select
+D E r
+D C l
+D del-upper-column-1 u
+D M d
+
+E e select
+E del-upper-column-2 u
+E N d
+E D l
+E F r
+
+F f select
+F del-upper-column-3 u
+F O d
+F E l
+F G r
+
+G g select
+G end-upper-column-1 u
+G P d
+G F l
+G H r
+
+H h select
+H end-upper-column-2 u
+H Q d
+H G l
+H I r
+
+I i select
+I end-upper-column-3 u
+I R d
+I H l
+I A r
+
+J j select
+J A u
+J S d
+J R l
+J K r
+
+K k select
+K B u
+K T d
+K J l
+K L r
+
+L l select
+L C u
+L U d
+L K l
+L M r
+
+M m select
+M D u
+M V d
+M L l
+M N r
+
+N n select
+N E u
+N W d
+N M l
+N O r
+
+O o select
+O F u
+O X d
+O N l
+O P r
+
+P p select
+P G u
+P Y d
+P O l
+P Q r
+
+Q q select
+Q H u
+Q Z d
+Q P l
+Q R r
+
+R r select
+R I u
+R space-upper-x8-y2 d
+R Q l
+R J r
+
+S s select
+S J u
+S - d
+S space-upper-x8-y2 l
+
+T t select
+T K u
+T ? d
+T S l
+T U r
+
+U u select
+U L u
+U ! d
+U T l
+U V r
+
+V v select
+V M u
+V / d
+V U l
+V W r
+
+W w select
+W N u
+W . d
+W V l
+W X r
+
+X x select
+X O u
+X , d
+X W l
+X Y r
+
+Y y select
+Y P u
+Y space-upper-x6-y3 d
+Y X l
+Y Z r
+
+Z z select
+Z Q u
+Z space-upper-x7-y3 d
+Z Y l
+Z space-upper-x8-y2 r
+
+end-upper-column-1 lower-upper-column-1 r
+end-upper-column-2 lower-upper-column-1 r
+end-upper-column-3 lower-upper-column-1 r
+end-upper-column-1 del-upper-column-1 l
+end-upper-column-2 del-upper-column-1 l
+end-upper-column-3 del-upper-column-1 l
+lower-upper-column-1 end-upper-column-1 l
+lower-upper-column-2 end-upper-column-1 l
+lower-upper-column-3 end-upper-column-1 l
+lower-upper-column-1 del-upper-column-1 r
+lower-upper-column-2 del-upper-column-1 r
+lower-upper-column-3 del-upper-column-1 r
+del-upper-column-1 lower-upper-column-1 l
+del-upper-column-2 lower-upper-column-1 l
+del-upper-column-3 lower-upper-column-1 l
+del-upper-column-1 end-upper-column-1 r
+del-upper-column-2 end-upper-column-1 r
+del-upper-column-3 end-upper-column-1 r
+
+lower-upper-column-1 A d
+lower-upper-column-2 B d
+lower-upper-column-3 C d
+lower-upper-column-1 - u
+lower-upper-column-2 ? u
+lower-upper-column-3 ! u
+
+del-upper-column-1 D d
+del-upper-column-2 E d
+del-upper-column-3 F d
+del-upper-column-1 / u
+del-upper-column-2 . u
+del-upper-column-3 , u
+
+end-upper-column-1 G d
+end-upper-column-2 H d
+end-upper-column-3 I d
+end-upper-column-1 space-upper-x6-y3 u
+end-upper-column-2 space-upper-x7-y3 u
+end-upper-column-3 space-upper-x8-y3 u
+
+space-upper-x8-y2 space-lower-x8-y2 select
+space-upper-x8-y2 R u
+space-upper-x8-y2 space-upper-x8-y3 d
+space-upper-x8-y2 Z l
+space-upper-x8-y2 S r
+
+space-upper-x8-y3 MN select
+space-upper-x8-y3 space-upper-x8-y2 u
+space-upper-x8-y3 end-upper-column-3 d
+space-upper-x8-y3 space-upper-x7-y3 l
+space-upper-x8-y3 - r
+
+space-upper-x7-y3 PK select
+space-upper-x7-y3 Z u
+space-upper-x7-y3 end-upper-column-2 d
+space-upper-x7-y3 space-upper-x6-y3 l
+space-upper-x7-y3 space-upper-x8-y3 r
+
+space-upper-x6-y3 ] select
+space-upper-x6-y3 Y u
+space-upper-x6-y3 end-upper-column-1 d
+space-upper-x6-y3 , l
+space-upper-x6-y3 space-upper-x7-y3 r
+
+end-upper-column-1 end-lower-column-1 select
+end-upper-column-2 end-lower-column-2 select
+end-upper-column-3 end-lower-column-3 select
+lower-upper-column-1 lower-lower-column-1 select
+lower-upper-column-2 lower-lower-column-2 select
+lower-upper-column-3 lower-lower-column-3 select
+del-upper-column-1 del-lower-column-1 select
+del-upper-column-2 del-lower-column-2 select
+del-upper-column-3 del-lower-column-3 select
+
+lower-lower-column-1 × u
+lower-lower-column-2 ( u
+lower-lower-column-3 ) u
+lower-lower-column-1 a d
+lower-lower-column-2 b d
+lower-lower-column-3 c d
+
+end-lower-column-1 ] u
+end-lower-column-2 PK u
+end-lower-column-3 MN u
+end-lower-column-1 g d
+end-lower-column-2 h d
+end-lower-column-3 i d
+
+del-lower-column-1 : u
+del-lower-column-2 ; u
+del-lower-column-3 [ u
+del-lower-column-1 d d
+del-lower-column-2 e d
+del-lower-column-3 f d
+
+- × select
+- S u
+- lower-upper-column-1 d
+- space-upper-x8-y3 l
+- ? r
+
+? ( select
+? T u
+? lower-upper-column-2 d
+? - l
+? ! r
+
+! ) select
+! U u
+! lower-upper-column-3 d
+! ? l
+! / r
+
+/ : select
+/ V u
+/ del-upper-column-1 d
+/ ! l
+/ . r
+
+. ; select
+. W u
+. del-upper-column-2 d
+. / l
+. , r
+
+, [ select
+, X u
+, del-upper-column-3 d
+, . l
+, space-upper-x6-y3 r
+
+× - select
+× s u
+× upper-lower-column-1 d
+× MN l
+× ( r
+
+( ? select
+( t u
+( upper-lower-column-2 d
+( × l
+( ) r
+
+) ! select
+) u u
+) upper-lower-column-3 d
+) ( l
+) : r
+
+: / select
+: v u
+: del-lower-column-1 d
+: ) l
+: ; r
+
+; . select
+; w u
+; del-lower-column-2 d
+; : l
+; [ r
+
+[ , select
+[ x u
+[ del-lower-column-3 d
+[ ; l
+[ ] r
+
+] space-upper-x6-y3 select
+] y u
+] end-lower-column-1 d
+] [ l
+] PK r
+
+PK space-upper-x7-y3 select
+PK z u
+PK end-lower-column-2 d
+PK ] l
+PK MN r
+
+MN space-upper-x8-y3 select
+MN space-lower-x8-y2 u
+MN end-lower-column-3 d
+MN PK l
+MN × r
+
+space-lower-x8-y2 space-upper-x8-y2 select
+space-lower-x8-y2 r u
+space-lower-x8-y2 MN d
+space-lower-x8-y2 z l
+space-lower-x8-y2 s r
+
+a A select
+a upper-lower-column-1 u
+a j d
+a i l
+a b r
+
+b B select
+b upper-lower-column-2 u
+b k d
+b a l
+b c r
+
+c C select
+c upper-lower-column-3 u
+c l d
+c b l
+c d r
+
+d D select
+d del-lower-column-1 u
+d m d
+d c l
+d e r
+
+e E select
+e del-lower-column-2 u
+e n d
+e d l
+e f r
+
+f F select
+f del-lower-column-3 u
+f o d
+f e l
+f g r
+
+g G select
+g end-lower-column-1 u
+g p d
+g f l
+g h r
+
+h H select
+h end-lower-column-2 u
+h q d
+h g l
+h i r
+
+i I select
+i end-lower-column-3 u
+i r d
+i h l
+i a r
+
+j J select
+j a u
+j s d
+j r l
+j k r
+
+k K select
+k b u
+k t d
+k j l
+k l r
+
+l L select
+l c u
+l u d
+l k l
+l m r
+
+m M select
+m d u
+m v d
+m l l
+m n r
+
+n N select
+n e u
+n w d
+n m l
+n o r
+
+o O select
+o f u
+o x d
+o n l
+o p r
+
+p P select
+p g u
+p y d
+p o l
+p q r
+
+q Q select
+q h u
+q z d
+q p l
+q r r
+
+r R select
+r i u
+r space-lower-x8-y2 d
+r q l
+r j r
+
+s S select
+s j u
+s × d
+s space-lower-x8-y2 l
+s t r
+
+t T select
+t k u
+t ( d
+t s l
+t u r
+
+u U select
+u l u
+u ) d
+u t l
+u v r
+
+v V select
+v m u
+v : d
+v u l
+v w r
+
+w W select
+w n u
+w ; d
+w v l
+w x r
+
+x X select
+x o u
+x [ d
+x w l
+x y r
+
+y Y select
+y p u
+y ] d
+y x l
+y z r
+
+z Z select
+z q u
+z PK d
+z y l
+z space-lower-x8-y2 r"""
+
+for line in graph_data.split("\n"):
+    if line == "":
+        continue
+    elif line[0] == "#":
+        continue
+
+    (node1, node2, edge_name) = line.split(" ")
+    graph.add_edge(node1, node2, key=edge_name)
+
+    #print "Adding edge ("+edge_name+") "+node1+" -> "+node2
+
+def shortest_path(node1, node2):
+    """
+    Figures out the shortest list of button presses to move from one letter to
+    another.
+    """
+    buttons = []
+    last = None
+    path = networkx.shortest_path(graph, node1, node2)
+    for each in path:
+        if last != None:
+            buttons.append(convert_nodes_to_button_press(last, each))
+        last = each
+    return buttons
+    #return [convert_nodes_to_button_press(node3, node4) for (node3, node4) in zip(*(iter(networkx.shortest_path(graph, node1, node2)),) * 2)]
+
+def convert_nodes_to_button_press(node1, node2):
+    """
+    Determines the button necessary to switch from node1 to node2.
+    """
+    print "getting button press for state transition: " + node1 + " -> " + node2
+    return graph.get_edge_data(node1, node2)["key"]
+
+def plan_typing(text, current="A"):
+    """
+    Plans a sequence of button presses to spell out the given text.
+    """
+    buttons = []
+    for target in text:
+        if target == current:
+            buttons.append("a")
+        else:
+            print "Finding the shortest path between " + current + " and " + target
+            more_buttons = shortest_path(current, target)
+            buttons.extend(more_buttons)
+            buttons.append("a")
+            current = target
+    return buttons
+