Générateur de séquences Karel J. AlphaBot

Les scores

Cette section sera remplie au fur et à mesure de la soumission des soumissions.

Ordinaire

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

Bonus Round

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

Karel J. AlphaBot

Contexte

Un cours d'introduction populaire à Java est Karel J. Robot (je l'utilise moi-même). Le robot interagit avec une grille de rues (coordonnées entières positives y) et d'avenues (coordonnées x entières positives) ainsi que des bips sonores, qui peuvent être placés et stockés sur la grille (notez que Karel et tous les bips sonores ne peuvent exister que sur un treillis points). Karel (le robot) ne doit effectuer que cinq actions: avancer de 1, tourner à gauche en place, poser un bip, prendre un bip et s'éteindre.

Dans mon cours d'informatique, l'une de nos premières tâches a été de programmer Karel pour apprendre à tourner à droite, à faire demi-tour et à effectuer l'action combinée d'avancer de 1 et de poser un bip. Quelques jours plus tard, une tâche consistait à utiliser ces méthodes et à écrire de nouvelles méthodes pour produire des lettres de l'alphabet.

Naturellement, une fois cette tâche terminée, j'ai écrit plus de méthodes pour créer chaque lettre de l'alphabet, ainsi que les dix chiffres numériques, et je prévois de comprendre comment faire une sorte de traitement de texte à partir du robot, où une chaîne serait entré dans STDIN et le robot placerait des bips sur la grille d'une manière qui ressemblerait aux lettres.

Chaque fois que j'écrivais private void draw#pour chaque personnage #, j'ajoutais un commentaire qui me disait des abréviations pour la séquence de commandes dont j'avais besoin.

J'ai les commandes suivantes (écrites en pseudocode) à ma disposition (clarification - ce sont les seules commandes utiles ).

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"

Conditions

Le robot doit procéder dans l'ordre suivant.

Le robot démarre dans le coin inférieur gauche du rectangle 5xN de la zone minimale dans laquelle la lettre sera dessinée.
Le robot dessine la lettre.
Le robot se déplace vers le coin inférieur droit du rectangle.
Le robot se déplace de deux espaces vers la droite et doit faire face au nord / haut

Voyons un exemple. Supposons que nous voulons dessiner A. L'emplacement du robot est la lettre qui indique sa direction (nord, sud, est, ouest). La lettre est en majuscule si le robot est sur place avec un bip et en minuscule si le robot est sur place sans bip. oreprésente des taches avec des bips et .représente des taches sans bips.

Comme nous le verrons plus tard, Aest-ce.

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

Voici une solution possible.

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

La finale mmlpour compléter la quatrième puce est implicite car elle apparaît dans chaque lettre et parce que je ne veux pas revenir en arrière et ajouter deux autres colonnes à tout dans la solution proposée ci-dessus.

Ainsi, une solution à faire Aest pddrdddammmrdmrdddmrddddlmml.

Notez que cela ne doit pas être votre solution. Votre algorithme peut parcourir toutes les colonnes, en plaçant les bips aux bons endroits et sans se fier à l'endroit où d'autres bips ont été placés ou seront placés. Quel que soit votre algorithme, le robot ne peut placer qu'un seul bip par espace sur la grille.

Le programme

Votre programme prendra en entrée une grille 5xN de la grille de la lettre. Notez qu'il n'y a pas de robot sur l'entrée; le robot est supposé être dans le coin inférieur gauche (sud-ouest), face au nord.

La sortie sera la séquence de lettres qui est le raccourci de la séquence.

Exemples d'entrées

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

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

Exemples de sorties

pddrdddammmrdmrdddmrddddlmml

prmmmlmlmmdrdrdddlmlmmdrdrmmmdrddddlmmlprdddlmldmmrmrmdmlmldmmrdrddddrmmmdlmml

C'est du golf de code, les gars. Les règles CG standard s'appliquent. Le code le plus court en octets gagne.

Bonus Round

Règles

Si vous souhaitez participer au tour de bonus, assurez-vous de rendre vos codes efficaces en mouvement! Vous trouverez ci-dessous une bibliothèque de toutes les lettres 5x5 que mon programme crée lors de son exécution. L'objectif du tour de bonus est d'écrire un programme qui imprime une séquence ABCDEFGHIJKLMNOPQRSTUVWXYZcontenant le moins de coups possible. Il n'y a aucune entrée dans STDIN. Le code sera évalué non pas sur la longueur du code mais sur son "score de déplacement". Le score de déplacement est conçu pour décourager les algorithmes de balayage qui visitent chaque point du rectangle.

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

Des lettres

.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

La même procédure que le défi d'origine doit être suivie: les lettres doivent être dessinées une à la fois avec une séparation d'espace entre chaque lettre.

Les règles CG standard s'appliquent. L'entrée avec le score de coup le plus bas gagne.

Pour résumer, les deux codes feront essentiellement les mêmes choses. Le premier code doit avoir un nombre minimal d'octets dans le code, et le second code doit utiliser le plus petit nombre de mouvements.

code-golf Arcturus
la source

Beau défi - aucune idée de la raison pour laquelle vous obtenez un vote négatif.

Deusovi

Merci @Deusovi. J'aimerais qu'ils expliquent pourquoi afin que je puisse clarifier tout ce qui n'a pas de sens ou l'améliorer.

Arcturus

" Karel (le robot) ne doit effectuer que cinq actions ": je pense qu'il vous manque " capable ", et il vous manque définitivement la cinquième action. Et je ne sais pas de quoi parle le bonus: allez-vous attribuer une prime à la personne qui écrit la meilleure solution?

Peter Taylor

Peut-être qu'au lieu d'un défi de golf de code le changer en un défi de golf à mouvement minimal? Puisqu'il s'agit d'efficacité.

LukStorms

Un défi de mouvement minimal avec un ensemble limité de mouvements n'est pas si intéressant sans la partie golf de code. Il devrait être assez facile de BFS le chemin optimal.

bopjesvla

Réponses:

perl -p0, 60 56 54 + 2 octets

le golf

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

Remarques

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

bopjesvla
la source

Une bonne utilisation de @-, pourrait être utile à partager sur les conseils pour jouer au golf en Perl !

Dom Hastings

JavaScript (ES6), 91

Un premier essai du défi de base.

Testez l'exécution de l'extrait ci-dessous dans un navigateur compatible EcmaScript 6 (testé dans Firefox)

Afficher l'extrait de code

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

Développer l'extrait

BONUS CHALLENGE REPONSE - Score pour l'alphabet complet = 869

Testez l'exécution du wnippet ci-dessous dans Firefox (meilleur plein écran)

Comme je n'aime pas les défis d' entrée fixe / sortie fixe , vous pouvez essayer votre entrée. N'oubliez pas que seules les lettres seront imprimées.

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

Développer l'extrait

edc65
la source

Comment va le bonus?

Arcturus

@Eridan le bonus se passe bien. Malheureusement, j'ai aussi un travail ... :)

edc65

D'accord! Je ne te blâme pas. Vous êtes le seul à avoir tenté le bonus.

Arcturus du