(Matlab)

Problem 3

Actually produce candy amounts that is under the target goal of $1 AND meets your preferences.

Extra credit: Dont just stop when the next candy choice would put you over the limit try adding a few more.

Deliverables:

Script that implements a greedy algorithm that tends to pick candies you rank highly

Run it a few times and output the result each time

Step by Step Instructions:

Start with reading the candy in and copying your RankCandy calculation from the previous problem

Two ways to do this do a look ahead to see if the next candy pick will break the bank (this is what the lecture does) and if so, dont add that candy in, just stop the loopEasiest to do this with a bKeepTrying Boolean variable

bKeepTrying = true

while bKeepTrying

Set bKeepTrying to be false if next one would go over limit

Second method is to just save the last valid set of amounts and stop when cost is too highwhile CalculateCandyCost(candy) < target

saveBestCandy = candy;

Increase one of the candy amounts

print out saveBestCandy

Extra credit: Start with method 1, but use a triedNTimes variable. Stop when youve tried (unsuccessfully) too many times (maybe 10?) to add in another candy

Self-check:

Run 1:

Current cost of candy: 99.00

Candy Cost Num Total

Rock candy 35.00 0 0.00

Gum 5.00 0 0.00

Lollipop 10.00 0 0.00

Taffy 3.00 3 9.00

Smarties 18.00 5 90.00

Run 2:

>>

Current cost of candy: 100.00

Candy Cost Num Total

Rock candy 35.00 1 35.00

Gum 5.00 1 5.00

Lollipop 10.00 0 0.00

Taffy 3.00 14 42.00

Smarties 18.00 1 18.00

Previous question :

Be greedy prefer to buy candies that you like over ones that you dont, particularly ones that are cheap. But you dont want all of the same kind. Here were just going to write a function that implements the preferred cheap part.

Deliverables:

Calculate a rank score for each candy based on its price and goodness

Briefly describe what you tried to do

Print out the candy and the ranks to the command line

Create a function that randomly picks a candy based on this rank score

Test that the randomly-pick function is working by first modifying and then running Lab8CheckPick.m with your function

Command-window output from that function

Step by Step Instructions:

2a) Make the rank score

Create your own ranking values. They can be anything you think of as reasonable, just so long as the rank goes up if you like the candy better (same cost) and the rank also goes up if you like the candy the same, but its cheaper.

This should be a calculated value dont just manually set rank values

Store them in the candy structure (the script already does that)

You can write a function to set the rank values if you want, but you dont have to.

To hand in:

Write an English description of what you were trying to do with your rank score in the section Reasoning behind rank score

Copy the script with the equation into the Answer script section

Print your struct out on the command line and copy the output to the

2a) Make the function that picks the candy randomly based on rank score

MyPickCandy is a function that (currently) takes in the rank score (as an array) and returns a number from 1 to length(array). Right now, it returns each number with equal likelihood. Modify this so that it returns higher-ranked candy items more often.

This is something called histogram sampling; its really just a fancy version of rolling a die or flipping a coin to randomly pick an item. Refer to lecture notes, but the brief description is: suppose you had three candies with rank values of 1 and 2 and 4. Then you should pick the first candy 1/7^th of the time, the second candy 2/7ths of the time, and the last candy 4/7ths of the time.

How to do this:

Sum up all of your rank values call it sumRank

Generate a uniformly distributed number between zero and sumRank

See which bin you lie ini.e., for the example above your bins would be

0 0+1 0+1+2 0+1+2+4

which is: 0 to1, 1 to 3, and 3 to 7

If your random number is between 0 and 1, return 1

If your random number is between 1 and 3, return 2

If your random number is between 3 and 7, return 3

i.e., if your random number is between a(k) and a(k+1), return k

Double check that youve handled the case of your random number being zero or sumRank

What to do:

Modify MyPickCandy.m to use the rank values instead of just picking

Check that you implemented your function correctly using Lab8CheckPick.m

You should get values that are close, but not exactly the same as, your original rank values. Its like flipping a coin youll get close to 50% heads, but not quite

To hand in:

The modified MyPickCandy.m script

The command window output from running Lab8CheckPick.m

Self-check: Note that your rank scores will be different but the CandyRank should reflect both CandyCost and CandyGoodness in the example below my favorite candy is the last but it costs more, so the 2^nd to last candy (which I also like but is cheaper) has the highest rank

Part a: You do NOT need to match the rank values/goodness values Ive given. They should depend on what youve set them to be.

>> candy

candy =

CandyName: {1x5 cell}

CandyCost: [35 5 10 3 18]

CandyAmount: [0 3 1 1 4]

CandyGoodness: [6 1 1 7 8]

numCandyTypes: 5

RankCandy: [6 7 3.5000 81.6667 15.5556]

Part b:

>> Lab8CheckPick

6 1 1 7 8

5.9931 1.0136 0.9757 7.0242 7.9934

>>

MyPickCandy.m

function [ tryCandy ] = MyPickCandy( rankCandy ) %PickCandy Pick one randomly based on the rank values % Throw a die and see what bin it lies in % See lecture notes

% Generate a number between 1 and the number of candies % Lab TODO: Change to be the sum of rankCandy pickVal = rand(1) * length(rankCandy);

% Make sure we set this to the first item before we start, % i.e., pickVal is in the first bin tryCandy = 1;

% Lab TODO: Change this variable to keep track of the % current rankCandy sum, instead of the index sumCandy = 1;

% Loop through the bins in order until you get to the one % that contains your number while sumCandy < pickVal && tryCandy <= length( rankCandy ) % Lab TODO: Change this so that it keeps track of the % rank values instead of the index sumCandy = sumCandy + 1; tryCandy = tryCandy+1; end

end

Lab8CheckPick.m

%% Script to check your PickCandy function % Change the "CHANGE HERE" bits % % Key matlab concepts % Structs - how to save data in one "variable" % Optimization - how to iteratively improve on something % More practice with functions, program flow

clear clc clf

% Read in and setup candy % CHANGE HERE: Make sure this is your function and your data file candy = GetCandyModified('CandyDataModified.txt');

% CHANGE HERE: Put your code to calculate rank scores here candy.CandyRank = candy.CandyGoodness;

%% The code to do the checking % Basically, call your function many, many times and see if it creates the % same probability/rank values candyPicked = zeros( size( candy.CandyRank ) ); for k = 1:100000 %% CHANGE HERE: change the function MyPickCandy % See instructions in MyPickCandy picked = MyPickCandy( candy.CandyRank ); % Record which one was picked candyPicked( picked ) = candyPicked( picked ) + 1; end

% Normalize and set to same range of values as rank candyPicked = sum( candy.CandyRank ) * candyPicked / sum( candyPicked );

%% CHECK HERE: The current version of MyPickCandy should % produce roughly equal numbers (i.e., something like 3.1 2.9 3.05) % Once MyPickCandy is correct these two arrays should be % fairly similar (i.e., something like 3 2 4 and 3.10 1.9 4.1) disp( candy.CandyRank ); disp( candyPicked );