Darts meets Codegolf

Question

I think everyone is familiar with the game of darts. For those that don't understand the scores, here is a useful link.

The board

A dartboard can be compared to a pie cut in 20 pieces.
Each piece is divided in 4 sections.

• a small outer ring called "double" (points x2)
• a big ring called "single" (points x1)
• another small ring called "triple" (points x3)
• another big ring called "single" (points x1)

In the middle of the board are 2 more rings, a green one and red one (classic board)

• Red ring, at the center of the board, is called "bullseye" or "double bull" and is good for 50 points. This one counts as a double and because of that it's allowed to checkout with it.
• Green ring is called "bull", "single bull", or simply "25" and counts as a single.

Challenge

Find all checkout possibilities with 3 darts or less.
The user can enter an integer and you will have to check if it's possible to get the score to 0 with 3 darts (or fewer).

Examples

example 1:

Input: 170  
Output: T20, T20, Bullseye

Example 2:

Input: 6  
Output: D3;  
        S3,S1,D1;  
        S2,D2;  
        S2,S2,D1;  
        D2,D1;  
        S4,D1;  
        D1,D1,D1;  
        S1,S1,D2;  
        T1,S1,D1;

Example 3:

Input: 169
Output: No possible checkout!

Rules

• Basic dart rules, you must end with a double (outer ring of the board or bullseye)
• No use of external resources.
• Hard coding of possible checkouts is allowed, but remember, this is codegolf, it won't get your code short ;)
• Cells to hit will be displayed in format C+N where C = T for Triple, D for double and S for single.
• bullseye can be called bullseye or DB, DBull or something similar.

Possible checkouts

To get you started, the highest possible checkout is 170.
169, 168, 166, 165, 163, 162, and 159 are not possible in 3 darts.
The lowest possible checkout is 2.

In addition

This isn't a requirement: add in a possibility to show all possible checkouts for all scores. Basically because I wonder how many combinations are possible :P

Winner will be the one with the shortest code.

Happy coding.

Answer 1

C++ 248 / 228 230 / 214 chars

Rev 0:

int f(int s){char m[4]="SDT";int t=0;for(int b=2;b<77;b+=1+(b==62)*12)for(int a=2;a<77;a+=1+(a==62)*12){int c=s-a/3*(a%3+1)-b/3*(b%3+1);if(((c+38)/40==1)|(c==50)&&(c%2==0)&(a>=b)){printf("%c%d %c%d D%d\n",m[a%3],a/3,m[b%3],b/3,c/2);t++;}}return t;}

Rev 1. Saved some characters by declaring all variables at once, and by eliminating unnecessary brackets. It turns out that in C++ all logic and bitwise and/or are lower precedence than comparisions.

int f(int s){char m[4]="SDT";int a,b,c,t=0;for(b=2;b<77;b+=1+(b==62)*12)for(a=2;a<77;a+=1+(a==62)*12){c=s-a/3*(a%3+1)-b/3*(b%3+1);if(c>1&c<41|c==50&&c%2==0&a>=b){printf("%c%d %c%d D%d\n",m[a%3],a/3,m[b%3],b/3,c/2);t++;}}return t;}

I did a function rather than program, as others have done. It returns the total number of possibilities found. It can be reduced from 230 to 214 characters by eliminating the totalising feature.

Sample output, score 6:

I count different first and second darts as the same combination, as the OP has done (example:

T1 S1 D1 = S1 T1 D1) even though this costs an extra 7 characters. I always list the higher score first (ignoring doubling and trebling) as I figure this is more relevant to the player (who may change his strategy if he misses with the first dart.) For the same reason I list the darts in order according to the second dart. I consider the 3rd dart to be completely different to the other two, therefore I consider D1 D2 and D2 D1 to be different cases whereas the OP has them listed as the same.

With this system of counting I get 42336 total possibilities, the same as mmumboss. Counting different first and second darts as different combinations, this goes up to 83349.

I haven't used a for loop with sets as others have done (I'm fairly new to C++ and I don't even know if it's possible.) Instead I abuse a conditional in the loop increment to jump from 20 up to 25. I use the variable from a single loop to encode all possible scores for a single dart, like this: S1 D1 T1 S2 D2 T2 etc. with modulus and division to decode. This saves on the verbosity of declaring more for loops, although it makes expressions more complicated.

The result of this is that an unused dart is shown as T0, but I think it's clear what is meant, especially as (by considering different first and second darts as the same combination) I have been able to group them all together at the beginning of my output.

Ungolfed version here. A couple of other features are use of the & and && operators selectively with | in such a way as to give the order of precedence I want without brackets.

int f(int s)
{
  char m[4] = "SDT";
  int a,b,c,t=0;
    for (b = 2; b < 77; b += 1 + (b == 62) * 12)
      for (a = 2; a < 77; a += 1 + (a == 62) * 12){
        c = s - a / 3 * (a % 3 + 1) - b / 3 * (b % 3 + 1);
        if (c>1 & c<41 | c == 50 && c % 2 == 0 & a >= b){
          printf("%c%d %c%d D%d\n", m[a % 3], a / 3, m[b % 3], b / 3, c / 2);
          t++;
        }
     }
   return t;
}

Answer 2

MATLAB (299 249 241 chars)

This is my first serious golfing. My first attempt (136 chars) gives the correct result, but not with the correct formatting. It gives all possibilities looking at the number of points for each dart. This means that single 20 and double 10 do have a separate entry, however, they are both displayed as 20. Of course the last dart is always a double.

function f(x);u=[1:20 25].';y=[u;2*u; 3*u(1:end-1)];v=combvec([combnk(y,2);[y y];[zeros(62,1) y];[0 0]].',y(22:42).').';v(sum(v,2)==x,:)

In the second attempt the formatting is improved, which has of course increased the number of characters:

function f(x);h=.1;u=h+[1:20,25].';y=[u;2*u;3*u(1:20)];v=combvec([combnk(y,2);[y,y];h*ones(62,1),y];[h,h]].',y(22:42).').';t='SDT';r=@fix;strrep(arrayfun(@(x)[t(int8((x-r(x))/h)),num2str(h*r(x)/(x-r(x)))],v(sum(r(v),2)==x,:),'un',0),'S0','')

Improved from 299 to 249 characters, while at the same time even improving the output formatting. For this improved version the output for the example cases is:

f(170):

'T20'    'T20'    'D25'

f(6):

'S1'    'S3'    'D1'
'S1'    'T1'    'D1'
'S2'    'D1'    'D1'
'S2'    'S2'    'D1'
'D1'    'D1'    'D1'
''      'S4'    'D1'
''      'D2'    'D1'
'S1'    'S1'    'D2'
''      'S2'    'D2'
''      'D1'    'D2'
''      ''      'D3'

f(169):

Empty cell array: 0-by-3

Additional:

According to my calculation skills there are a grand total of 42336 possibilities to end the dart game.

Answer 3

Ruby (260 chars)

"The last one should be a double" was the missing piece - couldn't figure out why 168 should not have results...:

c=->n,d=3{d=d-1;r=[];n==0?[r]:(d>=0&&n>0?(o='0SDT';((1..20).map{|p|(1..3).map{|h|c.(n-p*h,d).map{|m|r<<["#{o[h]}#{p}"]+m}}};c.(n-50,d).map{|m|r<<['DB']+m};c.(n-25,d).map{|m|r<<[?B]+m})):1;r.select{|*i,j|j[?D]}.tap{|x|d!=2?1:puts(x.map{|i|"#{i.join(?,)};"})})}

c.(170)

T20,T20,DB;

c.(6)

S1,S1,D2;
S1,T1,D1;
S1,S3,D1;
D1,D1,D1;
D1,S2,D1;
D1,D2;
T1,S1,D1;
S2,D1,D1;
S2,S2,D1;
S2,D2;
D2,D1;
S3,S1,D1;
D3;
S4,D1;

Answer 4

Python 2.7 (270 chars)

Not sure python will allow a one-liner, but he it is in three.

def f(n):
 a={'%s%s'%('0SDT'[i],n):n*i for n in range(1,21)+[25] for i in [1,2,3] if n*i<75};a['']=0
 for r in [' '.join(h[:3]) for h in [(x,y,z,a[x]+a[y]+a[z]) for x in a for y in a for z in {k:a[k] for k in a if 'D' in k}] if h[3]==n and len(h[0])<=len(h[1])]:print r

Or 278+ chars with a proper 'No Checkout' message (e.g. 290 here):

def f(n):
 a={'%s%s'%('0SDT'[i],n):n*i for n in range(1,21)+[25] for i in [1,2,3] if n*i<75};a['']=0;
 for r in [' '.join(h[:3]) for h in [(x,y,z,a[x]+a[y]+a[z]) for x in a for y in a for z in {k:a[k] for k in a if 'D' in k}] if h[3]==n and len(h[0])<=len(h[1])] or ['No Checkout']:print r

Here we go:

f(170)

T20 T20 D25

f(6)

S3 S1 D1
S2 S2 D1
S2 D1 D1
S1 S3 D1
S1 S1 D2
S1 T1 D1
 S2 D2
 S4 D1
  D3
 D2 D1
 D1 D2
T1 S1 D1
D1 S2 D1
D1 D1 D1

f(169)

No Checkout

Things I'm not happy with:

for x in a for y in a for z in

This is over 10% of the total. Is there a more compact way without itertools etc?

and len(h[0])<=len(h[1])

This is used to prevent duplicates in the case of a two dart finish (e.g. ['', 'S1', 'D1'] and ['S1', '', 'D1']). I deem order to matter (hey - the last dart has to be a double, so clearly order matters), but the non-throw is a special case.

Answer 5

05AB1E, 43 bytes

20L25ª3Lâ¨Ðʒθ<}Uã«XâXìε˜2ô}ʒPOQ}εε`…TSDsèì

Pretty slow.. Outputs as a list of lists, or an empty list if no finish is possible. My bulls are S25 and D25; if this is not allowed I can change it.

Try it online or verify a few test cases at once.

Explanation:

There are a couple of steps:

1) Create a list of all possible single, double, and triple darts:

20L         # Create a list in the range [1,20]
   25ª      # Append 25 to this list
      3L    # Create a list in the range [1,3]
        â   # Create all possible pairs of these two lists
         ¨  # Remove the last pair (which is the Triple Bull)
            # Now we have a list of all possible darts:
            #  [[1,1],[1,2],[1,3],[2,1],...,[20,3],[25,1],[25,2]]

2) Get all possible finishers (ending with a double) of up to 3 darts:

Ð           # Triplicate this list
 ʒ  }       # Filter the top copy by:
  θ         #  Where the last value
   <        #  Decremented by 1 is truthy (==1), so all doubles
     U      # Pop this filtered list of doubles, and store it in variable `X`
 ã          # Create all possible pairs of the list of darts with itself
  «         # Merge it with the list of darts
            # We now have a list containing all possible variations for 1 or 2 darts
 Xâ         # Then create all possible pairs of these with the doubles from variable `X`
   Xì       # And prepend the doubles themselves as well
            # Now we have all possible variations of 1 double; 1 dart + 1 double;
            # or 2 darts + 1 double
     ε   }  # Map each to:
      ˜     #  Deep-flatten the list
       2ô   #  And split it into parts of size 2
            #  (this is to convert for example a 2 darts + 1 double from
            #   [[[20,3],[5,1]],[1,2]] to [[20,3],[5,1],[1,2]])
            # Now we have a list of all possible finishers of up to 3 darts

3) Only keep those for which the total score is equal to the input-integer:

ʒ   }       # Filter this list by:
 P          #  Get the product of each inner-most lists
            #   i.e. [[20,3],[5,1],[1,2]] → [60,5,2]
  O         #  Take the sum of those
            #   i.e. [60,5,2] → 67
   Q        #  Check if this value is equal to the (implicit) input-integer
            # Now we only have the finishers left with a total value equal to the input

4) Convert the data to the pretty-printed result-list (i.e [[20,3],[5,1],[1,2]] becomes ["T20","S5","D2"]):

ε           # Map each of the remaining finishers of up to 3 darts to:
 ε          #  Map each inner list to:
  `         #   Push both values separately to the stack ([20,3] → 20 and 3)
   …TSD     #   Push string "TSD"
       s    #   Swap to get the integer for single/double/triple at the top of the stack
        è   #   Use it to index into the string
            #   NOTE: 05AB1E has 0-based indexing with automatic wraparound,
            #   so the triple 3 will wrap around to index 0 for character "T"
         ì  #   Prepend this character in front of the dart-value
            # (after which the result is output implicitly as result)

Answer 6

Kotlin, 254 bytes

Note: algorythm is based on Level River St's C++ answer.

{s:Int->val m="SDT"
var c=0
val r=(2..62).toList()+listOf(75,76)
for(t in r)for(o in r){val l=s-o/3*(o%3+1)-t/3*(t%3+1)
if((l>1&&l<41||l==50)&&l%2==0&&o>=t){println("${m[o%3]}${o/3},${m[t%3]}${t/3},D${l/2}")
c++}}
if(c<1)println("No possible checkout!")}

Try it online!