30
\$\begingroup\$

Suppose a new fairy chess piece named the Wazir is introduced to chess. Wazirs can move from a position (x, y) to:
 (x+1, y)
 (x, y+1)
 (x-1, y)
 (x, y-1)

That is, they move orthogonally like the rook, but only one step at a time like the king. How many such wazirs can be placed on an N×N chessboard so that no two wazirs can attack each other?

 On a 1×1 board, there can be only 1 such piece.
 On a 2×2 board, there can be 2 such pieces.
 On a 3×3 board, there can be 5 such pieces.

Given N, return the number of wazirs that can be placed on an N×N chessboard.

This is OEIS sequence A000982.

More test cases

725

832

1005000

\$\endgroup\$
  • 4
    \$\begingroup\$ So the Camel is to the Rook what the King is to the Queen? I.e. can only move orthogonally, and only one step at a time. \$\endgroup\$ – Adám Oct 2 '17 at 8:32
  • 2
    \$\begingroup\$ @SashaR May I rewrite your question as a proper code golf challenge? \$\endgroup\$ – Adám Oct 2 '17 at 9:09
  • 2
    \$\begingroup\$ Sure! That way I can also see how to word coding related questions in future \$\endgroup\$ – Sasha R Oct 2 '17 at 9:10
  • 15
    \$\begingroup\$ As a new user of this site, you've been very lucky this time. A lot of (off-topic) programming questions on this site has been permanently closed and downvoted, not edited as a challenge and upvoted like this one. As other people already explained, this site is for programming competitions only, not for asking homework. You can use the sandbox (at codegolf.meta.stackexchange.com/questions/2140/… ) before posting a challenge to avoid common mistakes next time; and note that most users on this site, as you have seen, use "unreadable" languages. \$\endgroup\$ – user202729 Oct 2 '17 at 14:52
  • 16
    \$\begingroup\$ This question is pretty confusing in that the Camel is already the standard fairy chess name for a piece like a knight that makes longer jumps and the piece you describe already has a fairy chess name: Wazir. \$\endgroup\$ – Mark S. Oct 3 '17 at 11:26

48 Answers 48

33
\$\begingroup\$

Whitespace, 45 bytes

   
	
		   
			 
 	  
   	
	      	 
	 	 	
 	

Try it online!

By the way, here is a proof that the ⌈n²/2⌉ formula is correct.

  • We can always place at least ⌈n²/2⌉ wazirs: just lay them out in a checkerboard pattern! Assuming the top-left tile is white, there are ⌈n²/2⌉ white tiles and ⌊n²/2⌋ black tiles on the n × n board. And if we place wazirs on the white tiles, no two of them are attacking each other, as every wazir only “sees” black tiles.

    Here’s how we place 13 wazirs on a 5 × 5 board (each W is a wazir).

              13 wazirs on a 5 × 5 board

  • We can’t do any better: let’s arbitrarily tile the checkerboard with 2 × 1 domino pieces, optionally using a 1 × 1 piece for the final corner of an odd-length chessboard, like so:

              domino cover of a 5 × 5 board

    We need ⌈n²/2⌉ dominoes to cover the chessboard. Clearly, putting two wazirs on one domino makes it so that they can attack one another! So each domino can only contain at most one wazir, meaning we can’t possibly place more than ⌈n²/2⌉ wazirs on the board.

\$\endgroup\$
  • \$\begingroup\$ You don't need the pigeonhole principle for the last part: you have exactly ⌈n²/2⌉ tiles, and at most camel per tile, so you have at most ⌈n²/2⌉ camels. \$\endgroup\$ – ShreevatsaR Oct 3 '17 at 7:29
  • 8
    \$\begingroup\$ @ShreevatsaR What ensures you that you can't put x > ⌈n²/2⌉ camels in ⌈n²/2⌉ tiles? It's the pigeonhole principle... \$\endgroup\$ – frarugi87 Oct 3 '17 at 7:58
  • 2
    \$\begingroup\$ I thought at first the code didn't load, so I refreshed the page, and it still didn't. Then I realized what language name was written at the top. \$\endgroup\$ – Arthur Oct 4 '17 at 9:28
  • 7
    \$\begingroup\$ I appreciate that you went and changed your C's to W's in your proof illustration. \$\endgroup\$ – Giuseppe Oct 4 '17 at 13:39
  • 4
    \$\begingroup\$ I also appreciate that the W's are all on the WHITE SPACES with an answer in WHITESPACE. \$\endgroup\$ – corsiKa Oct 4 '17 at 16:13
16
\$\begingroup\$

Oasis, 3 bytes

k>v

Try it online!

square - increment - integer halve

\$\endgroup\$
10
\$\begingroup\$

Prolog (SWI), 22 19 bytes

Saved 3 bytes thanks to Kevin Cruijssen

X*Y:-Y is(X*X+1)/2.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ X*Y:-Y is(X*X+1)/2. (19 bytes) \$\endgroup\$ – Kevin Cruijssen Oct 2 '17 at 13:43
  • 2
    \$\begingroup\$ @KevinCruijssen: Doh! I suggested the same change to another user, but somehow I didn't take my own advice. Thank you :) \$\endgroup\$ – Emigna Oct 2 '17 at 14:06
9
\$\begingroup\$

APL (Dyalog), 9 7 6 bytes

Now uses Mr. Xcoder's formula.

This is an anonymous prefix tacit function which takes N as argument.

⌈2÷⍨×⍨

Try it online!

×⍨ square N (lit. multiplication selfie, i.e. multiply by self)

2÷⍨ divide by 2

 ceiling (round up)

\$\endgroup\$
  • \$\begingroup\$ Wow!I have no idea how you did this !!Didn't get the logic thoughsigh \$\endgroup\$ – Sasha R Oct 2 '17 at 8:49
  • \$\begingroup\$ Darn, someone already found out the pattern. \$\endgroup\$ – Feathercrown Oct 2 '17 at 18:26
  • 1
    \$\begingroup\$ Huh, just realized the formula is on the OEIS page. Probably shouldn't have linked that. \$\endgroup\$ – Feathercrown Oct 2 '17 at 18:27
7
\$\begingroup\$

JS (ES6) / C# polyglot, 11 bytes

n=>n*n+1>>1

Test cases

let f =

n=>n*n+1>>1

console.log(f(7))
console.log(f(8))
console.log(f(100))

\$\endgroup\$
  • 3
    \$\begingroup\$ C# polyglot \$\endgroup\$ – Shaggy Oct 2 '17 at 16:41
  • \$\begingroup\$ @Shaggy Thanks for noticing! \$\endgroup\$ – Arnauld Oct 2 '17 at 16:49
  • 1
    \$\begingroup\$ JS and C# polyglot seems extremely rare, given the differences between them. +1 \$\endgroup\$ – caird coinheringaahing Oct 4 '17 at 11:36
6
\$\begingroup\$

dc, 6 bytes

2^2~+p

2^: square; 2~: divide by 2, pushing the quotient then the remainder; +p: add the remainder to the quotient & print.

Try it online!

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

05AB1E, 3 bytes

Straight implementation of the formula given by A000982

n;î

Try it online!

Explanation

n      # square
 ;     # divide by 2
  î    # round up
\$\endgroup\$
5
\$\begingroup\$

Python 2, 17 bytes

1 byte thanks to @ovs.

lambda x:x*x+1>>1

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Alternatively: lambda x:-~x**2/2 \$\endgroup\$ – RoryT Oct 2 '17 at 23:46
5
\$\begingroup\$

C (gcc), 23 18 17 bytes

  • Saved a byte thanks to Tahg; golfing n/2+n%2 to n+1>>1.
f(n){n=n*n+1>>1;}

Try it online!

C (gcc), 22 bytes (not using undefined behavior)

f(n){return n*n+1>>1;}

Try it online!

Some people really do not like exploiting a certain compiler's undefined bahavior when using specific compiler flags. Doing so does save bytes, though.

\$\endgroup\$
  • 3
    \$\begingroup\$ Odd way of providing an answer IMO, but: f(n){n=n*n+1>>1;} to save a byte. \$\endgroup\$ – Tahg Oct 2 '17 at 9:56
  • 1
    \$\begingroup\$ @Tahg Thanks; though in what way do you find my way of providing an answer odd? \$\endgroup\$ – Jonathan Frech Oct 2 '17 at 10:51
  • 2
    \$\begingroup\$ I didn't think changing the input argument was a normal way of returning a value in C. \$\endgroup\$ – Tahg Oct 2 '17 at 13:41
  • 2
    \$\begingroup\$ @YSC Yet in the compiler's opinion it is understandable and creates an executable which works. \$\endgroup\$ – Jonathan Frech Oct 3 '17 at 15:10
  • 5
    \$\begingroup\$ @YSC We believe here on PPCG that, if the program works on one interpreter, it is a valid submission. It works on an online interpreter, it is therefore valid without any further remarks. \$\endgroup\$ – Conor O'Brien Oct 3 '17 at 22:37
4
\$\begingroup\$

Brachylog, 6 bytes

^₂/₂⌉₁

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3, 19 bytes

lambda x:-(-x*x//2)

Try it online!

lambda x:-(-x*x//2)  # Unnamed function
lambda x:            # Given input x:
            x*x      # Square
           -         # Negate
               //2   # Halve and Floor (equivalent of Ceil)
         -(       )  # Negate again (floor -> ceil)

-1 byte thanks to Mr. Xcoder

\$\endgroup\$
  • \$\begingroup\$ x**2 -> x*x \$\endgroup\$ – Mr. Xcoder Oct 2 '17 at 13:00
  • \$\begingroup\$ @Mr.Xcoder Facepalm thanks \$\endgroup\$ – HyperNeutrino Oct 2 '17 at 13:06
  • \$\begingroup\$ What about lambda x:x*x+1>>1 ? \$\endgroup\$ – Alix Eisenhardt Oct 2 '17 at 15:47
  • \$\begingroup\$ Or lambda x:x*x+1//2 Disclaimer: I don't know this language's syntax or order of operations, so I guessed; I'm saying add 1 before you //2 instead of negating twice. \$\endgroup\$ – Dan Henderson Oct 2 '17 at 15:57
  • \$\begingroup\$ @DanHenderson You still need parentheses otherwise it's parsed as (x*x) + (1//2), so that isn't actually shorter. \$\endgroup\$ – Skyler Oct 2 '17 at 17:09
4
\$\begingroup\$

x86_64 machine language (Linux), 9 8 bytes

0:       97                      xchg   %eax,%edi
1:       f7 e8                   imul   %eax
3:       ff c0                   inc    %eax
5:       d1 f8                   sar    %eax
7:       c3                      retq

To Try it online!, compile and run the following C program.

#include<stdio.h>
const char *f="\x97\xf7\xe8\xff\xc0\xd1\xf8\xc3";
int main() {
  for(int i=1; i<10; i++) {
    printf("%d\n", ((int(*)())f)(i));
  }
}
\$\endgroup\$
3
\$\begingroup\$

J, 8 bytes

Anonymous tacit prefix function.

2>.@%~*:

Try it online!

*: square

>. ceiling (round up)
@ after
2%~ dividing by two

\$\endgroup\$
  • \$\begingroup\$ Alternate solutions: <.@-:@*: and *:<.@%2: \$\endgroup\$ – Conor O'Brien Oct 3 '17 at 22:39
  • 2
    \$\begingroup\$ @ConorO'Brien 2>.@%~*:‽ Where did I get that from? I can't read that – looks like line noise to me… \$\endgroup\$ – Adám Oct 3 '17 at 22:47
  • \$\begingroup\$ >.@-:@*: gets my vote. \$\endgroup\$ – Jonah Oct 4 '17 at 2:56
  • 1
    \$\begingroup\$ @Jonah If you squint, you can see a camel. \$\endgroup\$ – Adám Oct 4 '17 at 8:30
3
\$\begingroup\$

Actually, 3 bytes

²½K

Try it online!

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

R, 22 21 bytes

cat((scan()^2+1)%/%2)

Try it online!

Square, increment, integer divide. Easy peasy.

Input from stdin; it can take space or newline separated input and it will compute the max wazirs for each input boardsize. Output to stdout.

-1 byte thanks to plannapus

\$\endgroup\$
  • \$\begingroup\$ @plannapus fixed, thank you. \$\endgroup\$ – Giuseppe Dec 11 '17 at 20:48
2
\$\begingroup\$

Pyth, 6 bytes

.E**.5

Try it online!

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

Pyke, 3 bytes

Xhe

Try it here!

How?

X   - Square.
 h  - Increment.
  e - Floor halve.
\$\endgroup\$
2
\$\begingroup\$

C# (.NET Core), 14 12 bytes

-2 bytes thanks to Emigna

n=>(n*n+1)/2

Try it online!

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

Perl 5, 16 bytes

$_=0|$_*$_/2+.5

Try it online!

\$\endgroup\$
  • \$\begingroup\$ $_=$_*$_+1>>1 14 bytes \$\endgroup\$ – Nahuel Fouilleul Oct 4 '17 at 8:11
2
\$\begingroup\$

MATL, 5 bytes

UH/Xk

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ or UQ2/k at the same byte count. \$\endgroup\$ – Giuseppe Oct 2 '17 at 13:31
2
\$\begingroup\$

Cubix, 11 bytes

Iu*:^\)2,O@

Heheh, :^\)

Try it online!

Expands to the following cube:

    I u
    * :
^ \ ) 2 , O @ .
. . . . . . . .
    . .
    . .

Which is the same algorithm that many use.

  • ^Iu : read in input as int and change directions
  • :* : dup top of stack, multiply
  • \) : change direction, increment
  • 2, : push 2, integer divide
  • O@ : print output as int, end program.
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 12 bytes

⌈#^2/2⌉&
\$\endgroup\$
  • 2
    \$\begingroup\$ 11 bytes: ⌈#.5#⌉& \$\endgroup\$ – user202729 Oct 5 '17 at 0:48
2
\$\begingroup\$

Pyke, 3 bytes

Xhe

Try it here!

X   -   input ** 2
 h  -  ^ + 1
  e - floor_half(^)
\$\endgroup\$
  • \$\begingroup\$ I ninja'd you by about 12 hours :-/ \$\endgroup\$ – Mr. Xcoder Oct 3 '17 at 11:56
2
\$\begingroup\$

Ohm v2, 3 bytes

²½ı

Try it online!

² squares, ½ halves, ı ceils.

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

Jelly, 3 bytes

-1 thanks to Mr. Xcoder.

Based on my APL solution.

²HĊ

Try it online!

² Square

HHalve

ĊCeiling (round up)

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

Japt, 4 bytes

Been sitting on these since the challenge was closed.

²Ä z

Try it

Explanation: Square, add 1, floor divide by 2


Alternative

²ÄÁ1

Try it

Explanation: Square, add 1, bit-shift right by 1.

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

Commentator, 19 bytes

//{-//-}! {-#  -}<!

Try it online!

Who needs golfing languages? I've got confusing languages!

Ungolfed version:

5//{-8}//{5-}
print(10!= 5)
x={-1,3,4} # Smiley :-}
print(5<!=10)*/ # Weird comparision.

Try it online!

How does it work? I'll explain, with input 5

//                         - Take input.                           Tape: [5 0 0]
  {-//-}!                  - Square the input.                     Tape: [25 0 0]
  {-                         - Move one along the tape
    //                       - Copy the input to the tape.         Tape: [5 5 0]
      -}                     - Move one back along the tape
        !                    - Take the product of the tape.       Tape: [25 5 0]
         <space>           - Increment the tape head.              Tape: [26 5 0]
                 {-#  -}<! - Halve the tape head (floor division). Tape: [13 2 0]
                 {-          - Move one along the tape
                   #         - Set the tape head to 2.             Tape: [26 2 0]
                      -}     - Move one back along the tape
                        <!   - Reduce the tape by floor division.  Tape: [13 2 0]
\$\endgroup\$
1
\$\begingroup\$

OCaml, 19 bytes

let f n=(n*n+1)/2;;

Try it online!

I'm a bit bummed the name got changed from "camels" to "wazirs" before I managed to write this, but I figured I'd post it anyway.

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

TI-Basic, 7 bytes

round(Ans²/2,0

Alternatively (8 bytes):

int(Ans²/2+.5
\$\endgroup\$
  • \$\begingroup\$ -int(-.5Ans² also works \$\endgroup\$ – Oki Oct 5 '17 at 14:56
  • \$\begingroup\$ @Oki It sure does. I just wish they had a ceil( function. \$\endgroup\$ – Timtech Oct 5 '17 at 17:55
1
\$\begingroup\$

///, 35 bytes

/I///,*/+,//+/I//**,/,A//*/A//,//,I

Try it online!

Takes input in unary using symbol *, and output in unary using symbol A. This is allowed for some specific languages, including /// (meta)

Because there is no way to take input in ///, input should be hardcoded:

/I/«put input here»//,*/+,//+/I//**,/,A//*/A//,//,I

for input = 4.


Explanation: (before reading, you need to know that the only syntax of /// are /pattern/replacement/, which replace every occurence of pattern by replacement; and \ for escaping; other characters is printed to output)

For n=4:

/I/****//,*/+,//+/I//**,/,A//*/A//,//,I    Start program.
/I/****/                                   Replace all `I` in the program by the input.

/,*/+,//+/****//**,/,A//*/A//,//,****      Remaining part of the program.
/,*/+,/                                    Use the `,` as a scanner, scan through `*` after it and convert to `+`.
       /+/****//**,/,A//*/A//,//++++,      Note that only `*` in the second group is affected.
       /+/****/                            Replace all `+` (which is just created) by `n` asterisks (from the first `I` group)

/**,/,A//*/A//,//****************,         Now at the last of the program before the `,` there are `n²` asterisks.
/**,/,A/                                   Scan the `,` to the left to perform division by 2:
                                           replace each `**` by a `A` as the scanner `,` pass through.
/*/A//,//,AAAAAAAA                         Remaining program.
/*/A/                                      If there is any `*` remaining (if `n²` is odd), replace it with `A`.
     /,//                                  Remove the scanner `,`.
          AAAAAAAA                         Output the result.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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