# 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:** 1

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [June 3, 2011, 9:24pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/1 "2011-06-03T21:24:56Z")

</div>

Code golf is a popular sport on programmer-friendly websites like StackOverflow and Reddit. There’s a load of programmers here, from the look of it, so how about we have a game of code golf?

If you haven’t played before the rules are very simple. Somebody suggests a simple algorithmic task (i.e. generate all prime numbers less than 50 — no suggesting we write operating systems, etc.) You solve this task in your favourite programming language. The aim is to produce the most concise and elegant solution to the problem. Efficiency of the resulting code doesn’t usually come into it, it’s all about exposition. Improvements on previous submissions toward these ends are encouraged if you spot them. Feel free to suggest your own tasks.

I’ll go first: generate and print to stdout the powerset of the set { 1, 2, 3, 4 }.

A solution in Haskell:

```auto

main = print . filterM (const [True, False]) $ [1, 2, 3, 4]

```

---

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [June 3, 2011, 9:26pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/2 "2011-06-03T21:26:04Z")

</div>

Shit, wrong forum. Reported.

---

<div class="post-metadata">

**Author:** ![samclem](https://avatars.discourse-cdn.com/v4/letter/s/a9a28c/32.png) [@samclem](https://boards.straightdope.com/u/samclem)\
**Post date:** [June 3, 2011, 9:27pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/3 "2011-06-03T21:27:37Z")

</div>

Moved.

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [June 3, 2011, 9:34pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/4 "2011-06-03T21:34:20Z")

</div>

> [@](#):
>
> Somebody suggests a simple algorithmic task (i.e. generate all prime numbers less than 50 — no suggesting we write operating systems, etc.)

Would something like

```auto

print "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47"

```

count as “simple” or “elegant”?

---

<div class="post-metadata">

**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\
**Post date:** [June 3, 2011, 9:39pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/5 "2011-06-03T21:39:40Z")

</div>

> [@Chronos](#):
>
> Would something like
> 
> ```auto
> 
> print "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47"
> 
> ```
> 
> count as “simple” or “elegant”?

I wouldn’t count it. He said generate, not print.

---

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [June 3, 2011, 9:42pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/6 "2011-06-03T21:42:37Z")

</div>

> [@Chronos](#):
>
> Would something like
> 
> ```auto
> 
> print "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47"
> 
> ```
> 
> count as “simple” or “elegant”?

No, that’s cheating.

---

<div class="post-metadata">

**Author:** ![TriPolar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tripolar/32/3008_2.png) [@TriPolar](https://boards.straightdope.com/u/TriPolar)\
**Post date:** [June 3, 2011, 11:12pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/7 "2011-06-03T23:12:42Z")

</div>

> [@Chronos](#):
>
> Would something like
> 
> ```auto
> 
> print "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47"
> 
> ```
> 
> count as “simple” or “elegant”?

Not an algorithm in the sense generally applied to programming.

---

<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, 2:52am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/8 "2011-06-04T02:52:34Z")

</div>

In C#:

```auto

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Primes
{
    class Program
    {
        static void Main(string[] args)
        {
            int i, j;
            Console.Write("2, ");
            for (i = 3; i < 50; i+=2)
            {
                double k = Math.Sqrt(i);
                for (j=3; j <= k; j+=2)
                {
                    if (i % j == 0) { break;}
                }
                if (j > k) { Console.Write(i+", ");}
            }
            Console.ReadKey();
        }
    }
}

```

Next challenge: given an array of five two-character strings representing a poker hand of playing cards (i.e. “2s”, “3s”, “4s” … “Ts”, “Js”, “Qs”, “Ks” for the spades, “Xd”, “Xh” and “Xc” for the other suits), determine if the player has 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, 5:07am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/9 "2011-06-04T05:07:47Z")

</div>

In C#/LINQ:

```auto

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Golf
{
    class Program
    {
        static string ranks = "A23456789TJQKA"; 
        static void Main(string[] args)
        {
            var rankedCards = from x in args select x.Substring(0, 1).ToUpper();
            if (rankedCards.Distinct().Count() == 5 
                && rankedCards.Sum(x => { return rankedCards.Contains(ranks[ranks.IndexOf(x) + 1] + string.Empty) ? 1 : 0; }) == 4)
            {
                Console.Out.WriteLine("Is a Straight");
            }
            else
            {
                Console.Out.WriteLine("Is Not a Straight");
            }
            Console.In.ReadLine();
        }        
    }
}

```

Next Challenge:  
Hold on while I think of one.

---

<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, 5:27am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/10 "2011-06-04T05:27:15Z")

</div>

Next problem: For six given numbers find the calculation such that the first five numbers are consumed using only infix operators (+,-,/,\*) with only left to right precedence to produce the sixth. Example: 1, 20, 40, 90, 200, 1620 : 90 - 1 \* 20 +40 - 200 = 1620

---

<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:46am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/11 "2011-06-04T05:46:08Z")

</div>

For what it’s worth, you guys have all ignored the actual challenge in the OP…

---

<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:52am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/12 "2011-06-04T05:52:22Z")

</div>

For printing the primes less than 50, I suggest in Haskell

```auto

primeSieve (x:xs) = x:(primeSieve [y | y <- xs, y `mod` x /= 0])
main = print $ takeWhile (<= 50) $ primeSieve [2..]

```

---

<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:07am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/13 "2011-06-04T08:07:05Z")

</div>

> [@Red\_Skeezix](#):
>
> Next problem: For six given numbers find the calculation such that the first five numbers are consumed using only infix operators (+,-,/,\*) with only left to right precedence to produce the sixth. Example: 1, 20, 40, 90, 200, 1620 : 90 - 1 \* 20 +40 - 200 = 1620

In Haskell:

```auto

import Control.Monad -- Just to avoid rewriting replicateM

-- Defining the permutations function
-- Note: In GHC 6.10, the permutations function is already available in Data.List
choose l = chooser [] l
  where chooser xs (y:ys) = (y, xs ++ ys) : chooser (y:xs) ys
        chooser xs [] = []
permutations [] = [[]]
permutations l = [x : xs' | (x, xs) <- choose l, xs' <- permutations xs]

-- Left-associative application of a list of operations
-- to a list of inputs
evalLeft calc (x:xs) = foldl (\a (o, b) -> a `o` b) x $ zip calc xs

-- This makes output nicer to read, but is of no fundamental importance
prettyPrint [] [x] = show x
prettyPrint (c:cs) (x:xs) = show x ++ " " ++ c ++ " " ++ prettyPrint cs xs

-- findCalcs xs y produces a list of all calculations
-- which turn the list xs into y (xs may have arbitrary length)
findCalcs xs y = [prettyPrint (map snd cand) xs'
                   | cand <- replicateM (length xs - 1) ops, 
                     xs' <- permutations xs,
                     evalLeft (map fst cand) xs' == y]
  where ops = [((+), "+"), ((-), "-"), ((/), "/"), ((*), "*")]

--Example: Produces output "90.0 - 1.0 * 20.0 + 40.0 - 200.0"
main = print $ head $ findCalcs [1, 20, 40, 90, 200] 1620

```

---

<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:26am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/14 "2011-06-04T08:26:12Z")

</div>

Speaking of functions already available in Data.List in modern GHC, I can beat the OP at his actual challenge:

```auto

import Data.List
main = print $ subsequences [1, 2, 3, 4]

```

But I suppose that hardly counts… 🙂

---

<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, 9:37am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/15 "2011-06-04T09:37:20Z")

</div>

Decided to “golf down” that pretty printer…

```auto

import Control.Monad
import Data.List

evalLeft calc (x:xs) = foldl (\a (o, b) -> a `o` b) x $ zip calc xs

findCalcs xs y
 = [concat $ zipWith (++) (map show xs') ((map snd cand)++[""])
   | xs' <- permutations xs,
     cand <- replicateM (length xs - 1) ops,
     evalLeft (map fst cand) xs' == y]
 where ops = [((+), " + "), ((-), " - "), ((/), " / "), ((*), " * ")]

main = sequence_ $ map putStrLn $ findCalcs [1, 20, 40, 90, 200] 1620

```

Output:

```auto

90.0 - 1.0 * 20.0 + 40.0 - 200.0
90.0 - 1.0 * 20.0 - 200.0 + 40.0

```

---

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [June 4, 2011, 11:00am UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/16 "2011-06-04T11:00:46Z")

</div>

> [@Red\_Skeezix](#):
>
> In C#/LINQ:
> 
> ```auto
> 
> using System;
> using System.Collections.Generic;
> using System.Linq;
> using System.Text;
> 
> namespace Golf
> {
> class Program
> {
> static string ranks = "A23456789TJQKA"; 
> static void Main(string[] args)
> {
> var rankedCards = from x in args select x.Substring(0, 1).ToUpper();
> if (rankedCards.Distinct().Count() == 5 
> && rankedCards.Sum(x => { return rankedCards.Contains(ranks[ranks.IndexOf(x) + 1] + string.Empty) ? 1 : 0; }) == 4)
> {
> Console.Out.WriteLine("Is a Straight");
> }
> else
> {
> Console.Out.WriteLine("Is Not a Straight");
> }
> Console.In.ReadLine();
> }        
> }
> }
> 
> ```
> 
> Next Challenge:  
> Hold on while I think of one.

I don’t have a C# compiler installed, but doesn’t this allow a hand to wrap around? i.e. Q K A 2 3 is counted as a straight by your code, isn’t it, which according to Wikipedia is not a poker straight?

ETA: Actually, perhaps I’m misunderstanding what’s going on here due to my unfamiliarity with C#. What exactly does happen when you try to process Q K A 2 3? Does IndexOf only return a single index into the list? What happens if there’s more than one entry that equals that element?

---

<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, 2:50pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/17 "2011-06-04T14:50:54Z")

</div>

> [@Capt.Ridley\_s\_Shooting\_Party](#):
>
> I don’t have a C# compiler installed, but doesn’t this allow a hand to wrap around? i.e. Q K A 2 3 is counted as a straight by your code, isn’t it, which according to Wikipedia is not a poker straight?
> 
> ETA: Actually, perhaps I’m misunderstanding what’s going on here due to my unfamiliarity with C#. What exactly does happen when you try to process Q K A 2 3? Does IndexOf only return a single index into the list? What happens if there’s more than one entry that equals that element?

Yeah you’re right, I hadn’t accounted for the wrap-around. Stupid Aces having two values. Here’s a golf correction. (IndexOf returns the first element of the collection.)

```auto

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Golf
{
    class Program
    {
        static string ranks = "A23456789TJQKA"; 
        static void Main(string[] args)
        {
            var rankedCards = from x in args select x.Substring(0, 1).ToUpper();
            if (rankedCards.Distinct().Count() == 5 
                && rankedCards.Sum(x => { return rankedCards.Contains(ranks[ranks.IndexOf(x) + 1] + string.Empty) ? 1 : 0; }) == 4 
                && !(rankedCards.Contains("K") && rankedCards.Contains("2")))
            {
                Console.Out.WriteLine("Is a Straight");
            }
            else
            {
                Console.Out.WriteLine("Is Not a Straight");
            }
            Console.In.ReadLine();
        }        
    }
}

```

---

<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, 2:58pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/18 "2011-06-04T14:58:28Z")

</div>

> [@Red\_Skeezix](#):
>
> In C#/LINQ:
> 
> ```auto
> 
> using System;
> using System.Collections.Generic;
> using System.Linq;
> using System.Text;
> 
> namespace Golf
> {
> class Program
> {
> static string ranks = "A23456789TJQKA"; 
> static void Main(string[] args)
> {
> var rankedCards = from x in args select x.Substring(0, 1).ToUpper();
> if (rankedCards.Distinct().Count() == 5 
> && rankedCards.Sum(x => { return rankedCards.Contains(ranks[ranks.IndexOf(x) + 1] + string.Empty) ? 1 : 0; }) == 4)
> {
> Console.Out.WriteLine("Is a Straight");
> }
> else
> {
> Console.Out.WriteLine("Is Not a Straight");
> }
> Console.In.ReadLine();
> }        
> }
> }
> 
> ```
> 
> Next Challenge:  
> Hold on while I think of one.

I know that algorithmic complexity doesn’t count in this game, but once you ensure that the 5 cards are distinct, it is actually faster to sum up their indices, subtract off 5 \* the lowest index, and make sure that the resulting sum equals 10[sup]1[/sup]. I don’t know how to express that effectively in C#, though.

[sup]1[/sup] This makes the overall algorithm linear in complexity, instead of quadratic, since you can also do the distinctness check in linear time with a hash table. Not that it matters since the hands are only 5 cards, of course.

Edit: Never mind – if you’re going to use a hash table to check distinctness, you can also use it to do the “Contains” check. So both approaches are linear. I feel like doing it by summing up indices is more “elegant,” 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:25pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/19 "2011-06-04T15:25:21Z")

</div>

Oooh, I think I came up with an even more elegant way of doing the Poker Straight thing, that avoids doing the distinctness check. I haven’t given much thought to converting the hands into their numerical values, so this assumes that there’s an array called “hand” that has the numerical value of each card. The code also doesn’t handle Aces having two possible values, but it can be added in without too much trouble (just add a check for aces, and keep track of two values, rather than just one).

So, in Java:

```auto

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

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

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

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

```

Here’s what the code does, spoilered for those that want to work through it:

It builds a bit-vector representation of your hand, using 1s shifted by the appropriate amount.

For any hand that represents a straight, the bitvector will have 5 consecutive 1s in it (hands with duplicate cards will have fewer than 5 entries). Having 5 consecutive ones happens if and only if the bitvector represents a number that is 31 \* a power of 2. So first we divide out 31. Then we make sure the number is a power of 2 using a bit-manipulation trick.

---

<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, 3:40pm UTC](https://boards.straightdope.com/t/programmers-a-bit-of-code-golf/584245/20 "2011-06-04T15:40:19Z")

</div>

MilTan:

When I this version of your code: i get a straight on a 4 of a kind. (Not sure if i translated it wrong, i don’t have java on this machine so I cant directly verify yours.

```auto

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Golf
{
    class StraightAdding
    {
        public static void Main(string[] args)
        {
            uint [] hand = {1,1,1,1,2};
            uint val = 0;
            string res = "not ";

            foreach (int x in hand) 
                  {val |= (uint)(1 << x);}

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

            Console.Out.WriteLine("Is " + res + "a straight");
            Console.In.ReadLine();
        }
    }
}

```

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