Zeichenkette zur Hilbert-Kurve

27

Lassen Sie uns einige Zeichenfolgen dem 2D-Raum im fraktalen Stil zuordnen. Ihre Aufgabe ist es, eine Hilbert-Kurve zu berechnen und eine Zeichenfolge entlang zu legen.

Die Hilbert-Kurve, Iterationen 1 bis 8

Aufgabe

Die Aufgabe besteht darin, die einzeilige Eingabezeichenfolge entlang einer Hilbert-Kurve zu legen, die groß genug ist, um sie aufzunehmen, aber nicht größer. Versuchen Sie, die Anzahl der Bytes so gering wie möglich zu halten. Das ist doch !

Bedingungen

  • Mit Leerzeichen aufzufüllende Lücken, am Zeilenende ist jedoch kein Auffüllen erforderlich.
  • Der Anfang der Linie sollte in der oberen linken Ecke und das Ende in der unteren linken Ecke sein.
  • Sie können ein Programm oder eine Funktion erstellen.
  • Es könnten einige neue Testfälle auftauchen, also codieren Sie nichts!

Boni

Hinweis: Boni stapeln sich wie folgt: -50% & -20% on 100B= -20% on 50Boder -50% on 80B= 40B.

  • -50% Handelt es sich bei der Eingabe um eine mehrzeilige Zeichenfolge, kehren Sie den Vorgang um, um die ursprüngliche Eingabe zu erstellen. Testfälle für den Bonus: Verwenden Sie einfach die vorhandenen (inklusive der Bonus-Testfälle!)
  • -20% Wenn Sie alle unnötigen Leerzeichen aus der Ausgabe entfernen (z. B. am Ende einer Zeile).
  • -5% Wenn Sie den globalen Namespace nicht verschmutzen (Sie wissen, was ich meine!)

Testfälle

abcdefghijklmn

adef
bchg
 nij
 mlk


The quick brown fox jumps over the lazy dog.

Thn f ju
 ewooxpm
qckr rs 
ui btevo
    hlaz
    e  y
      do
      .g

Und für den Whitespace-Stripping-Bonus:

No  hitespac  her 

Noher

hesc
itpa

Bestenliste

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

# Perl, 43 + 2 (-p flag) = 45 bytes

Sie können den Namen der Sprache auch als Link festlegen, der dann im Leaderboard-Snippet angezeigt wird:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes
wizzwizz4
quelle
Wenn jemand mehr Testfälle machen kann, wäre das sehr dankbar.
Wizzwizz4
Die Zeichen sollten also durch Eckpunkte der Kurve dargestellt werden?
Fehler
No..hitespac..her.Wo die Punkte Leerzeichen sind, wäre ein besserer Testfall für den Bonus. (Und zur Zeit fehlt dem Testfall das Trailing .)
Martin Ender
Wenn Sie sich für das L-System entscheiden, können Sie auch http: // codegolf / questions / 48697 / ascii-l-system-renderer ausprobieren . Es könnte Ihnen helfen, Ihre Antworten auf Golf zu spielen.
wizzwizz4

Antworten:

7

CJam, 119 117 113 112 109 * 0,5 * 0,8 = 43,6 Bytes

Vielen Dank an Dennis für das Speichern von 1 Byte.

Hier ist ein Anfang ...

{+e`W<e~}:F;q_N-,4mLm]0aa{4\#4e!1=f*\:G[zGGW%zW%G].ff+2/{~.+~}%}@:L/\_N&{N/]z:z:~$1f>sS}{4L#' e]f{f=SF}N*N}?F

Testen Sie die Forward-Transformation . Testen Sie die inverse Transformation.

Ich bin sicher, es gibt einen kürzeren Weg, um die Kurve zu erzeugen ...

Erläuterung

Zuerst definiere ich eine Funktion zum Trimmen eines Elements vom Ende eines Arrays, weil ich das an mehreren Stellen brauche. Es erwartet das Array und das Element (innerhalb eines separaten Arrays) oben auf dem Stapel.

{
  +  e# Append the element to the array.
  e` e# Run-length encode.
  W< e# Discard last run.
  e~ e# Run-length decode.
}:F; e# Store in F and discard.

Jetzt bestimmt der Großteil des Codes die Größe der erforderlichen Hilbert-Kurve und erstellt sie als 2D-Array, in dem die Elemente Indizes entlang der Kurve sind. Ich konstruiere dies basierend auf der folgenden Beobachtung:

Betrachten Sie die 2x2-Hilbert-Kurve:

01
32

Die 4x4 Hilbert Kurve ist:

0345
1276
ed89
fcba

Wenn wir den Minimalwert von jedem Quadranten subtrahieren (und sie aus Gründen der visuellen Klarheit ein wenig trennen), erhalten wir:

03 01
12 32

21 01
30 32

Dieses Muster gilt für jede Größe. Dies bedeutet, dass wir die nächste Ebene aus der aktuellen Ebene konstruieren können, indem wir als die vier Quadranten verwenden: a) die Transponierung der aktuellen Ebene, b) die aktuelle Ebene selbst, c) die Transponierung entlang der Antidiagonale, d) erneut das aktuelle Niveau selbst. Und dann versetzen wir sie jeweils um das 0, 1, 3, 2-fache der Größe des aktuellen Pegels.

q           e# Read input.
_N-         e# Make a copy and remove all linefeeds.
,4mLm]      e# Take that string's length's logarithm with base 4, rounded up.
            e# This is the Hilbert curve level we need.
0aa         e# Push [[0]] as the level-0 Hilbert curve.
{           e# Store the Hilbert curve level in L. Then for each i from 0 to L-1...
  4\#       e#   Compute 4^i. This is the offset of the four quadrants.
  4e!1=     e#   Get [0 1 3 2] as the second permutation returned by 4e!.
  f*        e#   Multiply each of them by the offset.
  \:G       e#   Swap with the Hilbert curve so far and call it G.
  [         e#   Create an array with...
    z       e#     The transpose of G.
    G       e#     G itself.
    GW%zW%  e#     The anti-diagonal transpose of G.
    G       e#     G itself.
  ]
  .ff+      e#   Add the appropriate offsets to the indices in each of the four quadrants.
  2/        e# Split into a 2x2 grid.
  {         e# Map this onto each pair of quadrants...
    ~       e#   Dump both quadrants on the stack.
    .+      e#   Concatenate them line by line.
    ~       e#   Dump the lines on the stack.
  }%        e# Since this is a map, the lines will automatically be collected in an array.
}@:L/

Schließlich verwenden wir diese Hilbert-Indexkurve, um die entsprechende Transformation auf die Eingabe anzuwenden:

\_        e# Swap the curve with the input and make another copy.
N&{       e# If the input contains linefeeds, execute the first block, else the second...
  N/      e#   Split the input into lines. The stack now has a grid of indices and a grid
          e#   of characters.
  ]z:z:~  e#   This is some weird transposition magic which zips up the indices with the
          e#   corresponding characters from both grids, and finally flattens the grid
          e#   into a linear list of index/character pairs. Those cells that don't have
          e#   characters due to trimmed whitespace in the input will be turned into
          e#   arrays containing only an index.
  $       e#   Sort the pairs (which sorts them by indices).
  1f>     e#   Discard the indices.
  s       e#   Flatten the result into a single string.
  S       e#   Leave a space on the stack to be trim trailing spaces later.
}{        e# or...
  4L#     e#   Compute the size of the Hilbert curve.
  ' e]    e#   Pad the input to that size with spaces.
  f{      e#   Map this block over lines of the curve, passing the padding input as an
          e#   additional parameter...
    f=    e#     For each index in the current line, select the appropriate character
          e#     from the padded input.
    SF    e#     Trim spaces from the end of the line.
  }
  N*      e#   Join the lines with linefeed characters.
  N       e#   Leave a linefeed on the stack to be trim trailing linefeeds later.
}?
F         e# We left either a space or a linefeed on stack... trim that character from
          e# the end of the string.
Martin Ender
quelle
3

Python 3, 467 434 423 457 451 426 386 374 342 291 304 * 80% * 95% = 231,04 Byte

Das funktioniert so, dass ich die Hilbert-Kurve mit einem Lindenmayer-System erstelle und den Anweisungen für Links, Rechts und Vorwärts entlang einer Reihe von Zeichenfolgen folge. Es gibt jedoch wahrscheinlich viele Möglichkeiten, wie man besser Golf spielen könnte. vor allem in den Bedingungen und bei der Zusammenstellung der Saiten. (Ich habe versucht, [" "*p for i in range(p)]aber Strings unterstützen die Elementzuweisung nicht (anscheinend). Wenn ich das zum Laufen bringen könnte, könnte ich auch den Join loswerden.)

Edit: Golfed einige der Bedingungen mit Dank an Dennis . Und ich spielte die Saiten ab. Und eine No-Byte-Änderung, weil die Ergebnisse im Vergleich zu den obigen Beispielen transponiert herauskamen.

Bearbeiten: Der Bonus zum Entfernen von Leerzeichen wurde implementiert.

Bearbeiten: Ein Fehler in meinem Code zum Entfernen von Leerzeichen für sechs weitere Bytes wurde behoben

Edit: Da diese Antwort den globalen Namensraum nicht verschmutzt, bekomme ich hier laut wizzwizz4 den 5% Bonus .

Bearbeiten: Ändert, wie ginkrementiert und dekrementiert wird. Jetzt mit eval()und str.translate.

Bearbeiten: Diese Antwort ist jetzt ein Programm anstelle einer Funktion.

Bearbeiten: Einige Fehler aus dem vorherigen Golf wurden behoben.

s=input();m=(len(bin(len(s)-1))-1)//2;t=eval("[' ']*2**m,"*2**m);t[0][0],*s=s;x=y=g=0;b="A";exec("b=b.translate({65:'-BF+AFA+FB-',66:'+AF-BFB-FA+'});"*m)
while s:
 c,*b=b;g+=(c<"-")-(c=="-")
 if"B"<c:x,y=[[x+1-g%4,y],[x,y+g%4-2]][g%2];t[x][y],*s=s
print("\n".join(''.join(i).rstrip()for i in t).rstrip())

Ungolfed:

# hilbert(it) is now implemented in the code with exec("b=b.translate")

def hilbert(it):
    s="A"
    n=""
    for i in range(it):
        for c in s:
            if c == "A":
                n += "-BF+AFA+FB-"
            elif c == "B":
                n += "+AF-BFB-FA+"
            else:
                n += c
        s=n;n=""
    return s

def string_to_hilbert(string):
    length = len(string)
    it = (len(bin(length-1))-1)//2
    hil = hilbert(it)
    pow_2 = 2**it
    # we use eval("[' ']*pow_2,"*pow_2) in the code, but the following is equivalent
    output = [[" "for j in range(pow_2)] for i in range(pow_2)]
    output[0][0] = string[0]
    x = 0
    y = 0
    heading = 0
    while string: # while there are still characters in string
        char, *hil = hil
        if char == "-": heading = heading - 1
        elif char == "+": heading = heading + 1
        elif char == "F":
            if heading % 4 == 3: y += 1
            elif heading % 4 == 2: x -= 1
            elif heading % 4 == 1: y -= 1
            else: x += 1
            output[x][y], *string = string
    array = [''.join(i).rstrip()for i in output]
    array = "\n".join(array).rstrip()
    print(array)
    return
Sherlock9
quelle
Neugierig auf den 5% Bonus. Sind die Variablen in Python automatisch lokal?
EDC65
@ edc65 Ich habe dem Herausforderungsschreiber hier eine ähnliche Frage gestellt: chat.stackexchange.com/transcript/240?m=28529277#28529277 . Hoffe das hilft ein wenig. Wenn nicht, können wir die Diskussion im Chat fortsetzen.
Sherlock9
2

Ruby, 358 356 344 322 319 * 80% * 95% = 242,44 Bytes

Dies ist mein Python-Code, der in Ruby umgesetzt wurde. Ich sollte mehr Antworten in Ruby schreiben. Es ist eine anständige Sprache zum Golfspielen.

Edit: Ich habe vergessen, dass Funktionen in dieser Frage nicht benannt werden müssen.

Edit: Da diese Antwort den globalen Namensraum nicht verschmutzt, bekomme ich hier laut wizzwizz4 den 5% Bonus .

->s{l=s.size;m=((l-1).bit_length+1)/2;x=2**m;t=(1..x).map{[" "]*x};t[0][0]=s[0];x=y=g=z=0;d=1;b=?A;m.times{b=b.split("").map{|c|c==?A?"-BF+AFA+FB-":c==?B?"+AF-BFB-FA+":c}.join("")};(c=b[z];z+=1;g+=c<?-?1:c==?-?-1:0;(g%2>0?y+=g%4-2:x+=1-g%4;t[x][y]=s[d];d+=1)if c>?B)while d<l;puts (t.map{|i|(i*'').rstrip}*"\n").rstrip}

Ungolfed:

def map_string(string)
  len = string.size
  m = ((len-1).bit_length+1)/2
  pow = 2**m
  output = (1..pow).map{[" "]*pow}
  output[0][0] = s[0]
  x = y = heading = char_index = 0
  chars_in_output = 1
  b = ?A
  m.times do |j|
    a = b.split("").map do |char|
      if char == "A"
        "-BF+AFA+FB-"
      else if char == "B"
        "+AF-BFB-FA+"
      else
        char
      end
    end
    b = a.join("")
  end
  while chars_in_output < len
    char = b[char_index]
    char_index += 1
    if char == "-"
      heading += -1
    else if char == "+"
      heading += 1
    else if char == "F"
      if heading % 2 == 0
        y += heading % 4 - 2
      else
        x += 1 - heading % 4
      end
    end
    output[x][y] = string[char_index]
    char_index += 1
  end
  return (output.map{|i|(i*'').rstrip}*"\n").rstrip
Sherlock9
quelle
Ist dieser Code unter einer Codelizenz doppelt lizenziert? Ich möchte ein Derivat produzieren, das unter der GPL veröffentlicht wurde (obwohl jede GPL-kompatible Lizenz damit funktioniert). Es ist derzeit unter CC BY-SA 3.0 veröffentlicht.
wizzwizz4
@ wizzwizz4 Chatte hier: chat.stackexchange.com/rooms/56405/…
Sherlock9
1

JavaScript (ES6), 227 - 20%: 181,6 Byte

m=>{for(n=1<<((33-Math.clz32(m.length-1))/2),t='',y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

Der Versuch, den 5% Bonus zu bekommen

m=>{for(var n=1<<((33-Math.clz32(m.length-1))/2),t='',x,y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(var p,q,u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

241 * 0,8 * 0,95: 183,16 größer

Weniger golfen

m=>
{
  // calc the size of the bounding square, clz32 is a bit shorter than ceil(log2()
  n = 1<<( (33-Math.clz32(m.length-1)) / 2); 
  t = '';
  for(y = 0; y < n; y++) 
  {
    for(x = 0 ; x < n; x++)
    {
      // for each position x,y inside the square
      // get the index postion in the hilbert curve
      // see https://en.wikipedia.org/wiki/Hilbert_curve (convert x,y to d)
      for(u=y, v=x, h=0, s=n; s >>= 1; )
      {
        h += s*s*(3 * !!(p = u & s) ^ !!(q = v & s));
        q || (p && (u = s+~u, v = s+~v),[u,v]=[v,u])
      }
      // add char at given index to output  
      t += m[h]||' '; // blank if beyond the length of m
    }
    t += '\n'; // add newline add end line
  }
  return t.replace(/ +$/mg,'').trim() // to get the 20% bonus
}  

Prüfung

F=m=>{for(n=1<<((33-Math.clz32(m.length-1))/2),t='',y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

function Test() { O.textContent = F(I.value) }

Test()
#I { width: 90% }
#O { border: 1px solid #ccc}
<input id=I oninput='Test()' value='The quick brown fox jumps over the lazy dog.'>
<pre id=O></pre>

edc65
quelle
Würde es sich lohnen, vars hinzuzufügen , um den 5% -Bonus zu erhalten?
wizzwizz4
var s,x,y,u,v,t,p,q,n,hNein, es ist nicht wert @ wizzwizz4
edc65
Sie können einfach varvor der ersten Verwendung eines jeden setzen ... Oh, das ist noch schlimmer.
wizzwizz4
@wizzwizz4 Alles in allem, vielleicht hast du einen Punkt ... ich versuche es ... nein. Schade
edc65