Desafio para programador C/C++ ( oferta de emprego)

[pedrix21 0]

Boas pessoal, esta no netEmprego e encontrei isto

Um desafio para o pessoal

#define N    (1 << 25)
#define F(a,b)  { (a) ^= (b); (b) ^= (a); (a) ^= (b); }

uint32_t d[N];

int main(void)
{
   uint64_t h, i, j;

   for (i = 1; i < N; i++)
       d[i] = d[i-1] * 69069 + 1;

   for (i = 0; i < N; i++)
       for (j = 1; j < N; j++)
           if (d[j] < d[j-1])
               F(d[j-1], d[j])

   h = 0;

   for (i = 0; i < N; i++)
       h = h * 13 + d[i];

   h ^= 0x8678ADF24D4F64EFULL;

   printf("Please, mail your CV to %8.8s@grupopie.com\n", &h);

   return 0;
}

Ver Oferta de Emprego: http://www.net-empregos.com/1164427/desafio-para-programador-c/#ixzz1BjGlma3a

www.net-empregos.com - O maior site português de ofertas de emprego

[Triton 8]

Desafio fraquinho.

[Triton 8]

Então, mais ninguém consegui resolver?

Como já passou algum tempo e me pediram como explicar aqui fica:

SPOILER ALERT (Não ler o resto se querem tentar resolver):

A primeira coisa que devem fazer é compilar o código. Adicionar os devidos includes necessários. Depois reparar que o código implementa um LCG, um algoritmo simples para geração de números pseudo-aleatórios, embora mesmo sem reconhecer o algoritmo desse para resolver.

Depois meti uns prints antes e depois dos loops (podem mudar o valor de N para facilitar este passo). Vão reparar que um loop ali no meio está a ordenar o array da pior maneira possível. Basicamente a macro F é um in-place XOR swap. Substituam por um algoritmo eficiente para ordenação de números como radix sort ou qsort, et voilá.

[selicerin 0]

Em primeiro lugar peço desculpa por reavivar este tópico, mas nao fazia muito sentido criar um exactamente igual.

Estou a aprender C/C++ e dei com este anuncio por acaso (e uma pesquisa no google direccionou-me para aqui). Fiz o sugerido no post anterior, alterar o algoritmo de ordenação, mas o resultado que obtenho é uns caracteres estranhos (pontos de interrogação com fundo preto e por aí).

Nao estou interessado em responder ao anuncio, é apenas por curiosidade, mas agradecia se alguem me pudesse dar uma ajuda no porque de os prints saírem estranhos

[Triton 8]

Se bem me lembro é mesmo só fazer o que disse em cima que se chegava à reposta facilmente, mas como já passou tanto tempo já não me lembro de detalhes concretos.

[cffm 0]

Boas

Estive a ver o exemplo e não percebi bem qual o objectivo do desafio, isto é, o que têm de fazer para o terminar?

[Warrior 68]

Acho que isso é parte do desafio, mas o objectivo é descobrires para que mail enviar o currículo

[soniculture 0]

eu tenho um problema com este código!

Implementei o qsort direitinho mas no printf tenho problemas

aqui vai o warning:

warning: format '%8.8s' expects type 'char *', but argument 2 has type 'uint64_t *'

estou a utilizar o xcode!

Obrigado

[pmg 86]

eu tenho um problema com este código!

Implementei o qsort direitinho mas no printf tenho problemas

aqui vai o warning:

warning: format '%8.8s' expects type 'char *', but argument 2 has type 'uint64_t *'

O codigo original tem muitas coisas que podem ser melhoradas. Uma delas e o abuso do tipo "uint64_t" na impressao.

O que se passa e que o valor final da variavel h vai ser qualquer coisa como "0x4142434445464748" que pode ser uma representacao da string "HGFEDCBA" (em formato little-endian).

No codigo original eles passam o endereco desse valor para o printf e tudo funciona como esperado, embora seja errado.

Podes fazer um cast e esperar que continue a funcionar (se funciona sem cast, tambem funciona com cast), mas mesmo com o cast continua a ser errado.

    printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

ou isolas cada elemento do valor e imprime-lo isoladamente

    printf("Please, mail your CV to ");
    putchar((h >> 0) & 0xFF);
    putchar((h >> 8) & 0xFF);
    putchar((h >> 16) & 0xFF);
    putchar((h >> 24) & 0xFF);
    putchar((h >> 32) & 0xFF);
    putchar((h >> 40) & 0xFF);
    putchar((h >> 48) & 0xFF);
    putchar((h >> 56) & 0xFF);
    printf("@grupopie.com\n");

[soniculture 0]

Fiz debug do qsort e ele ordena o array mas como que troca a parte direita com a esquerda!

Por exemplo o d[0] deveria ser o d[50] e vice-versa!

É normal o qsort fazer isto?

Concordo contigo com o abuso do int64_t... nem percebo qual a necessidade!

Deixo-te o meu código:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <inttypes.h>

#define N 100

uint32_t d[N];

int sort(const void *x, const void *y)

int main (void) {

uint64_t i,h;
char palavra[64];

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*2+1;
	printf("%u\n",d[i]);
	getchar();
}

qsort(d,N,sizeof(int32_t),sort);

for (i=0;i<N;i++){
	printf("i= %llu, d[i] = %lu\n",i,(long unsigned int)d[i]);

}


h=0;
for (i=0;i<N; i++) {
	h=h*13+d[i];
}

        h ^=0x8678ADF24D4F64EFULL;

printf("%8.8s",(char*)&h);

return 0;
}

int sort(const void *x, const void *y) {
return (*(int32_t*)x - *(int32_t*)y);
}

[soniculture 0]

Cheguei a este resultado:

c\216\362\253 \316\334@grupopie.com

é possível?

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <inttypes.h>

#define N (1<<25)

uint32_t d[N];

int sort(const void *x, const void *y) {
return (*(int32_t*)x - *(int32_t*)y);
}

int main (void) {

uint64_t i,h;
uint32_t temp=0;

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*69069+1;
	//printf("i= %llu, d[i] = %lu\n",i,(long unsigned int)d[i]);
	}

qsort(d,N,sizeof(int32_t),sort);

for (i=0;i<(N/2);i++){
	temp=d[i];
	d[i]=d[i+N/2];
	d[i+N/2]=temp;
}

h=0;
for (i=0;i<N; i++) {
	h=h*13+d[i];
}

h ^=0x8678ADF24D4F64EFULL;

printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

return 0;
}

[pmg 86]

Cheguei a este resultado:

c\216\362\253 \316\334@grupopie.com

é possível?

A tua funcao de comparacao tem 1 bug ...

Estas a converter de "uint32_t" para "int32_t" e a subtrair os valores com sinal.

Na versao original, nao ha conversao.

Por exemplo, se os valores originais fossem "x = 0xFFFFFFFF" e "y = 0x00000001", x e maior que y ... mas depois de convertido para valor com sinal "x = -1" e "y = 1" e x NAO e maior que y.

Alem disso o codigo original assume uma implementacao com valores "little endian". Nao sei como se porta a tua implementacao, mas tem atencao a este ponto!

[soniculture 0]

Já alterei

o resultado dá o mesmo!

penso q se alterar a opção do printf para %1.1 chego a c@grupopie.com!

q achas?

[pmg 86]

Se so mudaste os casts, continuas a ter problema na funcao de comparacao ...

Supoe que "x" e "y" sao respectivamente 1 e 2. Quando subtrais um do outro (1 - 2) com valores de tipo "uint32_t" ("unsigned") o resultado e 4294967295. Se o "int" no teu computador for de 32 bits (faz "#include <limits.h>" e ve "sizeof (int) * CHAR_BIT") a conversao deste valor para tipo "int" nao e fiavel (mas provavelmente da o resultado esperado -1); se o "int" for de 64 bits, o resultado e um valor positivo ... indicando que 1 e maior que 2!!!!

Alem disso, depois de compores a funcao de comparacao, precisas de remover a parte do codigo que troca as metades do array.

[soniculture 0]

O código que fiz foi:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define N (1<<25)

uint32_t d[N];

int sort(const void *x, const void *y) {
return (*(uint32_t*)x - *(uint32_t*)y);
}

int main (void) {

uint64_t i,h;
uint32_t temp=0;

d[0]=0;

for (i=1;i<N;i++){
	d[i]=d[i-1]*69069+1;
	}

qsort(d,N,sizeof(uint32_t),sort);

for (i=0;i<(N/2);i++){
	temp=d[i];
	d[i]=d[i+N/2];
	d[i+N/2]=temp;
}


h=0;

for (i=0;i<N; i++) {
	h=h*13+d[i];
}
h ^=0x8678ADF24D4F64EFULL;


printf("Please, mail your CV to %8.8s@grupopie.com\n", (char*)&h);

	getchar();

return 0;
}

Estás a dizer que tenho que mudar o tipo que devolve a função, certo?

Ou seja uint32_t sort(const void *x, const void *y) 

[pmg 86]

Nao! A funcao tem que ter o prototipo "int foo(const void *, const void *);" senao pode dar faisca com o "qsort".

O que tens a fazer e nao misturar alhos com bugalhos ... OH! ... nao misturar numeros "signed" e "unsigned".

int sort(const void *x, const void *y) {
  const uint32_t *xx = x;
  const uint32_t *yy = y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}

[soniculture 0]

Exacto

Aquela ciclo para dividir o array a meio era pq a ordenação estava partida.

funciona direitinho!

Obrigado

[cffm 0]

Boas

Estava a tentar resolver com base no que foi dito pelo @pmg mas dá-me erro na conversão const void*' to const uint32_t*

O que será?

int sort(const void *x, const void *y) {
  const uint32_t *xx = x;
  const uint32_t *yy = y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}

Agradeço a ajuda!

[pmg 86]

A linguagem C++ e diferente da linguagem C. O meu codigo foi feito em C, mais propriamente C99.

Para funcionar em C++ precisa de ser convertido ... e eu nao sei C++

Experimenta assim

int sort(const void *x, const void *y) {
  const uint32_t *xx = (const uint32_t *)x;
  const uint32_t *yy = (const uint32_t *)y;
  if (*xx < *yy) return -1;
  if (*xx > *yy) return 1;
  return 0;
}

[cffm 0]

Boas

Obrigado pela ajuda. Eu também apenas sei C e C#, mas gostava de resolver isto em C++ porque estou a tentar batalhar um bocado nesta linguagem. Vou ver se consigo por a funcionar em C++.

Mais uma vez obrigado.