House Jobs and The Stable Marriage Problem
Jun1
Being the steward for a fraternity has it’s ups and downs. Being appointed as one this summer, my role comes with several responsibilities: making sure everyone does their jobs, collecting money, and choosing everyone’s cleaning job for the Summer.
So let’s talk about the last responsibility: Choosing people’s jobs. Identifying this problem, there are several factors to consider:
- Everyone’s Job preference
- Who’s preference has higher priority
- The location of that person’s room relative to the location of the job.
So why is the last one important? Because people are more likely to do house jobs that affect them: cleaning a bathroom closer to you has a lot of incentive compared to cleaning one that you never use.
My love for applications of my abilities made me pose the problem in a way solvable using math and computer science. So I present the “Stable Marriage” problem.
Stable Marriage Problem
Our problem has the following backstory: Let us suppose that we have an even amount of men and women. Everyone has a preference list, ordering who they want to marry. What are the best matchups?
Of course, I don’t know what kind of people would actually create a problem like this. Seriously, what kind of person would say: “Hey, there’s four of us, there’s four of you, so let’s get hitched! But wait, we all like different people, so how are we going to decide who’s going to marry who?”
Regardless of how rediculous the problem is, here’s the way it works:
1. Start with the first guy, and see if the girl he prefers is available:
i. If she is, then pair them up!
ii. If she isn’t, then check to see if she prefers our guy more:
a. If she does, then pair them up!
b.If she doesn’t, then our guy goes on to the next girl, starting again with step 1.
2. Once the guy is paired up, we start with the next guy, repeating at step 1.
Eventually, every guy will end up with the highest-ranking girl on his list that doesn’t prefer some else who prefers her. Thus, since every guy with such a girl, everyone is more or less “happy”. Thus, the marriage are “stable”.
Now, you probably notice that we could have done the same thing for girls. The method listed above find the optimal pairing for guys: Every guy gets with who they want, but this is not necessarily true for girls. If you interchange it so that the girls get to choose, then the opposite happens: girls get who they want, and guys maybe not.
So I guess the bottom line is that there’s two ways this problem could go: Optimizing for girls or for guys. Either way though, these solutions will look very similar.
What’s this got to do with house jobs?
The hypothetical problem that you saw above is just a part of Stable Matching. That’s the official name for this particular problem. It’s just finding a Stable Match – A situation in which one object does not prefer any other object that prefers it over their current pairing.
I bet you see where I’m going here.
We essentially have two groups of equal number that must be paired up: house jobs, and the people who live in the house. It’s easy enough to get the preferences of the people: you can just ask them to give you their choice in order. But how exactly does the house job prefer one person over another?
This is where math comes in. I generated a function that will the algorithm determine the preference of a house job. Here it is:
(Distance of job from person in question)*2 + (#of that person in the queue) = priority of person to housejob.
The lower the number, the more the house jobs prefers the person. Distances in this algorithm have three levels (so integers 1,2 and 3). This is multiplied by two to increase the effect that location has on the priority due to a house job. Otherwise, the number of the person wins over.
So, a perfect example of a Stable Marriage Problem.
[EDIT] I guess due to some difficulties, our house is getting shut down. Thus, no need to code this thing. Oh well, it was fun anyway.
Today I want to learn…. Introduction to Programming II
Jun0
So want to learn more about coding? Ready for the craziest thrill ride of your life? Well, it’s not going to be that big of a deal. But If you read my previous post on programming, you should know what a program is and how it is made. So, it’s time to learn that gibberish and figure it out from there. To teach you these concepts, I’ll be showing examples in the most widely used programming language at the time of this article: C++.
Compiled Languages and Scripting Languages
All programming languages can be divided into two categories, compiled and scripting. So what’s the big difference? Well, remember when I was saying that we need a compiler to make the computer be able to execute your code? Well, the difference between these languages is when and how the code is compiled. Compiled languages, in order to be run, must be sent through a compiler and then executed. Scripting languages, on the other hand, are sent to the computer as is. The computer then has an “interpreter” built in, and “compiles” it every time it is run, on the spot. To be truthful, compile is the wrong word for scripting languages, so it is best to think like they’re being read by the computer. The best way to think about it is that for compiled languages, we need an interpreter (compiler) before the computer can read the code, and for scripting languages, the computer learns the language so it can do the instructions, just by giving it the instructions raw. Both types of languages have their own advantages and disadvantages. For the examples, we’re using a compiled language, C++.
Includes
So, we know what a compiled language is. So what’s next? Every language has a basic set of terms (also known as functions) by default. Some languages allow you to insert more terms into your program, and that is what includes consist of. C++ requires certain functions in order to act like it should. So, we need to include a list of functions, like so:
#include <iostream>
using namespace std;
as you can see, we have an <iostream>. This provides us with functions that allow us to produce actual output that users can see. as for the “using namespace std;”, this is the basic set of commands that the C++ program will understand. the “std” is short for standard. So, inserting this at the top of your file will include the iostream set of commands, as well as the standard set of commands.
The Semicolon
This is a good time to talk about one of the most vital parts of programming: the semicolon. Basically, think of the semicolon like a period; it ends your sentences and instructions
Functions
One of the things that almost all programming languages have in common is functions. A function is basically a way to package a set of instructions. So if we want our program to execute that set of instructions, we simply “call” that function. Now, for C++, we need a “main function” that the program executes when it starts. For C++, it looks something like this:
int main ()
{
//Instructions Here
}
So now we need a command, or some instruction to give the computer. One of the most standard beginning programs for a programmer to make when learning a language is called a “hello world” program. Basically, all it does is spit out “hello world”. So, let’s do that here, with the command in the iostream known as “cout”, which will basically print out whatever we write after it. So here it is:
cout << “Hello World!”;
So the compiler knows that we want the computer to produce this particular output “Hello World”. So, in the end, what does are code look like? Something like this:
#include <iostream>
using namespace std;
int main () {
#instruction here
cout << “Hello World”;
return 0;
}
If you give this to a compiler, it will understand exactly what you are talking about, and create a program that can be execute on whatever OS your compiler is for. Sweet, right?
Today I want to learn…. Introduction to programming
Feb0
Programming is no easy thing to learn. Well, it kind of is. It’s usually much easier for the logical type of person, (such as individuals who are good at hard sciences (such as physics, Or maybe mathematicians). However, if you are not that type of person, don’t despair! After enough practice, programming can become second nature. Now, let’s go over what programming is:
What is programming?
That’s a good question. A program is just like a set of instructions. Imagine yourself trying to speak to someone who speaks a different language than you. Try giving instructions. It’s pretty hard to communicate. Now, think about how much easier it would be if we had a translator? Now that would be sweet. So, think about a program as a set of instructions that was translated to a language that computers can understand. That is exactly what a program is. Now, the actual verb “programming” refers to someone writing that set of instructions. So, if you’re a programmer, all you’re really doing is making a permanent to do list the the computer can look at as many times as it wants.
How do I make a program?
So assuming that you read the previous paragraph, you understand that a program is nothing more than a to-do list or a set of instructions. So here’s how a developer makes a really basic program:
1) The developer writes the code.
2) The developer runs his code through what is called a “compiler”. Now what is a compiler? It’s just a really fancy word for a translator. So the developer sends his/her code (set of instructions) to a compiler (translator), and the translator does its job and turns it into a file that a computer can read.
So the question comes down to: Why is programming so damned difficult and why are people getting paid 60 grand a year to do it?
Well here’s why: Because programmers have to learn to speak a completely new language.
It’s because you can’t just insert plain English or whatever language into a computer and see an awesome program pop out. In order for the translator to understand you, you have to speak his language (and no, his language is not money.) The translator speaks some sort of ridiculous gibberish to you. So, you have to learn to speak it back. This (as well as a few other things) is why computer scientists get paid the big bucks.
Don’t get discouraged just yet. Once again, programming is easy. Anyone can do it. It all depends on how much effort you put into it.
Now, you understand the basics behind a program, so the primer is over and the real learning can begin. Good luck, and read my next post if interested in becoming a most bawlerly programmer.