14
\$\begingroup\$

Introduction

A normal checkers board contains 8 x 8 = 64 squares:

enter image description here

You can see that in total, there are 12 white pieces. Black and white always have the same amount of pieces. If there are any more pieces on the board, the pieces would neighbouring, which is not allowed for this challenge. To clarify things, here are some examples:

The smallest board possible for this challenge is 3 x 3:

enter image description here

You can see that the maximum amount of pieces is equal to 2. So, when given N = 3, you need to output 2. If the input is N = 4, we get the following:

enter image description here

You can see that the maximum amount is also 2. So for N = 4, the output should be 2. For N = 5, the output should be equal to 5:

enter image description here

Examples

STDIN:  3
STDOUT: 2

STDIN:  4
STDOUT: 2

STDIN:  5
STDOUT: 5

STDIN:  6
STDOUT: 6

STDIN:  8
STDOUT: 12

Rules

  • Your submission must be a program, or function etc. that takes one integer and outputs or returns the number of pieces on the board
  • You can safely assume that the input is an non-negative integer > 2
  • This is , so the program with the least amount of bytes wins!
  • Note that the square in the lower left of the board is always dark. Pieces are only placed on dark squares
  • You have to occupy a full row with pieces
\$\endgroup\$
  • 3
    \$\begingroup\$ Why the restriction to full programs and STDIN/STDOUT? IMO that's just unfair to languages that have necessary program and/or input overhead. \$\endgroup\$ – lirtosiast Dec 2 '15 at 2:58
  • \$\begingroup\$ @ThomasKwa, you're right. Functions etc. are now allowed \$\endgroup\$ – Adnan Dec 2 '15 at 8:25

25 Answers 25

5
\$\begingroup\$

Par, 8 bytes

✶″½↓┐*½┐

One byte is used per character.

Explanation

               ## [implicit: read line]      Example
✶              ## Convert to number           7
″              ## Duplicate                   7 7
½              ## Divide by two               7 3.5    half the board
↓              ## Minus one                   7 2.5    leave one row empty
┐              ## Ceiling                     7 3      a whole number of rows
*              ## Multiply                    21       total number of spaces
½              ## Divide by two               10.5     only the blue squares
┐              ## Ceiling                     11       starts with blue, so round up
\$\endgroup\$
12
\$\begingroup\$

Hexagony, 19 bytes

?({{&2'2':{):!/)'*/

Try it online.

Explanation

This is still the same computation as I've used in my CJam and Labyrinth answers, but due to Hexagony's... special... memory model, it's a bit trickier to squeeze the computation into 19 bytes (so that it fits inside a side-length 3 hexagon).

Like my Labyrinth answer, this terminates with a division-by-0 error.

Here is the unfolded code:

enter image description here

As I said the code is entirely linear. You can piece the executed path together in order grey-purple-green-red-blue. The path actually continues a bit further until it hits the : on the left. Removing the / (which only redirect control flow), the entire program unrolled linearly is:

?({2':{)'*){&2':!:&?':

So the question is how does it work. Hexagony's memory is the line graph of a hex grid, where each edge of the grid contains an integer value (initially zero). The memory pointer (MP) is always on one edge and points in a certain direction along that edge. Arithmetic operations are generally applied to the two edges pointed at and stored in the edge the MP is on.

For this program, we'll be using the three edges labelled A, B, C, with the MP starting as shown here:

enter image description here

So here is how this works:

?  Read an integer N from STDIN into edge A.
(  Decrement to get N-1.
{  Move the MP forwards onto edge B.
2  Set the edge to 2.
'  Move the MP backwards onto edge C.
:  Divide edge A by edge B (rounding down) to compute (N-1)/2.
{  Move the MP forwards onto edge A.
)  Increment to restore value of N.
'  Move the MP backwards onto edge B.
*  Multiply edges A and C to compute N*(N-1)/2.
)  Increment to compute N*(N-1)/2 + 1.
{  Move the MP forwards onto edge C.
&  This actually a copy operation, but we use it to reset the edge to zero.
2  Set the edge to 2.
'  Move the MP backwards onto edge A.
:  Divide edge B by edge C to compute (N*(N-1)/2 + 1)/2.
!  Output the result as an integer. We're basically done now.
:  no-op (we already have this value)
&  Copy either B or C into A (doesn't matter).
?  Read a zero (EOF) into A.
'  Move the MP backwards onto an unused cell.
:  Divide some unused cell by A (which is zero), terminating with an error.
\$\endgroup\$
  • \$\begingroup\$ {{ moves the memory edge twice so the & in the second row seems to be doing nothing? Both neigbours should be 0 there \$\endgroup\$ – Eumel Dec 1 '15 at 16:09
  • \$\begingroup\$ @Eumel That's not the order in which the code is executed. After the first {, the IP jumps to the 2 in the left corner. After the ) in the right corner, the IP jumps to the ' in the bottom left corner. Then the IP traverse lines 2 and 4 in a weird cyclically wrapping way. \$\endgroup\$ – Martin Ender Dec 1 '15 at 16:11
  • \$\begingroup\$ oh i thought it only changed the ME not the IP. also +1 just for using hexagony that language is just too funny \$\endgroup\$ – Eumel Dec 1 '15 at 16:12
  • \$\begingroup\$ @Eumel It does. That's just how the edges of the code wrap in Hexagony. \$\endgroup\$ – Martin Ender Dec 1 '15 at 16:12
11
\$\begingroup\$

LabVIEW, 28 20 LabVIEW Primitives

\$\endgroup\$
8
\$\begingroup\$

CJam, 10 bytes

ri_(2/*)2/

Test it here.

Explanation

ri   e# Read input and convert to integer N.
_    e# Duplicate N.
(2/  e# Decrement, integer divide by two, to determine the number of rows that can be used.
*    e# Multiply by the input to determine the number of cells that can be used.
)2/  e# Increment, integer divide by two, which essentially ceil()s the result of the
     e# division.
\$\endgroup\$
8
\$\begingroup\$

Labyrinth, 11 bytes

Woohoo, only one byte behind CJam.

?:(#/*)_2/!

Try it online.

It's essentially the same thing:

? reads an integer value.
: duplicates the result.
( decrements it.
# pushes the stack depth which happens to be 2.
/ is integer division.
* is multiplication.
) increments the result.
_ pushes a 0.
2 turns it into a 2.
/ is once again integer division.
! prints the result as an integer.

However, at this point the program doesn't terminate yet. Instead, the instruction pointer has hit a dead end and turns around. But now / tries to compute 0/0 which terminates with an error.

\$\endgroup\$
5
\$\begingroup\$

Seriously, 8 bytes

,;D½L*½K

Seriously has the handy ½ (float divide by 2), and K (ceiling), so we don't need to add one before division.

Try it here with explanation.

\$\endgroup\$
5
\$\begingroup\$

Python 2, 22 21 bytes

lambda n:~-n/2*n+1>>1

I first separate in two cases, odd N and even N.

With odd N we can fill (N - 1)/2 rows, containing on average N/2 pieces. Since the first row always has more pieces we should ceil this result. So when N is odd we have ceil((N-1)/2 * N/2) pieces.

With even N we can fill N/2 - 1, or floor((N - 1)/2) rows, each row containing N/2 pieces.

We can combine these two expressions by ceil(floor((N-1)/2) * N/2). Since ceil(x/2) = floor((x+1)/2) we can use flooring division: ((N - 1) // 2 * N + 1) // 2.

\$\endgroup\$
3
\$\begingroup\$

JavaScript, 37 35 bytes

alert(((n=prompt()/2)-.5|0)*n+.5|0)

Explanation

Uses a similar technique to the rest of the answers. This is the ungolfed algorithm:

var n = parseInt(prompt());
var result = Math.ceil(Math.floor((n - 1) / 2) * n / 2);
alert(result);
\$\endgroup\$
3
\$\begingroup\$

dc, 12

?d1-2/*1+2/p

Test output:

$ for t in 3 4 5 6 8; do echo $t | dc -e?d1-2/*1+2/p; done
2
2
5
6
12
$ 
\$\endgroup\$
3
\$\begingroup\$

Pyth, 9 bytes

/h*/tQ2Q2

Same algorithm as my Python 2 answer.

\$\endgroup\$
3
\$\begingroup\$

Japt, 16 14 bytes

U-1>>1 *U+1>>1

Try it online!

How it works

Pretty simple:

         // Implicit: U = input number
U-1>>1   // Subtract 1 from U and integer divide by 2.
*U+1>>1  // Multiply the result by U, add 1, and integer divide by 2.
         // Implicit: output last expression

I wish there were some way to take into account that the two halves of the code are so similar. Suggestions welcome!

Old version (16 bytes):

U*½-½|0 *U*½+½|0
\$\endgroup\$
3
\$\begingroup\$

Java, 230 155 52

Golfed:

int f(int s){return(int)Math.ceil(s*((s-1)/2)/2.0);}

Ungolfed:

public class NumberOfPiecesOnACheckersBoard {

  public static void main(String[] args) {
    // @formatter:off
    int[][] testData = new int[][] {
      {3, 2},
      {4, 2},
      {5, 5},
      {6, 6},
      {8, 12}
    };
    // @formatter:on

    for (int[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new NumberOfPiecesOnACheckersBoard().f(data[0]));
      System.out.println();
    }
  }

  // Begin golf
  int f(int s) {
    return (int) Math.ceil(s * ((s - 1) / 2) / 2.0);
  }
  // End golf

}

Program output:

Input: 3
Expected: 2
Actual:   2

Input: 4
Expected: 2
Actual:   2

Input: 5
Expected: 5
Actual:   5

Input: 6
Expected: 6
Actual:   6

Input: 8
Expected: 12
Actual:   12
\$\endgroup\$
  • \$\begingroup\$ throws Exception is permissible. \$\endgroup\$ – Neil Dec 2 '15 at 10:04
  • 1
    \$\begingroup\$ OP allowed functions. \$\endgroup\$ – lirtosiast Dec 2 '15 at 15:11
  • \$\begingroup\$ You could use the Scanner class for input. That would save you a bunch of bytes I think. (The BufferedReader/InputStreamReader combo may be better in general usage, but this is code golf, and Scanner works just fine for simple input.) \$\endgroup\$ – Darrel Hoffman Dec 2 '15 at 15:37
  • \$\begingroup\$ Converting to a stand-alone function and using parameters/return values instead of standard input/output made a huge difference. \$\endgroup\$ – user18932 Aug 9 '16 at 22:05
2
\$\begingroup\$

Zilog ez80 machine code, 9 bytes

In hex:

6C 2D CB3D ED6C 2C CB3D

In assembly:

ld l,h
dec l
srl l
mlt hl
inc l
srl l

Input is in register h, and output is in l.

The Zilog ez80 is an 8-bit processor with an 8 bit accumulator and 24-bit registers. Unlike the z80, it has a mlt (8-bit multiply) instruction, which, in 16-bit mode, multiplies the high and low bytes of a register pair, here hl, and stores back in hl.

This only works for values for which twice the result fits in 8 bits; that is, n≤23.

\$\endgroup\$
2
\$\begingroup\$

TI-BASIC, 13 bytes

⁻int(⁻.5Ansint(Ans/2-.5

TI-BASIC's implicit multiplication helps, but it doesn't have integer division. ⁻int(⁻X is a shorter form of ceil(x).

\$\endgroup\$
2
\$\begingroup\$

vba, 46

Function f(x)
f=(((x-1)\2)*x+1)\2
End Function

Call with ?f(x), or =f(A1) in a formula

\$\endgroup\$
2
\$\begingroup\$

Pyth, 17 14 13 bytes

-3 bytes thanks to Ypnypn! Rearranged the numbers of the * operator to save 1 byte.

/+*Q-/Q2-1%Q2 1 2 (original)
/h*Q-/Q2!%Q2 2
/h*-/Q2!%Q2Q2

Explanation:

When n is even, we can occupy n/2-1 rows with n/2 pieces, making a total of n*(n/2-1)/2 pieces. This expression is equivalent to (n*(n/2-1)+1)/2

When n is odd, we can find how twice the number of pieces would look like, twice the number of pieces will span n-1 rows, and if I take away one piece, we can divide the n-1 rows into (n-1)/2 groups of 2 rows such that each group has n pieces, so the expression for this case is (n*(n/2)+1)/2

Now that both expressions are quite similar, we can write the code.

/h*-/Q2!%Q2Q2
        %Q2   Check if the number is odd
       !      Logical not to make 1 if even and 0 if odd
    /Q2       n/2
   -          n/2-1 if even, and n/2 if odd
  *        Q  n*(n/2-1) if even, n*(n/2) if odd
 h            Add one
/           2 Divide the result by two.

My first time using a golfing language.

\$\endgroup\$
2
\$\begingroup\$

Javascript, 33 bytes

a=prompt();alert(a*(a-1>>1)+1>>1)

If an ES6 function is allowed then 18 bytes:

a=>a*(a-1>>1)+1>>1
\$\endgroup\$
2
\$\begingroup\$

MATLAB, 37 25 bytes

@(a)ceil(fix(a/2-.5)*a/2)

I believe this should work, does for all test cases.

It also works on Octave. You can try online here.


For the old code I added the program to that workspace in a file named checkerboard.m. You can run it by simply entering checkerboard at the prompt, then when it starts, enter the required size at the prompt. The result will be printed.

For the new code, simply enter the code posted here into the prompt, then call the anonymous function as ans(n).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the up votes, finally reached 1000 Rep :) Woop. \$\endgroup\$ – Tom Carpenter Dec 1 '15 at 18:27
  • \$\begingroup\$ @ThomasKwa thanks for pointing that out. Saved 12 bytes :). \$\endgroup\$ – Tom Carpenter Dec 3 '15 at 1:46
2
\$\begingroup\$

Retina, 18 bytes

11(..?$)?
$_
11?
1

Input and output is in unary.

Try it online!

The latest version of Retina (newer than this challenge) could handle decimal I/O for four additional bytes:

.+
$*
11(..?$)?
$_
11?

Try it online!

With unary input and decimal output, we can do 16 bytes, but that seems like a bit of a stretch:

11(..?$)?
$_
11?

Explanation

Still the same approach as anyone elses, but using regex replacement on a unary representation of the number.

11(..?$)?
$_

This computes n*((n-1)/2). We do this by matching two characters at a time (division by two) and replacing them with the entire string (multiplication by n). The decrement of n is done by skipping the remainder of the string, if only one or two characters are left.

11?
1

This is integer division by 2, rounded up. We simply replace two characters with one (division by 2), but allow the last match to consist of only one character (rounding up).

\$\endgroup\$
  • \$\begingroup\$ Congratulations on your 1000th answer :p \$\endgroup\$ – Adnan Mar 30 '16 at 17:42
1
\$\begingroup\$

Python 3, 39 bytes

This is a little bloated, but I'm not sure I could golf much further than this. A link for testing.

n=int(input());print(((n-1)//2*n+1)//2)
\$\endgroup\$
1
\$\begingroup\$

Prolog, 39 38 bytes

Code:

p(N):-X is ((N-1)//2*N+1)//2,write(X).

Explanation:

Subtract 1 from input and integer divide by 2 to get number of rows available.
Multiply that number by input to get number of squares available. 
Add one and integer divide by 2 to round up, since at at least half the rows 
will have a checker at the first square.
Print.

Example:

p(8).
12

Try it online here

Edit: Saved 1 byte by replacing ceil/2 with +1//2

\$\endgroup\$
1
\$\begingroup\$

Mumps, 17 bytes

R I W I-1\2*I+1\2

Thanks to Emigna for the simple algorithm explanation. This exploits Mumps' mathematics "deficiency" that operations are executed strictly left-to-right (not PEMDAS) so parenthesis are not required. :-)

Output does look a tad odd, however, as Cache's Ensemble (the Mumps environment that I have access to) does not automatically output carriage returns even when pressed on input. If you want it prettier, add 4 characters for pre/post carriage returns:

R I W !,I-1\2*I+1\2,!

Thanks!

\$\endgroup\$
1
\$\begingroup\$

Bash, 32 bytes

read a;echo $((a*(a-1>>1)+1>>1))
\$\endgroup\$
1
\$\begingroup\$

Pyke, 8 bytes, noncompeting

Dt2f*h2f

dup,dec,half,mult,inc,half

Try it here!

\$\endgroup\$
1
\$\begingroup\$

Batch, 30 bytes

@cmd/cset/a(%1*((%1-1)/2)+1)/2

38 bytes if input on stdin is required:

@set/pa=
@cmd/cset/a(a*((a-1)/2)+1)/2
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.