Número de peças em um tabuleiro de damas

14

Introdução

Um tabuleiro de damas normal contém 8 x 8 = 64 quadrados:

insira a descrição da imagem aqui

Você pode ver que, no total, existem 12 peças brancas . Preto e branco sempre têm a mesma quantidade de peças. Se houver mais peças no tabuleiro, as peças serão vizinhas, o que não é permitido para esse desafio. Para esclarecer as coisas, aqui estão alguns exemplos:

O menor quadro possível para esse desafio é 3 x 3 :

insira a descrição da imagem aqui

Você pode ver que a quantidade máxima de peças é igual a 2 . Portanto, quando dado N = 3 , você precisa gerar 2 . Se a entrada for N = 4 , obtemos o seguinte:

insira a descrição da imagem aqui

Você pode ver que o valor máximo também é 2. Portanto, para N = 4 , a saída deve ser 2 . Para N = 5 , a saída deve ser igual a 5 :

insira a descrição da imagem aqui

Exemplos

STDIN:  3
STDOUT: 2

STDIN:  4
STDOUT: 2

STDIN:  5
STDOUT: 5

STDIN:  6
STDOUT: 6

STDIN:  8
STDOUT: 12

Regras

  • Sua submissão deve ser um programa, função, etc., que use um número inteiro e produz ou retorna o número de peças no quadro
  • Você pode assumir com segurança que a entrada é um número inteiro não negativo> 2
  • Isso é , então o programa com a menor quantidade de bytes vence!
  • Observe que o quadrado no canto inferior esquerdo do quadro está sempre escuro. As peças são colocadas apenas em quadrados escuros
  • Você tem que ocupar uma linha cheia de peças
Adnan
fonte
3
Por que a restrição a programas completos e STDIN / STDOUT? A IMO é injusta com idiomas que possuem programa e / ou sobrecarga de entrada necessários.
lirtosiast
@ThomasKwa, você está certo. Funções etc. são agora permitidas
Adnan

Respostas:

5

Par , 8 bytes

✶″½↓┐*½┐

Um byte é usado por caractere.

Explicação

               ## [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
Ypnypn
fonte
12

Hexagonia , 19 bytes

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

Experimente online.

Explicação

Esse ainda é o mesmo cálculo que eu usei nas minhas respostas CJam e Labyrinth, mas devido ao modelo de memória ... especial ... do Hexagony, é um pouco mais complicado compactar o cálculo em 19 bytes (para que ele caiba dentro de um hexágono 3 de comprimento lateral).

Como minha resposta do labirinto, isso termina com um erro de divisão por 0.

Aqui está o código desdobrado:

insira a descrição da imagem aqui

Como eu disse, o código é totalmente linear. Você pode juntar o caminho executado em ordem cinza-roxo-verde-vermelho-azul. O caminho continua um pouco mais até atingir o :lado esquerdo. Removendo o /(que redireciona apenas o fluxo de controle), todo o programa desenrolado linearmente é:

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

Então a questão é como isso funciona. A memória do hexagony é o gráfico de linhas de uma grade hexadecimal, em que cada extremidade da grade contém um valor inteiro (inicialmente zero). O ponteiro de memória (MP) está sempre em uma borda e aponta em uma determinada direção ao longo dessa borda. As operações aritméticas são geralmente aplicadas às duas arestas pontiagudas para e armazenados na borda da MP está ligado.

Para este programa, usaremos as três arestas rotuladas A , B , C , com o MP iniciando como mostrado aqui:

insira a descrição da imagem aqui

Então, aqui está como isso funciona:

?  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.
Martin Ender
fonte
{{move a borda da memória duas vezes para que o & na segunda linha pareça não estar fazendo nada? Ambos os neigbours devem ser 0 lá
Eumel 01/12/2015
@Umumel Essa não é a ordem em que o código é executado. Após o primeiro {, o IP salta para o2 canto esquerdo. Depois do )canto direito, o IP salta para o 'canto inferior esquerdo. Em seguida, o IP percorre as linhas 2 e 4 de uma maneira estranha e ciclicamente envolvente.
Martin Ender
oh eu pensei que só mudou o ME não o IP. também +1 apenas por usar hexagonia que a linguagem é muito engraçada
#
@Eumel Sim. É assim que as bordas do código são agrupadas no Hexagony.
Martin Ender
8

CJam, 10 bytes

ri_(2/*)2/

Teste aqui.

Explicação

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.
Martin Ender
fonte
8

Labirinto , 11 bytes

Woohoo, apenas um byte atrás do CJam .

?:(#/*)_2/!

Experimente online.

É essencialmente a mesma coisa:

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

No entanto, neste momento, o programa ainda não termina. Em vez disso, o ponteiro de instruções atingiu um beco sem saída e se vira. Mas agora /tenta calcular o 0/0que termina com um erro .

Martin Ender
fonte
5

Sério , 8 bytes

,;D½L*½K

Sério tem o útil ½ (flutuar dividir por 2) e K(teto), portanto, não precisamos adicionar um antes da divisão.

Experimente aqui com explicação.

lirtosiast
fonte
5

Python 2, 22 21 bytes

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

Eu primeiro separo em dois casos, N ímpar e N.

Com N ímpar, podemos preencher (N - 1) / 2 linhas, contendo em média N / 2 peças. Como a primeira linha sempre tem mais peças, devemos limitar esse resultado. Então, quando N é ímpar, temos peças de teto ((N-1) / 2 * N / 2).

Com N uniforme, podemos preencher linhas N / 2 - 1 ou piso ((N - 1) / 2), cada linha contendo N / 2 partes.

Podemos combinar essas duas expressões por teto (piso ((N-1) / 2) * N / 2)). Desde ceil (x / 2) = andar ((x + 1) / 2) podemos usar piso Divisão: ((N - 1) // 2 * N + 1) // 2.

orlp
fonte
3

JavaScript, 37 35 bytes

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

Explicação

Usa uma técnica semelhante ao restante das respostas. Este é o algoritmo não destruído:

var n = parseInt(prompt());
var result = Math.ceil(Math.floor((n - 1) / 2) * n / 2);
alert(result);
user81655
fonte
3

dc, 12

?d1-2/*1+2/p

Saída de teste:

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

Pitão, 9 bytes

/h*/tQ2Q2

O mesmo algoritmo da minha resposta do Python 2.

orlp
fonte
3

Japonês , 16 14 bytes

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

Experimente online!

Como funciona

Bem simples:

         // 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

Eu gostaria que houvesse alguma maneira de levar em conta que as duas metades do código são muito semelhantes. Sugestões são bem-vindas!

Versão antiga (16 bytes):

U*½-½|0 *U*½+½|0
ETHproductions
fonte
3

Java, 230 155 52

Golfe:

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

}

Saída do programa:

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

fonte
throws Exceptioné permitido.
Neil
1
OP funções permitidas.
lirtosiast
Você pode usar a Scannerclasse para entrada. Isso economizaria um monte de bytes, eu acho. (A BufferedReader/ InputStreamReadercombinação pode ser melhor no uso geral, mas este é o golfe código, e Scannerfunciona muito bem para a entrada simples.)
Darrel Hoffman
A conversão para uma função autônoma e o uso de parâmetros / valores de retorno em vez da entrada / saída padrão fizeram uma enorme diferença.
2

Código da máquina Zilog ez80, 9 bytes

Em hexadecimal:

6C 2D CB3D ED6C 2C CB3D

Na montagem:

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

A entrada está no registro he a saída está nol .

O Zilog ez80 é um processador de 8 bits com um acumulador de 8 bits e registradores de 24 bits. Diferentemente do z80, ele possui uma mltinstrução (multiplicação de 8 bits), que, no modo de 16 bits, multiplica os bytes alto e baixo de um par de registradores aqui hle armazena novamentehl .

Isso funciona apenas para valores para os quais duas vezes o resultado se encaixa em 8 bits; isto é, n≤23.

lirtosiast
fonte
2

TI-BASIC, 13 bytes

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

A multiplicação implícita do TI-BASIC ajuda, mas não possui divisão inteira. ⁻int(⁻Xé uma forma mais curta de teto (x).

lirtosiast
fonte
2

vba, 46

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

Ligue com? F (x) ou = f (A1) em uma fórmula

SeanC
fonte
2

Pitão, 17 14 13 bytes

-3 bytes graças a Ypnypn ! Reorganizou os números do operador * para economizar 1 byte.

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

Explicação:

Quando n é par, podemos ocupar n / 2-1 linhas com n / 2 partes, perfazendo um total de n * (n / 2-1) / 2 partes. Essa expressão é equivalente a (n * (n / 2-1) +1) / 2

Quando n é ímpar, podemos descobrir como seria o dobro do número de peças, o dobro do número de peças abrangerá n-1 linhas e, se eu retirar uma peça, podemos dividir as n-1 linhas em (n- 1) / 2 grupos de 2 linhas, de modo que cada grupo tenha n partes, portanto a expressão para este caso é (n * (n / 2) +1) / 2

Agora que as duas expressões são bastante semelhantes, podemos escrever o código.

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

Minha primeira vez usando uma linguagem de golfe.

Element118
fonte
2

Javascript, 33 bytes

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

Se uma função ES6 for permitida, 18 bytes:

a=>a*(a-1>>1)+1>>1
Neil
fonte
2

MATLAB, 37 25 bytes

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

Eu acredito que isso deve funcionar, funciona para todos os casos de teste.

Também funciona no Octave . Você pode tentar online aqui .


Para o código antigo eu adicionei o programa para a área de trabalho em um arquivo chamado checkerboard.m. Você pode executá-lo simplesmente digitando checkerboardno prompt e, quando iniciar, digite o tamanho necessário no prompt. O resultado será impresso.

Para o novo código, basta inserir o código postado aqui no prompt e chamar a função anônima como ans(n).

Tom Carpenter
fonte
Obrigado pelos votos, finalmente chegou a 1000 Rep :) Woop.
Tom Carpenter
@ThomasKwa obrigado por apontar isso. Salvo 12 bytes :).
TomTomenter3 de
2

Retina , 18 bytes

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

Entrada e saída são unárias .

Experimente online!

A versão mais recente do Retina (mais recente que esse desafio) pode lidar com E / S decimal por quatro bytes adicionais:

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

Experimente online!

Com entrada unária e saída decimal, podemos fazer 16 bytes, mas isso parece um pouco exagerado:

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

Explicação

Ainda é a mesma abordagem que qualquer pessoa, mas usando a substituição de regex em uma representação unária do número.

11(..?$)?
$_

Isso calcula n*((n-1)/2). Fazemos isso combinando dois caracteres de cada vez (divisão por dois) e substituindo-os pela string inteira (multiplicação por n). O decréscimo de né feito ignorando o restante da sequência, se houver apenas um ou dois caracteres.

11?
1

Esta é a divisão inteira por 2, arredondada para cima. Simplesmente substituímos dois caracteres por um (divisão por 2), mas permitimos que a última correspondência consista em apenas um caractere (arredondamento para cima).

Martin Ender
fonte
Parabéns pela sua 1000ª resposta: p
Adnan
1

Python 3, 39 bytes

Isso está um pouco inchado, mas não tenho certeza se poderia jogar muito mais longe do que isso. Um link para teste.

n=int(input());print(((n-1)//2*n+1)//2)
Sherlock9
fonte
1

Prolog, 39 38 bytes

Código:

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

Explicação:

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.

Exemplo:

p(8).
12

Experimente online aqui

Editar: salvou 1 byte substituindo ceil / 2 por + 1 // 2

Emigna
fonte
1

Caxumba, 17 bytes

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

Graças a Emigna pela explicação simples do algoritmo. Isso explora a "deficiência" matemática de Mumps de que as operações são executadas estritamente da esquerda para a direita (não do PEMDAS), de modo que os parênteses não são necessários. :-)

A saída parece um pouco estranha, no entanto, como o Ensemble do Cache (o ambiente Mumps ao qual tenho acesso) não gera automaticamente retornos de carro mesmo quando pressionado na entrada. Se você quiser mais bonito, adicione 4 caracteres para retornos de carro pré / pós:

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

Obrigado!

zmerch
fonte
1

Bash, 32 bytes

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

Lote, 30 bytes

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

38 bytes se a entrada no stdin for necessária:

@set/pa=
@cmd/cset/a(a*((a-1)/2)+1)/2
Neil
fonte