Programmers: a bit of code golf?

The Game Room
21

Wait – integer division can screw that up. So if val == 32, then the check will pass. There should be an extra check to make sure that (val % 31 == 0).

And now I wonder whether that check would actually be sufficient. I haven’t convinced myself that all multiples of 31 will either have 5 consecutive 1s or more than 5 1s, though.

Red: It’s integer division that screws up the code there, too. So if val is less than 31, val /= 31 gives 0, which will pass the second check. The modulus check accounts for it, though.

22

Here is fixed code, FWIW:



unsigned int val = 0;
string res = "not ";

foreach (x : hand) {val |= 1 << x}

if ((val % 31 == 0)) {
  val /= 31;
  if ((val && (val - 1)) == 0) 
     res = "";
}

System.out.println("Is " + res + "a straight");
23

And, to wrap things up, just checking for divisibility by 31 doesn’t do it. 93 in binary is 1011101, so if you only check for divisibility by 31, a hand of A3457 would show up as a straight.

24

I get how it works now, if it’s a straight this will be true: val = 31 * 2^n. That’s pretty clever. Got any more problems. I’m doing laundry today and not feeling like reading.

25

Do the various solutions for checking for a straight distinguish the possibility of a straight flush?

26

No. Are they supposed to?

27

Of course, this can be easily handled using the same basic technique. In addition to keeping the “val” bitvector, keep a “suit” bitvector, with some mapping like Spade -> 1, Heart -> 2, etc. Then at the end check to see if the “suit” bitvector is a power of 2 (which means that only one suit is represented in the hand).

28

All of the interesting problems I can think of revolve more around getting complexity down than “elegance.” Also, I’m a sucker for playing clever tricks with bit-manipulation. So here’s one. A very useful operation in certain applications is “population count,” where you count the number of 1s in a given bitvector. (In fact, the operation is so important that the Alpha 21264 supported CTPOP that would do exactly that).

How would you write a program to implement CTPOP (for a single uint)? To give you something to shoot for, it can be done in O(#1s) time.

If you want a better problem for Code Golf, how about: given the day on which January 1st falls, print out all months that have 5 Saturdays.

29

C:



unsigned int CTPOP(unsigned int x)
{
  unsigned int retval = 0;
  while(x)
  {
    x &= x - 1;
    retval++;
  }
  return retval;
}
30

Well damn – I was hoping it would take longer than (checks timestamps) 8 minutes :slight_smile:

31

In fairness, you gave it away by using the same trick in your straight-tester. :slight_smile:

32

whoops, revising

33

Eh, I just discovered the Data.Time module in GHC, but I’m not thrilled with its treating everything as integers, instead of giving them their own datatypes. So I’ll repost what I posted a minute ago, acknowledging that it could probably be made much more concise:

In Haskell (with apologies for “thingy”; my mind blanked on a better name):



data Day = Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday
 deriving (Read, Show, Eq, Enum, Bounded)

data Month = January | February | March | April | May | June | July | August | September | October | November | December
 deriving (Read, Show, Eq, Enum, Bounded)

cycleSucc x = if x == maxBound then minBound else succ x

monthLength True February = 29
monthLength False February = 28
monthLength _ x = 31 - ((x' `div` 7 + x') `mod` 2) where x' = fromEnum x

thingy leap days [] = []
thingy leap days (m:ms) = let (a, b) = splitAt (monthLength leap m) days
                          in (m, a) : (thingy leap b ms)

fiveSaturdays leap start
 = [m | (m, a) <- thingy leap (iterate cycleSucc start) [January .. December],
        length (filter (Saturday==) a) == 5]

-- Example
main = print $ fiveSaturdays False Thursday

Output:



[January,May,August,October]

The “leap” flag specifies whether it’s a leap year or not, so, for instance, changing the example’s False to True produces:



[January,May,July,October]
34

Hah. monthLength is pretty clever :slight_smile:

35

Here’s one that doesn’t print out pretty month names, or accept pretty day names (instead, it uses 0-indexed integers for both), but it’s fast:



int offsets[7] = {3, 0, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3};

void printMonths (bool leap, int day) {
   if (leap) {offsets[1] = 1}
   for (int i = 0; i < 12; i++) {
      if ((day + offsets* >= 5) && (day < 5)) printf("%d
", i);
      day = (day + offsets*) % 7;
   }
}

The offsets array definitely detracts from its elegance.

36

Of course, it wouldn’t be hard to make yours pretty-print either; just index into an array of month names when you print. Whether it’s necessary or not, well, that was left unspecified in the problem. :slight_smile:

37

While I was off I see you guys already solved it but here’s my solution for the saturdays problem.



 public static void Main(string[] args)
        {
            int[] months = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
            
            int dayOfJan1 = int.Parse(args[0]);
            Console.Out.WriteLine("If it's not a leap year:");
            HowManySaturdays(months, dayOfJan1);
            Console.Out.WriteLine("If it's a leap year:");
            months[1] = months[1] + 1;
            HowManySaturdays(months, dayOfJan1);            
            Console.In.ReadLine();
        }
        public static void HowManySaturdays(int[] months, int dayOfJan1)
        {
            int dayOfTheYear = 0;
           

            for (int i = 0; i < months.Length; i++)
            {
                if ((((dayOfJan1 + dayOfTheYear) % 7) + (months* - 29)) >= 6)
                {
                    Console.Out.WriteLine(string.Format("Month {0} has 5 saturdays.", i + 1));
                }
                dayOfTheYear += months*;
            }
        }

How about this for a problem: The sum of the digits for n! given that n is large say n > 100.

38

Hm, good problem. First, a fairly direct, concise solution with no attention paid to mathematical cleverness or complexity issues (in Haskell, as always, unless otherwise specified):



sumDigits 0 = 0
sumDigits n = let (a, b) = divMod n 10 in b + sumDigits a
sumFactorialDigits n = sumDigits $ product [1..n]

For example, sumFactorialDigits 101 returns 639

39

Does Haskell use BigNums under the hood? I’m trying to think if there’s a way to do this without explicitly realizing the factorial, and avoiding any representation issues… but I’m drawing a blank.

40

Haskell is capable of using BigNums, which is indeed what drives the above code.

I agree the interesting challenge is to solve the problem without calculating the full factorial, though I as well do not know off the top of my head how to do so.