Friday, February 20, 2015

The anagram of Samarang is Anagrams

A few days ago I randomly stumbled upon the "check if two strings are anagrams" interview question, and it piqued my interest.

While it is immediately obvious there is an O(n-logn) algorithm for this -- sort the character arrays and compare them -- after a few moments I flashed on the O(n) algorithm for comparing two strings and determining if they are anagrams of each other.

This got me thinking, and I remembered the fun I had about 15 years ago assembling a huge list of english words and checking to see if the .com domain names were available. A little quick googling found some interesting word lists and I was off to the races.

I ended up implementing the O(n) comparison algorithm along with a data structure that chops up the word list by word length and then hashes the words using a hashing algorithm that causes potential anagrams to hash to the same bucket. However, checking all the words in each hash bucket is O(n^2)

Thus, it is typically much slower than the simpler nlogn algorithm in Python, because the lengths of the strings and the typical hash bucket are small, the python list.sort() function is highly optimized, and once you do have the strings and bucket sorted, the search for anagrams is O(n).

And O(n^2-logn) < O(n^2-n)

The moral of this story is, in order to figure out the best algorithm, you need to consider the whole problem. I fell in love with the O(n) comparison, but didn't notice for a while that changing the problem from "check if two strings are anagrams" to "find all the anagrams in a word list" made a big difference.

Still, it was a fun evening of coding, and my python is getting marginally less horrible.

You can find the python code, word lists and sample output here.

PS: Samarang is a place in Indonesia

Wednesday, January 7, 2015

Troubleshooting a Brother DCPL2540DW Wifi Configuration

This is one of those posts I'm mostly doing for the benefit of "The Next Poor Bastard". My Mom got a new DCPL2540DW printer the other day and it took a little headbanging to get it talking to the other devices in the house.

It's a fairly nice printer: built in scanner/copier, two-sided printing, WiFi with autoconfiguration, etc. Initial setup was easy, including one-touch wifi configuration.

Just one problem: you could see the printer on the network, but attempts to print to it just died -- nothing could talk to it. Connecting a machine to it via USB worked fine, so there was a problem with the configuration.

Condensing down about two hours of troubleshooting:

  • The Wifi status printout page doesn't tell you anything useful, but the Network menus have a status option that does -- stuff like IP address.
  • The Printer was connecting to the WiFi router fine, but instead of getting an address in the 192.168.2.X range like all the other devices, it was showing a 169.X.X.X address -- a self-assigned IP address.
  • My guess is that the WiFi router doesn't like to route packets to 169.X.X.X addresses, but probably accepts packets from them. So all the local devices could see the printer's "hey guys, open for business" announcement, but not do anything with it.
  • OK, several possible ways to fix this: tweak the router so it routes between 192.168.X.X and 169.X.X.X, force the printer to get its IP from the router, or the brute-force solution: give the printer a fixed IP address in the 192.168.2.X range.
  • So brute-force it is: go into the router configuration DHCP settings, and adjust the range of IP addresses it gives out to connected devices. It was 192.168.2.2-254, I changed it to .2-249. Then go into the printer's settings, and there's an option for setting the IP address -- set it to 192.168.2.250.

Bing! Printing now works from everywhere; Macs, iPads (Airprint), even the phones.

Some other minor tidbits:

  • The Mac drivers package only installs on Mac OS 10.7 and higher, but Mom had an older 10.6.8 machine. However, you can download individual components (CUPS printer driver and Twain scanner driver) and they do install.
  • With the scanner driver installed, you can use Image Capture to control the printer and scan, even from a 10.6.8 machine.
  • You can print from a 10.5.X machine using the generic PCL 6 CUPS driver, but not over the network; you have to use the USB connection.

I'm probably going to try and get remote email printing working at some point, if so I'll update this post.

Brother Support Pages for Printer

Sunday, December 28, 2014

The Compex Cubes Puzzle

Often during the holidays, I do a little programming project based on something that just strikes my fancy. For example, one year I merged a bunch of dictionaries and then ran the words through DNS to see if they were available as domain names.

This year, my Mother -- Provider of Perfect Presents -- gave one of my sons an interesting puzzle called the "Complex Cube". It has 54 T-shaped wooden parts, each made of 4 unit cubes, and the challenge is to assemble them into a 6x6x6 cube.


I played with it a little bit, and soon got to the point where I realized it might be faster to write a program to analyse the problem, so given that I am a lazy person, I wrote a python script to solve it. It's really pretty simple, you just start at the bottom and scan across the rows and columns in each row, placing blocks in each empty position.

There are some easy optimizations you can do, like realizing there are only 12 possible block rotations you need to try because of assumptions you can make about positions you have already filled in, but the script still took anywhere from 5 minutes to 5 hours to generate a solution, even after doing some cute hacks to make it faster (like not using recursion, but keeping track of things with a state stack).

Then I realized that if I limit the search to solutions that are reflectively symmetric, the search space becomes much smaller, because I'm only solving a puzzle with 27 blocks instead of 54. Solution time goes down to under a minute and the solution looks nicer.

However, the output left a little to be desired...

Level 1
+-------------+
| P I N N N Q |
| L I M N H O |
| E I J K H H |
| E E G F H D |
| E A F F F D |
| A A A B C D |
+-------------+
Level 2
+-------------+
| P P M Z Q Q |
| L I M K X O |
| L J J K X O |
| V W G K X Y |
| T U G B C D |
| R R R B C S |

+-------------+
 
...and so on. So I got the idea of playing around with the Processing language to see if I could visualize it better. The result was a little script that displays the cube in 3D, lets you rotate and zoom it, and animates the solutions.

Needless to say, it took me twice as long to write the Processing visualization script as it did to write the Python solvers, and it probably took me twice as long to write the solvers as it would have taken to just solve the puzzle by hand.

But then, as I said above, I'm lazy... :)

You can find the scripts here if you'd like to play with them. Processing is built on top of Java and quite fun to play with.

Sunday, September 7, 2014

A Google Apps Sheet for STV Elections

I've been using Google apps like Sheets in my Kickstarter project, but one thing Sheets doesn't do is complex surveys. While you can link a survey to a sheet, the survey question types are pretty basic, and in particular it does not let you do a ranked survey (in other words, "here are N options, pick any number of them that you like and place them in order of preference.")

When I was on the EVE Online Council of Stellar Management, I became quite the election-systems nerd, because I was pushing hard for a reform of the election system. So just for fun, I decided to see if I could implement a Multiple-Choice Ballot in Google Apps.

What I ended up was a sheet with a bunch of embedded scripts that lets you:

  • Create a Multiple-Choice Ballot with optional additional questions (radios, dropdowns and fields) and voter validation.
  • Store the results in a sheet.
  • Export the results in the standard .blt ballot format used by many election systems.
  • And best of all, run the election using the Simple-STV and Wright-STV systems.
You can find the template sheet at http://stv.madoverlord.com/. Just make a copy of it in your own Google Drive and start playing with it.

Enjoy!

Wednesday, February 5, 2014

Clever Combining CSV Files to Cure KickStarter Conundrums

I recently ran a successful KickStarter for a Bubblegum Crisis Ultimate Edition (you can still sign up here), and in the aftermath ran into an annoying problem.

KickStarter lets you run a Backer Survey after the project is funded, and that's how backers tell you things like their names, addresses and so on. A typical KickStarter will have many different "support levels" providing different benefits.

Annoyingly, KickStarter forces you to design a survey format for each individual support level, with no way of cloning surveys. But what really got me steamed was the discovery that when you export the survey results, you get a CSV file for each survey, and the format of that CSV file depends on the items in each individual survey.

That makes it a royal pain in the ass to import the data into your own database -- I mean, I had 38 CSV files, each with its own ordering of fields. Plus given that people take their time filling out the surveys (2 months later and they're still trickling in), I was going to be doing the import multiple times.

To solve this, I wrote a quick little python script, combine-csv.py, that reads in an entire directory of CSV files, extracts all the unique field names from them, and then outputs a single file containing all the rows of data, with a column for each unique field. In cases where a row does not have an entry for a particular field, it gets a blank entry. Also, if a file contains multiple columns that have the same name, the data in them is combined into a single column, separated by the | delimiter.

Added: optional count field name; if present, each unique line is emitted only once, with the last field being a count of the number of occurrences. If not present, the source file name is appended.

You can find it here: combine-csv.py.zip

You use it like this:

python combine-csv.py [source directory] [destination csv file] {optional count field name}

Enjoy!

Update: I also whipped up a standalone AllCSV app that does the same thing; available for both Mac and Windows. It does not currently do the occurrence counting.

Tuesday, September 3, 2013

Voronoi-tesselated Klein Bottle

OK, I admit I've caught the bug of messing around with Math objects and making pretty printable objects from them.

This is my take on the Klein Bottle, inspired in large part by Dizingof's perforated bottle. Mine, however, uses the Voronoi tesselation to perforate the bottle. The various files are available on Thingiverse if you'd like to mess with it.


It was made by using ViaCad and MeshLab, as follows:

* In Viacad, I created 3 surfaces: the bottle body, the neck, and a patch that covers the intersection of the bottle and the neck. The bottle and neck were exported as very fine meshes, the patch as a regular resolution mesh.

* In MeshLab, I imported the bottle and the patch.

* Filters > Color... > Disk Vertex Coloring to color the Bottle using the points in the patch, adjusting the parameter until the patch was fully colored.

* Render > Color > None and then Filters > Selection > Select Faces by Color. Select RGB mode, set the sliders all to 1, turn on Preview, and then tune down the R value until you get everything selected but the patch area.

* Filters > Selection > Invert Selection, then Filters > Selection > Delete Selected Faces and Vertices to make the hole. It will be a bit bigger than the patch, but this is what you want, it makes for a nice effect.

* This is a good point to save your work. MeshLab gets crashy if you do too much, so make a lot of checkpoints. As a general rule, if something is crashing MeshLab -- or not giving proper results -- get things to the point just before the crash, save, then restart MeshLab and import the saved mesh.

* Turn off display of the patch, then Import the Neck. If the neck has a different shade from the bottle, then Filters > Normals > Invert Faces... to change the normals.

* Filters > Mesh > Flatten... to combine the two meshes.

* One problem you may run into is that the Voronoi Tesselation seems to mess up at the join between the neck and the bottle. To avoid this, use Filters > Cleaning > Merge Close... and set a pct of 8-10 (Try 8, if it doesn't work, backtrack and try bigger numbers.

* Save the results and then do the Voronoi tesselation. See my Voronoi Tetrahedron for the details on how to do that.

Monday, August 26, 2013

Voronoi-tesselated Tetrahedron

I'm enjoying playing with mathematical objects and printing them. Yesterday I created a Voronoi-tesselated tetrahedron. Halfway through the print I dropped some bells into the central cavity to make a baby-rattle. The object is now on Thingiverse if you want to make one.



My starting point was a blog post showing how to do Voronoi Tesselations in MeshlabHowever, Meshlab is a bit crashy, so I had to do some experimentation. Here is the general procedure I came up with -- hope it helps you create some nice objects.

Launch Meshlab

Make sure Selected Face Rendering is on.. It's the icon with red in it to the right of the light bulb icon.

File > Import Mesh to import your nice fine WATERTIGHT mesh (otherwise, expect bad things to happen), or Filters > Create Mesh Layer > ... to start with a primitive (like the Tetrahedron)

Before you go further, you need to make sure that your object is properly aligned to the XY plane. Click the Wireframe icon (next to the dots icon, then rotate the model (left-click drag it) until there are 3 points that you want to be on the base of your model located where you can drag a marquee over just those points, then click the Select Points icon (next to the Rabbit icon) and do just that.  Then use Filters > Normals... > Transform: Rotate to fit on a plane, check both options and apply.

If you don't have enough vertexes (100-300k is good), use Filters > Remeshing > Subdivision: Midpoint (for primitives) or Filters > Remeshing > Sudivision: Butterfly (for more complex objects) to add triangles. Always set Iterations to 1, you don't want to get too many triangles. Also Edge Threshold to 0.

Click Layers icon (looks like a stack of paper) to show layers.

Filters > Sampling > Poisson-disk Sampling. Number of Samples = 50 to 60. Click Apply, and a new layer will appear in the layers list.

Click on your mesh object in the Layers list so that it is hilighted in yellow. After the sampling, it won't be.

Filters > Color Creation > Voroni Vertex Coloring. Check BackDistance. Click Apply. Your object will get nicely colored with Voroni cells.

Render > Color > None. The colors will disappear. You do this so that the next step is easier to see.

Filters > Selection > Select Faces by Vertex Quality. Check Preview. Slide Max Quality all the way to the right. Slide Min Quality left until you get nice thin borders -- but not too thin. Click Apply.

If the lines are not GREY, use Filters > Selection > Invert Selection. Click Apply. Lines will go grey, areas between them will be red.

Filters > Selection > Delete selected Faces. Now you have a holed, but flat, object.

Filters > Smoothing > Laplacian Smooth with Iterations = 3 to 5 will give you much smoother lines.

This is good place to save a checkpoint. File > Export Mesh AS... NOT File > Export Mesh, which will copy over your old file!!! Save it as a .stl.

Filters > Remeshing > Uniform Mesh Resampling. Precision 1%, Offset 53%, check Absolute Distance. Now wait a bit, and you'll get your thick version of the object. If Meshlab crashes, you probably had a bad initial mesh, it's quirky -- and you're screwed.

In the Layers panel, click on the eyes next to your original object and your Poisson samples to turn them off. You'll only see your new offset mesh.

Filters > Remeshing > Quadric Edge Collapse Decimation. Set the target to be .75 of the original number of vertexes. This smooths things out.

Repeatedly apply Filters > Remeshing > Curvature Flipping Optimization until the object is not getting any better (it may settle down to toggling between two states).

Now you want to increase the number of triangles and make them smooth. Alternate between these two:

Filters > Remeshing > Subdivision: Butterfly, Iterations = 1, Edge Threshold = 0.

then,

Filters > Smoothing > Taubin Smooth

When you get to the number of vertices you think you need, Export As... and save your STL.

Oh, in the case of primitives, they will only be 1mm in size, so use Filters > Normals... > Transform: Scale to make them bigger before saving. The limit is 10x, so maybe do a 10x and a 2x = 20x.