CS 405/505 ASSIGNMENT #7

Due Wednesday, November 9, 2005

1. Write Prolog predicates to do the following. Test your predicates on the 3 example cases given.

(a) An integer is said to be perfect if the sum of its factors, including 1, is equal to the number itself. Determine if an integer is perfect and if so, return it's list of factors, otherwise fail. You may find the arithmetic operation M mod N to be useful. For example,

• perfect(6, Factors) => Factors = [1, 2, 3]
• perfect(298, Factors) => no
• perfect(496, Factors) => Factors = [1, 2, 4, 8, 16, 31, 62, 124, 248]

(b) Assume the predicate carddeck(CardDeck), whose code may be found here, which returns a deck (i.e. list) of cards, each card represented as a pair for the suit and card value (e.g. card(king, spade)). Select a card from the above deck of cards, assuming they have been shuffled. This card should not have been selected previously. You will want to maintain a list of cards already selected, indicated by their position in the deck. Assume the predicates random(N, R), whose code may be found here, which returns a random number R between 0 and N-1 inclusive, and nth(N, List, Element), whose code may be found here, which returns the N-th Element in List starting from 0. For example (your answers may vary),

• drawcard([], Card) => Card = card(10, diamond)
• drawcard([35], Card) => Card = card(5, spade)
• drawcard([35, 4], Card) => Card = card(3, club)

(c) Blackjack is a card game where the goal is to have the total values of one's cards to be as close to 21 as possible without going over 21 (called a bust). A win is to be closer to 21 than the dealer. An Ace may count as either 1 or 11 and a Jack, Queen and King all count as 10. All other cards are counted at face value. The game begins with the player and dealer each getting 2 cards, one at a time by turns. Depending on the total value of the 2 cards, each may elect to take additional cards in turn. Once a player elects not to take a card (called a stand), they may not do so in any successive turn. The dealer will not take any additional cards beyond a point total of 17 and will always count an Ace as 11 unless this causes a point total over 21. Simulate this game using your own strategy as the player (which may be the same as the dealer's strategy). For example,

• blackjack(Player, Dealer) =>
  Player = [card(10, diamond), card(3, club), card(5, club), stand]
  Dealer = [card(5, spade), card(5, diamond), card(king, spade), stand, win]
• blackjack(Player, Dealer) =>
  Player = [card(7, club), card(ace, club), stand]
  Dealer = [card(3, spade), card(7, diamond), card(queen, diamond), stand, win]
• blackjack(Player, Dealer) =>
  Player = [card(8, diamond), card(4, spade), card(jack, spade), bust]
  Dealer = [card(ace, club), card(9, heart)]

2. Consider the Core program segment S below:

count := n;
sum := 0;
while (count <> 0) loop
sum := sum + count;
count := count - 1;
end loop;

Using the axiomatic semantics of Core, show that the assertion {n >= 0} S {sum = n * (n + 1) / 2} is correct.

Hint: Use the loop invariant {sum = (n * (n + 1) - count * (count + 1)) / 2}. The consequence rules may be used to force the other rules into a form consistent with this loop invariant. (You should analyze the program to understand why this loop invariant was chosen.)