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 }.
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.
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
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
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.)
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();
}
}
}
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.
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:
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.
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.
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();
}
}
}
