mh-z web-log

Here’s what I never liked about the game Minesweeper: It’s a puzzle game, but there’s a huge element of luck in it. Solving small boards is relatively easy, but the problem is that you’ll inevitably and frequently get into states where it’s impossible to deduce where the mines are, and you have to just take a //step// into a risky unknown area, a click of faith, as it were. You can probably use probability to figure out where there’s less likely to be a mine, and I bet that’s an aspect in solving more puzzles, but I’m sure (although I never spent any inordinate amounts of time playing the game) that when you get “stuck” and need to take that blind leap of faith and you hit a mine after spending lots of time trying to open up and solve a large board, that that’s rather frustrating. That’s pretty much why I never bothered to play the game (and so I found other outlets for boredom). So wouldn’t it be nice if you could play Minesweeper without running into those ambiguous scenarios?

I wrote a [http://mh-z.com/misc/minesweeper2.html minesweeper solver] a while back, which generates a random board and then simulates all the steps it’d take a person to solve the board. The solver algorithm takes advantage of the configuration of mines it’s already detected and explores all possibilities, and if it’s possible to deduce that a particular spot is definitely free of mines or definitely a mine, even if that deduction would take many layers of reasoning, the program does get to that point. That’s about all it does for the moment; writing the program was just a fun exercise (in response to an interview question) that took about a day.

So the next step, which I thought about long ago but never really had the inclination to implement before having a conversation last weekend about it, would be to build a version of Minesweeper you can actually play which generates boards that are solvable. Here’s how I’d do it:

The aforementioned solver generates a random board, steps on an initial square, then tries to solve the rest of the board. When it gets into an ambiguous scenario which would require guessing, it just gives up. Given that I can generate a random board and see if it’s fully solvable or ends in ambiguity, I can just keep on trying, with different random boards, until I hit upon one which the solver can solve. Then we know you’ll be able to solve it, too, knowing you can’t get stuck — you may run into tricky puzzles based on configurations of mines, but you’ll be able to puzzle it out, like Sudoku.

Maybe that’s why games like Sudoku are popular these days — there’s guaranteed to be a solution, always a definite next step, even though it can be very tricky for us humans to find. A tough Sudoku puzzle where you weren’t sure whether a solution existed would be pretty frustrating.

One factor I need to consider is that the solvability of the board depends on where you initially step, and your first step could itself be directly on a mine. So I could either try to simulate the experience of “real” minesweeper by generating a board around you after you step (guaranteeing that the first step is a safe spot) and guaranteeing solvability from that point, or I could automatically open up a random square as the first step — this is where you’re standing now, your safe ground from which to explore and open up the rest of the board. In keeping with the theme of not having to guess, I’m leaning towards the second option; this would also make it simpler to solve a saved puzzle.

Also, I originally implemented the solver itself in JavaScript, so generating dynamic random puzzles can be done by your browser, without putting any load on a server. I need to “thread” the JS, though, since generating (i.e., repeatedly attempting to solve different random mine configurations in) a puzzle is slow, depending on its size and the number of mines. (I could use the generation time as a metric for how difficult a puzzle would be for a human player to solve.) Updates as I go.

Yay, I’m [http://youtube-channels-beta.blogspot.com/ famous]. Sort of. Not really. :)

I was mainly responsible for the video/playlist browser gadget at the top of the page. There’s some cool AJAX pagination going on behind the scenes which allows for very long scrollboxes full of stuff without having to load //all// the stuff from the server ahead of time, when most visitors won’t scroll through all of it.

This is [http://www.youtube.com/user/grythx my own YouTube channel] (one of ‘em, at least) where I’ve uploaded a bunch of songs I composed way back in the day (mostly high school) on my computer. There’s some good, some bad… I mostly just wanted to put this out there because it’s not like I’m ever going to finish most/many/any of these. I recommend “006″ and “Negative Energy”, or check out the “Cool Stuff” playlist (I’m sure I can think of a better name). Enabling “HQ” mode in the player improves the sound a lot, too.

I had about 700 comments to mark as spam in WordPress, which shows 20 comments per page on its bulk-edit-comments screen. That’s too many pages to hit “check all” and “mark as spam” on, when the database server on this host is a little pokey, in general. To make a long story short, I opened up the PHP source file (“edit-comments.php”) for this screen and saw that the number of comments per page is hardcoded, with the number “20″ appearing several times throughout the file. Huh? It took me, literally, two minutes to set a constant $COMMENTS_PER_PAGE at the top of the file, update all the “20″s to reference that, and set the value to 100. I thought everybody knew that hardcoding values isn’t the best of programming practices, and I’ve gone through four or five upgrades of WordPress, so clearly it’s actively being developed. Unless I’m completely missing something, I’d have thought better of a project with such popularity.

My ideal philosophy for Web application design is as follows:

The entire application exists on a single page, which loads once after the user logs in. All HTML is sent to the client at this point. All further interaction between the user (client) and the server is in the form of JSON data which is sent back and forth. This data generally doesn’t contain HTML or any specific formatting information; that was already sent over either in the form of HTML templates, or else rendered dynamically by Javascript code, which constructs specific widgets. For example, a textual screen with fields in specific places is sent as an HTML template, and the data for the template’s fields are sent as a separate JSON data block. Javascript on the client side is responsible for rendering the template and putting it up on screen. Certain fields in the template may reference sub-templates or more advanced widgets, such as sortable data tables, and the data, which was received through JSON, is rendered into the appropriate presentation and inserted into the template as needed.

As the user navigates from screen to screen, the hash portion of the URL is updated, enabling the browser’s Back button and bookmark functionality.

For an application with many screens, where loading all screens at the beginning before showing anything to the user would cause too much of a wait, the application can load sets of screens in the background once the initial set of screens is loaded and displayed.

A screen template may include more than just HTML with fields denoted; it may include Javascript code which is specific to rendering that screen. The code can then be eval’ed in order to add the requisite functions to the app’s codebase.

As a user is editing data, the browser should frequently send save-state information to the server, so as to prevent data loss in the event of a browser crash or connection-lost condition. On subsequent login, the user’s data should always be recoverable.

On the server side, the server is very data-centric and knows very little about the application’s UI structure. It just handles requests for data, and responds with it, given that the authenticated user has the relevant permissions. It has handlers which can respond with many forms of data. The server’s handlers are flexible and can respond to a single request which requires data gathered from many sources: this way, the UI’s data needs don’t need to be tied too closely to the handlers which satisfy them. In fact the term //source// would be better than //handler//. A true handler, on the other hand, may handle requests to update data.

To be continued…

Ever wonder where the computer terms “[http://en.wikipedia.org/wiki/Endianness big-endian]” and “little-endian” came from?
: In the novel, Gulliver washes up on the shore of Lilliput and is ‘captured’ by the inhabitants while asleep. He discovers that Lilliput and Blefuscu are permanently at war because of differences over the correct way to eat a boiled egg – from the rounded end according to the Blefuscudians, or from the sharp end according to the Lilliputians. The supporters of the differing views were called “Big-endians” and “Little-endians.”
From [http://en.wikipedia.org/wiki/Lilliput_and_Blefuscu this entry on Lilliput and Blefescu].

I’m not that impressed with this [http://scbr.com/docs/products/dhtmlxGrid/index.shtml DHTML grid] widget: It’s intended as a generic editable table which shows data in a Web browser, using JavaScript to control all user interaction client-side. I’m working on something similar which allows easy form generation straight out of a MySQL database, gathering as much data as possible from the database itself (by querying MySQL for column data type, keys, etc.). Anyway, I’ve given a lot of thought to how the interface should work, and what I like to provide the most efficient and logical “data editing experience”. Problems with this demo are:

1. I don’t like having to double-click to edit a cell. What’s wrong with single click?
2. The cell type is not clear before clicking on it. For example, the Book Title column is apparently a text field since it’s editable in-cell. But the Author column opens a small text-area, however without a visible cursor.
3. The Shipping dropdown does not render as a true drop-down box (one row high, with a drop-down showing the excell options), rather a list box (overlayed on top of the other elements). This is a problem I ran into as well, though: apparently there is no DHTML function which will tell a list box to open up; it has to be manually clicked by the user. Maybe it’s possible to simulate a “click” event and send it to the list box element.
4. If I open a list box by double-clicking one of the cells under Shipping, and then scroll the whole table from side to side usings its scrollbar, the list box showing the shipping options stays in place relative to the browser window, not the frame in which the table is shown. You can end up with a dropdown box not positioned over the element whose choices it’s showing.
5. Why does clicking in a cell with a checkbox not check the box? Instead one needs to click exactly in the checkbox. Clicking in the rest of the cell area just moves the current row highlight, which is not useful.
6. It’s not possible to edit the Date of Publication field. I would think that showing off a date-editing widget is an important piece of functionality, since there are so many ways to go about this. For example, I could be given a cursor to edit the text of the date directly, or separate dropdowns for year/month/day, or a small pop-up calendar overlay, and so on.
7. Tab functionality doesn’t work properly. Half of the time, Tab will take me to the next element, but ofter it will start moving the focus to other links on the page or browser menu options.
8. The current row is highlighted, but the focused cell is not.

On the other hand, their [http://scbr.com/docs/products/dhtmlxTree/index.shtml Tree] and [http://scbr.com/docs/products/dhtmlxTabbar/index.shtml Tab-bar] widgets seem pretty nice. It’s just the grid that’s poorly designed.

(Still not seeing the world through ruby-tinted glasses.)

Argh. Killed another few hours on the below problem with no progress. Or rather, maybe a miniscule bit of progress. It seems that after I start the WEBrick server, the very first page load sees the database, but no additional hits do. I can connect to the “new” function in my test controller and see a “create” button there along with fields it’s pulled out of the database. However on refreshing the page or selecting anything, the same old error (mysql.o can’t be found) comes back, and persists until I restart the server. After poring over page after web-page of Q&A issues/solutions with RoR’s MySQL connectivity, reinstalling MySQL and trying 15 other things, I’m going to say that… I’m sure with enough effort I could track down a solution, but for the time being I’m laying this to rest. My next step might be to bite the bullet and just download Instant Rails and see if I can pull pieces out of that, but I get the sense after reading all those pages that parts of this framework are a bit immature, like that database connector. The programming model at least sounds solid.

(The train hasn’t quite left the station.)

Last night I was feeling brave and decided to take the plunge and learn a little about Ruby on Rails. First step, of course, was to install the needed components.

Following the directions on the RoR homepage, everything went smoothly until I tried to get MySQL hooked up. Although there’s the Instant Rails package which includes everything preconfigured (Ruby, Rails, MySQL, some Web server or other), I already had MySQL and Apache running (with a live “testbed” site — didn’t want to damage anything here) so I opted for the “manual” install. Besides, it shouldn’t be too hard. After installing various versions of PHP+Apache+MySQL on at least 5 machines, getting everything to work together is sometimes tricky and takes a little troubleshooting, but I’m familiar with the process.

I was able to create and run a “Hello World” app and understand more about what Rails does. Basically, Ruby is just a programming language. I’m not familiar with it so I can’t comment too much about the feel of it yet, but by ASP standards (where by default you have the choice of Visual Basic or JScript), it’s more like Visual Basic: line endings have meaning, you won’t find braces or semicolons lying around anywhere, and also Like Python, indentation level also has meaning. But enough about the language itself; hopefully I’ll be able to comment more about that at a later date.

Rails is simply a set of scripts (written in Ruby, of course) which creates folders and writes out a whole slew of source code and configuration files which form your Web application’s framework. So by the time you start developing, you’re running on a nice framework of code which abstracts routine database operations (typically done tediously through SQL queries) into simple language constructs. Instead of SQL, you just deal with objects in the language.

So in the above sense, there’s no reason for it to be Ruby on Rails. It could have been PHP on Rails or C++ on Rails. It seems the Rails developers had a “thing” for Ruby, and who knows, maybe it is more elegant than other languages out there. I can’t tell you about that yet.

Anyhow, the Ruby interpreter is the same sort of thing as the PHP interpreter. You invoke it from the command prompt with a script as input, and it runs the script. Unlike PHP, it seems that there currently is no Apache module for Ruby. If you want to use it with Apache, it has to get invoked in CGI mode, and you need FastCGI to make that efficient.

Installing Ruby was easy. Next I installed RubyGems, which is a tool written in Ruby for automatically downloading and installing packages (sort of like PEAR from the PHP world, but seemingly more feature-rich.) I issued a command to tell Gems to downloaded and installed Rails, and another command to download and install the MySQL adapter. That’s where something must have gone wrong… since no matter what I did, my application would not connect to the database. It printed this error:

no such file to load -- ./mysql.o

Uninstalling and re-installing the MySQL adapter did not work. Attempting to install different versions of the adapter did not work, since something went wrong during the installation.

This version’s installation worked:

C:\ruby>gem install mysql
Select which gem to install for your platform (i386-mswin32)
 1. mysql 2.7.1 (mswin32)
 2. mysql 2.7 (ruby)
 3. mysql 2.6 (ruby)
 4. mysql 2.5.1 (ruby)
 5. Cancel installation
> 1
Successfully installed mysql-2.7.1-mswin32
Installing ri documentation for mysql-2.7.1-mswin32...
Installing RDoc documentation for mysql-2.7.1-mswin32...

C:\ruby>

All other versions did not work:

Building native extensions.  This could take a while...
 *** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of
necessary libraries and/or headers.
Check the mkmf.log file for more details.
You may need configuration options.

...

ERROR:  While executing gem ... (RuntimeError)
    ERROR: Failed to build gem native extension.
Gem files will remain installed in c:/ruby/lib/ruby/gems/1.8/gems/mysql-2.7 for
inspection.

The folder mentioned immediately above needed to be manually deleted whenever this occurred.

Anyway, that’s as far as I got in a few hours last night. I’ll go fight with this some more, later.

Textpattern is limited in that I can’t independently create sections and pages. What I’d like to do is create an array of pages and then create, as it were, “views” which tie together a particular section with a particular page.

I.e., a “page” should correspond to a way of mapping the entry database to HTML. A “section” should correspond to a way of selecting articles out of the database, based on a singular tag or a more complex set of rules. Then we should have “views”, which say “present section X using page Y”.

The problem is that (1) A given article may only belong to one section, and (2) Textpattern only lets us assign a specific page to a specific section. So let’s say I want to have two different renderings of the articles on the front page, one with a larger font and different color set, and one which only shows the first, say, 50 words of each post. Apparently I can’t do this.

This is just a temporary solution, because I want to create a better piece of blogging software at some point (and I’m dearthing on time). Not necessarily more configurable and flexible, but just something for me to use. What would be nice, and I’ve posted this before elsewhere, but I’ll reiterate, is the following feature set:

(1) Articles may be shown as excerpts on the front page; however pressing “more” or ‘(+)’ loads the rest of the article, still on the front page, using an AJAX-style data load and dynamic page manipulation.

(2) The “add-comment” form is available and hidden on the main page below each full article. Press the “comment” link and the form instantly appears. Adding a comment is done asynchronously, without ever leaving the main page.

(4) Viewing and paging through comments is done asynchronously, also on the main page.

I’m surprised no blogging tools support AJAX yet, considering that it’s really not that complex to implement what I’m talking about, above. Time to put my money (or fingers?) where my mouth is and start coding this, then.

When I say “the ‘Opera’ of Blogging software”, what I mean is that just like Firefox and Opera differ, in that Firefox is very extensible and it’s easy to add tons of plugins (in fact, you need to, to get certain functionality), Opera has all this optimized and built-in. As a consequence it’s not as extensible, but it does what you want. For example, if you want to save the tabs you have open in your current session so you can restart your computer and come back to the same set of windows/tabs you had open before, Opera has this built in. With Firefox, you’ll need the incredible Tab Mix Plus.

I’m working on a solver for Sudoku, and happened to start writing it in Javascript (since just about everything else I’m doing these days in in that language). You can call it JScript, or ECMAScript, too. Same thing. To tell the truth, I very much like the language. The main problem is, it’s not fast, and although it seems that the actual problem I’m solving should (with the application of appropriate logic) be computationally very light, it bogs down the browser enough that the program is periodically interrupted with an “a script on this page is running slowly… would you like to continue running scripts?” message. I figured I could crank this program out right off the bat as a Web-page embedded Javascript, but debugging is a bit tough in that context, so perhaps it’s back to the drawing board. And yet, my program is 90% done. Come on brain, you can do it. Although it would be “easy” in C, part of the challenge lies in building an efficient algorithm that’ll yet work in a slow language like Javascript.

Also, check out websudoku.com, where they actually advertise puzzle-generation services for people who want to construct a book. Seems to me, once you have a solver program, actually generating puzzles should be a piece of cake. Method for generating puzzles: Take a completely filled-in Sudoku board, and “shuffle” it. Then start randomly removing numbers to create holes, and each time you remove a number, run a solver pass on the board. When you finally remove a number and the solver no longer can finds a solution, the game is ready. We can also control the “depth” the solver is allowed to search, so by setting the depth to something very shallow, we can make easy puzzles, and so on.

By “shuffle”, above, I mean that I’m sure there are a set of invariants by which applying them in the right order, any board can be transformed into any other board. For example, we could:

(a) Swap any row in sets [1-3],[4-6],[7-9] with another row in the same set.
(b) Swap any column with another column in the same manner.
© Exchange all of number X with all of number Y throughout the board.

Maybe that’s enough, in which case, only a small number of original puzzles of different “prototypes” are actually needed, and then they can be transformed into many other puzzles which seem completely different, but are really “topologically” the same.

When I write code in PHP, the amount of time I waste deciding whether to use single quotes around something or double quotes around something, or in deciding that something I started with single quotes (thinking it would be a simple string) should be converted to double quotes so that I can embed a variable in the string and making the change, or vice versa, while maybe a second or two each time, adds up. Therefore, I’ve decided to just use double quotes all the time. I’m used to escaping the double-quote character when it needs to appear inside a string from C++, so that’s no trouble. Even though I’ll have to escape more characters on average, it’s nicer to have a consistent appearance in the code. Finally, whatever extra processor time it takes to parse double-quoted strings for embedded variables really should be negligible, and if it isn’t, I either shouldn’t be using a scripted language like PHP anyway, or should use one of several PHP compilers which should optimize away scanning within double quotes. So to sum it up, ignoring single-quoted strings saves decision and code-fixing time on my part, leads to more consistent code, and in my humble opinion looks better.

Something from the past, so I have an easy post today. I was experimenting with particles in this program, way back when I first learned C++: It’s a VGA (320×200) firework simulator. Runs nicely under any version of Windows.

Download

Keys: ‘n’ for a normal explosion, ‘m’ for a big explosion. Although the resolution is low, high frame rate (70 hz, where each animation frame is sync’ed with the monitor) and anti-aliasing ("algorithm" created purely by trial-and-error) make the animation look smooth.

It’s cool! Play with it. If you hold down ‘n’ you’ll feel like you’re in the shower.