October 30, 2012
I wrote a lightweight, low-level ASCII/Unicode processing library in C++ out of dissatisfaction with existing solutions. It’s very minimalistic and has no external dependencies. It supports the bare minimum features for dealing with text encodings:
// detect the encoding for a string encoding_type detect_encoding(const std::string &input); // determine whether a string is valid in a particular encoding bool is_valid(const std::string &input, encoding_type encoding); // convert a string from one encoding to another std::string convert_encoding(const std::string &input, encoding_type input_encoding, encoding_type output_encoding, bool include_bom); // get the number of code points in a string size_t get_length(const std::string &input, encoding_type encoding); // return the number of bytes of the code point at pos, or 0 if the byte index does not refer to a valid code point size_t get_char_size(const std::string &input, size_t pos, encoding_type encoding); // get the code point at a particular byte index uint32_t get_char(const std::string &input, size_t pos, encoding_type encoding); // set the code point at a particular byte index void set_char(std::string &input, size_t pos, uint32_t code_point, encoding_type encoding); // add a code point to the end of a string void add_char(std::string &input, uint32_t code_point, encoding_type encoding); // determine whether a code point is a letter bool is_alpha(uint32_t code_point); // determine whether a code point is uppercase bool is_upper(uint32_t code_point); // determine whether a code point is lowercase bool is_lower(uint32_t code_point); // determine whether a code point is titlecase bool is_title(uint32_t code_point); // determine whether a code point is a number bool is_numeric(uint32_t code_point); // determine whether a code point is whitespace bool is_whitespace(uint32_t code_point); // determine whether a code point is a line separator bool is_newline(uint32_t code_point); // convert a code point to uppercase (return the input if no uppercase form exists) uint32_t to_upper(uint32_t code_point); // convert a code point to lowercase (return the input if no lowercase form exists) uint32_t to_lower(uint32_t code_point); // convert a code point to titlecase (return the input if no titlecase form exists) uint32_t to_title(uint32_t code_point);
Get it here!
October 28, 2012
Anyone who has taken a class on computability theory, compilers, or finite automata knows that regular expressions can be parsed in linear time by generating a nondeterministic finite automaton (NFA) from the regular expression and converting it into a deterministic one (DFA).
Unfortunately, regular expression libraries like Python’s
remodule frequently generate exponential-time parsers. Why? The reason is that regex libraries like
reproduce backtracking parsers that can do more than just parse regular languages. They can parse some non-regular languages and support extra features like backreferences, which finite automata alone cannot do.
To combat this, I’ve built the backbone of a true regular expressions library: a finite automata engine. It can be used to build a regex parser generator that takes worst-case linear time, as a true regex parser should do.
August 21, 2012
I recently built a partially self-balancing electric unicycle called “Bullet,” featuring:
- A custom MIG-welded steel chassis
- A 450 Watt electric motor
- Two 7 Ah 12 Volt batteries
- A 5DOF inertial measurement unit
- The OSMC H-bridge
- An ATmega328P microcontroller
I say “partially” self-balancing because it only balances along one axis (forward/backward), and the rider still needs to balance left and right (it’s analagous to riding a bicycle “no hands”). It operates much like a Segway—you lean forward to accelerate, and lean back to brake. The top speed is about 15 mph, and it easily goes 5 miles on a single charge. This was my primary mode of transportation on the MIT campus (see the “Press and Aftermath” section below).
The thing in my right hand (in the video at the bottom) is a “kill switch”—if I let go of it, the unicycle deactivates the motor, much like a treadmill safety key.
Also, you may notice that the circuit is fully exposed. When the unicycle falls forward, the circuit has about two inches of ground clearance (so it never hits the floor). However, I’m currently building a proper case for more protection.
To estimate its orientation, Bullet integrates readings from the gyro and accelerometer using a complementary filter. To balance, the angle estimate is fed through a PID loop (with no integral term). The loop runs at 625 Hz. The output from this stage determines the duty cycle of a 1.22 kHz PWM signal, which is connected to the H-bridge. The code was written in C, and is in the public domain.
The circuit itself is essentially a pretty standard microcontroller setup—filtering capacitors on the power rails, RESET pin held high (for AVR microcontrollers), external 20 MHz crystal oscillator, some indicator LEDs, and the IMU connected to the ADC pins. Two of the digital output pins are wired to the motor controller, which is connected to the motor and the batteries. The motor controller has an onboard switching voltage regulator that powers the logic subcircuit (and also the charge pump for the high-side MOSFETs of the H-bridge). I expect that most undergraduates in electrical engineering could probably reconstruct the circuit given this description, burn the code onto the microcontroller, and have a working electric unicycle controller. A trip to the machine shop to construct the chassis and voilà, you’ve made your very own self-balancing unicycle!
Learning to ride
Unfortunately, one cannot simply pick up a self-balancing unicycle and ride it with ease. It took me several hours to be able to ride in a straight line without crashing, and it took several days to learn how to turn in a controlled manner. Many of my friends have tried riding it, usually with little success (including some actual unicyclers). However, my talented friend Harry can ride it about as well as I do.
Here are some riding tips, in case you ever build one:
- Don’t let go of the safety switch unless you crash. Bullet is designed to help you balance—let it do it’s job (even while mounting). If you ever let go of the safety switch while riding, you will fall (however, it was designed so that if you accidentally let go for a fraction of a second, you can usually recover).
- Bumps in the terrain are always bigger than they appear.
- Put most of your wait on the seat, not the pedals.
- Gain weight! An inverted pendulum with a high center of gravity is easier to balance than one where most of the weight comes from the motor and wheel. To illustrate this fact, try balancing a long broom on your hand (with the broomstick in your palm) vs. a short broom.
- When you first press the safety switch, Bullet will assume an upright position as fast as it can, even if you are in the way. So don’t be in the way (it can run into your ankles or run over your foot)!
As I said earlier, Bullet is the primary way I navigate MIT and the surrounding Cambridge area. I often zoom past students, faculty, custodians, and tourists, with generally positive reactions from everyone. I’ve been told one can be fined for riding a scooter in the Infinite Corridor. Fortunately, Bullet ain’t no scooter.
However, Bullet is heavy. I live on the fifth floor of a dorm with no elevator, so carrying Bullet up and down the stairs can be quite tiresome. If I were to start over, I would try to minimize weight with a wheel hub motor, NiCad or NiMH batteries, and an aluminum frame (instead of steel).
Bullet’s small size (compared to a bicycle, scooter, moped, etc.) means I can take it on the bus or train with no problem, so I can take public transportation to the stop nearest my destination and ride Bullet the rest of the way. With over 5 miles of range on a single-charge, battery life is usually not a problem in my urban hometown.
I am certainly not the first person to build an electric unicycle. Perhaps the most well-known self-balancing unicycle is Trevor Blackwell’s Eunicycle, which also uses the OSMC. His design is similar to mine, but uses a much more expensive battery pack ($218 for his vs $44 for mine). Also, the Eunicycle’s motor and gearbox cost a grand total of $644, whereas Bullet’s drive system (including the wheel itself) was $195. Finally, the IMU he uses is about $100 more than mine. Overall, Bullet is several hundred dollars cheaper than the Eunicycle, but this comes at a price (mostly weight).
Focus Designs (of whom Adam Savage of MythBusters fame is a customer) manufactures a commercial electric unicycle called the SBU (“Self-Balancing Unicycle”). At $1,795, the SBU is much more expensive than mine, but it has extra safety features and a hub motor, which results in a smoother ride. For comparison, Bullet uses a toothed belt drive, and the Eunicycle features a metal gearbox. Because of the belt drive, I can often feel Bullet’s motor engaging the wheel with a slight jerk.
Here is a video of me riding it and some of my friends trying it out (no audio, sorry):
Press and aftermath
Bullet has been featured on a number of media outlets, including:
- MIT Admissions
- Hack A Day
- MIT CSAIL
- Slice of MIT
- The Huffington Post
- Coolest Gadgets
- The Green Optimistic
- New Rising Media
- All Best Reviews
- The Register
- Cambridge Bicycle
- The Discovery Channel
Unfortunately, while interning at Dropbox in the summer of 2012, someone broke into my dorm’s summer storage area and stole Bullet. It was fun while it lasted!