The New World OrderWho wants to be on the Advertising Team?An open prompt for all users



Science journals of interest: Scientific American - Nature - New Scientist - Science AAAS - Science Daily

LAST EDITED: March 17, 2015

Here are some interesting links I had stickied:
Yeano's thread: Proving Something is Independent of our Axioms.
Yeano's thread: Algebraic Topology and Model Theory

We have LaTeX running on GT! Thanks to Xhin!


Team Building Puzzle
Posted: Posted October 10th by EN



Successfully navigating the waters during sea voyages is a challenging task. A captain’s most important decision is selecting the right crew for the voyage. A mix of different skill sets are required to sail the ship efficiently, navigate to the destination, and fish for food along the way.

The table shows a list of crew members that are available for you to hire for the voyage. Each crew member demands a salary for the voyage and has different skill levels of Fishing, Sailing, and Navigation.

In order for your journey to be successful, you must have a cumulative skill of 15 or more in each of the three skill categories from all of your chosen crew members. You may choose as many crew members as you like.

What is the minimum achievable cost for the voyage? How do you get it?

settingsOptions
There are 17 Replies

Most people would try to brute force the answer (especially with our computers to do it). Would you suggest there is a better way of going about it?

Posted October 10th by Kohlrak
Kohlrak

There are a couple of useful techniques mentioned in the thread below. I also want to see what other creative ways people might try to solve it.

Posted October 10th by EN
EN

I did some analysis on the data (will attach a CSV at some point) and determined a few things:

Best fishermen -- Dan, Eva, Henry, Amy | Carl, Ida, Greg, Bill | Fred
Best Sailors -- Amy, Carl, Dan, Henry | Fred, Ida, Bill, Eva | Greg
Best Navigators -- Bill, Fred, Greg, Ida | Eva, Carl, Henry, Dan | Amy

Best all around: Carl, Eva, Dan, Ida | Henry, Amy, Bill, Fred | Greg

"Best" in this case means that they have the lowest score -- scores were calculated by dividing the salary (without the 000) by the proficiency in any area. All around bests were calculated by totaling all three scores.

I realized later that a better idea would be to crunch the salaries together and subtract the minimum salary so it looks like the 1-5 of the proficiency scale and then get a better way of comparing them.

Buuuut this didn't help so I'm going to do this a different way.

Posted October 11th by Xhin
Xhin
 

I decided to look only at each individual proficiency...

Henry, Dan, Eva, and Amy are the minimum team to reach 15 in fishing. This is true on both actual data and score.

Amy,Carl,Henry,Dan are the minimum for sailing. Again, true in both ways.

Bill, Fred, Greg, Ida are the minimum for navigation

It's worth noting that while there are differences between the ranking in absolute proficiency and ranking in score, the differences are evidently small enough that the same three lists shows up every time.

Posted October 11th by Xhin
Xhin
 

Best list

If you go by the best list, you need a minimum of Carl, Eva, Dan, Ida, Henry, Amy, Bill to reach 15 in all categories.

Fishing: 23
Sailing: 23
Navigation: 16

Salary: 339,000

This doesn't seem optimal.

One problem is that getting fishing and sailing to 15 together is easy, but the navigation list is the complete opposite. So just to confirm, I'm going to try to hit 15 by hitting 15 by navigation first and building from there..

Navigation-centric run

Bill,Fred,Greg,Ida,Dan,Amy = (15,17,19), $308,000

I think this is probably optimal. For one thing, Dan and Amy are in both lists. Reaching 15 on sailing and fishing simultaneously is easy, reaching 15 on navigation is hard, so it makes sense to get that out of the way first and then hit the bests on the other categories.

Of the bests lists, Dan/Amy/Henry seem to be universal, so I'm going to try it with all variations of those three:

Bill,Fred,Greg,Ida,Dan,Amy = (15,17,19), $308,000
Bill,Fred,Greg,Ida,Dan,Henry -- (17,16,20) $326,000
Bill,Fred,Greg,Ida,Henry,Amy -- (16,18,20) $336,000

Posted October 11th by Xhin
Xhin
 

Greg has a terrible total score but there's no replacement for him -- on any list that has Bill and Ida already, you would need THREE people to replace him to reach 15 on navigation.

So you definitely need Greg.

Fred is similarly terrible, but if you have Greg, Bill and Ida already you need at least two people to replace him.

Bill needs three people to replace him, Ida needs two people to replace her.

I can't imagine reaching 15 on navigation without Bill, Ida, Greg *and* Fred.

At that point your scores are (8,9,17) and you need 7 more fisherman and 6 more sailor skills to hit 15 on those categories. That's going to take a minimum of 2 people.

I chose Dan and Amy for those two people because the total of their Fisherman+Sailor scores were the lowest. Henry actually has more proficiency in both but his salary is much higher than Dan or Amy and that shows when you add the totals together.

I think this is probably your optimum list. I've been trying to find a flaw in it and have been unsuccessful.

Bill,Fred,Greg,Ida,Dan,Amy = (15,17,19), $308,000

Posted October 11th by Xhin
Xhin
 

Here's a CSV of the data table I was using:
http://gtx0.com/rendered/team_building.csv
name -- straightforward
fishnum -- fishing proficiency
sailnum -- sailing proficiency
navnum -- navigation proficiency
salary -- salary with the extra zeroes removed
fish -- salary/fishnum
sail -- salary/sailnum
nav -- salary/navnum
total = fish + sail + nav

Posted October 11th by Xhin
Xhin
 

I like the way you think. Greg definitely is a powerhouse. To compare, I was able to find a five person crew for $40000 less than what you currently have.

Posted October 11th by EN
EN

I went ahead and made a program to find your variation (and all possible variations). Here's the output:
http://gtx0.com/rendered/sail.htm

Posted October 12th by Xhin
Xhin
 

I have no idea how you'd solve this with math -- unless you altered my algorithm to turn it into a matrix and used matrix math.

Posted October 12th by Xhin
Xhin
 

By the way I don't know what the correct way of programming permutations is, but the way I did it was to run every number from 1 to 511, convert it to binary, and use each bit to determine whether that person was in the team or not. 511 is (2^9)-1, with 9 being the number of people.

Posted October 12th by Xhin
Xhin
 

That's the solution I found, too. Technically what you generated were combinations. not permutations, since the order of the crew doesn't matter. But that's a pretty clever way of generating them.

Posted October 12th by EN
EN

It may be cheating, but using LINGO I wrote up an integer optimization program that gives me the following results:

Objective Value: 268k

Crew members: Amy, Bill, Carl, Greg, Henry



Posted October 14th by Malas
Malas
 

I don't think that's cheating. I used Python. I don't know of an easy way to do this without computers.

Posted October 15th by EN
EN

By the way Xhin, this type of problem can also be flipped around. Instead of trying to find out the minimum amount to spend to meet a certain point requirement, you can maximize points given a cost limit. This can be applied to games, maybe even ones you run here. Given different items/stats that you can buy in different areas, you could find out the most (or "best") that you could do given a certain amount of money.

Posted October 15th by EN
EN

I originally tried doing it on paper as a standard optimization problem (Kuhn-Tucker conditions) but I haven't the least idea how to solve the problem, on paper, when the optimal set is restricted to integers.

Posted October 15th by Malas
Malas
 

Yep. Integer programming is just that much more difficult than regular linear programming.

Posted October 15th by EN
EN
Reply to: Team Building Puzzle

Enter your message here


Site Rules | Complaints Process | Register Complaint Facebook Page
GTX0 © 2009-2017 Xhin GameTalk © 1999-2008 lives on