Karel J. AlphaBot Sequence Generator

Wyniki

Ta sekcja zostanie wypełniona po wprowadzeniu zgłoszeń.

Normalna

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

Runda bonusowa

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

Karel J. AlphaBot

tło

Popularnym kursem wprowadzającym do Javy jest Karel J. Robot (używam go osobiście). Robot wchodzi w interakcję z siatką ulic (dodatnie współrzędne Y) i alei (dodatnie współrzędne X), a także sygnałów dźwiękowych, które można umieszczać i przechowywać na siatce (zwróć uwagę, że Karel i wszelkie sygnały dźwiękowe mogą istnieć tylko na siatce zwrotnica). Karel (robot) wykonuje tylko pięć czynności: przesuń się o 1 do przodu, skręć w lewo na miejscu, odłóż sygnał dźwiękowy, podnieś dźwięk i wyłącz się.

Na moich zajęciach z informatyki jednym z naszych pierwszych zadań było zaprogramowanie Karela, aby nauczył się, jak skręcać w prawo, zawracać i wykonywać połączoną akcję przesuwania się do przodu o 1 i odkładania sygnału dźwiękowego. Kilka dni później zadaniem było wykorzystanie tych metod i napisanie nowych metod do tworzenia liter alfabetu.

Oczywiście po zakończeniu tego zadania napisałem więcej metod tworzenia każdej litery alfabetu, a także dziesięciu cyfr, i planuję wymyślić, jak zrobić z robota swego rodzaju edytor tekstu, w którym ciąg znaków zostanie wprowadzony do STDIN, a robot umieści brzęczyk na siatce w sposób przypominający litery.

Za każdym razem, gdy pisałem private void draw#dla każdej postaci #, dodawałem po niej komentarz, który wskazywałby mi skróty do sekwencji poleceń, których potrzebuję.

Mam do dyspozycji następujące polecenia (zapisane w pseudokodzie) (wyjaśnienie - są to jedyne przydatne polecenia).

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"

Warunki

Robot musi postępować w następującej kolejności.

Robot rozpoczyna się w lewym dolnym rogu prostokąta 5xN o minimalnej powierzchni, do której zostanie narysowana litera.
Robot rysuje literę.
Robot przesuwa się do prawego dolnego rogu prostokąta.
Robot przesuwa się o dwa pola w prawo i musi być skierowany na północ / w górę

Przeanalizujmy przykład. Załóżmy, że chcemy rysować A. Lokalizacją robota jest litera wskazująca jego kierunek (północ, południe, wschód, zachód). Litera jest pisana wielkimi literami, jeśli robot znajduje się w miejscu z sygnałem dźwiękowym, a małe litery, jeśli robot znajduje się w miejscu bez sygnału dźwiękowego. oreprezentuje plamy z sygnałami dźwiękowymi i .reprezentuje plamy bez sygnałów dźwiękowych.

Jak zobaczymy później, Ajest to.

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

Oto jedno z możliwych rozwiązań.

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

Ostateczne mmluzupełnienie czwartego punktu jest niejawne, ponieważ pojawia się w każdej liście i ponieważ nie chcę wracać i dodawać kolejnych dwóch kolumn do wszystkiego w powyższym proponowanym rozwiązaniu.

Tak więc jednym rozwiązaniem Ajest pddrdddammmrdmrdddmrddddlmml.

Pamiętaj, że to nie musi być twoje rozwiązanie. Twój algorytm może przechodzić przez każdą kolumnę, umieszczając sygnały dźwiękowe w odpowiednich miejscach i nie polegając na tym, gdzie zostały umieszczone lub zostaną umieszczone inne sygnały dźwiękowe. Bez względu na algorytm, robot może umieścić tylko jeden sygnał dźwiękowy na pole na siatce.

Program

Twój program weźmie na wejściu siatkę 5xN tego, co jest siatką dla litery. Zauważ, że na wejściu nie ma robota; zakłada się, że robot znajduje się w lewym dolnym (południowo-zachodnim) rogu, twarzą na północ.

Wynikiem będzie ciąg liter, który jest skrótem dla sekwencji.

Przykładowe dane wejściowe

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

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

Przykładowe wyniki

pddrdddammmrdmrdddmrddddlmml

prmmmlmlmmdrdrdddlmlmmdrdrmmmdrddddlmmlprdddlmldmmrmrmdmlmldmmrdrddddrmmmdlmml

To jest golf golfowy, chłopaki. Obowiązują standardowe zasady CG. Najkrótszy kod w bajtach wygrywa.

Runda bonusowa

Zasady

Jeśli chcesz wziąć udział w rundzie bonusowej, upewnij się, że Twoje kody działają sprawnie! Poniżej znajduje się biblioteka wszystkich 5 x 5 liter, które mój program tworzy podczas działania. Celem rundy bonusowej jest napisanie programu, który wypisze sekwencję ABCDEFGHIJKLMNOPQRSTUVWXYZzawierającą jak najmniej ruchów. Brak danych wejściowych do STDIN. Kod będzie oceniany nie według długości kodu, ale według „wyniku ruchu”. Wynik ruchu ma na celu zniechęcenie algorytmów wymiatających, które odwiedzają każdy punkt prostokąta.

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

Listy

.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

Należy postępować zgodnie z tą samą procedurą, co w przypadku oryginalnego wyzwania: litery należy rysować pojedynczo, z odstępem między literami.

Obowiązują standardowe zasady CG. Wpis o najniższym wyniku ruchu wygrywa.

Podsumowując, oba kody będą zasadniczo wykonywać te same czynności. Pierwszy kod powinien zawierać minimalną liczbę bajtów w kodzie, a drugi kod powinien wykorzystywać najmniejszą liczbę ruchów.

code-golf Arktur
źródło

Zgrabne wyzwanie - nie mam pojęcia, dlaczego jesteś przegłosowany.

Deusovi

Dzięki @Deusovi. Chciałbym, żeby wyjaśnili, dlaczego, więc mogę wyjaśnić wszystko, co nie ma sensu, lub poprawić.

Arcturus

„ Karel (robot) wykonuje tylko pięć akcji ”: Myślę, że brakuje ci „ zdolności ” i zdecydowanie brakuje ci piątej akcji. I nie jestem pewien, na czym polega runda bonusowa: czy przyznasz nagrodę osobie, która napisze najlepsze rozwiązanie?

Peter Taylor

Być może zamiast wyzwania golfa kodowego zmień je na wyzwanie golfa z minimalnym ruchem? Ponieważ chodzi o wydajność.

LukStorms

Minimalne wyzwanie ruchowe z ograniczonym zestawem ruchów nie jest tak interesujące bez części golfowej. Optymalna ścieżka BFS powinna być łatwa.

bopjesvla

Odpowiedzi:

perl -p0, 60 56 54 + 2 bajty

golf

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

notatki

/\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
źródło

Przyjemne użycie @-, może być przydatne, aby podzielić się wskazówkami na temat gry w golfa w pytaniu Perl !

Dom Hastings,

JavaScript (ES6), 91

Pierwsza próba podstawowego wyzwania.

Przetestuj poniższy fragment kodu w przeglądarce zgodnej z EcmaScript 6 (testowany w przeglądarce Firefox)

Pokaż fragment kodu

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

Rozwiń fragment kodu

BONUS CHALLENGE ANSWER - Wynik dla pełnego alfabetu = 869

Przetestuj uruchomienie poniższego kodu w przeglądarce Firefox (lepszy pełny ekran)

Ponieważ nie lubię problemów ze stałym wejściem / wyjściem , możesz spróbować swoich danych wejściowych. Pamiętaj tylko, że zostaną wydrukowane tylko litery.

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

Rozwiń fragment kodu

edc65
źródło

Jak idzie bonus?

Arcturus,

@Eridan bonus idzie dobrze. Niestety mam też pracę ... :)

edc65,

Dobrze! Nie winię cię. Tylko ty próbowałeś bonusu.

Arcturus