Karel J. AlphaBot-Sequenzgenerator

Scores

Dieser Abschnitt wird ausgefüllt, sobald Beiträge eingereicht wurden.

Normal

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

Bonusrunde

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

Karel J. AlphaBot

Hintergrund

Ein beliebter Einführungskurs in Java ist Karel J. Robot (ich benutze es selbst). Der Roboter interagiert mit einem Raster von Straßen (positive ganzzahlige y-Koordinaten) und Alleen (positive ganzzahlige x-Koordinaten) sowie mit Signaltönen, die auf dem Raster platziert und gespeichert werden können (beachten Sie, dass Karel und alle Signaltöne nur in Gittern existieren können Punkte). Karel (der Roboter) darf nur fünf Aktionen ausführen: um 1 vorwärts gehen, nach links abbiegen, einen Piepser abstellen, einen Piepser aufheben und sich selbst ausschalten.

In meiner Informatik-Klasse bestand eine unserer ersten Aufgaben darin, Karel so zu programmieren, dass er lernt, wie man nach rechts dreht, sich umdreht und die kombinierte Aktion ausführt, um 1 vorwärts zu gehen und einen Piepser abzustellen. Einige Tage später bestand die Aufgabe darin, diese Methoden zu verwenden und neue Methoden zu schreiben, um Buchstaben des Alphabets zu erzeugen.

Natürlich habe ich nach Abschluss dieser Aufgabe mehr Methoden geschrieben, um jeden Buchstaben des Alphabets sowie die zehn numerischen Ziffern zu erstellen, und ich habe vor, herauszufinden, wie man aus dem Roboter eine Art Textverarbeitungsprogramm mit einer Zeichenfolge erstellt würde in STDIN eingegeben und der Roboter würde Piepser auf eine Art und Weise auf das Gitter legen, die den Buchstaben ähnelte.

Jedes Mal, wenn ich private void draw#für ein Zeichen schrieb #, fügte ich einen Kommentar hinzu, der Abkürzungen für die Befehlsfolge enthielt, die ich benötigte.

Ich habe die folgenden Befehle (in Pseudocode geschrieben) zur Verfügung (Klarstellung - dies sind die einzigen nützlichen Befehle).

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"

Bedingungen

Der Roboter muss in der folgenden Reihenfolge vorgehen.

Der Roboter startet in der unteren linken Ecke des 5xN-Rechtecks mit der minimalen Fläche, in die der Buchstabe gezeichnet wird.
Der Roboter zeichnet den Brief.
Der Roboter bewegt sich in die untere rechte Ecke des Rechtecks.
Der Roboter bewegt sich zwei Felder nach rechts und muss nach Norden / oben zeigen

Lassen Sie uns ein Beispiel durcharbeiten. Angenommen, wir möchten zeichnen A. Der Standort des Roboters ist der Buchstabe, der seine Richtung angibt (Norden, Süden, Osten, Westen). Der Buchstabe wird in Großbuchstaben geschrieben, wenn sich der Roboter an einem Ort mit einem Piepser befindet, und in Kleinbuchstaben, wenn sich der Roboter an einem Ort ohne Piepser befindet. oStellt Spots mit Pieptönen dar und Stellt .Spots ohne Pieptöne dar.

Wie wir später sehen werden, Aist dies.

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

Hier ist eine mögliche Lösung.

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

Das endgültige mmlAusfüllen des vierten Aufzählungszeichens ist implizit, weil es in jedem Buchstaben vorkommt und weil ich nicht noch einmal zwei Spalten zu allem in der oben vorgeschlagenen Lösung hinzufügen möchte.

So eine Lösung zu machen Aist pddrdddammmrdmrdddmrddddlmml.

Beachten Sie, dass dies nicht Ihre Lösung sein muss. Ihr Algorithmus kann jede Spalte durchgehen, indem er die Piepser an den richtigen Stellen platziert und sich nicht darauf verlässt, wo andere Piepser platziert wurden oder platziert werden. Unabhängig von Ihrem Algorithmus kann der Roboter nur einen Piepser pro Feld auf dem Gitter platzieren.

Das Programm

Ihr Programm verwendet als Eingabe ein 5xN-Raster des Rasters für den Buchstaben. Beachten Sie, dass am Eingang kein Roboter vorhanden ist. Es wird angenommen, dass sich der Roboter in der unteren linken Ecke (Südwesten) in Richtung Norden befindet.

Die Ausgabe ist die Folge von Buchstaben, die die Abkürzung für die Folge sind.

Beispieleingaben

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

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

Beispielausgaben

pddrdddammmrdmrdddmrddddlmml

prmmmlmlmmdrdrdddlmlmmdrdrmmmdrddddlmmlprdddlmldmmrmrmdmlmldmmrdrddddrmmmdlmml

Das ist Codegolf, Jungs. Es gelten die Standard-CG-Regeln. Kürzester Code in Bytes gewinnt.

Bonusrunde

Regeln

Wenn Sie an der Bonusrunde teilnehmen möchten, sorgen Sie dafür, dass sich Ihre Codes effizient bewegen! Unten finden Sie eine Bibliothek mit allen 5x5-Buchstaben, die mein Programm erstellt, wenn es ausgeführt wird. Ziel der Bonusrunde ist es, ein Programm zu schreiben, das eine Sequenz druckt ABCDEFGHIJKLMNOPQRSTUVWXYZ, die so wenig Züge wie möglich enthält. Es erfolgt keine Eingabe in STDIN. Der Code wird nicht nach der Länge des Codes, sondern nach seiner "Bewegungsbewertung" bewertet . Die Bewegungsbewertung soll Sweeper-Algorithmen verhindern, die jeden Punkt im Rechteck aufsuchen.

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

Briefe

.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

Das gleiche Verfahren wie bei der ursprünglichen Herausforderung muss angewendet werden: Buchstaben müssen nacheinander mit einem Leerzeichen zwischen den Buchstaben gezeichnet werden.

Es gelten die Standard-CG-Regeln. Der Eintrag mit der niedrigsten Zugpunktzahl gewinnt.

Zusammenfassend wird gesagt, dass beide Codes im Wesentlichen die gleichen Aktionen ausführen. Der erste Code sollte eine minimale Anzahl von Bytes im Code haben, und der zweite Code sollte die geringste Anzahl von Zügen verwenden.

code-golf Arcturus
quelle

Ordentliche Herausforderung - keine Ahnung, warum Sie schlecht bewertet werden.

Deusovi

Vielen Dank @Deusovi. Ich wünschte, sie würden erklären, warum, damit ich alles klären kann, was keinen Sinn ergibt oder es verbessert.

Arcturus

" Karel (der Roboter) soll nur fünf Aktionen ausführen ": Ich denke, Sie vermissen " fähig ", und Sie vermissen definitiv die fünfte Aktion. Und ich bin mir nicht sicher, worum es in der Bonusrunde geht: Werden Sie der Person, die die beste Lösung schreibt, eine Prämie gewähren?

Peter Taylor

Vielleicht anstelle einer Code-Golf-Herausforderung in eine Golf-Herausforderung mit minimalem Move ändern? Da geht es um Effizienz.

LukStorms

Eine minimale Zugherausforderung mit einer begrenzten Anzahl von Zügen ist ohne den Codegolf-Teil nicht so interessant. Es sollte ziemlich einfach sein, BFS auf den optimalen Weg zu bringen.

Bopjesvla

Antworten:

Perl -p0, 60 56 54 + 2 Bytes

Golf

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

Anmerkungen

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

Nizza Gebrauch @-, könnte eine nützliche sein, um auf die Tipps für das Golfen in Perl Frage zu teilen !

Dom Hastings

JavaScript (ES6), 91

Ein erster Versuch zur grundlegenden Herausforderung.

Testlauf des folgenden Snippets in einem EcmaScript 6-kompatiblen Browser (getestet in Firefox)

Code-Snippet anzeigen

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

Erweitern Sie das Snippet

BONUS-HERAUSFORDERUNGS-ANTWORT - Ergebnis für vollständiges Alphabet = 869

Teste das wnippet unten in Firefox (besserer Vollbildmodus)

Da ich keine Fixed-Input- / Fixed-Output- Herausforderungen mag , können Sie Ihre Eingabe ausprobieren. Denken Sie daran, dass nur Buchstaben gedruckt werden.

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

Erweitern Sie das Snippet

edc65
quelle

Wie läuft der Bonus?

Arcturus

@Eridan der Bonus läuft gut. Leider habe ich auch einen Job ... :)

edc65

In Ordnung! Ich beschuldige dich nicht. Du bist der einzige, der den Bonus versucht hat.

Arcturus