Archive for the ‘english’ Category

On a soduku solver…

Saturday, October 3rd, 2009

Yesterday, when I was on the bus, I got pulled into a sudoku. Then I started wondering how a machine could be programmed to solve these puzzles.

Note: For the rest of this post:

  • A square is the un-devidable unit containing 1 number
  • A section is a 3×3 grid of squares
  • A column is a 10 square vertical strip
  • A row is a 10 square horizontal strip
  • A board is the 9×9 sudoku board

There a few simple rules that go into solving these puzzles. Namely :

  • What are the possible values for this square (based on row, column and section)
  • What are the possible places for this number (in this section)

The two questions aren’t identical, since a numbers position can be influenced by the positions of numbers in other columns or rows that share the section.

The first question comes down to :

  1. Take the ensemble of possible numbers
  2. Remove all that are already in the current row
  3. Remove all that are already in the current column
  4. Remove all that are already in the current section
  5. if there is only one left, put it in the square
  6. lather
  7. rinse
  8. repeat

The second question comes down to:

For each number not entered in each section

  1. Check for number in the rows that pass through this section, eliminate the squares that belong to them if found
  2. Check for number in the columns that pass through this section, eliminate the squares that belong to them if found
  3. if only one square is left, put the number in it
  4. profit

OK, mabey that one’s a bit vague, I’ll try to make it clearer with a drawing

Example of a row and column problem

Example of a row and column problem

In the above image, concentrate on the bottom middle section. If you look, you’ll notice that there are 4s in the top 2 rows of this section, we can conclude that our 4 must be on the bottom row. We also notice that there is a 4 in the left most column of this section, which only leaves the bottom middle square as a possibility for this 4.

By combining the 2 rules stated above, we should be able to solve any sudoku puzzle.

Any how, that’s all for now. Proof by code will be comeing in an update.

AAC – Round 2

Wednesday, May 20th, 2009

I’ve just gotten back into ffmpeg fun after a long haitus, during which ffmpeg v5 has come out.

(No deb instructions this time since I’ve passed on to arch, which has a perfectly functional package).

A couple of thing seem to have changed though, namely:

  • Bitrates are now in bytes/seconde rather than kbytes/seconde (unless otherwise stated)
  • AAC is no longer an encoder module (use libfaac)
  • mp4/amr containers don’t seem to work to well with libfaac, use 3gp instead to be safe.

Which gives:

ffmpeg -i input.avi -vcodec h263 -b 409600 -s 352×288 -acodec libfaac -ab 65536 -ar 48000 -ac 2 -f 3gp output.3gp

Happy encoding

DNS 101

Monday, March 2nd, 2009

I just thought that I’d post a quickie on DNS FQDNs (Fully qualified domain names).

Go to your browser, type in www.google.com, you get the google home page. Everythings normal there.

Now, change your url, ad a dot (so that it reads www.google.com.) . The page still loads.

This is risky, since it can lead to a duplicate content malus on google, but is perfectly normal DNS behaviour.

The actual FQDN is www.google.com. . It’s just that, to make our lives easier, the last dot is optional.

Unfortunatly, there’s no way to get rid of them (even 301s seem flaky).

That’s all, just so that the next time you see bizzars urls, you have a reason for them all ready for your boss ;)

New server – same blog

Wednesday, February 18th, 2009

I’ve just finished moving my blog (and my mail) over to a new server.

For once, the new machine is less powerful than the old.

This blog is now running on an opengate with 512Mb ram and 512Mb of disk (!)

The small install size (systme + data <400Mb) is obtained by using a basic Debian install, and by taking a rm to most of the documentation and things like that.

I might even try to get it down to under 300Mb soon.

Comment spam

Sunday, January 25th, 2009

Oh well, the turning test is commeing closer and I need to update my challange code to keep ahead of the curve.

The new test is a multiplication, but it isn’t in math notation, so it should hold out a little better

Motivation

Thursday, January 15th, 2009

Sometimes I wonder why there isn’t more stuff on this blog.

I think it boils down to the fact that I seem to be almost incapible of sticking to one project.

As an example, at the moment here are the projects that I have on the go (more or less):

-Learn Japanese (progressing slowly thanks to flash cards on my computer)
-Finish the work on the house (advancing by obligation, but slowley)
-Finish off my web gallery project (stalled since I got something stable up this summer)
-Learn to play the guitar (stalled since before Christmas, need to find the time to get back to it)
-Proofread the FMP translations (waiting for the material to arrive, but I should chase the translator up).
-Build a home entertainment system/DVR (need to finish the home first :P )
-Start blogging again (OK, there is some progress there ;) ).

And I haven’t put the projects here that have been on hold  for more than 6 months :( .

Does anyone have some hints on how to stay focused for more than a week on a project? This is beginning to get out of control.

Oh well, maybe writing this list will motivate me a bit.

P.S: in the wild hope of getting some visits again after having neglected this blog for so long, I’m going to linkspam this post a bit, sorry in advance :)

I Hate downtime

Wednesday, July 9th, 2008

Yesterday evening, I agreed to turn my Home Server ™ off too help some people sleep.

Unfortunatly my servers sleep turned out to be the big sleep, and this morning it refused to start.

A few hours and a HD transplant later, evrything is back on line, now running on a Semperon 2600 and 1Go of ram :)

Ubuntu vs AAC (round 1)

Saturday, June 7th, 2008

For better or for worse, (generally for worse) a lot of multimedia systems seem to like making peoples lives difficult.

This is painfully obvious with AAC and the formats that use it (think mp4).

Luckally, playback can be assured by using a nice arrangement of plugins that are downloaded just in time to play the offending file on your computer (thanks ubuntu).

This help doesn’t extend to re-encoding though, so for those of you lucky enough to have an mp4 capable phone (like the sony erricsons), you can find that putting the latest Bleach on your phone to be an exercise in frustration.

The reasons for this are numerous and complexe but come down to the simple fact that if cannonicle put aac encoders in Ubuntu they’d be sued to kingdom come in the states (thank god I don’t live there ;) ).

Help is at hand though, since even if the versions of the enncoding tools included with Ubuntu don’t come equiped, you can re-compile them so that they work as intended.

First up: ffmpeg

FFmpeg is one of the many swiss army knives used for video encoding available with Linux. It’s probably the easiest to use, and like it’s cousins, the ubuntu version comes cripled.

What to do?

First of all, make sure we have what’s needed to re-build it

sudo apt-get build-dep ffmpeg

Then add a few libraries (that add the magic support)

sudo apt-get install libfaac-dev libfaac0 libfaad-dev libfaad2-0 libfaad0

Finally, get the source code to ffmpeg

mkdir ffmpeg
cd ffmpeg
apt-get source ffmpeg

Now the fun starts, you should have 3 files and a directory before you.

Cd into the directory.

Now let’s move this thing arround a bit:

Open: debian/rules

This file tells dpkg how to build ffmpeg, we want to add a config flag so go to the lines that start with “confflags” and add on to one of them:

–enable-libfaad –enable-libfaac

Save, and quit, now all you have to do is re-build the package

dpkg-buildpackage

go have a coffee while it builds, and then install the result:

cd ..
dpkg -i ffmpeg*

To use, something like this is needed:

ffmpeg -i Source.avi -vcodec h263 -b 400 -s 352×288 -acodec aac -ab 64 -ar 48000 -ac 2 -f mp4 Dest.mp4

Update:

For eugenia (and anyone else who also wants AMR support), here are the debs with it (supported in the ‘if it breaks you get to keep both pieces’ way since I haven’t got the means to test them atm:

Update :

I’ve removed the download links for now since the files aren’t available on my server any longer. If anyone needs them, let me know

Bye bye Dapper, Welcome Hardy

Sunday, April 27th, 2008

I’ve just finished upgrading my server to Ubuntu Hardy, with virtual no trouble.

The only problem came from the kernel, which now calls  ide drives ’sd…’ instead of ‘hd…’ so hda1 becomes sda1.

Update grub or face the consequances.You have been warned!

Bye bye trackbacks

Thursday, April 10th, 2008

FYI, I’ve deactivated trackbacks since nobody seems to want to send me one :’(

And because spammers seem to love them :-[