The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Candy Algorithm

Not sure if this is the correct forum but there used to be a place to ask intersting logic questions.

Question:
The mayor of a small town wants to distribute candies to every house in his riding. He has a stock of 40 types of candies and he knows how many kids are in each household and what each kid likes. Something like:

House,Candy
1,2
1,3
2,4
2,1
2,5
and so on.

The above shows that House#1 has two kids and they like candies #2 and #3 each. House#2 has three kids and the like candies #4, #1, and #5 each.

The mayor wants to know what are the top 10 candies that would suffice the largest number of houses?
AA
Thursday, November 24, 2005
 
 
The search term you are looking for is "Operations Research".
Matthias Winkelmann
Thursday, November 24, 2005
 
 
Am I the only one who thinks the phrase : "that would suffice the largest number of houses" is not precise enough to mean anything in terms of algorithm and criteria ?
Alexis MICHEL Send private email
Thursday, November 24, 2005
 
 
I guess there is confusion because of the way I laid out the data. Here is another example using sets:

House1 {2,3}
House2 {4,1,5}
House3 {1,2,5}
House4 {5,6,10}
House5 {1,2}
House6 {2,3}
House7 {1,2,3}
House8 {2,6,8}
and so on.

In this example, if the mayor had to choose top 3 candies, it would be Candy1, Candy2, Candy3 because they will suffice 50% (4 out of 8) houses (House1, House5, House6, House7)
AA
Thursday, November 24, 2005
 
 
I love these posts where the poster doesn't even understand the homework question well enough to paraphrase his professor's phrasing into another equivalent one that he hopes the professor won't recognize.
Art Wilkins
Thursday, November 24, 2005
 
 
Hi Art

I will ignore your presumption and wait for someone to solve the problem. Thanks for your insight.
AA
Thursday, November 24, 2005
 
 
AA,

show us your try first. We can then comment on your solution and give further ideas and optimizations, maybe even different solutions if your one basically works. This way you have the best chance to go with a homework question.
AA & !AA = 0
Thursday, November 24, 2005
 
 
I'll try to better structure the problem: let's say each node "T" is a candy type, with a demand "DT". Each demand is the number of houses that demands the given candy type.. so you have to build this structure and then it becomes a reordering problem: you take the node with the biggest demand, then second... and so on.
If N is the number of houses and T the number of candy types, the worst case complexity is O(T.N)+O(T.log(T)). The first term is for cycling through each house counting each candy type the house is demanding. The second term is the classical reordering complexity.
Johncharles Send private email
Thursday, November 24, 2005
 
 
Why do you need someone to solve this problem for you?
John
Thursday, November 24, 2005
 
 
Okay, decision analyis:

some thoughts:

1. Diminishing value: the value for each added type of candy (c) per household (h) decreases: if h(1) wants c(1) and c(2) then c(1) will provide 60% of the value for h(1) (v(1)) and c(2) will only add 40% to v(1).

2. Politics: the mayor does not want to maximize the absolute overall value (v = v(1)+v(2)+v(3)...). Instead, he wishes to distribute the value somewhat evenly. Reason: the anger of h(1) with v(1)=0 with their knowledge of h(2) with v(2)=100 will result in next_election = lost;

Instead, he'll chose a value function of v = v(1)*v(2)*v(3)... therefore ensuring a somewhat even distribution of value amongst the households. Therefore, he'll first fullfill at least one wish from each h.

BUT after rereading the post I just noticed we're dealing with households which are coalitions of children. In each coalition, the mechanics outlined in 2. are at work: If one child gets candy and the other doesn't, the overall value v(n) is probably negative.

At this point, the mayor will notice that he can't win: either he fullfills all wishes of half of the families (=the other half kills him) OR he fullfills half of the wishes in each and every family (all of them kill him).

He'll spend the money on eggnogg and get mighty drunk and reelected.
Matthias Winkelmann Send private email
Thursday, November 24, 2005
 
 
John, I need advice on how to approach this problem (not necessarily need a completely coded solution).
AA
Thursday, November 24, 2005
 
 
I'll bite...

# read in the poll from STDIN
candy_poll = STDIN.readlines.map { |line| line.chomp }

# candy_poll_index maps a house to a unique array of candies that is consumed by that house
candy_poll_index = Hash.new { |k, v| k[v] = [] }
candy_poll.each do |vote|
  house, candy = vote.split(',').map { |x| x.to_i }
  candy_poll_index[house].push(candy) if not candy_poll_index[house].include?(candy)
end

# given a candy_poll_index, finds the
# most popular candy (by household)
def find_most_popular(candy_poll_index)
  vote_count_index = Hash.new { |k, v| k[v] = 0 }
  candy_poll_index.each_value do |candies|
  candies.each { |candy| vote_count_index[candy] += 1 }
 end
 vote_count_index.sort_by { |house, votes| votes }.reverse[0][0]
end

# find the 10 most popular candies
popular_candies = []
1.upto(10) do |count|
  popular_candy = find_most_popular(candy_poll_index)
  popular_candies.push(popular_candy)
  candy_poll_index.each_value { |value| value.delete(popular_candy) }
end

puts "The ten candies that satisfy the most households are " +
      "#{popular_candies[0..8].join(', ')} and #{popular_candies[9]}."


Very ugly solution provided without warranty.  I'm not even sure if this is what you are looking for.

Happy Thanksgiving!
anon
Thursday, November 24, 2005
 
 
By the way, this has horrible time complexity.  Depending on how large your town is (although you did mention it was small) you might want to find another method.
anon
Friday, November 25, 2005
 
 
I have only read about 1/3 of the posts but here is an idea:

- build an array where each element coresponds to a type of candy
- initialize the set with 0
- walk the houses set and whenever you find a candy in its set do increment the current node value
- once this is done you have
a) an array with candies preferences - sort this array and you get the preference order
b) you have a total number of candies, and the type / quantity so you could calculate various distribution
eg candy/house or candy/kid and so on

The algorithm is suitable for parallel processing ...
Van Goch Send private email
Friday, November 25, 2005
 
 
Van Gogh found the same solution as me.... probably this means it's the right one... and it's complexity is not overkill (read my post): it's polinomial - quadratic
Johncharles Send private email
Friday, November 25, 2005
 
 
Create 3 tables: House, Candy and a Child table. Child joins the other 2 together.

Create Table House(
    houseid  int
)

create table Candy(
    candyid  int,
    candydesc  varchar(50)
)

create table Child(
    childid  int,
    houseid  int,
    candyid  int
)

The following query should give a list of top 3 candies.

select top 3 candydesc, (Select count(c2.candyid) from child c2 where c2.candyid = c1.candyid) as [Count]
from candy c1

PS. Haven't checked table definitions work.

PPS. Not very scalable query.
Justin Send private email
Saturday, November 26, 2005
 
 
Van Goch - I think the problem is that the house has to be completely satisfied for it to count. That is, if candy 2 is offered, but candy 4 isn't, then a house

 houseN{2, 4}

won't count.

Here's a possible approach:

1) Create an M-dimensional array of bitmaps of N bits, where N is the number of candies and M is the number of houses.

2) Flip the bit to 1 for every candy enjoyed in each house.

3) Create candidate bitmaps for offerings of candy.

4) Loop over all houses, and bitwise && the candy bitmap with the house bitmap. If the result is equal to the original house bitmap, then everyone in the house is satisfied, and you can increment the counter for that candy bitmap.

5) At the end, compare all of the candy bitmaps.

This scales horribly. With 3 candies, I think the number of house/candy bitmap combinations is M * "N choose 3", which is:

  M * N! / (3! * (N-3)!)

 = M * N * (N-1) * (N-2) / 6

which scales like O(MN^3).

But giving away candy to kids is a bad idea, anyway. It just makes them hyper.
EKB Send private email
Sunday, November 27, 2005
 
 
Oops... meant "bit array", not "bitmap".
EKB Send private email
Sunday, November 27, 2005
 
 
As an example of out of the box thinking...

"He has a stock of 40 types of candies..."

And the question...

"The mayor wants to know what are the top 10 candies that would suffice the largest number of houses?"

The easiest way to solve the problem is simply go around to each house, give each kid the desired candy and then at the end of the day, see which ones were the most popular.  Glib answer?  Pay attention to the way the question is worded.  The initial stock of 40 types is considered infinite and presumably there's no cost to lugging all that candy around.  Heck, he doesn't have to do it all in one day either.

As Alexis, Mitchell and others have pointed out, you need more precise boundary conditions otherwise you're doing a lot of compute-intensive work just finding the general possibilities.

If the question was worded along these lines...

"Today, the mayor just realized he's about to loose the next election which takes place tomorrow.  Since he's also the owner of a candy company and has 100 pieces of 40 varieties of candies at his disposal, he's decided to bribe families to vote for him.  He only has time to visit 50 households.  If he can get at least one parent in each household to vote for him, he will win the election.  (He only needs 25 households if both parents vote for him.)  Given the childrens' preferences - what is the fewest number of pieces of candy he should pack?"

...then it would be easy to optimize the algorithm.
Anonymous Coward
Monday, November 28, 2005
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz