8
\$\begingroup\$

You want to create a square chessboard. Adjacent tiles must alternate black and white like a standard chessboard, and the bottom left corner can be either black or white.

Your program will take in two positive integers, the number of black and the number of white tiles. These will always be less than 1024. You don't have to use all the tiles.

Output the maximum side length of a chessboard pattern that can be constructed using the given amount of tiles.

Test Cases:

12, 15 -> 5
8, 8 -> 4    
4, 0 -> 1
\$\endgroup\$
  • \$\begingroup\$ Hey! I've edited your question to say what I thought you meant. If it isn't, you can edit it again. Welcome to PPCG! \$\endgroup\$ – CG One Handed Apr 16 at 21:27
  • 2
    \$\begingroup\$ I think this is a nice question but, unfortunately, poorly stated. OP means that by giving you some black tiles and some white tiles (0 to 1000 for every color) find out the dimensions of the biggest chessboard that you can make out of them.Interesting test cases: Input[10,15] and Output[4] and also Input[12,12] and Output[4] \$\endgroup\$ – J42161217 Apr 16 at 22:16
  • 4
    \$\begingroup\$ You also posted this last week, where you were directed to the sandbox \$\endgroup\$ – xnor Apr 17 at 1:13
  • 8
    \$\begingroup\$ Last test case should be 1. \$\endgroup\$ – Nick Kennedy Apr 18 at 6:30
  • 2
    \$\begingroup\$ @SriotchilismO'Zaic, we also sometimes accept the shortest solution in one particular language. "Best explanation", though, is not a valid criterion for accepting a solution. \$\endgroup\$ – Shaggy Apr 20 at 16:55

10 Answers 10

10
\$\begingroup\$

JavaScript (ES7), 30 bytes

b=>w=>((b<w?b:w)*2|b!=w)**.5|0

Try it online!

Given the number of black squares \$b\$ and the number of white squares \$w\$, this computes:

$$s=\left\lfloor\sqrt{2\times\min(b,w)+k}\right\rfloor$$ with: $$k=\begin{cases} 0&\text{if }b=w\\ 1&\text{if }b\neq w \end{cases}$$

For even sizes \$s\$, we need \$s^2/2\$ squares of each kind (e.g. for \$s=8\$: \$32\$ black squares and \$32\$ white squares).

For odd sizes \$s\$, we need \$\lfloor s^2/2\rfloor\$ squares of one kind and \$\lceil s^2/2\rceil\$ squares of the other kind (e.g. for \$s=5\$: \$12\$ black squares and \$13\$ white squares, or the other way around). The parameter \$k\$ is set to \$1\$ if \$max(b,w)\geq min(b,w)+1\$, which represents this extra square on one side.

\$\endgroup\$
6
\$\begingroup\$

Jelly, 6 bytes

«Ḥ+nƽ

Try it online!

A dyadic link that returns the maximum board size.

Test suite for all permutations of numbers to 20

Explanation

«      | Minimum
 Ḥ     | Doubled
  +n   | Plus 1 if inputs not equal
    ƽ | Integer square root

Arnauld’s answer has a good explanation for why this works; please consider upvoting him too!

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

Haskell, 35 bytes

x#y=floor$sqrt$min(x+y)$1+2*min x y

Try it online!

Explanation

This answer calculates the following formula:

$$\left\lfloor\sqrt{\min(a+b,2\min(a,b)+1)}\right\rfloor$$

Why does this formula work? Well lets start by noting the following:

Every square of even side length can be tiled by \$2\times 1\$ tiles.

and

Every square of odd length can be tiled, spare a single \$1\times 1\$ square, by \$2\times 1\$ tiles.

Now we note that if we put these \$2\times 1\$ tiles on a chessboard each would lay on top of one black square and on white square. So if we make an even chessboard every tile needs to have a pair of the other color, and if we make an odd chessboard every tile but one needs a pair of the other color. This tells us that the answer is never more than \$\left\lfloor\sqrt{2\min(a,b)+1}\right\rfloor\$. \$2\min(a,b)\$ is the maximum number of pairs we can make and the \$+1\$ is for the last square that doesnt' need a pair. The problem with this is that if \$a=b\$ we will not have the extra square for the odd case. So we add another condition: Our result cannot be more than \$\left\lfloor\sqrt{a+b}\right\rfloor\$. That is we can't make a square which has more tiles than we have available.

So we just take the lesser of the two options.

$$\left\lfloor\sqrt{\min(a+b,2\min(a,b)+1)}\right\rfloor$$

We can notice that this is the same as Arnauld's formulation since if \$a=b\$ then \$2\min(a,b)\$ is just \$a+b\$.

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

Ruby, 36 bytes

->x,y{'%i'%[x+y,x-~x,y-~y].min**0.5}

Try it online!

x-~x is a golfed version of 2*x+1; we're subtracting x's twos-complement negation from itself. After that I'm just using this answer's formula, but collapsing the two nested mins into one, then using string formatting to truncate to an integer.

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

Retina 0.8.2, 50 bytes

O#`\d+
\d+
$*
(1*),(1?\1)1*
$1$2
^(^1|11\1)*1*
$#1

Try it online! Link includes test cases. Explanation:

O#`\d+

Sort the numbers in ascending order. Let's call them l and h.

\d+
$*

Convert to unary.

(1*),(1?\1)1*
$1$2

Compute l + max(h, l + 1). This is the equivalent to 2 * min(b, w) + (b != w). See @Arnauld's answer for why this works.

^(^1|11\1)*1*
$#1

Find the highest integer square root.

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

05AB1E, 8 7 bytes

Ë≠+ß·tï

Try it online or verify all test cases.

Exlanation:

Uses a trivial derivative of the formula @Arnauld used in his JavaScript answer to save a byte:

$$s=\left\lfloor\sqrt{2\times\min(b+k,w+k)}\right\rfloor$$ with still: $$k=\begin{cases} 0&\text{if }b=w\\ 1&\text{if }b\neq w \end{cases}$$

Ë        # Check if the two values of the (implicit) input-pair are the same
         #  (1 if truthy; 0 if falsey)
 ≠       # Falsify (!= 1), so 1 becomes 0 and vice-versa
  +      # Add that to each of the (implicit) input-values
   ß     # Only leave the minimum of that
    ·    # Double it
     t   # Take the square root
      ï  # And truncate/floor it by casting to an integer
\$\endgroup\$
1
\$\begingroup\$

Japt, 11 bytes

Port of Arnauld's JS solution. Takes input as an array.

ñÍÌÑ+Ur¦)¬f

Try it

ñÍÌÑ+Ur¦)¬f     :Implicit input of array U
ñ               :Sort by
 Í              :  Subtracting from 2
  Ì             :Last element (Yes, there are more straightforward ways of getting the minimum but I like this method and it doesn't cost any bytes)
   Ñ+           :Multiply by 2 and add
     Ur         :U reduced by
       ¦        :  Testing for inequality
        )       :End reduce
         ¬      :Square root
          f     :Floor
\$\endgroup\$
1
\$\begingroup\$

R, 32 bytes

min(sum(n<-scan()),2*n+1)^.5%/%1

Try it online!

Takes b and w from stdin.

Uses the formula from this answer, but leveraging the behavior of min to take the minimum of all its arguments.

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

Perl 6, 29 26 bytes

{0+|sqrt 2*@_.min+[!=] @_}

Thanks to Jo King for -3 bytes.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ [min] @_ can be @_.min and you can move the [!=] to the end to save on the brackets. 26 bytes \$\endgroup\$ – Jo King Apr 20 at 22:41
0
\$\begingroup\$

Japt, 10 bytes

Port of Arnauld's JS solution.

mV Ñ|U¦V ¬

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG and welcome to Japt! :) Note, though, that you need to floor the result of the square root. Otherwise this'll fail for the likes of 12, 12. \$\endgroup\$ – Shaggy Apr 19 at 22:45

Your Answer

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