Programmers: a bit of code golf?

Here’s a new problem. I haven’t thought much about it, so I don’t know if it’s too complex for code golf.

Given a cribbage hand, 6 cards + unknown turn card. Which two cards should be discarded to give the highest expected value for scoring points (not during play).

Cribbage scoring rules:

Card values:
Aces = 1. Faces = 10. Others = Rank.

Point values:
Combinations that add to 15 = 2 points.
Pairs = 2 points.
Runs of 3 (three sequential cards) = 3 points.
Flush in the 4 cards that are not the turn = 4 points.
Flush in all 5 cards = 5 points.
Jack in the non-turn cards that is the same suit as the turn card = 1 point.

Notes: you can’t score both a 4 card flush and a 5 card flush.

Example:

Hand: 5h, 6c, 5s, 7s Turn: 5c
Score:
(pairs)
5h + 5c = 2
5s + 5h = 2
5s + 5c = 2

(15’s)
5h + 5c + 5s = 2

(runs)
5h 6c 7s = 3
5s 6c 7s = 3
5c 6c 7s = 3

Total score:
9 + 2 + 6 = 17

And septimus before me, rolling his own bignums from scratch.

I’ve done this one before, but to be fair I won’t submit unless I roll a new version from scratch. :smiley:

(ETA: I thought of “Count this cribbage hand” as a possible golf, but thought it might be too complex for the game. Next we’ll be coding database query languages and Windows bug fixes. :slight_smile: )

In fact I didn’t even look at my old code (though disbelievers may be forgiven).
Please PM me with any bug reports. :frowning:



#include     <stdlib.h>
#include     <stdio.h>
#include     <string.h>

/*
 * Cribbage hand-counting, without warrantee.
 * Copyleft (C) 2011 Septimus G. Stevens, VII
 *
 * Since all you high-level guys will have
 *   built-in combination generators,
 *   I'll kluge a 'general-purpose' one of my own,
 *   brutish but adequate here.
 */
static char Cntbit[] = {
#define BB1(x)     x, x+1, x+1, x+2
#define     BB2(x)     BB1(x), BB1(x+1), BB1(x+1), BB1(x+2)
#define     BB3(x)     BB2(x), BB2(x+1), BB2(x+1), BB2(x+2)
     BB3(0), BB3(1), BB3(1), BB3(2),
};
#define     Bitcnt(x) (Cntbit[(x) & 0xff] + Cntbit[(x) >> 8])
/* Loop thru K-combinations of n */
#define     For_combos(c,k,n)     \
     for (c = 0; c < 1<<n; c++) if (Cntbit[c] == k)

static char Elem1[] = {
#define     EROW(x)     x, 0, 1, 0, 2, 0, 1, 0
#define     ERO2(x) EROW(x), EROW(3), EROW(4), EROW(3)
     ERO2(-9), ERO2(5), EROW(6), EROW(5),
     ERO2(7),  ERO2(5), EROW(6), EROW(5),
};

#define     E1(x)     (Elem1[(x) & 0xff] >= 0 \
          ? Elem1[(x) & 0xff] : 8 + Elem1[(x) >> 8])
#define     E2(x)     E1((x) & (x) - 1)
#define     E3(x)     E2((x) & (x) - 1)
#define     E4(x)     E3((x) & (x) - 1)
#define     E5(x)     E4((x) & (x) - 1)

/* General card manipulations */
char Cardnames[] = "A23456789TJQK";
char Suitnames[] = "SHDC";
#define     ch2ix(s, c)   (strchr(s, c) - (s))
#define     CN2CI(s)      (ch2ix(Cardnames, s[0]) \
                           + 13 * ch2ix(Suitnames, s[1]))
#define     CI2R(i)       ((i) % 13)
#define     CI2S(i)       ((i) / 13)
#define     R2K(r)        ((r) < 9 ? (r)+1 : 10)

int     Hand[6], Nhand[5];

#define     NI2R(i)         CI2R(Nhand*)
#define     NI2S(i)         CI2S(Nhand*)
#define     N2K(i)          R2K(NI2R(i))
#define     NI2M(i)         (1 << NI2R(i))

/* Count the cribbage hand Nhand */
int gscore(void)
{
     int     combo, i, s1, ss, msk, thisc, totc, score;

     /* We can save a line of code by doing Runs first */
#define     ISRUN(m)     ! ((m) & (m) + (1 << E1(m)))
     /* Runs of five */
     msk = NI2M(0) | NI2M(1) | NI2M(2) | NI2M(3) | NI2M(4);
     score = (Bitcnt(msk) == 5 && ISRUN(msk)) ? 5 : 0;
     /* Runs of four */
     if (! score) For_combos(combo, 4, 5) {
          msk =  NI2M(E1(combo)) | NI2M(E2(combo))
               | NI2M(E3(combo)) | NI2M(E4(combo));
          if (Bitcnt(msk) == 4 && ISRUN(msk)) score += 4;
     }
     /* Runs of three */
     if (! score) For_combos(combo, 3, 5) {
          msk = NI2M(E1(combo)) | NI2M(E2(combo)) | NI2M(E3(combo));
          if (Bitcnt(msk) == 3 && ISRUN(msk)) score += 3;
     }

     /* Flush and Nobs */
     s1 = NI2S(0);
     ss = NI2S(4);
     for (i = 0; i < 4; i++) {
          if (NI2R(i) == 10 && NI2S(i) == ss)
               score += 1;
          if (NI2S(i) != s1)
               s1 = 9;
     }
     if (s1 < 9)
          score += 4 + (s1 == ss);

     /* Pairs */
     For_combos(combo, 2, 5)
          if (NI2R(E1(combo)) == NI2R(E2(combo)))
               score += 2;

     /* Fifteens, brutish */
     totc = N2K(0) + N2K(1) + N2K(2) + N2K(3) + N2K(4);
     if (totc == 15) score += 2;
     For_combos(combo, 2, 5) {
          thisc = N2K(E1(combo)) + N2K(E2(combo));
          if (thisc == 15) score += 2;
          if (thisc == totc - 15) score += 2;
     }
     For_combos(combo, 1, 5)
          if (N2K(E1(combo)) == totc - 15) score += 2;

     if (1) return score;
     printf("The score of ");
     for (i = 0; i < 5; i++)
          printf("%c%c ",
               Cardnames[NI2R(i)],
               Suitnames[NI2S(i)]);
     printf(" is %d
", score);
     return score;
}

double mscore(int j1, int j2)
{
     int     i, k, m;
     double     totscore = 0;

     for (i = k = 0; i < 6; i++)
          if (i != j1 && i != j2)
               Nhand[k++] = Hand*;
     for (k = 0; k < 52; k++) {
          Nhand[4] = k;
          for (m = 0; m < 6; m++)
               if (Hand[m] == k) break;
          if (m == 6)
               totscore += gscore();
     }
     return totscore / 46.0;
}

int main(int argc, char **argv)
{
     int     i, combo, j1, j2, bj1, bj2;
     double     tscore, bestsco = -1;

     if (argc != 7) exit(1);
     for (i = 0; i < 6; i++)
          Hand* = CN2CI(argv[i + 1]);

     For_combos(combo, 2, 6) {
          j1 = E1(combo);
          j2 = E2(combo);
          tscore = mscore(j1, j2);
          if (tscore > bestsco)
               bestsco = tscore, bj1 = j1, bj2 = j2;
     }
     printf("From hand ");
     for (i = 0; i < 6; i++)
          printf("%c%c ",
               Cardnames[CI2R(Hand*)],
               Suitnames[CI2S(Hand*)]);
     printf(", the best discards are ");
     printf("%c%c ",
               Cardnames[CI2R(Hand[bj1])],
               Suitnames[CI2S(Hand[bj1])]);
     printf("%c%c
",
               Cardnames[CI2R(Hand[bj2])],
               Suitnames[CI2S(Hand[bj2])]);
}


Ouch! :smack: :eek: :mad: :frowning: :smack: Please ask Moderator to delete my previous post.

In my misplaced insecurity about combination generation I posted something overcomplicated, with a bug to boot. No guarantees on following, but it is simpler and has at least one fewer bug! :cool:



#include     <stdlib.h>
#include     <stdio.h>
#include     <string.h>

/*
 * Cribbage hand-counting, without warrantee.
 * Copyleft (C) 2011 Septimus G. Stevens, VII
 */
static char Cntbit[] = {
#define BB1(x)     x, x+1, x+1, x+2, x+1, x+2, x+2, x+3
#define     BB2(x)     BB1(x), BB1(x+1), BB1(x+1), BB1(x+2)
#define     BB3(x)     BB2(x), BB2(x+1), BB2(x+1), BB2(x+2)
#define     BB4(x)     BB3(x), BB3(x+1), BB3(x+1), BB3(x+2)
#define     BB5(x)     BB4(x), BB4(x+1), BB4(x+1), BB4(x+2)
#define     BB6(x)     BB5(x), BB5(x+1), BB5(x+1), BB5(x+2)
     BB6(0), BB6(1), BB6(1), BB6(2),
};

char Cardnames[] = "A23456789TJQK";
char Suitnames[] = "SHDC";
#define     ch2ix(s, c)   (strchr(s, c) - (s))
#define     CN2CI(s)      (ch2ix(Cardnames, s[0]) \
                    + 13 * ch2ix(Suitnames, s[1]))
#define     CI2R(i)       ((i) % 13)
#define     CI2S(i)       ((i) / 13)
#define     R2K(r)        ((r) < 9 ? (r)+1 : 10)

int     Hand[6], Nhand[5];

#define     NI2R(i)         CI2R(Nhand*)
#define     NI2S(i)         CI2S(Nhand*)
#define     N2K(i)          R2K(NI2R(i))
#define     NI2M(i)         (1 << NI2R(i))

/* Count the cribbage hand Nhand */
int gscore(void)
{
     int     combo, i, i1, i2, i3, jex, s1, ss, msk, thisc, totc, score;

#define     ISRUN(m)     ! ((m) & (m) + 1  + ((m)-1 & ~(m)))
     /* Runs of five */
     msk = NI2M(0) | NI2M(1) | NI2M(2) | NI2M(3) | NI2M(4);
     score = (Cntbit[msk] == 5 && ISRUN(msk)) ? 5 : 0;

     /* Runs of four */
     if (! score)
     for (jex = 0; jex < 5; jex++) {
          for (msk = i = 0; i < 5; i++)
          if (i != jex)
               msk |= NI2M(i);
          if (Cntbit[msk] == 4 && ISRUN(msk)) score += 4;
     }

     /* Runs of three */
     if (! score)
     for (i1 = 0; i1 < 5; i1++)
     for (i2 = i1+1; i2 < 5; i2++)
     for (i3 = i2+1; i3 < 5; i3++) {
          msk = NI2M(i1) | NI2M(i2) | NI2M(i3);
          if (Cntbit[msk] == 3 && ISRUN(msk)) score += 3;
     }

     /* Flush and Nobs */
     s1 = NI2S(0);
     ss = NI2S(4);
     for (i = 0; i < 4; i++) {
          if (NI2R(i) == 10 && NI2S(i) == ss)
               score += 1;
          if (NI2S(i) != s1)
               s1 = 9;
     }
     if (s1 < 9)
          score += 4 + (s1 == ss);

     /* Pairs */
     for (i1 = 0; i1 < 5; i1++)
     for (i2 = i1+1; i2 < 5; i2++)
          if (NI2R(i1) == NI2R(i2))
               score += 2;

     /* 5-card Fifteens */
     totc = N2K(0) + N2K(1) + N2K(2) + N2K(3) + N2K(4);
     if (totc == 15) score += 2;

     /* 4-card Fifteens */
     for (i1 = 0; i1 < 5; i1++)
          if (N2K(i1) == totc - 15) score += 2;

     /* 2- and 3-card Fifteens */
     for (i1 = 0; i1 < 5; i1++)
     for (i2 = i1+1; i2 < 5; i2++) {
          thisc = N2K(i1) + N2K(i2);
          if (thisc == 15) score += 2;
          if (thisc == totc - 15) score += 2;
     }

     if (1) return score;
     printf("The score of ");
     for (i = 0; i < 5; i++)
          printf("%c%c ",
               Cardnames[NI2R(i)],
               Suitnames[NI2S(i)]);
     printf(" is %d
", score);
     return score;
}

double mscore(int j1, int j2)
{
     int     i, k, m;
     double     totscore = 0;

     for (i = k = 0; i < 6; i++)
          if (i != j1 && i != j2)
               Nhand[k++] = Hand*;
     for (k = 0; k < 52; k++) {
          Nhand[4] = k;
          for (m = 0; m < 6; m++)
               if (Hand[m] == k) break;
          if (m == 6)
               totscore += gscore();
     }
     return totscore / 46.0;
}

void solve(void)
{
     int     i, combo, j1, j2, bj1, bj2;
     double     tscore, bestsco = -1;

     for (j1 = 0; j1 < 6; j1++)
     for (j2 = j1+1; j2 < 6; j2++) {
          tscore = mscore(j1, j2);
          if (tscore > bestsco)
               bestsco = tscore, bj1 = j1, bj2 = j2;
     }
     printf("From hand ");
     for (i = 0; i < 6; i++)
          printf("%c%c ",
               Cardnames[CI2R(Hand*)],
               Suitnames[CI2S(Hand*)]);
     printf(", the best discards are ");
     printf("%c%c ",
               Cardnames[CI2R(Hand[bj1])],
               Suitnames[CI2S(Hand[bj1])]);
     printf("%c%c
",
               Cardnames[CI2R(Hand[bj2])],
               Suitnames[CI2S(Hand[bj2])]);
}

int main(int argc, char **argv)
{
     int     i, j, k;

     if (argc != 7) exit(1);
     for (i = 0; i < 6; i++)
          Hand* = CN2CI(argv[i + 1]);
     solve();
}


Here’s a Cribbage scorer:



#! /usr/bin/env ruby

class Card

    include Comparable

    RANKINGS = ["A","2","3","4","5","6","7","8","9","T","J","Q","K"]

    attr_reader :rank
    attr_reader :suit
    
    def initialize(str)
        @rank = RANKINGS.index(str[0..0].upcase)
        @suit = str[1..1].upcase
    end
    
    def <=>(other)
        if other.is_a?(String)
            @rank <=> RANKINGS.index(other.upcase)
        else
            @rank <=> other.rank
        end
    end
    
    def to_s
        RANKINGS[@rank] + @suit
    end
    
    def value
        (@rank >= 10) ? 10 : @rank+1
    end

end
def best_hand(held_cards,draw_deck)

    # Set up the hands
    possible_hands = {}
    held_cards.choose(4) {|hand| possible_hands[hand] = 0}
    
    draw_deck.each do |turn_card|
        possible_hands.each do |four_hand,score| 
            possible_hands[four_hand] += score_hand(four_hand,turn_card)
        end
    end 

    
    best_hand = [nil,0]
    possible_hands.to_a.each do |hand|
        best_hand = [hand,best_hand].max {|a,b| a[1] <=> b[1]}
    end
    
    return best_hand[0]
end 
    

def score_hand(hand,turn_card)

    score = 0
    # Flushes
    if not (hand[1..-1].detect {|card| card.suit != hand[0].suit})
        score += 4  # flush
        if turn_card.suit == hand[0].suit
            score += 1  # 5-card flush
        end
    end
    
    # His nobs
    hand.each {|card| score += 1 if card == "J" && card.suit == turn_card.suit}

    # Scoring with the turn card included
    hand = hand + [turn_card]
    
    for i in (2..5) do
        hand.choose(i) do |cards|
            
            if 15 == cards.inject(0) {|s,c| s + c.value}
                score += 2
            end
            
            if i == 2
                score += 2 if cards[0] == cards[1]
            end
            
            if i == 3
                sorted_hand = cards.sort
                base_rank = sorted_hand[0].rank
                no_run = false
                sorted_hand.each_with_index do |card,indx|
                    if card.rank != base_rank + indx
                        no_run = true
                        break
                    end
                end
                score += 3 unless no_run
            end
        end
    end

    return score
end   

if __FILE__ == $0

    deck = []
    Card::RANKINGS.each do |rank|
        ["Spades","Clubs","Hearts","Diamonds"].each do |suit|
            deck << Card.new(rank+suit)
        end
    end
    
    example = ["5h", "6c", "5s", "7s"].map {|s| Card.new(s)}
    puts score_hand(example,Card.new("5c"))
    
    # pick a random hand
    
    player_hand = []
    6.times do 
        player_hand << deck.delete_at(rand(deck.size))
    end
    
    print "The best discards for "
    p player_hand.map {|card| card.to_s}
    print " are "
    p (player_hand-best_hand(player_hand,deck)).map {|card| card.to_s}
    
end 
    


The “choose” code I used upthread, added into Arrays for combinations. I made use of that for scoring pairs and runs, and just threw it all in a loop. It could be made slightly more efficient, but this is a fast problem to solve.

One thing I noticed about your solution, septimus - if all you care about is what the best hand is, you don’t really need to divide by 46. (I didn’t).

For scoring the pairs and runs I made use of all the combinations,



#define     ISRUN(m)     ! ((m) & (m) + 1  + ((m)-1 & ~(m)))
....
     return totscore / 46.0;


Of the two lines from my code excerpted above, I find the 1st more interesting than the second. :cool: (And if micro-efficiency is a goal, I’d avoid the ten threesome sorts rather than the divide.)

One thing I noticed about yours, panamajack - do you handle runs of 4 or 5 properly?

(ETA: Checking Red Skeezix’ post I see he misstated the rule for scoring runs of 4 or 5. They count 4 or 5 points respectively, not the 6 or 9 points that Red implies and Panamajack implements.)

I did it per the stated rules, and took advantage of them so to speak. I do admire that little ISRUN macro.

Of course, it’s easily changed :



     if i**>**=3
       <...>
       case i
       when 3 : score += 3
       when 4 : score -= 2
       end unless no_run
    end


I was thinking of a variation on an earlier challenge:

Use the definition of Nodes above, except that costs can be either positive or negative. Edges are uni-directional, of course. You are given only the start and end nodes. Determine if a “shortest path” exists, and return it if it does. [If you’re using a language that might need it, assume the number of nodes is less than 2^32].

The cribbage hand 6 7 8 8 9 collects 8 points for the two 4-runs, as your code computes. But 6 7 8 9 9 also collects 8 points, with your code counting only 5 points. You can fix yours by adding a new variable, but I find my approach more “natural.” :smiley:

For the new problem, if the previous solution provides a function minpath(start, desti), is it not good enough to first do more-or-less
FOREACH node
IF (minpath(base_start, node) < infinity
AND minpath(node, base_desti) < infinity
AND minpath(node, node) < 0)
THEN abort

I’m at a disadvantage when you guys use Haskell or Ruby. 25 years ago, much of my professional programming still involved “languages” much lower-level than C. 20 years ago the “new language” I needed to learn was LaTeX. These days I dabble at coding just to stave off Alzheimer’s. I did make some effort to learn “modern” languages, but picked the wrong ones. Recently I started coding a little Javascript and was (check forum) … disappointed to learn that
“85” - 1
yields 84, while
“85” + 1
yields “851”. :smack:

Not quite, as since it is a directed graph, the criterion for there being a lower bound to the paths is not “There are no negative-weight edges”, but, more subtly, “There are no negative-weight edges which are both A) part of a cycle and B) part of a path between the given start and end nodes”.

(Even in an undirected graph, the criterion would be not “There are no negative-weight edges”, but, rather, “There are no negative-weight edges reachable from both the given start and end nodes”)

But, with one proviso, that’s exactly what my pseudo-code detected. (Though to be complete, I’d need to specify minpath().)
(The proviso being that negative-weight edges in the cycle are OK, as long as the total cycle cost is non-negative.)

(And then, even after verifying that there is a lower bound to the paths, there is still the problem of actually finding the minimal path when it may possibly contain a negative-weight edge, a context in which Dijkstra’s algorithm is no longer correct)

Oops, I am sorry, I misread your code. And your proviso corrects my own error.

So you are exactly correct for determining whether a minimal path exists. But the problem is still that Dijkstra’s algorithm does not generally correctly find those minimal paths in a context where adding edges to a path may reduce its total cost. (It will not go far out of its way to seek out an edge of immense negative cost, for example)