Pontuações

Esta seção será preenchida quando os envios forem inseridos.

Normal

1. bopjesvla    Perl                54
2. edc65        Javascript (ES6)    91
3. name         language            score
4. name         language            score
5. name         language            score

Rodada de Bônus

1. name   language   score
2. name   language   score
3. name   language   score
4. name   language   score
5. name   language   score

Karel J. AlphaBot

fundo

Um curso introdutório popular para Java é Karel J. Robot (eu mesmo estou usando). O robô interage com uma grade de ruas (coordenadas inteiras positivas em y) e avenidas (coordenadas inteiras positivas com x), além de bipes, que podem ser colocados e armazenados na grade (observe que Karel e quaisquer bipes só podem existir na rede pontos). Karel (o robô) deve executar apenas cinco ações: avançar 1, virar à esquerda no lugar, pousar um sinal sonoro, pegar um sinal sonoro e desligar-se.

Na minha aula de Ciência da Computação, uma de nossas primeiras tarefas foi programar Karel para aprender a virar à direita, dar a volta e executar a ação combinada de avançar por 1 e soltar um sinal sonoro. Uma tarefa alguns dias depois era usar esses métodos e escrever novos métodos para produzir letras do alfabeto.

Naturalmente, depois que terminei essa tarefa, escrevi mais métodos para criar todas as letras do alfabeto, além dos dez dígitos numéricos, e planejo descobrir como criar uma espécie de processador de texto no robô, onde uma string seriam inseridos no STDIN e o robô colocaria sinais sonoros na grade de maneira que se parecesse com as letras.

Toda vez que escrevia private void draw#para cada personagem #, adicionava um comentário que dizia abreviações para a sequência de comandos que eu precisava.

Tenho os seguintes comandos (escritos em pseudocódigo) à minha disposição (esclarecimento - estes são os únicos comandos úteis ).

Turn Left
    Rotate the robot 90˚ counterclockwise
    Abbreviated as "l"

Turn Right
    Rotate the robot 90˚ clockwise
    Abbreviated as "r"

Move
    Move one space forwards
    Abbreviated as "m"

Put Beeper
    Put a beeper on the spot that Karel is on
    Abbreviated as "p"

Drop Beeper
    Move, then Put Beeper
    Abbreviated as "d"

Turn Around
    Turn Left, then Turn Left
    Abbreviated as "a"

Condições

O robô deve prosseguir na seguinte ordem.

• O robô inicia no canto inferior esquerdo do retângulo 5xN da área mínima em que a letra será desenhada.
• O robô desenha a letra.
• O robô se move para o canto inferior direito do retângulo.
• O robô move dois espaços para a direita e deve ficar voltado para o norte / para cima

Vamos trabalhar com um exemplo. Suponha que queremos desenhar A. A localização do robô é a letra que indica sua direção (norte, sul, leste, oeste). A letra é maiúscula se o robô estiver em um local com um sinal sonoro e minúscula se o robô estiver em um local sem um sinal sonoro. orepresenta pontos com sinais sonoros e .representa pontos sem sinais sonoros.

Como veremos mais adiante, Aé isso.

.ooo.
o...o
ooooo
o...o
o...o

Aqui está uma solução possível.

Grids   .....   .....   .....   .....   .....   .....   .....   .....   .....
        .....   .....   .....   .....   .....   .....   .....   .....   .....
        .....   .....   .....   N....   E....   oE...   ooE..   oooE.   oooW.
        .....   .....   N....   o....   o....   o....   o....   o....   o....
        n....   N....   o....   o....   o....   o....   o....   o....   o....

Letters           p       d       d       r       d       d       d       a

        .....   .....   .....   .....   .....   n....   e....   .E...   .oE..
        .....   .....   .....   .....   N....   o....   o....   o....   o....
        ooWo.   oWoo.   Wooo.   Nooo.   oooo.   oooo.   oooo.   oooo.   oooo.
        o....   o....   o....   o....   o....   o....   o....   o....   o....
        o....   o....   o....   o....   o....   o....   o....   o....   o....

          m       m       m       r       d       m       r       d       d

        .ooE.   .oooe   .ooos   .ooo.   .ooo.   .ooo.   .ooo.   .ooo.
        o....   o....   o....   o...S   o...o   o...o   o...o   o...o
        oooo.   oooo.   oooo.   oooo.   ooooS   ooooo   ooooo   ooooo
        o....   o....   o....   o....   o....   o...S   o...o   o...o
        o....   o....   o....   o....   o....   o....   o...S   o...E

          d       m       r       d       d       d       d       l

A final mmlpara completar o quarto marcador está implícita porque aparece em todas as letras e porque não quero voltar e adicionar mais duas colunas a tudo na solução proposta acima.

Assim, uma solução a fazer Aé pddrdddammmrdmrdddmrddddlmml.

Observe que essa não precisa ser sua solução. Seu algoritmo pode percorrer todas as colunas, colocando os bipes nos locais apropriados e sem depender de onde outros bipes foram colocados ou serão colocados. Não importa qual seja o seu algoritmo, o robô pode colocar apenas um sinal sonoro por espaço na grade.

O programa

Seu programa terá como entrada uma grade 5xN do que é a grade da letra. Observe que não há robô na entrada; presume-se que o robô esteja no canto inferior esquerdo (sudoeste), voltado para o norte.

A saída será a sequência de letras que é a abreviação da sequência.

Entradas de Amostra

.ooo.
o...o
ooooo
o...o
o...o

o...o.ooooo
o...o...o..
ooooo...o..
o...o...o..
o...o.ooooo

Saídas de amostra

pddrdddammmrdmrdddmrddddlmml

prmmmlmlmmdrdrdddlmlmmdrdrmmmdrddddlmmlprdddlmldmmrmrmdmlmldmmrdrddddrmmmdlmml

Isso é código de golfe, pessoal. Aplicam-se as regras padrão de CG. O código mais curto em bytes vence.

Rodada de Bônus

Regras

Se você quiser participar da rodada de bônus, certifique-se de tornar seus códigos eficientes em termos de movimento! Abaixo está uma biblioteca de todas as letras 5x5 que meu programa cria quando é executado. O objetivo da rodada de bônus é escrever um programa que imprima uma sequência ABCDEFGHIJKLMNOPQRSTUVWXYZque contenha o mínimo de movimentos possível. Não há entrada para STDIN. O código será classificado não no tamanho do código, mas em sua "pontuação de movimentação". A pontuação do movimento foi projetada para desencorajar os algoritmos de varredura que visitam todos os pontos do retângulo.

d: 1
l: 1
m: 4
p: 1
r: 1

Cartas

.ooo.   oooo.   ooooo   oooo.   ooooo   ooooo   .oooo   o...o
o...o   o...o   o....   o...o   o....   o....   o....   o...o
ooooo   oooo.   o....   o...o   oooo    oooo.   o.ooo   ooooo
o...o   o...o   o....   o...o   o....   o....   o...o   o...o
o...o   oooo.   ooooo   oooo.   ooooo   o....   oooo.   o...o

ooooo   ....o   o...o   o....   ooooo   o...o   ooooo   oooo.
..o..   ....o   o..o.   o....   o.o.o   oo..o   o...o   o...o
..o..   ....o   oo...   o....   o.o.o   o.o.o   o...o   oooo.
..o..   o...o   o..o.   o....   o...o   o..oo   o...o   o....
ooooo   .ooo.   o...o   ooooo   o...o   o...o   ooooo   o....

oooo.   oooo.   ooooo   ooooo   o...o   o...o   o...o   o...o
o..o.   o...o   o....   ..o..   o...o   o...o   o...o   .o.o.
o..o.   oooo.   ooooo   ..o..   o...o   .o.o.   o.o.o   ..o..
oooo.   o..o.   ....o   ..o..   o...o   .o.o.   o.o.o   .o.o.
....o   o...o   ooooo   ..o..   ooooo   ..o..   ooooo   o...o

o...o   ooooo
.o.o.   ...o.
..o..   ..o..
.o...   .o...
o....   ooooo

O mesmo procedimento que o desafio original deve ser seguido: as letras devem ser desenhadas uma de cada vez com uma separação de espaço entre cada letra.

Aplicam-se as regras padrão de CG. A entrada com a menor pontuação de movimento vence.

Para resumir, ambos os códigos farão essencialmente as mesmas coisas. O primeiro código deve ter um número mínimo de bytes no código e o segundo código deve usar o menor número de movimentos.

perl -p0, 60 56 54 + 2 bytes

golfe

/
/;$:="m"x"@-";$_=mmmmlma.s/
/rmr$:a/gr.mml;y/.o/md/;

notas

/\n/; # capture the length of the first line
$:="m"x"@-"; # assign a string of m's with that length to $:
s/^/mmmmlmll/; # move to the starting position (-1,0)
s/\n/rmr$:rr/g; # replace all newlines with kareliage returns
y/.o/md/; # replace dots with moves and o's with drops
s/$/mml/; # append mml

JavaScript (ES6), 91

Uma primeira tentativa para o desafio básico.

Teste a execução do snippet abaixo em um navegador compatível com EcmaScript 6 (testado no Firefox)

// BASIC CHALLENGE ANSWER

f=s=>`mmmmr${[...s].map(c=>c<' '?[`mrmr${b}a`,b=m][0]:(b+=m,c>m?'pm':m),b=m='m').join``}ml`

/* ALSO ...
f=s=>`mmmmr${s.replace(/.|\s/g,c=>c<' '?[`mrmr${b}a`,b=m][0]:(b+=m,c>m?'pm':m),b=m='m')}ml`
*/


// TEST
// now, I need to implement Karel (and test it) to do a significant test
// (a super limited version of Karel, of course. Just what is needed)

Karel=(cmd, width, height) =>  // even if for this test we have a limited height to handle
{ 
  var grid = [...('.'.repeat(width)+'\n').repeat(height)],
  o = width+1,
  p = o*(height-2)+1,
  d = [-o, 1, o, -1], // direction offsets
  q = 0, // face up
  s = [...grid],    
  steps = [];

  s[p] = 'n';
  steps.push([s.join``,'-']);
  
  [...cmd].forEach(c => 
    (
      c == 'l' ? q = q-1 &3
      : c == 'r' ? q = q+1 &3
      : c == 'a' ? q = q+2 &3
      : c == 'm' ? p += d[q]
      : c == 'p' ? grid[p] = 'o'
      : c == 'd' ? grid[p += d[q]] = 'o'
      : 0,
      s = [...grid],  
      s[p] = s[p] == 'o' ? 'NESW'[q] : 'nesw'[q],
      steps.push([s.join``,c])
    )
  )
  return [s.join``,steps]
}  
function go(cmd)
{
  var result = Karel(cmd,260,7)
  RESULT.innerHTML = result[0];
  STEPS.innerHTML = 'Steps:<br>'+result[1].map(x=>'<pre>'+x.join('\n')+'</pre>').join('')
}
function test(input)
{
  var exp = input.innerHTML;
  var cmd = f(exp);
  var result = Karel(cmd,20,7)
  CMD.innerHTML = cmd;
  RESULT.innerHTML = result[0];
  STEPS.innerHTML = 'Steps:<br>'+result[1].map(x=>'<pre>'+x.join('\n')+'</pre>').join('')
}

pre {
  float: left;
  border: 1px solid #888;
  margin: 2px
}

div {
  clear: both;
}

#CMD {
  word-break: break-all;
  white-space: normal;
  width:50%;
  overflow:auto;
}

#Y {
  width:50%;
}

Test cases (click to run a test)<br>
<pre id=T1 onclick='test(this)'>.ooo.
o...o
ooooo
o...o
o...o</pre>
<pre id=T2 onclick='test(this)'>o...o.ooooo
o...o...o..
ooooo...o..
o...o...o..
o...o.ooooo</pre>
<div>Command string:<br><pre id=CMD></pre></div>
<div>
Your Command:<br><input id=Y><button onclick='go(Y.value)'>-></button>
</div>  
<div>Result:<br><pre id=RESULT></pre></div>
<div id=STEPS>Steps</div>

RESPOSTA DO DESAFIO DE BÔNUS - Pontuação para o alfabeto completo = 869

Teste a execução do wnippet abaixo no Firefox (melhor tela cheia)

Como não gosto de desafios de entrada fixa / saída fixa , você pode tentar sua entrada. Lembre-se, apenas as letras serão impressas.

// Optimal - working on small pattern but too slow (scale bad)
// So I build the total command letter by letter - that surely is NOT globally optimal

Key=sol=>sol.pos+' '+sol.setBits

Solve=(target, startRow, startDir, cmd)=>{
  // Target is a rectangle string 5x5, newline separated for total (5+1)*5 chars
  if (target[target.length-1] != '\n') target += '\n';
  
  var T = ~new Date()
  var width = 5, height = 5, startPos = (width+1)*startRow;
  var offset = [-width-1, 1, width+1, -1];
  var turns = [ "", "r", "rr", "l" ];
  var cmds = [ "m", "rm", "rrm", "lm", "d", "rd", "rrd", "ld" ];
  var visited = {}, scan =[[],[],[],[],[],[],[],[]], cscan;
  
  var baseSol = { steps:[], pos: startPos, dir: startDir, setBits: 0};
  var score = 0, j = 0
  var bit, key, turn, curSol, move, result
  var targetBits = 0; 
  [...target].map((c,i)=>targetBits |= ((c=='o')<<i)) // 30 bits
  
  // First step, from outside, set bit in mask if it's set in target
  if (target[startPos]=='o') baseSol.setBits = 1<<startPos;
  console.log(target, targetBits.toString(16))
  visited[Key(baseSol)] = scan[0].push(baseSol);
  

  for (j = 0; j<99; j++)
  {
     cscan = scan[j];
     scan.push([])
     
     // console.log(`T: ${T-~new Date} J: ${j} SC: ${cscan.length}`)
     while (cscan.length > 0)
     {
        baseSol = cscan.pop()
        //console.log('Base', baseSol.dir, baseSol.pos, baseSol.setBits.toString(16), baseSol.steps.length)
        for(turn = 0; turn < 4; turn++)
        {
           // set direction, move and drop if you can
           curSol = {};
           curSol.dir = baseSol.dir + turn & 3;
           curSol.pos = baseSol.pos + offset[curSol.dir];
           // console.log(turn, curSol.dir, curSol.pos)
           if(target[curSol.pos] > ' '
              || curSol.dir == 1 && target[curSol.pos]=='\n'
             ) // if inside grid or on right border facing east
           {
              score = j + (turn == 2 ? 3 : turn == 0 ? 1 : 2);
              bit = 1 << curSol.pos;
              if (targetBits & bit)
                 curSol.setBits = baseSol.setBits | bit, move = 4 | turn;
              else
                 curSol.setBits = baseSol.setBits, score += 3, move = turn;
              if (!visited[key = Key(curSol)]) 
              {
                 curSol.steps = [...baseSol.steps, move] // clone and add
                 // task completed if on  right border and all bits ok
                 if (target[curSol.pos]>' ')
                 { // not on right border, proceed  
                    visited[key] = scan[score].push(curSol)
                 }  
                 else if (curSol.setBits == targetBits)
                 {
                    result = curSol.steps.map(v=>cmds[v]).join``
                    result = (cmd == '' 
                    ? target[startPos]=='o' ? 'p' : '' 
                    : target[startPos]=='o' ? 'd' : 'm') + result;
                    console.log(`T: ${T-~new Date} J: ${j} CMD: ${result}`)
                    return [cmd+result, curSol.pos / (width+1) | 0];
                 }
              }
           }
        }
     }
  }
  // Miserable failure!
  return []
}  

console.log=(...x)=>LOG.innerHTML+=x+'\n';
// TEST
Karel=(cmd, width, height) =>  // even if for this test we have a limited height to handle
{ 
  var grid = [...('.'.repeat(width)+'\n').repeat(height)],
  o = width+1,p = o*(height-2)+1,d = [-o, 1, o, -1], // direction offsets
  steps = [],s = [...grid],q = 0; // face up

  s[p] = 'n';
  steps.push([s.join``,'-']);
  
  [...cmd].forEach(c => 
    (
      c == 'l' ? q = q-1 &3
      : c == 'r' ? q = q+1 &3
      : c == 'a' ? q = q+2 &3
      : c == 'm' ? p += d[q]
      : c == 'p' ? grid[p] = 'o'
      : c == 'd' ? grid[p += d[q]] = 'o'
      : 0,
      s = [...grid],  
      s[p] = s[p] == 'o' ? 'NESW'[q] : 'nesw'[q],
      steps.push([s.join``,c])
    )
  )
  return [s.join``,steps]
}  


var AlphabetMap = `.ooo..oooo..ooooo.oooo..ooooo.ooooo..oooo.o...o.ooooo.....o.o...o.o.....ooooo.o...o.ooooo.oooo..oooo..oooo..ooooo.ooooo.o...o.o...o.o...o.o...o.o...o.ooooo
o...o.o...o.o.....o...o.o.....o.....o.....o...o...o.......o.o..o..o.....o.o.o.oo..o.o...o.o...o.o..o..o...o.o.......o...o...o.o...o.o...o..o.o...o.o.....o.
ooooo.oooo..o.....o...o.oooo..oooo..o.ooo.ooooo...o.......o.oo....o.....o.o.o.o.o.o.o...o.oooo..o..o..oooo..ooooo...o...o...o..o.o..o.o.o...o.....o.....o..
o...o.o...o.o.....o...o.o.....o.....o...o.o...o...o...o...o.o..o..o.....o...o.o..oo.o...o.o.....oooo..o..o......o...o...o...o..o.o..o.o.o..o.o...o.....o...
o...o.oooo..ooooo.oooo..ooooo.o.....oooo..o...o.ooooo..ooo..o...o.ooooo.o...o.o...o.ooooo.o.........o.o...o.ooooo...o...ooooo...o...ooooo.o...o.o.....ooooo`.split('\n')
var LetterMap = [];
var l,row,m;

for (l=0;l<26;l++)
{
  for(m='',row=0;row<5;row++)
    m += AlphabetMap[row].substr(l*6,5)+'\n'
  LetterMap[l]=m;  
}

print=Message=>{
  var Alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  var startRow = 4, cmd=''
  var startDir = 0 // start facing UP
  ;[...Message].forEach(l => (
    [cmd, startRow] = Solve(LetterMap[Alphabet.search(l)], startRow, startDir, cmd),
    startDir = 1, // after each letter will be facing RIGHT
    cmd += '\n' // addin a newline (scoring 0) just for readability
  ))

  if (startRow != 4) 
    cmd += 'mr'+'m'.repeat(4-startRow)+'rr' // on last row and facing up
  else 
    cmd += 'ml' // ...facing up

  // Recalc score
  var score = 0
  ;[...cmd].forEach(c=>score += c=='m'? 4 : c<' '? 0: 1)

  var robot = Karel(cmd.replace(/\n/g,''), 26*7, 7)
  O.innerHTML=cmd+'\nScore:'+score
  R.innerHTML=robot[0]
  RS.innerHTML=robot[1].join`\n`
}  

function test()
{
  var msg = I.value.toUpperCase()
  msg=msg.replace(/[^A-Z]/g,'')
  I.value=msg
  print(I.value)
}

test()

fieldset {
  padding:0;
}

pre {
  margin: 2px;
}

#RS {
  height: 200px;
  width: 50%;
  overflow:auto;
}

#I { width: 50% }

<fieldset ><legend>Message to print</legend>
<input id=I value='ABCDEFGHIJKLMNOPQRSTUVWXYZ'><button onclick='test()'>go</button></fieldset>
<fieldset ><legend>Command Result (newlines added for readability)</legend>
<pre id=O></pre></fieldset>
<fieldset ><legend>Robot output</legend>
<pre id=R></pre></fieldset>
<fieldset ><legend>Robot step by step</legend>
<pre id=RS></pre></fieldset>
<fieldset ><legend>log</legend>
<pre id=LOG></pre></fieldset>