Thursday, April 14, 2011

25 Horses, 5 lanes, no clock, top 5 (not 3)

This is a logic problem I got from BruteForce.

The idea is that you have 25 horses, a 5 lane track, no timer, and want to find the fastest 5 horses. How many races can you do it in?

NOTE THAT THE ORIGINAL PROBLEM WANTED ALL 5 IN ORDER, AND THIS WAY JUST GIVES THE FASTEST 5 POSSIBLY OUT OF ORDER AND NEEDS A 9TH RACE TO ORDER THEM PROPERLY.

I stayed up all night once to come up with an 8, and thought i did, but in the morning realized that I had made a mistake. BruteForce found a description of a solution for 8. It was on the same track as me, but he didn't make the mistake I did. I take no credit.

Anyhow, here's the write-up so it's a little more visual and easier to parse than the text answer he found.

You start by running 6 races. 5 races let every horse run, and the 6th is the winner's race. You're left with:

Ordering after race 6

Note that "1" is clearly the fastest horse, since he was never beaten, and we have some information about every horse relative to at least one other horse. We can also remove some as hopeless, since they're too far back along the known relative speed graph to possibly be in the top 5.

Let's remove those.

Losers removed

Now what? Well, if we want the top 3 in order we'd race 1.2, 1.3, 2, 2.2, and 3. That's 5 horses and the answer to the "top 3 in 7" problem. That's not what we want, though.

We're going to instead race 1.3, 2.2, 3, 3.2, and 4. Why? We know that at least one of 1.2 and 2 are in the top 5, and can figure that out based on the result of our race 7. Here's our race 7.

Race 7

Let's take the easiest result case first. 3 and 4 are the top 2. 3 had to have beaten 4, since we knew it was already faster. 2 is therefore in the top 4 in second position, and the final horse is one of 1.2, 2.2, 3.2, 4.2, 5. That's 5 horses and we can just race them. Brown indicates horses to be in race 8.

Simple 7 result

Now let's look at a complicated result. 1.3 and 2.2 are the top 2, in that order. What do we know?

The key piece of information is that since 2.2 beat 3, 3 cannot be in the top 5. Why? For 3 to be in, 2 would have to be in, as well as 2.2. Both beat 3. But that also means, since 1.3 beat 2.2 that 1.2 is in there too. We ran out of places. The same logic rules out 2.3. Depending on the result of race 7, you might have to flip the graph but can then apply the same reasoning as it ends up being symmetrical.

So in this case, which is an example of the most complicated situations from race 7, ends up looking like this:

Complex 7 result

1.3 and 2.2 run again, and 1.2 doesn't need to run because it has to be in the finals anyhow. The top 3 from this race are in the top 5 with 1 and 1.2.

This was a much better problem than the "top 3" version.

Monday, February 01, 2010

Flame on!

I'm sure this won't be controversial at all.

Mississippi vs Vermont, and everyone else

The standout seems to be Utah. Go Mormons!

Thursday, January 21, 2010

RIP Professor Moody

Nothing more to say about this, just that Professor Moody is no longer alive.

RIP

Friday, December 04, 2009

Grinching TSO

This is going to be a bunch of bitching, but it gets nicer at the end.

So last night we went to the Trans Siberian Orchestra Christmas concert at the Honda Center in Anaheim. I guess it's where the Ducks play, but I've never been there for any reason in the past. I shall never go there again, since even Cindy can't fit comfortably in the seats. You can imagine how ridiculous it was for me. Imagine the middle seat on an airplane if there were a wall where you typically put your feet under the seat in front of you. It's actually painful to sit there.

The concert started late, and they quickly informed us to stay until the end for a special treat that would only be happening in LA. I was wondering why they'd need to encourage people to stay when the show started.

For over an hour they played crappy Christmas music interspersed with someone telling a boring story about a bar and vodka in rhymed verse. By rhymed verse I mean that someone swapped out words from "How the Grinch Stole Christmas" and used the same meter. Instead of whoville we have a bar, too bad the writer wasn't hit by a car.

Anyhow, this all pretty much sucked with perhaps one decent song. I'm typically amazed at live music performances, since it's something that I can't do. Not this time, as at least half of the parts could be learned by a 10 year old in a week - assuming that they hadn't ever played before. A few hours if they had any experience at all. The hardest thing for them to learn would be the incessant head-banging/hair twirling that seemed to be the primary job requirement. Think "The Exorcist," but the heads spin more quickly, and the vomit is coming out of the instruments (except in the case of the singers).

But the simplicity and spinning heads of it wasn't the worst part. That's reserved for the constant applause whoring that the performers were carrying out. They'd randomly hold crappy notes for way too long and then do the "gimme some cheers" hand gesture to get people to acknowledge their misplaced feat. Even if they were as good as they seemed to think they were, I would have still been annoyed after an hour of that crap. Sustains that weren't meant to be are more annoying than a screaming baby.

So this stuff finally ends. Hardly anyone actually walked out yet, and they decided to have a sort of awards show for the members of the group. "Let's have a round of applause for the Orson Welles, nay James Earl Jones of our generation, the guy who wouldn't shut the fuck up between the songs!" And the crowd roared. And they roared for all of the performers in due time as they were so slowly announced.

So after this mini ceremony, the show actually got decent. Not great, but at least listenable. They played some new non-christmas stuff that sounded neat, and then played the famous songs that they're known for. There was far less speaking and singing during this "better" part of the show. If you ever buy one of their CDs to hear one of the neat songs (like Wizards in Winter, or something) and hear some random crappy singing on a track after or before the one you're wanting to listen to, realize that that is most of their music and that the cool songs are the outliers.

So anyhow, after a while of this better concert the owner comes out and says that our treat is ready for us. By now at least 10% of the people had walked out in disgust, so they missed out on the best part of the evening. Joe Walsh was there to play a few songs (obviously "Life's Been Good to Me So Far" or whatever it's called). He was definitely the best performer (despite being 62 or so) and I had more fun in his 15-20 minutes than in the rest of the concert combined. I felt that in a way I got my money's worth since he did so well.

Walking out, we heard others echoing our sentiments that the show definitely got better as the night went on, but it was about an hour and a half too long - the first hour and a half. As was told to Amadeus in the 1984 Best Picture of the same name: "Too many notes. Cut a few and it'll be perfect."

"Which few, your majesty?"

"The first 15,934."

But there was one man who loved the show, and he was sitting directly to my right. He was clapping in time with the music, and at one point he and I shared a moment together as only we were clapping. Later, he began slapping his hand against the cup holder to let us know how much he still liked it. Note that the cup holder is connected to the arm rest, and the arm rest is connected to his chair, and every fucking chair is connected to every other chair in the row. I looked at Cindy as we were shaken by quarter notes at 140bpm and she whispered "just let him have fun and enjoy it" to me while smiling at the atrocity we were stuck witnessing.

The only show that I liked less than this one so far in my life was some crappy art show in Laguna where actors posed to reenact famous paintings. By famous, I mean that if you looked them up you could figure out what they are but you'd never have heard of them otherwise. That's how famous these were.

Cindy is going to be concentrating more on the absurd "Hark! the Herald Angels Sing" dramatic reading (I can't call it a song) that one of the singers chose to attack our ears and sensibilities with.

Saturday, August 01, 2009

Been a long time

So in the last month or so I've been pretty busy with next to nothing to blog about. The biggest change that I've made is that I bought a motorcycle. It's one of those things that is nowhere near as dangerous as the stats make it out to be due to the activity attracting maniac retards who end up killing themselves. The biggest things to worry about are intersections and traffic moving in other directions.

Anyhow, it's fun as all hell. I got an Aprilia SL 750 Shiver, mainly because it was one of 3 bikes that felt right when I sat on them. The other 2 options had a lot more power, and a 750 seemed "weak" enough to both learn on and to be powerful enough even in the future after I feel more comfortable with my riding. The other 2 options were also 4 and 9 thousand dollars more, which was also part of the decision making process.

The computer controls the throttle, and there are 3 modes. Rain, Touring, and Sport. I spent several days in Rain mode getting comfortable since the throttle is nerfed. I've now upgraded myself to Touring mode, and I doubt I'll ever use Sport mode except on track days. I tried it for about 30 seconds and went back to Touring mode. It turns the bike into a rocket.

It's pretty damn relaxing to be out there riding on empty roads. I always hated automatic cars since I feel like I have absolutely no control over what the engine and transmission are doing. A motorcycle is always a manual, plus the way you handle it is far more immersive. Plus you're right there in the wind, zipping along and loving every minute of it.

My goal now is to become a decent rider, and after that I'll try to get good, and then better than that. At the same time I'm hoping to demonstrate that it's really not that hard to be safe on a bike and avoid death - just don't be a retard, and actually work at getting good with handling it.