# Programmers: a bit of code golf?

**URL:** <https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245>\
**Category:** The Game Room\
**Created:** [June 3, 2011, 9:24pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245 "2011-06-03T21:24:56Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 3:42pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/21 "2011-06-04T15:42:23Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 3:49pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/22 "2011-06-04T15:49:06Z")

</div>

Here is fixed code, FWIW:

```auto

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");

```

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 3:52pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/23 "2011-06-04T15:52:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Red\_Skeezix](https://avatars.discourse-cdn.com/v4/letter/r/aca169/32.png) [@Red\_Skeezix](https://boards.straightdope.com/u/Red_Skeezix)\
**Post date:** [June 4, 2011, 4:24pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/24 "2011-06-04T16:24:25Z")

</div>

> [@MilTan](#):
>
> 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.

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.

---

<div class="post-metadata">

**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\
**Post date:** [June 4, 2011, 4:36pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/25 "2011-06-04T16:36:30Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 4:40pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/26 "2011-06-04T16:40:00Z")

</div>

> [@Bryan\_Ekers](#):
>
> Do the various solutions for checking for a straight distinguish the possibility of a straight flush?

No. Are they supposed to?

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 5:11pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/27 "2011-06-04T17:11:17Z")

</div>

> [@Bryan\_Ekers](#):
>
> Do the various solutions for checking for a straight distinguish the possibility of a straight flush?

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).

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 5:21pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/28 "2011-06-04T17:21:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 5:29pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/29 "2011-06-04T17:29:44Z")

</div>

> [@MilTan](#):
>
> 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.

C:

```auto

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

```

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 6:49pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/30 "2011-06-04T18:49:56Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 6:54pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/31 "2011-06-04T18:54:54Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 7:22pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/32 "2011-06-04T19:22:38Z")

</div>

_whoops, revising_

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 7:31pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/33 "2011-06-04T19:31:21Z")

</div>

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:

> [@MilTan](#):
>
> 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.

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

```auto

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:

```auto

[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:

```auto

[January,May,July,October]

```

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 7:40pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/34 "2011-06-04T19:40:37Z")

</div>

Hah. monthLength is pretty clever 🙂

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 7:54pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/35 "2011-06-04T19:54:19Z")

</div>

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:

```auto

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 8:02pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/36 "2011-06-04T20:02:18Z")

</div>

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. 🙂

---

<div class="post-metadata">

**Author:** ![Red\_Skeezix](https://avatars.discourse-cdn.com/v4/letter/r/aca169/32.png) [@Red\_Skeezix](https://boards.straightdope.com/u/Red_Skeezix)\
**Post date:** [June 4, 2011, 8:04pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/37 "2011-06-04T20:04:42Z")

</div>

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

```auto

 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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 8:23pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/38 "2011-06-04T20:23:03Z")

</div>

> [@Red\_Skeezix](#):
>
> How about this for a problem: The sum of the digits for n! given that n is large say n \> 100.

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):

```auto

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

---

<div class="post-metadata">

**Author:** ![MilTan](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MilTan](https://boards.straightdope.com/u/MilTan)\
**Post date:** [June 4, 2011, 8:28pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/39 "2011-06-04T20:28:42Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 4, 2011, 8:31pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/40 "2011-06-04T20:31:52Z")

</div>

> [@MilTan](#):
>
> 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.

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.

[Previous page](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245.md?page=1)

[Next page](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245.md?page=3)