Friday, July 23, 2010

The Cake is a Trap

Ten cakes on a table, ten cakes for our meals
ten cakes in all shapes, with icings and frills

but one of these cakes is no cake it all
underneath all that icing, its dog poop I smell

its a modern process, the waiter informed
dog poop to angelfood, its been magically transformed!

I stood there dumbfounded, speechless and stunned
I stood there too long, till all the real cakes were gone

my friend, this is bullshit, I will not eat one bite
he said: no its dog shit, then winced at his slight

I ate no cake or sweets the rest of that night
suffice it to say, I misplaced my appetite

cake into dog poop, I think that is fine
but feces in my food? now that is a crime!

I confronted the chef who was unapologetic
he said I was rude, intolerant, pathetic

the chef and his friends think they can win this game
they're wrong; they can't make me think its the same

You can cover it with icing and lie to my face
but no one can take dog poo and convince me its cake

Thursday, July 22, 2010

Piss Poor Programming

Though I try, it is difficult to go for too long without hearing or seeing an excruciatingly annoying add for yet another dating site.  Sometimes it is some annoying chick talking at me from a Pandora ad, or maybe a tv commercial that makes me want to throw up, or just a banner on a website featuring a female model who is definitely not in need of the service being advertised and in no way representative of the people that are.

All of these websites are crap.  Like the mythbusters often do, I will base this strong assertion on a sample size of one:  okcupid.

Okcupid is a dating site.  The particulars of why they think they are different and not a complete failure are irrelevant.  Here is a list of the kinds of girls okcupid matches me up with.  And when I say "matches me up" I mean it sends me an email telling me to check out some girls profile because it thinks I would be interested in them.  These girls are one of the following:

1) Ugly Girls.  I've tried dating girls that I had no attraction to and it didn't work out.  According to ugly people, this makes me shallow, and I am damn proud of it.

2) Girls That Are Taken.  Okcupid allows you to post information in a profile.  One piece of information is whether or not you are dating someone.  Its not free text, or even a complicated field.  Its like a combo box.  I'm pretty sure a first year programmer using a toy language like BASIC could write something like "if they are already dating someone, stop trying to match them up with people."

3) Girls That I Have Explicitly Told Okcupid I Don't Want.  Okcupid provides a mechanism for you to identify girls that you never want to see again, in the form of a "hide" button.  They claim that upon using this mechanism, you will no longer see that person.  When I see a girl that I don't want to date, maybe because she's ugly, or she told okcupid that she likes men but in the written descriptions of herself says she doesn't ever date men (WTF?), I click on hide.  Then, a few weeks later (or longer), okcupid sends me an email suggesting I check out the profile of the girl I hid.  I'm not making this up.

4) Girls I Already Know In Real Life.  I can't foresee many situations where running into someone I already know on a depressing, crappy dating site will improve our chances of being with each other.  Thats like running into some girl that already rejected you at a self-improvement seminar, or maybe a moped dealership, or a dungeons and dragons game.  Finding out she has no dating life just twists the proverbial knife.



I was inspired to write this post because, in my okcupid profile, I wrote that I don't care about the Beattles.  I did this because I have discovered that sharing that information makes music nerds angry, quickly, and I really really love to harrass people with strong opinions on what other people like.  And because its true.  Today, okcupid sent me an email about an "icebreaker" message.  Subject: the Beattles.  Apparently, after scanning my profile with the most primitive parser imaginable and seeing the word "Beattles" it decided I liked them and thought it should match me up with some excited Beattles-loving girl whose hopes I just crushed.

I don't really know how to work this in, but I would like to keep all of my okcupid-bashing in one post, and I've been dying to complain about it, so I'm just going to add it:  the people who run okcupid also post on a pseudo-statistics related blog where someone looks at aggregate data (like how tall people say they are in their profiles) and then makes wild assertions by either confusing correlation with causality, or simply being ignorant of statistics.  Firefly Girl thinks they are really smart.  Firefly Girl was not a math major.

Tuesday, July 20, 2010

Piece to the Puzzle

[At a salsa club]
Me: Why did you want to learn how to lead?
Girl: Because I want to dance with girls.
Me: Weird.

Yeah, I still have the gift.  Saying the wrong thing.  I think I managed to recover...something about "I am a big fan of girls dancing together."  The part where I think all men are ugly, and I hate it that people call it the "lead" and the "follow" here instead of "the guys part" and "the girls part" for the same reason I hate it when people refer to The Linux Operating System as "gnu/linux" -- I kept that to myself.  While we're on this subject, whoever is telling Betsy what I write here needs to stop.  She messaged me on facebook to tell me it was rude of me to wish a red shell upon her boyfriend, even though she never played Mario Kart, and still didn't un-un-friend me.  I know, right?  Well, I hope he gets hit by a blue shell.  How do you like that?  Seriously, who has never played Mario Kart?  Raise your hand.  If your hand is raised, you need to put the computer away, go outside and buy a Super Nintendo (or an "N64") and play some Mario Kart.  This is more important even than knowing who the A-Team is.  Well, maybe...oh man, if you don't know who the A-Team is....

I digress.  I will start from the beginning.

By some mysterious fortune, a craigslist ad I posted about finding a salsa partner received some actual responses.  Three girls responded, and two met up with me in real life.  They are both beginners, but they have potential.

The interesting part, is the beginner class that I elected to take with...dance partner candidate #1, had a lot of girls.  This was at Century Ballroom.  Way more girls than Belltown Dance Studio.  I'm not sure I've ever seen that many attractive girls in the same room in seattle--ok, thats a lie--I have.  Not often though.  The dance class was irritating:  it was taught by a bunch of Swing [dancing] teachers (I'm guessing) who kept using the incorrect name for one of the moves over and over and over again.  In Salsa, there is a move called Enchufla.  If you were drunk and didn't know much about dancing, it would look like what some people call the "inside turn" in Swing (I call it that-turn-i-do-after-the-first-turn-i-do).  Unfortunately, Salsa has its own inside turn, and it is not Enchufla.  The Salsa inside turn is similar to a cross body lead, and some people call is the Progressive Left Turn.  Also, these teachers were deliberately teaching everyone to dance too far apart.  Probably, again, because they were swing teachers and in swing you do dance far apart.  This was most irritating to me because I already dance too far apart, and learning to dance tighter, so that I can survive in a properly crowded club, is something that I have been working on for a while.  Its tough when you have long legs and get really excited.

But, whatever.  I did learn a new move.  And almost everyone in the class thought I was amazing.  That was cool.  Learning Salsa in Philly for a few years, from whom I am now labeling the best teachers in the world (one was from sweden), and then moving to Seattle and taking a beginner lesson, is basically the same thing as when we used to play Starcraft I on Battle.net in high school, but create new accounts so that the server would match us against beginners and it would be easier to win.  It works a lot better in real life though.

Some girls from my class seemed interested in me.  I don't know why.  I look pretty bad this month:  circles under the eyes, and a bad haircut because I did it myself with one of those shaver things that comes with big plastic pieces.  Most importantly, about what I was talking about a few paragraphs ago:  I made some new friends.  Female friends.  That want to go dancing.  Also, they are attractive.

I went to this club Halo after our last salsa class tonight with them.  We have plans to go salsa dancing thursday.  If I play my cards right, I could be dancing regularly with not only two, but three girls.  Mayyybe even four. 

Even without them, Halo on a monday night is apparently awesome.  There were so many girls there, the genders were evenly balanced for once and because I also knew people from this class I took, I was able to dance to song after song without long breaks in between trying to find girls to dance with.  Because of this I was able to actually get into it and the moves started coming automatically and I was able to dance to the music.  It was amazing.  I had been planning to teach the one or two girls from craigslist over a period of time, eventually breaking into the salsa scene in a month or two, but now I'm thinking I could just start going with the girls whose numbers I got tonight.  Dancing is awesome because it doesn't have a singleton rule like Dating usually does.  Of course, these girls are beginners too, but they have some natural talent.  I do need to find someone who dances at my level.  Speaking of which, I danced with the girl that used to ignore me from the last studio I went to.  I don't think she hates me.

Oh, and black shirt girl.  Yeah, I forget her name.

I am doing too much to keep track of.  I'm stressed from my boring ass job, and from keeping up with the flying, and now the dancing, and I haven't been able to try my latest 3-sat optimization cause I just don't have time.  Then there is the Settlers.  The guitar and the volleyball pretty much got dropped for a while, and I completely forgot I was even going to try to rock climb again.  Poker will have to wait.  I'm beginning to believe it is physically impossible to excel at all of those things at once.  Not without bringing a whiteboard to the rock gym.  And when will I have time to make a pirate themed Lego comic?

[edit]
Good salsa video--one of these moves looks like the pretzel

Monday, July 19, 2010

Scud Running

Landing on the right number of people for a small plane is worse than trying to get a settlers game going.  I'd prefer to take at least one person, because I feel like accomplishing something, but two people can easily make the plane overweight.  Three passengers is a challenge.  So with people backing out, and then me asking other people at the last minute, it just becomes what I consider a scheduling nightmare.  Other people probably just call it making plans, but in my opinion anything that takes more than three to six text message to arrange is too complicated.

That being said, it turns out that my decision to learn the 172SP Cessna in addition to the 172P Cessna is paying off big time:  yesterday and today I had no trouble scheduling the club's 172SP, even though a ton of people were all flying the 172Ps.  I pay for it; the SP is more expensive.  However, when you like to make plans a few days before, it is worth it because you can still get a plane.  I am considering moving up to the 172 RG, because the RG stands for Retractable Gear and even fewer people can fly it.  I love how all of my motivation for flight training stems from scheduling issues.

One disadvantage of the 172 SP is that it has bigger fuel tanks.  This is great if you want to go far, and not so great if you want to carry four people (because fuels weighs a lot), even small people.  So it looks like the max number of passengers I can offer to take, and be sure about taking them without going home and calculating weight and balances stuff, is two.

Hoqiuam

Yesterday, we went to Hoqiam.  I initially thought I was going to take starbucks girl #1, but she backed out again.  Then, Saturday morning, I thought we weren't going to go at all.  I was looking at all the information sources sounded bleak:  instrument conditions everywhere, cloud heights in the hundreds of feet (instead of thousands), overcast layers directly over the airports I wanted to land out.  I was logged into the online scheduler in the middle of deleting my reservation when I decided to check the weather forecast products one last time, and something I saw made me decide that, worst case, scenario, I might be able to pop over to Bremerton, pick up Bridget, and maybe fly around for a few minutes.

Then I get to the airport, and the whole damn sky is bright blue.  No clouds in sight.  The same thing happened today, so it seems like this whole area is typically super cloudy in the morning, and then at 2100Z, which I can never remember is 2pm Seattle time, all the clouds just to poof and disappear.

My landings are crap.  I mean, they are both safe and don't damange the aircraft, but talk about sloppy.  When I was landing at Bremerton to pick up Bridget, I started bouncing in and out of ground effect and had to take off again to re-fly the whole approach.  I don't think I'd make a very good glider pilot.  Anyway.

I had made an actual "cross country" flight plan for this trip--my first real flight plan since getting my license.  It Was Awesome.  First, I made the flight plan start and end at Bremerton, because I already know how to fly between Boeing Field and Bremerton.  Then, I didn't put "checkpoints" (read: do-a-lot-of-extra-work points) every fifteen miles.  Instead, I put my checkpoints wherever I wanted, and there weren't many.  I planned to use only a single naviation device (Hoqiuams VOR) instead of like three different ones to get extra practice.  Then, I didn't bother writing down the winds or calculating correction angles for the heading.  I'm the kind of pilot where flying heading 252 versus 248 isn't going to make a much of a difference because I'm going to get off course either way.

So the flight plan, both making and following it, was a breeze.  Then we got near the coast, the one place we wanted to go, and the one place with some clouds.  It was a tiny, thin, but nearly solid layer of clouds at two thousand two hundred feet.  My "personal weather minimums," a collection of random visibility and cloud heights that I established because people say you should have personal weather minimums, dictated that I never fly where the cloud ceiling is less than three thousand feet.  So, I changed my personal weather minimum to two thousand, two hundred feet and ducked under the overcast layer.  It was an extremely clear day, and the clouds had lots of holes that I could see through, and it was basically completely unlike "scud running" for real, but it was exciting because I was pushing my ridiculously safe personal limits, and I could give up at any time because I had a completely clear sky behind me.

We did end up turning back--the clouds and the ground seemed like they were getting lower, and I am very much not a fan of flying close to the ground.  And it was getting darker under there, and we still couldn't see the coast.  I turned back, pushed the throttle all the way open and climbed up through a hole in the clouds.  I wanted to try to fly over the super thin cloud layer and at least be above Hoqiuam.  I figure, that counts as getting there even though it would be illegal for me to descent through the clouds to land (unless I found a big hole--unlikely).  As we continued on, it looked like the clouds went way out over the ocean, forming their own horizon.  There was really no point.  So we went back to Bremerton.

When we got back to Bremerton and joined the traffic pattern, some jackass flew way, way to far past the runway before turning and making his final descent.  Because we were behind him, we, too, then had to fly too far away before turning and making our descent.  I came in too high, as usual, but the landing wasn't bad.

Despite the ease of my super awesome flight plan, I was nevertheless exhausted.  Long (by my standards) cross country flights are always exhausting for me, and I think it is because there is a constant workload that is demanding on the brain.  It is very draining, and I must have been doing it on adrenaline during my flight training.  I want to do a lot more flights like this, so that this stuff becomes automatic and I don't have to concentrate so hard.  After flying back to Boeing Field, the plane's clock said the engine had been running for a total of two hours for the time I had it.


Issaquah and West Point

Today, same thing.  I almost canceled our flight because of weather and when we got to the airport it was blue skies.

I took Luke and my steampunk friend on a tour over their houses.  I also convinced the air traffic controller at Boeing Field that I am an idiot.  Luke lives east of Seattle, so we flew over lake Washington, and then over Bellevue, and then over Issaquah.  My steampunk friend lives in what I call West Point, because thats what is says on my pilot map.  People on the ground call it something else.

It was a quick tour, but way less stressful than going somewhere far away.  There were a lot of seaplanes taking off from Lake Union, which we had to fly over, and they were hard to spot.  That was annoying.

Then, we headed back into Boeing Field and I accidently went into SeaTac's airspace because I misjudged at which point I had to descend.  And the controller at Boeing Field noticed.  That was not good.  You can lose your license for something like that.  I'm told, though, that when you get in trouble with ATC/FAA they usually give you a number to call when you land, and they didn't do that for me.  So, hopefully only the girl at Boeing noticed and not anyone at SeaTac.

My landing was crap because I was proccupied with out I just busted SeaTac's airspace.  I came in to high, had to slip it in (i.e. turn the airplane sideways), then I bounced in and out of what I thought was ground effect, and then we had a hard landing because I misjudged how high we were (the larger runway made me think we were lower than we were) and then I skidded a bit when we touched down because I didn't have the plane lined up right.  I don't think I damaged the plan at all--aside from leaving some rubber on the runway.  I need to practice my landings in the SP model.

The whole point of this trip for me, besides taking my friends flying, was to familiarize myself with the airspace in that part of Seattle.  I suppose I did accomplish that--the hard way.

Wednesday, July 14, 2010

Jack Left Town

http://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.htmlLast night I set my alarm for 8:30pm instead of 8:30am.  For this reason, perhaps, I remembered one of my dreams.

I was in the western part of the east coast, walking through a sort of park thing along a road in a development I didn't live in.  Suddenly all these guys and girls showed up.  The girls were wearing like low cut black stuff and bunny ears and the guys were wearing tuxes, and they were all coming from some kind of vegas-style risque show.  They were having an afterparty bbq thing after a show, even though it was like the middle of the afternoon.  Anyway, I smiled at the girls and ignored the guys--I was on my way to leave.  I had a cessna parked on the other side of the development.

As I made my way out of the group, following a path down a short stairway, some guy hits me in the back with a plastic baseball bat.  Like he wound up for it and everything.  It was the kind of bat kids play whiffle ball with.  He was, I guess, doing that to everyone, to be funny.  I glared at him, then walked across the parking lot looking for something bat-like to return the favor.

I found a pile of rusty, corrugated iron pipe things next to a house, and grabbed a long, thin piece of metal that was roughly the same scale as a baseball bat, and started walking back towards Mr. Funnypants.  Everyone in their little playboy bunny group was suddenly unhappy and started shouting at me.  I crossed most of the parking lot before electing not to return the friendly hit and retreated to return the rusty pipe where I found it.  Except that when I lightly tossed the pipe back onto the pile, I missed, and the pipe slammed into the house with more force than I had thrown it (because my stupid subconscious mind is a jackass) becoming embedded in one of the 4x4s holding the porch up.  There was a guy and a girl hanging out on the porch.  I apologized to the guy, but he called the police.  The girl on the porch started yelling at him that I didn't mean any harm.  I quickly made my exit through the rest of the development and went back to my plane, knowing that if I managed to take off before the cops got there, there would be no way for them to tie me to the incident (my plane did not have foot-high tail numbers).

But, by this point, I had started to wake up, enough to try to restart the dream (dreams that I have while waking often repeat themselves with modifications--its like watching Evil Dead 1 and 2) and insert a part where one of the bunny girls runs up while I'm holding the pipe and writes her number on my free hand with a sharpie.  However, when I added that detail, a cop car shows up while I'm still preflighting (checking the flaps and the ailerons, actually) and then I woke up completely and wondered why it was 9:40.

Back when I read slashdot I remember an article saying one possible explanation for dreams is that your subconscious is trying out different scenarios to test how you would react.  If thats the case, I recommend not attacking me with plastic sports equipment.

[Edit]
AWS Tools Docs

Combinatorial Calculator

10 pounds of Legos = 3000 pieces:  http://www.wired.com/geekdad/2009/06/finding-lego-bricks-in-bulk/

Some lego stores: http://www.bricklink.com/browseStores.asp?countryID=US&groupState=Y

Tuesday, July 13, 2010

...to protect and preserve this fleet...

Yes. I'm putting the fleet back together. I'm putting our family back together. This ends now.


Capitol Ships:

6286 Skulls Eye Schooner

I forgot about this one...this thing is badass.


6285 Black Seas Barracuda

Jon's older brother had this one, I think.  I remember the red sails.  And wanting to play with it.  Jon and I always played with army toys though.  He didn't really dig the Lego thing.  Someone on ebay retrofitted this baby into like a 20 gun ship or something.  I may do the same, if I can get my hands on two.

6289 Red Beard Runner

This one looks weird.  Why would anyone build a ship with sails like that?

6274 Carribean Clipper

Ooh...what is this?  I think I faintly remember this one.

6271 Imperial Flagship (older one)

Ok I knew the soldiers had a big one.

6280 Imperial Armada Flagship (the other older one)

This is uh...smaller...than the pirate ships.  Maybe this was misnamed.

10210 Pirates Imperial Flagship (newer one)

This is the one I just bought.  Sexy lady.  Interesting that they put the word "pirates" in the title even though it is a soldier ship.  Have lego set names also been affected by the nature of web searches?

6243 Pirates Brickbeard's Bounty

This appears to simply be a newer version of the Black Seas Barracuda.


Other Ships:

6268 Renegade Runner
I had this one :D and I built it while watching some classic christmas movie about a guy who works at a credit union who wished he'd never been born.

6291 Lego Spaniard Ship
This appears to be the exact same ship as 6280 Imperial Armada Flagship.  Maybe the hats are different.  Or the sails?  If the sails are different it counts.

6250 Cross Bone Clipper

I seem to have been unaware of this one as a child.

6261 Raft Raiders

I had this one.  This is...technically a boat.  Its not like the pirates need any more ships...damn.

6296 Shipwreck Island

This is very ship-like.

6277 Imperial Trading Post

This set came with a small trading ship.  I had it.  It was fun.


Oh, hello.

[Edit]
Aw, someone beat me to it: http://historybricks.com/2010/01/10/lego-pirates-ships-comparison/http://historybricks.com/2010/01/10/lego-pirates-ships-comparison/

[Edit]
And the black pearl!  I want to make this:  http://www.mocpages.com/moc.php/64518

Sunday, July 11, 2010

I happen to have no dress in my cabin.

I've spent the weekend watching my computer solve 3-SAT problems, and trying to make it go faster.  I think I got the 75-variable instances down to 2 hours.  Thats a lot better.  While I was waiting for these two finish, I decided that it would be a great idea to play with some Legos.  I have long avoided bringing any Legos into my home, because they are incredibly addictive.  But, concentrating on a problem for long periods of time seems to erode my common sense.


I went to a store and bought a tiny, inexpensive ($6) set, a Lego car, and built it.    I don't like the fact that you can't put a little Lego person inside, but I do like the way it looks.Here is a picture:


















And then I build this Pirate ship:



They have a lot of fancy new pieces and fancy new colors now.  Still ridiculously expensive.  I bought it because I've never owned a "big" pirate ship--I only had like a small pirate interceptor.  And technically it isn't a pirate ship because it is the red coats ship, or whatever.  The lego store didn't have any ships flying the jolly roger.  While it is big by Lego standards, it is actually kind of small by mine.  For one thing, they didn't bother putting cannons on the top deck.  Why would you go to the trouble of having a lower deck if not more room for cannons?  Also, I'd like to a bigger superstructure, with walkways instead of ladders, etc.  Maybe four times as many cannons.  This thing...it can be a scout.

Anyway, my 3-Sat algorithm, Ultimatum, is kicking ass.  It can solve any satisfiable instance fairly quickly, and the unsatisfiable ones are getting knocked out in polynomial time.  I still don't understand why it works, and I didn't do much work in that direction over the weekend because I focused entirely on making it not take forever.  A 50-variable problem took like a minute, and a 75-variable problem took six hours.  Thats not very handy, espeically since right now I believe the biggest threat to the polynomiality of Ultimatum is the larger problem instances.  After some optimizations a 50-variable problem now runs in two minutes, and a 75-variable one takes two hours.  I'm gonna call that progress.

My next steps are uncertain.  I am dying to publish or at least share my discovery with the rest of the world but I feel like I can't, or shouldn't, until I can prove why it works.  I've had a number of ideas about how to prove that Ultimatum is polynomial and they all turned out to be stupid.  I am actually considering giving up, again, and for a little while, because I'm probably going to need to hit this thing from a fresh angle.  Also, I still don't believe that I've actually solved it.  This time I have actual evidence before my eyes, but I have oscillated between thinking that I have it and realizing that I don't far too often to believe it.  Except for when I was standing in the Lego store, trying to convince myself to buy the pirate ship.  Turns out telling yourself that you are going to be famous and get a million dollars is enough blow $180 on a plastic toy for children.  Silly, I know.  Be proud of me; the Taj Mahal was $300.

I could make my own test problems, sure, but the whole exponential nature of NP-Complete problems makes it difficult to test anything more than 30 variables.  So for now I'll just lay low and make sure I can solve every problem in satlib.  And then, when my brain has a chance to rest, maybe I will overdose on caffeine for a week and try to figure out what the proof is.

I heard that people proved something about graphs of a certain size (4?) always being planar by simply enumerating every possible graph of size four.  Maybe I could do that?  Probably not.  Enumerating every 3-sat problem is intractable.

Wow.  Legos are so damn expensive Amazon has my ship I just bought for only a cent cheaper.  I think I'm going to build an armada.  If I can afford it.  This sucks.  The sets I wanted as a kid are like twice the price now, since they only ever ran for three years.  Whatever.  I'm gonna go play with my pirate ship.  Wait!  I need another one.  It needs a friend.  To battle.

When I worked at Neoquest there was this pirate game you could play.  It involved punching shapes out of cards and building tiny cardboard ships.  And there were dice involved.  Some of the images in this search link show them.  I want to find a copy of that game so I can read the rules--maybe we could make a Lego version of it.  I like this idea because I could then maybe rationalize buying every Lego pirate ship every made.

[Edit]
You can thank Evan for this link.

Saturday, July 10, 2010

HELLA YES

Hail to the King, Baby:

uuf75-0100.cnf
UNSATISFIABLE cluster = 0, 21, 49

Thats the sexy little message my algorithm had waiting for me when I got up this morning.

For two days now I've been watching my algorithm do its thing.  Ever fearful of bugs that would get my hopes up for nothing, I initially had it print everything it was doing to the screen.  It actually looked like them matrix in reverse.  I stared at it for hours, transfixed, perhaps the way some people watch sports.  Things things called "jumps" were bad--we didn't like them.  "Merges" were good though--I was rooting for them.  The first time I ran my algorithm with a sizeable UNSAT instance, it ran all night inside the Eclipse console, slowed down by the time it took to print everything out.  I had to go to work, and since there is a heat wave of over 32.7C (90F) and I live in the 6th floor in a building made by idiots who thought I wouldnt need airconditioning, I had to stop the algorithm and turn my computer off.

I bundled up my code and went off to work, telling my self I would restart the algorithm on my work computer...maybe in a screen session so I could hide it.  Unfortunately, the tool I used to bundle the code was git, and I didn't know what staging was, so the code was missing some chunks when I got to work.  Very sad.  That was friday.

I came home and worked on my algorithm some more.  Reduces the text output so it would go faster and waste less time on IO.  Then I ran it again, on an UNSAT problem with 75 variables.  It went quicker this time.  I watched it for hours, fascinated.  It was clear that the algorithm had quickly discovered (after 3 or 4 hours) that the first variable (X) must be False, but the companion discovery it needed, that X must be true, did not come quickly.  It got it though.

Here is where I stand:  I have an algorithm that performs a polynomial number of operations and then throws an exception.  Thus far it has solved every problem in less than half of its allotted operations, however I have no idea how to prove that it will never need more, and I have no idea if there is some worst-case problem lurking out there in the realm of possibility that my algorithm cannot handle.

My current strategy involves making it solve every 3-sat problem I can get my hands on.  The only problem is, polynomial doesn't mean fast.  My algorithm does no more than m^3 steps, where m is the number of variables.  However, each of those steps takes about m^c, where c is some constant that would make any algorithms professor very cross.  This is mostly because in my excitement I programmed some of the most inefficient code ever--I didn't care, so long as it was polynomial.  Well...now I do care.  Because it takes forever to run.

Now, I suppose, I'll try an optimize it.  Maybe find a supercomputer I can run it on.  It might not be that bad...maybe it didn't actually run all night.  I went to bed at like 12:30 or 1:00 am, so for all I know it could have stopped shortly after.  Maybe what I need to do is add timing information.

[Edit]
First optimization:  when I have to search through two enormous lists of clauses, I no longer copy them to a third list first.

SatLib


[Nothing to see here]
Q. Why can't I connect to my EC2 instance
A. You used your private key from last time you tried aws instead of the one you just created for your instance, you didn't open up the SSH port using amazons lame security editing interface, and you tried to ssh in as yourself instead of 'root' (need to prepend root@)

setting up what I need on Fedora Core
useradd -m bob
passwd bob
# you still can't ssh in as bob...
scp -i /home/dave/awskeys/sat/sat.pem /home/dave/msat4.git root@longassname.amazonaws.com:/
msat4.git
yum install git-core -y
yum install screen -y
vim /etc/sudoers  #add new user

#have to download the jdk from sun's retarded website, which you can only access with a fat, modern browser
#scp it to the EC2 instance
#run suns intaller; its a pain the ass

#(do this as the user)
export PATH=$PATH:/opt/jdk1.6.0_21/bin
echo "export PATH=$PATH:/opt/jdk1.6.0_21/bin" >> .bashrc
export JAVA_HOME=/opt/jdk1.6.0_21/
echo "export JAVA_HOME=/opt/jdk1.6.0_21/" >> .bashrc
or: export PATH=$PATH:$JAVA_HOME/bin
#edit sshd_config and set ChallengeResponseAuthentication to yes
#also change PasswordAuthentication to yes


compling like eclipse does it but without ant because fedora core SUCKS
#using junit from eclipses plugin folder.  figure that can't fail
scp -i /home/dave/awskeys/sat/sat.pem ./junit-4.1.jar root@longassname.amazonaws.com:/home/bob/

export cp=`find lib -iname '*.jar' -exec echo -n {}: \;`.
javac -d bin `find src -iname '*.java'` -cp $cp

Screen
# when you run screen you will see:
#    Cannot open your terminal '/dev/pts/0' - please check.
# because you had to log in as root because AWS is dumb.
# execute this:
sudo chmod o+rw /dev/pts/0

to detach Ctrl+a,d
to reattached:  screen -r

rename window:  Ctrl+a, Shift+A
look at windows:  Ctrl-a, Shift+"


[edit]
It takes 6 hours for my linux box to prove that a 75-variable problem is unsatisfiable:

started at: Sat Jul 10 11:47:02 PDT 2010
ended at: Sat Jul 10 11:47:02 PDT 2010
total time: 21611586 ms

Somebody is going to be renting a lot of EC2 instances....

Thursday, July 8, 2010

Bitter Irony

In Philadelphia, a Duck Boat was involved in a collision.  A few friends wrote to tell me about it but I didn't realize the irony until now:  the Philly and Seattle operations are owned by the same company and the Duck Boat was apparently run over by a boat.  I want to gloat so bad but it looks like two people may have lost their lives, and aside from my simmering hatred, I can feel only sadness for the victims.

Monday, July 5, 2010

Oops

Ok.  I'm back on the 3Sat.  But its under control!  At least, I haven't put any stickies on my wall.  I did run out of paper.   Anyway.

Ok wait, so if you are not a math person just stop reading now.  Unless your name is Betsy, in which case I miss you and please un-un-friend me on facebook.  Also I hope your boyfriend slips on a banana peel and gets hit by a red shell.

Anyway, I used to tell this story about how I was in graphics class, and the professor mentioned how one file format was 1 based, "so you java and c++ programmers will have to subtract 1 from the indexes" and the really annoying kid who at the time, lived in constant fear that there were people left who didn't yet know that he loved java and that java is teh best language evar, piped up with yet another braindead comment:  "or you could just use a hashmap."

I was shy back then, but this put me over the edge; I turned to him and asked "WHY WOULD YOU DO THAT?" in my i-hate-your-guts-and-hope-you-die voice.  The entire class laughed at him and I found myself smiling.

Anyway thats a terrible story and I don't know how anyone ever enjoyed it--maybe its because they knew who I was talking about.  But I digress.  I bring this up, because I'm feeling a sense of irony.

My great weeklong 3-Sat bender?  The one that ended with my algorithm being defeated by the first unsatisfiabled test problem I threw at it?  Well, the format those test problems are stored in has a really lame name like ".cnf" and it is one based.  Yeah.  Guess who forgot to subtract 1 from an index:

}else if(i < 0){
  //negative numbers mean the literal is negated
  literals.add(Literal.get(i*-1).getNegation());
}else{
  literals.add(Literal.get(i));


In case you can't read Java code, the above section states that I am an idiot, and that the algorithm that I spent more than a week writing, HyperReduce, was never fully tested (the variable i is the 1-based CNF index, and Literal.get() takes 0-based indexes).  For all we know it could still work.  I have no interest in finding out if it does.  Just thinking about it gives me a headache...and I'd have to get out all of my hypercube boxes from their hiding place under my guitar stuff.  The algorithm I'm working on now is a lot simpler, and does not require trips to 7-11 to buy soap.  And I've still been functioning like a normal human being this time.

In deferrence to my former classmate, who was the brunt of comments that, in light of this discovery, I now feel remorse for, I contemplated writing "maybe I should have used a hash map now."  But that is still a retarded idea.  With the exception of languages that are missing a subtraction operation, there is absolutely no excuse for using a hashmap to transform between 0-based and 1-based indexes ever, because anyone who even knows what a hash map is knows not to use it for that purpose!  I suppose, in theory, one could use it without knowing what it is...thats a stretch though.

Anyway, I unit tested every inch of the algoritm, but didn't pay much attention to the code that opened a file and read it.  And that brought the whole thing down.  For all we know HyperReduce could still work.  Will it?  I'll find out as soon as I'm really really bored for a really long time.

This is a little like the time I stayed up all night fixing our implementation of a Pipelined MIPS processor in VHDL  and at the end got stumped because I forgot what hexadecimals are.

Why did I stop to write about this?  Honestly, its because I don't even want to think about how to take the index and both add -1 and multiply -1.  I hate this stuff.

[Edit]
Ok I think the subtraction happens after the multiplication.  Well, lets just see what happens.

[Nothing to see here]
git bundle create somefile HEAD
git pull somefile