MathJax

SyntaxHighlighter

Highlight

Custom CSS

Wednesday, November 3, 2010

Showing transitive dependencies with Leiningen

When you specify a dependency on a Java library in Leiningen, you might pull in all sorts of random transitive dependencies (eg there are no less than three logging frameworks/facades that could be pulled in). Figuring out which artifacts pull in those transitive dependencies is a snap in Leiningen; just do this:

# Generate a pom for Maven to parse
lein pom
# Create a dependency tree with Maven
mvn dependency:tree

You'll get some output that looks like this:

[INFO] +- org.clojure:clojure:jar:1.2.0:compile
[INFO] +- org.clojure:clojure-contrib:jar:1.2.0:compile
[INFO] +- org.clojars.sids:htmlcleaner:jar:2.1:compile
[INFO] +- commons-lang:commons-lang:jar:2.5:compile
[INFO] +- commons-io:commons-io:jar:1.4:compile
[INFO] +- clj-file-utils:clj-file-utils:jar:0.1.2:compile
[INFO] +- log4j:log4j:jar:1.2.15:compile
[INFO] +- lein-daemon:lein-daemon:jar:0.2.1:compile
[INFO] |  \- commons-daemon:commons-daemon:jar:1.0.1:compile
[INFO] +- org.apache.hadoop:hadoop-core:jar:0.20.2-dev:compile
[INFO] |  +- commons-logging:commons-logging:jar:1.0.4:compile
[INFO] |  +- org.slf4j:slf4j-api:jar:1.4.3:runtime
[INFO] |  +- org.slf4j:slf4j-log4j12:jar:1.4.3:runtime
[INFO] |  +- commons-httpclient:commons-httpclient:jar:3.1:runtime
[INFO] |  +- commons-cli:commons-cli:jar:1.2:compile
[INFO] |  +- commons-net:commons-net:jar:1.4.1:runtime
[INFO] |  |  \- oro:oro:jar:2.0.8:runtime
[INFO] |  +- javax.servlet:servlet-api:jar:2.5:runtime
[INFO] |  +- org.mortbay.jetty:jetty:jar:6.1.14:compile
[INFO] |  |  +- org.mortbay.jetty:jetty-util:jar:6.1.14:compile
[INFO] |  |  \- org.mortbay.jetty:servlet-api-2.5:jar:6.1.14:compile
[INFO] |  +- org.mortbay.jetty:jsp-2.1:jar:6.1.14:compile
[INFO] |  |  +- org.eclipse.jdt:core:jar:3.1.1:compile
[INFO] |  |  \- ant:ant:jar:1.6.5:compile
[INFO] |  +- org.mortbay.jetty:jsp-api-2.1:jar:6.1.14:compile
[INFO] |  +- commons-el:commons-el:jar:1.0:runtime
[INFO] |  +- org.apache.ant:ant:jar:1.7.0:runtime
[INFO] |  |  \- org.apache.ant:ant-launcher:jar:1.7.0:runtime
[INFO] |  +- net.java.dev.jets3t:jets3t:jar:0.6.1:runtime
[INFO] |  \- xmlenc:xmlenc:jar:0.52:runtime
[INFO] \- clj-http:clj-http:jar:0.1.1:compile
[INFO]    +- org.apache.httpcomponents:httpclient:jar:4.0.1:compile
[INFO]    |  \- org.apache.httpcomponents:httpcore:jar:4.0.1:compile
[INFO]    \- commons-codec:commons-codec:jar:1.4:compile

Easy peasy.

Tuesday, November 2, 2010

Tips for ignoring files with Git

There are 3 different ways to ignore files in Git:

  1. Global: create a .gitignore file in your home directory
  2. Per project: create a .gitignore file in the project's root source directory
  3. Per project: create a .git/info/exclude file in the project's hidden git directory

Update

Well... okay, so really, there are 4 ways, but the 4th way I haven't found a good use case for.

Amazingly, this flexibility in design does have a purpose (I don't believe the original intention was for the developer to close his eyes and pick a gitignore to stick files in randomly). The granularity offered in this design allows you to have a clear separation of what is generated by the build, and what is ignored by personal preference. For example, you can commit a .gitignore that only ignores logs and test output, while using a global gitignore file to ignore your vim or emacs swap files.

If you don't pollute your project space with files or data that may not be useful to everybody, it's easier for new developers to jump onto your project and figure out what's going on without wading through the fluff. For example, here's a good reason for not checking in your .classpath or .project files in Eclipse. Going one step further, it's probably not even a good idea to commit a gitignore file that names them.

On a project with enough people, it's simply not feasible to commit a .gitignore that names swap files for every editor, project files for every IDE, DS_Store for people who only use macs, thumb.db files for people who only use windows, and so on. For smaller projects, it doesn't hurt anything, but there are other places where this information could possibly be stored. Here is what I propose for each method of ignoring files:

  1. Global .gitignore should ignore your favorite editor's swap files, the .DS_Store on a mac, or thumbs.db on windows; basically anything you personally need ignored for every project.
  2. Per project .gitignore should ignore only files generated by the build (logs, test output, build targets).
  3. Per project .git/info/exclude should ignore files you personally need, but only for this project. For example, if you are normally an Eclipse user, your global .gitignore should contain the .classpath and .project files, but for a particular project where you must use Netbeans, consider placing the nbproject directory in this file.

Saturday, October 23, 2010

Installing VimClojure 2.2.0

I spent a good morning trying to figure out how to set this darned thing up so I could write some Clojure, so I'm sure as hell going to document it in case somebody else wants to know (or I get one of those mind erasing kits and forget how to do this)!

Install the VimClojure plugin

  1. Download the VimClojure script here.
  2. Unzip vimclojure-2.2.0.zip in your ~/.vim directory, but take the files in the bin directory and put them in your PATH (in particular, you'll want the ng-server script).
  3. Add the following to your ~/.vimrc: let vimclojure#WantNailgun = 1

Install the VimClojure Nailgun client

  1. Download the appropriate sources for VimClojure 2.2.0; they are located here.
  2. Unzip the sources and enter the vimclojure-nailgun-client directory.
  3. Run make and move the generated binary into your PATH.

Install the VimClojure Nailgun server

You can get these from Clojars using Leiningen or Maven. For example, if you run lein deps on a simple project like the one below, it will download the VimClojure server:

(defproject vimclojure-test "1.0.0-SNAPSHOT"     
  :dependencies [[org.clojure/clojure "1.2.0"] [org.clojure/clojure-contrib "1.2.0"]]
  :dev-dependencies [[vimclojure/server "2.2.0"]])

Set up your environment to run the Nailgun server

Export the following environment variables, telling the ng-server script where to find the server, Clojure, and the contrib libraries. Here's what mine looks like:

export CLOJURE_EXT=/opt/clojure:/opt/clojure-contrib/target:$M2_REPO/vimclojure/server/2.2.0

Run the server and start Vim

Finally, you can run the ng-server script, and write some Clojure with Vim!

Monday, September 20, 2010

More considerations for using jQuery 1.4.2 in Firefox 3.5 extensions

I wrote about these considerations in an earlier post, but that post only touched on the efforts involved to actually get it working in the first place. There are more security issues to consider once it's actually done (no matter which route you've taken to get things working).

As background for this post, you are invited to read the MDC documentation about XPCNativeWrapper, but it is not necessary. Suffice it to say that it is not safe to manipulate DOM elements within privileged (aka chrome aka extension) code. For example, if I, as a malicious web page author, have overridden document.getElementById to do something nasty (or even something benign like alert("hi");), when you use the document object as a context in jQuery, you'll get my behavior instead of the intended selection behavior. This problem is circumvented by wrapping unsafe DOM elements from my webpage in a wrapper that does not allow unsafe function calls (hence the XPCNativeWrapper).

The problem is that the wrapper limits access to unsafe properties, meaning that some properties that jQuery could expect, could be missing (depending on what you are doing). A tempting alternative is to simply reference the wrappedJSObject property of the wrapper, which will get you the underlying object, but that opens you up to a whole slew of injection attacks (so don't do it).

I don't really have a solution for this either, outside of just making sure you only access what you need. In my mind though, I think the best solution is to simply not use jQuery at all.

References

Wednesday, September 8, 2010

Converting e-books to PDF

The djvulibre-bin package allows you to convert djvu files in Debian. You can covert these to ps files using djvups, and then use ps2pdf to convert them to pdf form.

CHM files can be converted using chm2pdf; just pass in the --book or --webpage switch and you're good to go.

Time to normalize my e-book collection...

Tuesday, August 10, 2010

Maven, Spring, Hibernate, Struts2, same old same old.. and what? Scala!

I recently had a project using the standard J2EE technology stack, but with an added twist of using Scala (in addition to Java). It was relatively smooth, with a few gotchas, which I will note here.

Lack of IDE support

I enjoy using vi much more than any of the Big Three IDEs for Java, so it wasn't as much of an issue for me, but my teammate was using IDEA, and he was having all sorts of problems (one reason is because one of the Scala plugins for IDEA seems to be completely busted as of this writing). I did try researching the plugins for other IDEs, and I found the Eclipse plugin to be the most sensible (unsurprising, as most of the developers of Scala seem to be using Eclipse).

If you have Scala code that depends on Java code, it's not much of a problem (as you can just compile the Java first, then compile the Scala). On the flip side, if both Scala and Java code depend on each other, you'll have trouble in the form of red squiggly underlines in Netbeans and IDEA that you simply cannot turn off.

Luckily though...

Maven support works beautifully

You won't have any trouble building your project from the command line with Maven - even if there are you have Scala and Java code with interdependencies. Here's what I added to my POM, updated for Scala 2.8.0, to make the whole thing work:

<plugin>
  <groupId>org.scala-tools</groupId>
  <artifactId>maven-scala-plugin</artifactId>
  <version>2.12</version>
  <configuration>
    <args>
      <arg>-deprecation</arg>
      <arg>-unchecked</arg>
    </args>
  </configuration>
  <executions>
    <execution>
      <id>compile</id>
      <goals>
        <goal>compile</goal>
      </goals>
      <phase>compile</phase>
    </execution>
    <execution>
      <id>test-compile</id>
      <goals>
        <goal>testCompile</goal>
      </goals>
      <phase>test-compile</phase>
    </execution>
    <execution>
      <id>process-resources</id>
      <phase>process-resources</phase>
      <goals>
        <goal>compile</goal>
      </goals>
    </execution>
    <execution>
      <id>process-test-resources</id>
      <phase>process-test-resources</phase>
      <goals>
        <goal>testCompile</goal>
      </goals>
    </execution>
  </executions>
</plugin>

If you put your sources in src/main/scala, IDEs should be able to pick them up without a problem.

No more generating getters and setters

In Java, you'd navigate through something like 5 menu options so the IDE could generate 20 lines of boilerplate to make your class a "JavaBean". The nice folks who wrote Scala understand your pain and offer the @BeanProperty annotation:

import scala.reflect.BeanProperty
import java.io.Serializable
import java.lang.{Long => JLong}
import java.lang.{Integer => JInt}
import javax.persistence._

@Entity 
@Table(name = "reviews")
class Review extends Serializable {
    @BeanProperty
    @Id
    @GeneratedValue(strategy = GenerationType.AUTO)
    var id: JLong = _

    @BeanProperty var rating: JInt = _
    @BeanProperty var content: String = _
}

That's a standard Hibernate entity, written in Scala (Hibernate is none the wiser). The @BeanProperty annotation generates the getX and setX methods for you, so that Hibernate will be happy (the regular x and x_= Scala methods exist also).

Hibernate really only wants the Java classes, dammit!

Notice in the above example that Hibernate will barf if you try to make your id a scala.Long instead of java.lang.Long. The same holds for other types like Double and Float (Integer is Int in Scala, but I made the import alias just to be explicit).

Hibernate also really wants your collections to be Java collections instead of Scala collections. You can still work with Scala collections, but you'll have to import implicit conversions for them:

import scala.collection.JavaConversions._

For the performance wary, all that does is wrap the Java collections so you can interact with them in a more idiomatic way (it won't copy the collection).

Struts2

Struts seems to work quite well with Scala. Stacktraces will even show the specific line (in the Scala source) where the error occurred. The only minor gotcha I had was that when your Action classes extend ActionSupport, the SUCCESS, ERROR, etc constants are not in scope. You'll have to import them from Action directly:

import com.opensymphony.xwork2.Action._

Conclusion

Opinions on the project varied on our 2 person team. I was able to crank out much more code at a faster pace, but my coworker struggled a lot with the IDE support. On the flip side, integrating Scala into a Java project was a heck of a lot smoother than I thought.

Monday, July 19, 2010

Fix Java application focus issues by upgrading to wmii 3.9

I've been using wmii as my window manager for quite a while now, and I like it a lot. However, the latest version in Debian Lenny is 3.6, and it's quite dated. I was made painfully aware of this fact when I discovered that Netbeans (yea, I know; I'm forced to use it at work) would not regain focus after opening up a floating menu. This little annoyance drove me nuts and caused me to upgrade to wmii-3.9, which could've been a fairly painless process (but I like to make things hard on myself).

Firstly, installing the newer wmii is a relatively simple task: you'll want to grab the 3.9.2 sources from here (don't check them out of mercurial; it will only make the process more painful for you). Then untar the tbz and issue the following commands in the source directory:

make deb-dep
make deb

The deb will be built for you in the directory above, and you can install it at your leisure.

Secondly, configuring wmii could be a simple task, but I thought I'd try out this new fangled Ruby gem for configuring wmii. It was a mistake.

There's no documentation on which version of the gem the bundled config.yml is to work against, nor is it mentioned whether or not I should be using Ruby 1.8.7 or 1.9.1. I would assume that it would work against both, but after hours of suffering through incessant broken pipe errors and trying to optimize the configuration (switching views taking almost half a second - wtf?!), I decided to just go with the bundled wmiirc configuration.

As it turns out, the 3.9 configuration has changed, so my old wmiirc didn't work. Upon closer examination, the changes weren't that huge, and I was able to port my old settings over pretty easily.

You may see them here.

Update

Woops. I recall the instructions say to do make deb, but that doesn't work. Try this instead:

make deb-dep
dpkg-buildpackage -us -uc -b

Wednesday, July 7, 2010

Setting up my X100e with Debian Sid

I had some fun adventures putting Debian sid on my X100e! I'm eagerly awaiting the release of the 2.6.35 kernel (which has acpi support for the X100e amongst other yummy goodies), so I decided to dist-upgrade to sid (and use the 2.6.32 kernel in sid while waiting). Oh! But what wonderful adventures there were to be had!

First of all, wmii was totally busted as it wouldn't respond to any commands involving my mod key (which is alt). I noticed (using xev) that shift+alt did not register properly, so of course wmii wouldn't respond. Here's the fix (don't ask me what it means):

setxkbmap -symbols 'pc+us+inet(evdev)+level3(ralt_switch)+ctrl(swapcaps)+compose(lwin)'

Then I discovered that I couldn't use the middle mouse button to scroll with the trackpoint. Since the xorg.conf file has mostly gone the way of the dodo, here are the magic xinput commands to get that working:

xinput set-int-prop 'TPPS/2 IBM TrackPoint' 'Evdev Wheel Emulation' 8 1
xinput set-int-prop 'TPPS/2 IBM TrackPoint' 'Evdev Wheel Emulation Button' 8 2
xinput set-int-prop 'TPPS/2 IBM TrackPoint' 'Evdev Wheel Emulation Timeout' 8 200
xinput set-int-prop 'TPPS/2 IBM TrackPoint' 'Evdev Wheel Emulation Axes' 8 6 7 4 5

Now, I just take all that stuff and jam it into my xinitrc, then I never think about what any of it means and use wmii happily.

Of course, I still had to build the fglrx kernel modules and modify the xorg.conf to make the video card sing:

Section "Device"
 Identifier "Radeon 3200 HD"
 Driver "fglrx"
 BusID "PCI:1:5:0"
 Option "VideoOverlay" "on"
 Option "OpenGLOverlay" "off"
EndSection

Section "Screen"
 Identifier "Thinkpad Screen"
 Monitor "Thinkpad LCD"
 DefaultDepth 24
EndSection

Section "Monitor"
 Identifier "Thinkpad LCD"
 Option "DPMS"
EndSection

Section "ServerLayout"
 Identifier "Thinkpad Layout"
 Screen "Thinkpad Screen"
 Option "AIGLX" "true"
EndSection

Section "DRI"
 Mode 0666
EndSection

Section "Extensions"
 Option "Composite" "enable"
EndSection

Critical result: HAPPY!

Friday, June 4, 2010

Getting thinkpad_acpi to work in a X100e on Debian Lenny

When I booted up my X100e, I got a message that said thinkpad_acpi: Not yet supported thinkpad detected. To fix this, I had to apply a patch to the linux kernel. I was already using the 2.6.30-bpo.2-amd64 kernel from lenny-backports, so I could just copy my old kernel configuration over (because I'm too lazy to tweak what comes with the stock kernel).

There's a nice newbie friendly tutorial that teaches you how to use make-kpkg, but the skinny is this:

cd /usr/src/linux
cp /boot/config-2.6.30-bpo.2-amd64 .config
make oldconfig
fakeroot make-kpkg clean
fakeroot make-kpkg --initrd --append-to-version=.20100604 kernel_image

Incidentally, the only file I needed to change was thinkpad_acpi.c, and it is a module, so if anybody knows how I can do this without compiling the entire kernel, I'd love to know.

Tuesday, May 25, 2010

Transaction behavior in Firefox 3.0 SQLite API

Small gotcha if you are writing a Firefox 3.0 extension: while SQLite lets you do nested transactions, multiple concurrent transactions, and checkpoints, the Firefox API doesn't fully support those. The beginTransaction, commitTransaction, and rollbackTransaction methods in mozIStorageConnection fully expect only one transaction to be active at a time (you'll get an exception if you try to nest transactions by beginning a transaction while another is active).

Update

For 3.5, it looks like this is still true; there is even a note that says the underlying engine does not support nested transactions (possibly an older version of SQLite is in use.. darn).

Wednesday, May 12, 2010

Storing Numbers in nsIPrefService

Tip of the day: don't use nsIPrefService to store JavaScript Number objects when writing a Firefox extension. Take a look at what happens in XPCShell:

js> var prefService = Components.classes["@mozilla.org/preferences-service;1"].
    getService(Components.interfaces.nsIPrefService);
js> var branch = prefService.getBranch("foo");
js> Date.now();
1273727558711
js> branch.setIntPref("date", Date.now());
js> branch.getIntPref("date");
-1877723439

The reason for this is that while JavaScript Number objects do not overflow, underlying ints in the C++ code that nsIPrefService is implemented in certainly will. I really should've been tipped off by the setIntPref method name =P

Monday, May 10, 2010

Peeking inside Components.classes for Firefox 3.5.8

For the longest time, I had wondered what kind of magical smurfs, krakens, and leprechauns lived inside of Components.classes; but today I felt like sort of an idiot because I realized I could just do this:

echo "for(var p in Components.classes){print(p)}" | xpcshell | sort > cc.txt
echo "for(var p in Components.interfaces){print(p)}" | xpcshell | sort > ci.txt

The xpcshell function is just a little bash function I have for running XPCShell (on Debian, XULRunner binaries are located in /usr/lib/xulrunner-1.9.1; they may vary for the reader):

function xpcshell {
  local DIR=/usr/lib/xulrunner-1.9.1
  $DIR/run-mozilla.sh $DIR/xpcshell $@
}

This is a pretty good tool for testing extension code out, as long as you don't want to do anything with a ChromeWindow; it'll crash if you try to get fresh with it like that!

$ xpcshell
[loading 'xpcshell.js'...]
js> var app = Components.classes["@mozilla.org/appshell/appShellService;1"].
  getService(Components.interfaces.nsIAppShellService);
js> var uri = Components.classes["@mozilla.org/network/io-service;1"].
  getService(Components.interfaces.nsIIOService).
  newURI("http://developer.mozilla.org", null, null);
js> app.createTopLevelWindow(null, uri, 0, 0, 0, null);

(process:8032): Gdk-CRITICAL **: gdk_screen_get_rgb_visual: assertion `GDK_IS_SCREEN (screen)' failed
/usr/lib/xulrunner-1.9.1/run-mozilla.sh: line 131:  8032 Segmentation fault      "$prog" ${1+"$@"}

Sources

https://developer.mozilla.org/en/XPCOM_Interface_Reference/nsIAppShellService
https://developer.mozilla.org/En/NsIURL

Thursday, April 22, 2010

Considerations for using jQuery 1.4.2 in a Firefox 3.5 extension

Due to certain project requirements, I found myself using jQuery within a Firefox 3.5 extension, and boy was it a doozy. The problem is that most Firefox extensions just dump a bunch of code inside the script tag of an overlay on top of browser.xul (see more discussion here). The ramifications of this are that any var you declare is global to the browser and to any other extension the user has installed. Some extensions, like Firebug, get around this by prefixing every global variable with FB_, but this solution will not work with jQuery.

If I decide to include jQuery in my overlay like so:

<script src="chrome://myextension/content/jquery-1.4.2.js"></script>

...this leads to a variety of problems. Firstly, jQuery will automatically set the window.jQuery and window.$ variables in the chrome window, overriding the values that were already there. This is not a terrible problem for $ (which jQuery is nice enough to give it back to you via a call to jQuery.noConflict()), but the jQuery variable is overridden as well. This poses a problem for other not-so-nice extensions that actually use jQuery in this rude manner. For example, if I included jQuery 1.4.2 in my extension and you included jQuery 1.3.2, it would be a crapshoot to determine whose jQuery gets loaded (depends on the overlay loading order).

A second problem for jQuery 1.4.2 is that it actually manipulates the DOM to test for the availability of certain features, which is a big no-no for overlays. The DOM isn't actually available in a XUL document until after all of the overlays have loaded (after all, the overlays themselves dictate elements that should be in the DOM). If you try to access the DOM in an overlay, your overlay will silently not be loaded. Incidentally, all JavaScript in overlays should be executed by an event handler to avoid this problem:

window.addEventListener(
  "load",
  function () {
    // Do stuff after the overlay has loaded
  },
  false
);

One horrific solution to this is to load jQuery in a load handler, and edit the actual jQuery source to stop it from installing itself onto window. For the sadists out there, here's what it would look like:

window.addEventListener(
  "load",     
  function () {
    Components.classes["@mozilla.org/moz/jssubscript-loader;1"].
      getService(Components.interfaces.mozIJSSubScriptLoader).
      loadSubScript("chrome://myextension/content/jquery.js");
  },
  false
);

Of course, chrome://myextension/content/jquery.js would have to be a modified version of jQuery that simply sets the jQuery and $ in the current scope, rather than on window itself. The details of such a hack are omitted (though it's simply a 2 line change within the jQuery source). This solution; however, still allows jQuery itself to run free and wild, doing who-knows-what to the DOM after it has loaded, which is fine and dandy for a webpage but potentially ... explosive for a chrome window.

Another solution is to get jQuery loading within a Firefox code module. Code modules are "sort of" like Google Chrome's content scripts in that any code in a code module will execute in its own context (thus it is unable to stomp on code in overlays unless you explicitly tell it to), but Firefox code modules do not give you access to any sort of DOM, so loading jQuery naively will cause exceptions to be thrown.

So far, I have not found any acceptable solution to this problem. The "cleanest" possible solution may be a jsdom style fake DOM (taking advantage of the Firefox internals to provide implementations such as nsIDOMDocument, and nsIXMLHttpRequest) to fool jQuery, but that's a lot of work.

A poster on the jQuery forums, chewie1024, suggests giving jQuery a real live browser window within a code module by simply giving it a reference to the main browser window. This solution is nice and simple:

var EXPORTED_SYMBOLS = ["jQuery", "$"];

var windowMediator = Components
  .classes["@mozilla.org/appshell/window-mediator;1"]
  .getService(Components.interfaces.nsIWindowMediator);            
var enumerator = windowMediator.getEnumerator("navigator:browser");
if (enumerator.hasMoreElements()) { 
  var window = enumerator.getNext();
  var location = window.location;
  var document = window.document;
  break;
}

// jQuery source follows here...

...however, you'll still have to hack jQuery to make it not install itself on the window object, and you'll have to live with the fact that jQuery will muck around with the DOM on that window. On the flip side, you'll have jQuery in a code module that you can import into any overlay, in any scope you like.

One thing to note is that in the above solution, jQuery will keep a reference to that main window, and anything you do with jQuery will be done on that window by default. That is, make sure that you pass in a context to jQuery or it will be operating on the wrong thing. Another thing to note is that the window that jQuery keeps a reference to can be closed and some of its members could be garbage collected. Unknown behavior will result if that is the case, so keep an eye out if you use this solution (because the symptoms will be seemingly random).

In conclusion, I have no satisfactory solutions to this problem, so if anybody knows of one, please send me a message.

Monday, April 19, 2010

Maven: building a JAR with all the dependencies

One of my colleagues has requested this information of me a few times; in retrospect, it is rather a complicated thing to have to do to achieve the desired effect. Stick this into your pom.xml under the build section; it will create the JAR along bundled with all the dependencies during the package phase:

<build>
  <plugins>
    <plugin>
      <artifactId>maven-assembly-plugin</artifactId>
      <configuration>
        <appendAssemblyId>true</appendAssemblyId>
        <descriptorRefs>
          <descriptorRef>jar-with-dependencies</descriptorRef>
        </descriptorRefs>
        <archive>
          <manifest>
            <mainClass>my.package.Main</mainClass>
          </manifest>
        </archive>
      </configuration>
      <executions>
        <execution>
          <id>make-assembly</id>
          <phase>package</phase>
          <goals>
            <goal>assembly</goal>
          </goals>
        </execution>
      </executions>
    </plugin>
  </plugins>
</build>

Sunday, April 18, 2010

Hiding XUL elements on OSX on Firefox 3.5.8

I was recently confused as to why the following code would not work in a XUL overlay:

var foo = document.getElementById("foo");
foo.style.display = "none";

In this case, the element foo was a XUL element; not HTML. Further investigation found that the above code worked on Windows and Linux builds of Firefox, but not OSX; only the following appeased the Firefox gods:

var foo = document.getElementById("foo");
foo.hidden = true;

This does what you want on all platforms; not especially obvious from the austere MDC article!

Sunday, April 4, 2010

Wireless for Thinkpad X100e

There's a bit of trickery involved in getting the wireless to work on one of those sexy X100es. lspci will give this output:

03:00.0 Network controller: Realtek Semiconductor Co., Ltd. Device 8172 (rev 10)

...but the driver you want is the RTL8192E driver from Realtek's download site. make and make install it the normal way, and stick r8192se_pci into your /etc/modules.

I had a problem with WEP and WPA2 encryption; I could connect fine but after 15 minutes or so, the connection would drop and there would be no way to reconnect. I find that WPA works fine.

Update

This didn't work from me unless I used a 2.6.30 kernel.

Transferring data from one PS3 to another

Recently, I wanted to transfer my 320GB drive from my old first generation PS3 to a PS3 slim. My initial thought was: "Oh, I'll just remove the hard drive from the old one and stick it in the new one". Ha! How misguided that effort was. The data in a hard drive is tied to that system; if not, you could just clone a bunch of drives and play your friends' PSN network games for free.

My second idea was to use the PS3's backup tool to export all my data to an external drive, and then restore from my new PS3. Unfortunately, that doesn't work either because you can't restore copy protected data and games to a different system (for the same reason as above). Here's what I ended up doing:

Deactivate the old system

I had been sharing games with my girlfriend and cousins, and I realized that if I did not deactivate the old system, my games would not work on the new one. This is done through a "hidden" menu under Account Management. This is actually a pretty important step! If I had bought videos and never deactivated the system, then I'd never be able to watch them in my new system =X

In my particular case, the old system had firmware 3.15, which still retains the OtherOS feature. By the time I wanted to deactivate my system though, the new 3.21 firmware had been released, and I didn't really want to upgrade and remove that feature. I ended up spoofing the version number so I could login and deactivate my stuff.

Use the Data Transfer Utility

So Sony realized that people might want to transfer data from an old PS3 to a new one, especially if their old PS3's are getting the YLOD. Unfortunately, their solution is an extremely annoying one: connect the two PS3's via and ethernet cable and have one transfer the data over to the other.

I didn't want to lose my copy protected save data, so I did it :( The Data Transfer Utility is extremely finicky. If you don't follow these instructions, it will not work.
  1. Both PS3's must be firmware version 3.15 or greater
  2. Connect both PS3s to the TV and then connect them via a network cable (can be CAT5 or crossover)
  3. Turn them both on and use the Data Transfer Utility from the source PS3 first; don't touch the destination PS3
  4. Follow the instructions until it tells you to set the destination PS3 to receive, then do so
  5. With about 70GB of data to transfer, this took a few hours

Use the Backup Utility

After following the steps above, my new PS3 had all my old data, but it was on the Slim's 120GB drive instead of the 320GB drive I had in my old PS3. I finally used the Backup Utility to move my data to an external drive, swapped out the Slim's 120GB drive for my larger one, and then restored the backup onto the same machine.

Conclusion

Sony needs to store my savegames in a fucking cloud like Steam.

Thursday, March 25, 2010

The Anatomy of a Firefox 3.5 Extension

The directory structure of a Firefox 3.5.x extension looks like this:

.
   |-chrome
   |---content
   |---modules
   |---skin
   |-----css
   |-----images
   |-defaults
   |---preferences
   |-locale
   |---en-US
   |-chrome.manifest
   |-install.rdf

chrome.manifest

This structure is not mandated by Firefox; you'll have to let it know in your chrome.manifest, which looks like this:

content  myextension chrome/content/
content  myextension chrome/content/ contentaccessible=yes
locale   myextension en-US locale/en-US/
skin     myextension classic/1.0 chrome/skin/
resource myextension chrome/modules/
overlay  chrome://browser/content/browser.xul chrome://myextension/content/myOverlay.xul

Old versions of Firefox allowed you to serve up images with chrome URI's (ie, starting with chrome://), but that feature was removed in Firefox 3.x. To emulate the old behavior, you'll need to add contentaccessible=yes. Since older versions of Firefox don't recognize that contentaccessible (in fact, they ignore it; see below), you'll need to put both lines in the manifest.

install.rdf

The manifest is for describing some things about your extension, but you'll have to put the rest of the information in a file called install.rdf. Here's a sample:

<?xml version="1.0"?>                            
<RDF xmlns:em="http://www.mozilla.org/2004/em-rdf#" 
     xmlns="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
  <Description about="urn:mozilla:install-manifest">
    <em:id>myextension@lousycoder.com</em:id>
    <em:name>My Extension</em:name>
    <em:version>1.0.0</em:version>
    <em:type>2</em:type>
    <em:targetApplication>
      <Description>
        <em:id>{ec8030f7-c20a-464f-9b0e-13a3a9e97384}</em:id>
        <em:minVersion>3.5</em:minVersion>
        <em:maxVersion>3.6.*</em:maxVersion>
      </Description>  
    </em:targetApplication>
    <em:aboutURL>chrome://myextension/content/about.xul</em:aboutURL>
    <em:iconURL>chrome://myextension/skin/images/logo.png</em:iconURL>
    <em:updateURL>https://www.lousycoder.com/update.rdf</em:updateURL>
    <em:creator>Me!</em:creator>
    <em:description>
      A test extension for funsies.
    </em:description>
    <em:homepageURL>http://www.writeonglass.com</em:homepageURL>
  </Description>
</RDF>

Most of the data there is self explanatory, but the version numbers can be tricky when it comes to auto update. Extension versions must follow a very specific format, and auto-update does some very complicated logic to determine which version is greater than another. For example, version 1.0 is considered the same as version 1.1-1 (because 1 - 1 = 0); yes arithmetic is conveniently done for you! Also, strings are compared bytewise instead of alphabetically. For this reason, I would advise extension version strings to only consist of numbers and periods... unless the extension is being hosted by AMO in the beta channel (in which case, version strings are ignored, and the newest version is the one last uploaded).

Overlays

XUL overlays are "merged" with whatever XUL document you are overlaying onto; in the case above it would be chrome://browser/content/browser.xul. In this way, you can add menus and/or buttons to Firefox's UI. There are special considerations for Javascript executing in the context of a browser overlay; for example, the window refers to a chrome window, and the document object refers to a XUL document, as opposed to their normal web page counterparts. Additionally, setting any global variables on window makes them available for other overlays (and extensions), so it's quite easy to clobber other extensions if you are not careful.

Modules

Code modules are executed in their own context, and the global object is not any window. In fact, the window and document objects are not even defined within code modules. There is no way to clobber variables with other extensions, as the only variables exposed by a module are the ones declared in the special EXPORTED_SYMBOLS array (see modules at MDC).

Gotchas

If you have any syntax errors in your XUL files (eg the overlay files), your extension will be shown as installed, but no errors will appear in the Error Console. If you open the XUL file directly in Firefox, via File -> Open -> file://path/to/xul/file.xul, you'll see any errors that Firefox did not report.

If you do not place the trailing slash after any path in chrome.manifest (eg chrome/content instead of chrome/content/), then Firefox will silently ignore that line in the manifest.

References

https://developer.mozilla.org/en/Chrome_Registration
https://developer.mozilla.org/en/Toolkit_version_format
https://developer.mozilla.org/index.php?title=en/Extension_Versioning,_Update_and_Compatibility
https://addons.mozilla.org/en-US/developers/docs/policies/maintenance#beta-addons
https://developer.mozilla.org/En/Code_snippets/Modules

Monday, March 22, 2010

Windows XP: How many different versions are there?

Because it's so confusing:
  • OEM
    • Usually sold with the computer
    • Certificate of authenticity usually says OEM
    • CD says "only for distribution with a new PC"
    • CD is branded by Dell or HP or etc
  • Retail (bought standalone from a store or if Windows CD says "Upgrade")
  • Branded (specifically branded by a big company)
  • Action Pack (part of MS Action Pack)
  • Volume License (licensed for multiple copies of Windows for a large business)

Friday, March 19, 2010

EeePC with an external monitor

Triumph! For the longest time, I wondered why X would never honor my DPI settings, even if i passed it the -dpi 96 command line flag. My fonts would look fine using the EeePC screen but look too small on my external monitor (or if I fiddle with my xorg.conf it'd be the other way around). It turns out I have to add sections for each monitor and name the identifiers something special to normalize that DPI:

Section "Monitor"
  Identifier  "LVDS"
  Option    "DPMS"
  DisplaySize 270 158 # 1024x600 @ 96dpi
EndSection

Section "Monitor"
  Identifier "VGA"
  Option    "DPMS"
  DisplaySize 488 304 # 1920x1200 @ 96dpi
EndSection

Thursday, February 4, 2010

A Scala quine

A Scala quine (credit doesn't go to me):

object Q extends Application{val s="object Q extends Application{val s=%c%s%1$c;printf(s,34,s)}";printf(s,34,s)}

Wednesday, February 3, 2010

Project Euler #27: Quadratic primes

Here is problem #27.

Again, judicious application of elementary number theory can reduce the search space.

First, notice that the restriction that $$f(0)$$ is a prime immediately constrains $$b$$ to be a prime.

Furthermore, $$f(b)$$ is definitely NOT a prime, as:

$$f(b) = b^2 + ab + b$$
$$f(b) = b(b + a + 1)$$

When considering a polynomial, then, $$0 <= n <= b$$, $$-1000 < a < 1000$$, and $$b$$ must be prime. We are given that for values of $$b \approx 1601$$, only 80 consecutive primes are produced, so the search space is already thinning with this very naive analysis.

Further analysis could probably tighten the bounds on $$a$$, but with just these bounds, a solution can be found in under 10 seconds.

Using a precomputed list of primes, this Ruby program finds the solution in approximately 6 seconds:

def f(n, a, b)
  n*n + a*n + b
end

def count(ps, a, b)
  (0..b).take_while { |n| t = ps.include? f(n, a, b) }.count
end

def primes
  # Grab a file of the first few primes to make calculation
  # easier.
  file = File.new("primes.txt")
  set = Set.new
  while (p = file.gets)
    set.add(p.to_i)
  end
  file.close
  set
end

b_max   = 1000
ps      = primes
bs      = ps.take_while { |b| b <= b_max }
bs      = bs + bs.map { |b| -b }
a, b, c = 0, 0, 0

bs.each do |b_i|
  (-b_max..b_max).each do |a_i|
    c_i = count(ps, a_i, b_i)
    if c_i > c
      a, b, c = a_i, b_i, c_i
    end
  end
end

puts a*b

Monday, February 1, 2010

Windows: Is it oem or retail?

I have a bunch of Windows installs, and I can't tell if they are OEM or Retail installs. Usually they are OEM, but sometimes I'm surprised. There is a quick and easy way to tell (within Windows) if it's OEM or retail:

  1. Go to My Computer -> Properties -> General
  2. Check under the "Registered to:" field and look at the product ID, which is separated into 4 groups of characters
  3. If the 2nd group is all numbers, it is Retail, otherwise it will say OEM

Project Euler #67: Maximum path sum II

Here is the question:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
   3
  7 5
 2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

A clever algorithm gives the answer in $$O(log(n))$$ time.

Consider this smaller problem:

   1
  2 3
 4 5 6

Once you arrive at element 2, you will only ever want to move to number 5, and never 4. Thus, the triangle can be reduced to this:

   1
  7 3
   5 6

Similarly, when you arrive at 3, you will only ever want to move to 6, so this is the new reduction:

   1
  7 9

So lastly, when you reach element 1, you will only ever want to move to 9, giving max sum to be 10.

This is the strategy employed to solve this problem, and here is a solution in Scala:

import scala.io.Source
import scala.Math._

val data = Source.fromFile("problem-00067.txt")
                 .getLines
                 .toList
                 .map(_.trim.split(" ").map(_.toLong))
                 .toArray

for (i <- data.length - 2 to 0 by -1;
     j <- 0 until data(i).length) {
  val left = data(i + 1)(j)
  val right = data(i + 1)(j + 1)
  data(i)(j) += left max right
}

val result = data(0)(0)
println(result)

Credit goes to Jessica Rhee for this solution.

Thursday, January 28, 2010

Screen cheat sheet

Here's my screen cheat sheet. It's simultaneous incredibly useful and ridiculous to configure. Actually reminds me of my other favorite tool with this syndrome: vim.

Configuration

I like to bind C-o instead of C-a for screen commands; I feel that C-o is easier for my old hands to hit. Here's the skinny on what goes inside that cryptic screenrc:

# Use C-o to issue commands to screen
escape ^Oo

I also bind F5 and F6 to previous and next window:

# F5 for previous window
bindkey -k k5 prev
# F6 for next window
bindkey -k k6 next

SSH

To be able to use ssh-agent within screen, you'll need this in your screenrc:

setenv SSH_AUTH_SOCK $HOME/.ssh/screen_agent
screen -t remote ssh-agent ssh-agent -a $SSH_AUTH_SOCK $SHELL

Internal commands

C-o "         Shows a list of sessions.
C-o w         Shows name of session the lower left.
C-o c         Creates a new session.
C-o d         Detaches the current session.
C-o A         Names the current session.
C-o n         Cycle to next session.
C-o p         Cycle to previous session.
C-o F         Fit the session to the current terminal.
C-o :quit     Quit all running sessions.
C-o S         Open a new region in a session.
C-o      Enter a newly created region.
C-o X         Close a region in screen.
C-o ]         Enables copy mode for copying or scrolling; use PgUp, or PgDn, etc.
              Press  to mark text for copying.
              Press  again to copy the text.
              Press C-o ] again to paste.

External commands

screen -ls    List sessions.
screen -r     Reattach a session.
screen -r foo Reattach to foo.
screen -S foo Create a screen named foo.

Conclusion

Clear as mud right?

Project Euler #15: Lattice paths

This is problem #15.

This problem can be viewed as a multi-permutation of 20 L's and 20 R's where L means "go left" and R means "go right". This way, no searching is needed and the solution can be calculated directly as:

$$\frac{(20 + 20)!}{20!20!}$$

Wednesday, January 27, 2010

Wmii

Recently, I stopped using XFCE in favor of wmii. Everybody else in the office was using a tiling window manager and I just felt left out. My C-fu and Haskell-fu just isn't strong enough to worry about both language syntax and window manager configuration so both dwm and xmonad were out the door. I was quite pleasantly surprised that I could use whatever language (including bash) to configure wmii. As proof, here is a snippet from my wmiirc that controls what shows up in the status bar:

status() {
  echo -n 'Wlan0:' $(/sbin/iwconfig wlan0 | sed 's/ /\n/g' | grep Quality) '| '
  echo -n 'Temp:' $(~/.wmii-3.5/temp) '| '
  echo -n $(acpi -b | sed 's/.*, \{0,2\}\([0-9]\{1,3\}%\),.*/Bat: \1/') '| '
  echo -n $(date +"%a %b %d %I:%M%p")
}

The temp script is something I wrote and placed in my .wmii-3.5 directory (incidentally, scripts placed in there will show up when pressing mod-a).

Navigation

The commands for navigating between created windows is very familiar, as they are the same keys used for navigation in vim. Moving the windows is also the same; they just involve holding another modifier key. In addition, wmii is pretty good about which windows should be floating, and which windows should not be. I'm quite pleased with the switch.

Autostart

One initial hurdle was that I was a little confused about how to autostart applications in wmii, but in retrospect I feel dumb because its ridiculously simple; just put the apps you want in your wmiirc. Here's what I have:

# Swap capslock and control
setxkbmap -option ctrl:swapcaps
# Set mouse acceleration to 1.0
xset m 1
# Run pidgin (if not already running)
[ "`ps aux | grep pidgin | grep -v grep`" =  "" ] && pidgin &

For some reason, my mouse acceleration starts out at 2, which is way too fast. And the last line is a trick to only run pidgin if it's not already running.

Pidgin

Lastly, I just needed something to notify me if I had messages in pidgin because I no longer had a system tray or task bar. Installing the packages libnotify1 and pidgin-libnotify, along with turning on the libnotify and message notification plugins puts a little asterisk next to the tag where pidgin is when you receive a message. However, I've just been giving pidgin multiple tags so I don't miss messages.

Conclusion

Critical result: HAPPY

Monday, January 25, 2010

Project Euler #3: Largest prime factor

First, some clarification: I'm referring to the process of finding a non-trivial factor of a number (not one, and not itself) when I speak of factorization. This is not the same as finding the prime power decomposition of a number.

These algorithms are presented as more fun alternatives for solving project euler problem 3, rather than a bland trial and error approach.

Fermat's Factorization Method

Fermat's factorization method is quite simple and forms the basis for faster algorithms. It works like this: suppose you have an integer n to be factored, and it can be expressed as the difference of two squares:

$$n = a^2-b^2$$

Then n can easily be factored like so:

$$n = (a+b)(a-b)$$

Luckily enough, all odd integers can be written like this (proof left to the reader). The problem that remains is to find out how to express n as the difference of two squares, and this can be done quite easily. For example, one can start at $$a = \sqrt{n}$$ and incrementing, checking whether or not $$a^2-n$$ is a perfect square.

Unfortunately, this naive process can take longer than trial division, so I would not recommend it (for the interested reader; however, there are many ways to speed up this method).

A more clever method exists if the integer in question has relatively small factors; however, before introducing it, I have to discuss some notation:

Division

The notation $$a|b$$ means "a divides b". In other words, there exists an integer c such that $$ac=b$$.

Congruences

The notation $$a \equiv b \pmod{m}$$ means that $$m|a-b$$, or that "m divides the difference of a and b". The notation may be unfamiliar, so a small exercise may help. Take a gander at the following statement:

$$a \equiv r \pmod{m}$$ and $$0 \leq r < m$$ This means that r is the remainder when a is divided by m, which is a more familiar concept.


Pollard's Rho Method

This approach works well for large odd numbers with small factors. The first step is to generate some random Diophantine polynomial, such as:

$$f(x)=x^2+a$$ where $$a\not=0,-2$$

Now generate a sequence of $${x_k}$$ such that:

$$x_{k+1} \equiv f(x_k) \pmod{m}$$, with $$k \ge 0$$

The goal is to find some small, non-trivial factor $$d$$ of $$n$$. Since there are exactly $$d$$ congruent classes modulo $$d$$, and $$d < n$$, the integers $$x_k$$ must become periodic (modulo $$d$$). That is, there must exist residues $$x_i$$ and $$x_j$$ such that $$x_i \equiv x_j \pmod{d}$$, where $$i < j$$. Therefore, the strategy is to choose $$x_0$$ and $$f$$ such that $$x_i \equiv x_j \pmod{d}$$, but $$x_i \not \equiv x_j \pmod{n}$$. If suitable values can be chosen, note that $$d | x_j - x_i$$ but $$n \not | x_j - x_i$$. This means that $$gcd(x_j - x_i, n)$$ is a non-trivial factor of $$n$$. Pretty clever huh? Notice that knowledge of the value of $$d$$ is not used to compute $$gcd(x_j - x_i, n)$$.


Conclusion: Trial Division

Despite it all, my preference is for a simple approach: trial division with a pre-generated list of primes. Most Project Euler problems can be solved pretty quickly if you've got a big enough list; the only problem that remains is how to efficiently generate such a list...

Saturday, January 23, 2010

Project Euler #120: Square remainders

Here is the question:

Let r be the remainder when $$(a-1)^n + (a+1)^n$$ is divided by $$a^2$$.

For example, if $$a = 7$$ and $$n = 3$$, then $$r = 42$$: $$6^3 + 8^3 = 728 \equiv 42 \pmod{49}$$. And as $$n$$ varies, so too will $$r$$, but for $$a = 7$$ it turns out that $$r_{max} = 42$$.

For $$3 \leq a \leq 1000$$, find $$\sum r_{max}$$.

Actually this, is a very easy problem, solved using a formula you may have learned about in elementary school.

The formula mentioned is, of course, the binomial formula; the same one that forms Pascal's Triangle. If one simply expands $$(a-1)^n$$ and $$(a+1)^n$$ via the binomial formula, then adds them together, one sees that the odd terms cancel each other out.

Now:

When $$n = 1$$, the remainder modulo $$a^2$$ is just $$2a$$.

When $$n > 1$$, and $$n$$ even, it's easy to see that the remainder is $$2$$.

When $$n > 1$$, and $$n$$ odd, the remainder is $$2na$$.

It remains to do a search through values of n to find the maximum remainder. Here is a solution in Scala:

def f(a: Int) = {
  def g(n: Int) = n match {
    case 1 => 2 * a
    case _ if n % 2 == 0 => 2
    case _ => 2 * n * a
  }                 
  (1 to (2 * a)).map(g _)
          .map(_ % (a * a))
          .reduceLeft(_ max _)
}

println((3 to 1000).map(f _).reduceLeft(_ + _))

Project Euler #26: Reciprocal cycles

Here is problem #26:

Insight into some elementary number theory will help shorten this search for the longest cycle.

It's better to start computing cycle lengths starting from 999 down because a number 1/n cannot have more than n repeating digits in its decimal expansion. To convince yourself of this, think about what is happening when you do long division. Suppose you calculating 1/7:

First you divide 1.0 by 7 and find the remainder. Computationally, this is the same as dividing 10 by 7, then multiplying the remainder by 10, dividing by 7 again, and so on. See the sequence of computations for calculating 1/7 below, written in this manner:

$$(1 * 10) / 7 = (1) * 7 + 3$$
$$(3 * 10) / 7 = (4) * 7 + 2$$
$$(2 * 10) / 7 = (2) * 7 + 6$$
$$(6 * 10) / 7 = (8) * 7 + 4$$
$$(4 * 10) / 7 = (5) * 7 + 5$$
$$(5 * 10) / 7 = (7) * 7 + 1$$
$$(1 * 10) / 7 = (1) * 7 + 3$$
$$(3 * 10) / 7 = (4) * 7 + 2$$

Notice that the parenthesized numbers on the right hand side are precisely the first few digits in the decimal expansion of 1/7 = .14285714... and further notice that:

$$1 * 10 \pmod{7} \equiv 10^1 \pmod{7}$$
$$3 * 10 \pmod{7} \equiv 10^2 \pmod{7}$$
$$2 * 10 \pmod{7} \equiv 10^3 \pmod{7}$$
$$6 * 10 \pmod{7} \equiv 10^4 \pmod{7}$$
$$4 * 10 \pmod{7} \equiv 10^5 \pmod{7}$$
$$5 * 10 \pmod{7} \equiv 10^6 \pmod{7}$$
$$1 * 10 \pmod{7} \equiv 10^7 \pmod{7}$$
$$3 * 10 \pmod{7} \equiv 10^8 \pmod{7}$$

As you can see, at the next to last step, the digits start to repeat. In fact, the number of repeating digits is given by $$e = ord_{10}n$$, where $$e$$ is the smallest positive integer such that $$10^e \equiv 1 \pmod{n}$$. The preceding is not a proof of this fact, but hopefully is convincing enough.

I have written another blog post about calculating order, so please refer to that if needed. Finally, here is a Ruby program exploiting this info:

class Array
  def tail
    self.drop(1)
  end
end

def order(a, m)
  b = 1
  (1...m).each do |i|
    b = (a*b)%m
    return i if b == 1
  end
end

def max_period(best, numbers)
  return best if numbers.nil?
  n = numbers.first
  ord = order(10, n)
  return [n, ord] if ord == n - 1
  return max_period([n, ord], numbers.tail) if ord > best.last
  return max_period(best, numbers.tail)
end

numbers = 999.step(2, -1).select { |n| n % 2 != 0 && n % 5 != 0 }
result = max_period([0, 0], numbers)
puts result.first

Project Euler #24: Lexicographic permutations

Here is the question:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Only an elementary understanding of combinatorics is required to solve this problem by hand. Start with the smallest possible digit (0 in this case), then find the number of permutations of the remaining digits. If this number is less than 1000000, then 0 cannot be the first digit in the 1000000th permutation.

Try 1 instead, and count the number of permutations. Keep going with 2, 3, 4, etc until the number of permutations exceeds 1000000. Suppose that fixing the first digit at $$k$$ results in more than 1000000 permutations; this means the first digit is fixed at $$k-1$$, and the second digit must be examined by this method.

A diligent Project Euler enthusiast can execute this method by hand, but here is a simple program written in Scala that demonstrates this method:

val digits = List(0,1,2,3,4,5,6,7,8,9)
val target = 1000000

def fact(n: Int): Int = {
  def recur(n: Int, acc: Int): Int = if (n == 1) acc else recur(n-1, n*acc)
  if (n == 0) 1 else recur(n, 1)
}

def compute(list: List[Int]): List[Int] = {
  def recur(list: List[Int], current: Int): List[Int] = {
    val permutations = fact(list.length - 1)
    val index = (target - current) / permutations
    val digit = list(index)
    val next = current + index * permutations
    list.length match {
      case 2 if target - current == 0 => list
      case 2 if target - current == 1 => list.reverse
      case _                          => digit :: recur(list - digit, next)
    }
  }
  recur(list, 1)
}

val result = compute(digits).mkString("")
println(result)

Wmii: Dealing with a lack of xrandr support

I use wmii on my EeePC, which is frequently connected to and disconnected from an external monitor. Earlier I posted about how to get my DPI under control using two monitors, but a different issue I had was with wmii and the lack of xrandr support. When I plug in the external monitor, I get a lot of extra screen real estate, but the status bar stays in the same place instead of moving to the bottom of the screen to take advantage of that extra real estate.

The unhappy workaround to this problem is to place this in your .xsession:

while true; do
  wmii
done

If you do this and login via gdm by selecting "XClient script" as your session, you can quit wmii without stopping X. This will re-launch wmii and all your windows will be retagged. Not optimal, but it will do for now.

Netbeans 6.8: Enable anti aliasing in fonts

So many GUI options and no checkbox to enable this. Awesome.

Edit etc/netbeans.conf in the Netbeans install directory and add this to netbeans_default_options:

-J-Dswing.aatext=true