In Part 2, we had a full-blown party going! But things were convenient; since we had a meal for every guest, everyone eventually got served. Now we'll address a likely scenario - a top meal that no guest wants:
my_party = Party.new(
%w[vegetarian vegan keto normal paleo],
%w[normal paleo vegan vegetarian])
Console output:
Party Status:
Meals: ["paleo", "normal", "keto", "vegan", "vegetarian"]
Guests: ["normal", "paleo", "vegan", "vegetarian"]
No one was served the last round
Party Status:
Meals: ["paleo", "normal", "keto", "vegan", "vegetarian"]
Guests: ["paleo", "vegan", "vegetarian", "normal"]
Guest wanting a paleo meal has been served
Party Status:
Meals: ["normal", "keto", "vegan", "vegetarian"]
Guests: ["vegan", "vegetarian", "normal"]
No one was served the last round
Party Status:
Meals: ["normal", "keto", "vegan", "vegetarian"]
Guests: ["vegetarian", "normal", "vegan"]
No one was served the last round
Party Status:
Meals: ["normal", "keto", "vegan", "vegetarian"]
Guests: ["normal", "vegan", "vegetarian"]
Guest wanting a normal meal has been served
Party Status:
Meals: ["keto", "vegan", "vegetarian"]
Guests: ["vegan", "vegetarian"]
No one was served the last round
Party Status:
Meals: ["keto", "vegan", "vegetarian"]
Guests: ["vegetarian", "vegan"]
No one was served the last round
. . . . <hundreds of lines later> . . . . .
Party Status:
Meals: ["keto", "normal", "vegetarian"]
Guests: ["vegan", "vegetarian", "normal"]
No one was served the last round
Traceback (most recent call last):
11913: from stacksandqueues2.rb:104:in `<main>'
11912: from stacksandqueues2.rb:97:in `meal_service'
11911: from stacksandqueues2.rb:91:in `move_queue'
11910: from stacksandqueues2.rb:91:in `move_queue'
11909: from stacksandqueues2.rb:91:in `move_queue'
11908: from stacksandqueues2.rb:91:in `move_queue'
11907: from stacksandqueues2.rb:91:in `move_queue'
11906: from stacksandqueues2.rb:91:in `move_queue'
... 11901 levels...
4: from stacksandqueues2.rb:91:in `move_queue'
3: from stacksandqueues2.rb:82:in `move_queue'
2: from stacksandqueues2.rb:74:in `view_party'
1: from stacksandqueues2.rb:21:in `display_meals'
stacksandqueues2.rb:21:in `inspect': stack level too deep (SystemStackError)
Welp! What happened? Well, we got an error because the queue keeps cycling round and round, aligning different guests with the "keto" meal, but there is no match. We need a way to trash this unwanted meal, but only after making sure that there's no guest with a keto-meal preference.
We know that a top meal is unwanted if the entire queue has cycled once. So we need to keep track of how many guests have rejected the top meal; when this number equals the number of guests in the queue, we know that no one wants our top meal.
Let's introduce a rejected counter as an argument for the move_queue method. This counter is initially set to zero. For each meal-guest mismatch, rejected is incremented by 1. Then rejected is compared to the queue size; if both values are equal, the top meal is "trashed" and rejected is reset to 0:
def move_queue(rejected=0)
view_party
if match?
meals.take_meal
served = guests.leave_queue
puts "Guest wanting a #{served} meal has been served\n\n"
else
rejected += 1
guests.rejoin_queue
puts "No one was served the last round\n"
puts "Top Meal Rejections: #{rejected}\n\n"
if rejected == guests.size
rejected = 0
trashed_meal = meals.take_meal
puts "Unwanted #{trashed_meal} meal has been trashed!\n\n"
end
move_queue(rejected)
end
end
Party Status:
Meals: ["paleo", "keto", "normal", "vegetarian"]
Guests: ["normal", "paleo", "vegan", "vegetarian"]
No one was served the last round
Top Meal Rejections: 1
Party Status:
Meals: ["paleo", "keto", "normal", "vegetarian"]
Guests: ["paleo", "vegan", "vegetarian", "normal"]
Guest wanting a paleo meal has been served
Party Status:
Meals: ["keto", "normal", "vegetarian"]
Guests: ["vegan", "vegetarian", "normal"]
No one was served the last round
Top Meal Rejections: 1
Party Status:
Meals: ["keto", "normal", "vegetarian"]
Guests: ["vegetarian", "normal", "vegan"]
No one was served the last round
Top Meal Rejections: 2
Party Status:
Meals: ["keto", "normal", "vegetarian"]
Guests: ["normal", "vegan", "vegetarian"]
No one was served the last round
Top Meal Rejections: 3
Unwanted keto meal has been trashed!
Party Status:
Meals: ["normal", "vegetarian"]
Guests: ["vegan", "vegetarian", "normal"]
Awesome! Our unwanted keto meal has been trashed, and the meal service can continue unhindered - hopefully!
Now, yes, yes, I hear all you time-complexity aficionados:
"This
rejectedcounter approach may work for small get-togethers, but what if you have 500 guests or more? Are we really going to cycle through them all to trash one meal?"
You're right - that would feel like forever and irritate our guests to no end. So how about we (the delightful party hosts) stand next to the meal stack, and once a first guest rejects a meal, we yell out to everyone: "HEY! DO ANY OF YOU WANT THIS TYPE OF MEAL?" If no one answers, then we trash it. Let's create the necessary methods:
# Add this method to the GuestQueue class:
def include?(meal)
guests.include?(meal)
end
# Add this method to the Party class:
def does_any_guest_want(meal)
guests.include?(meal)
end
# Modify the 'Party#move_queue' method to the following:
def move_queue
view_party
if match?
meals.take_meal
served = guests.leave_queue
puts "Guest wanting a #{served} meal has been served\n\n"
else
puts "No one was served the last round\n"
if does_any_guest_want(meals.top_meal)
guests.rejoin_queue
else
trashed_meal = meals.take_meal
puts "Unwanted #{trashed_meal} meal has been trashed!\n\n"
end
move_queue
end
end
Another scenario to explore is when the meals are gone but there are still guests waiting to be served. I'll leave that to you :) Like, perhaps a method that stacks additional meals to serve the remaining guests?
I truly hope that this tutorial has fleshed the concepts of Stacks and Queues out a little more! Please let me know what you think in the comments. Thank you so much for sticking with me this far.
Top comments (1)
Nice read!