Number of pieces on a checkers board

Question

Introduction

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

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:

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:

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:

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 code-golf, 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

Answer 1

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:

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:

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.

Answer 2

LabVIEW, 28 20 LabVIEW Primitives

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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
$ 

Answer 10

Pyth, 9 bytes

/h*/tQ2Q2

Same algorithm as my Python 2 answer.

Answer 11

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

Answer 12

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

Answer 13

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.

Answer 14

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

Answer 15

vba, 46

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

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

Answer 16

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.

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

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)

Answer 21

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

Answer 22

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!

Answer 23

Bash, 32 bytes

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

Answer 24

Pyke, 8 bytes, noncompeting

Dt2f*h2f

dup,dec,half,mult,inc,half

Try it here!

Answer 25

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