# Map string to Hilbert curve

Let's map some strings to 2d space, fractal style. Your task is to compute a Hilbert curve and lay a string along it.

The task is to take the single-line input string, and lay it out along a Hilbert curve big enough to contain it, but no bigger. Try to make the byte count as low as possible; this is after all!

### Conditions

• Any gaps to be padded with whitespace, but padding is not required at the end of lines.
• The start of the line should be in the top-left corner, and the end in the bottom-left.
• You may create a program or function.
• There may be some new test-cases appearing, so don't hardcode anything!

### Bonuses

Note: Bonuses stack like this: -50% & -20% on 100B = -20% on 50B or -50% on 80B = 40B.

• -50% If the input is a multi-line string, reverse the process to create the original input. Test cases for the bonus: just use the existing ones (including the bonus test cases!)
• -20% If you strip all unnecessary whitespace from the output (e.g. at the end of a line).
• -5% If you don't pollute the global namespace (you know what I mean!)

### Test cases

abcdefghijklmn

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


And for the whitespace-stripping bonus:

No  hitespac  her

Noher

hesc
itpa


/* Configuration */

var QUESTION_ID = 66958; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 43394; // This should be the user ID of the challenge author.

/* App */

return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:[.]\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

var body = a.body;
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
});

});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

var lang = a.language;
if (/<a/.test(lang)) lang = jQuery(lang).text();

languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.lang > b.lang) return 1;
if (a.lang < b.lang) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body { text-align: left !important}

width: 290px;
float: left;
}

#language-list {
width: 290px;
float: left;
}

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<div id="language-list">
<h2>Winners by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

# Language Name, N bytes


where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

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


If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

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


You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

• If anyone can make some more testcases, that would be appreciated. – wizzwizz4 Dec 19 '15 at 14:54
• So the charactes should be represented by vertices of the curve? – flawr Dec 20 '15 at 11:55
• No..hitespac..her. where the dots are spaces would be a better test case for the bonus. (And currently, the test case is missing the trailing .) – Martin Ender Dec 20 '15 at 11:56
• If you are taking the L-system approach, you might also want to try http://codegolf/questions/48697/ascii-l-system-renderer. It could help you to golf your answers. – wizzwizz4 Dec 22 '15 at 9:53

## CJam, 119117113112 109 * 0.5 * 0.8 = 43.6 bytes

Thanks to Dennis for saving 1 byte.

Here is a start...

{+eW<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  I'm sure there's a shorter way to generate the curve... ### Explanation First, I define a function to trim some element from the end of an array, because I need that in several places. It expects the array and the element (inside a separate array) on top of the stack. { + 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.  Now the majority of the code determines the size of the required Hilbert curve and constructs it as 2D array where the elements are indices along the curve. I construct this based on the following observation: Consider the 2x2 Hilbert curve: 01 32  The 4x4 Hilbert curve is: 0345 1276 ed89 fcba  If we subtract the minimum value from each quadrant (and separate them a bit for visual clarity), we get: 03 01 12 32 21 01 30 32  This pattern holds for any size. It means that we can construct the next level from the current one, by using as the four quadrants: a) the transpose of the current level, b) the current level itself, c) the transpose along the anti-diagonal, d) again the current level itself. And then we offset them 0, 1, 3, 2 times the size of the current level, respectively. 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/  Finally, we use this Hilbert curve of indices to apply the appropriate transformation to the input: \_ 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).
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
f=    e#     For each index in the current line, select the appropriate character
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.


# Python 3, 467434423457451426386374342291 304 * 80% * 95% = 231.04 bytes

The way this works is that I make the Hilbert curve using a Lindenmayer system and follow the left, right and forward instructions along an array of strings. There are probably many ways this could be golfed better, though; especially in the conditionals and in making the array of strings. (I did attempt [" "*p for i in range(p)] but strings don't support item assignment (apparently). If I could get that to work, I could get rid of join, too)

Edit: Golfed some of the conditionals with thanks to Dennis. And I golfed down the array of strings. And a no-byte change because the results were coming out transposed compared to the examples above.

Edit: Implemented the whitespace-stripping bonus.

Edit: Fixed a bug in my whitespace-stripping code for six more bytes

Edit: Since this answer doesn't pollute the global namespace, I get the 5% bonus, according to wizzwizz4 here.

Edit: Changed how g is incremented and decremented. Now using eval() and str.translate.

Edit: Fixed some bugs from the previous golf.

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
while string: # while there are still characters in string
char, *hil = hil
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

• Curious about the 5% bonus. Are the variables automatically local in Python? – edc65 Apr 6 '16 at 13:41
• @edc65 I asked the challenge writer a similar thing here: chat.stackexchange.com/transcript/240?m=28529277#28529277. Hope that helps a little. If not, we can continue the discussion in chat. – Sherlock9 Apr 7 '16 at 4:38

# Ruby, 358356344322 319 * 80% * 95% = 242.44 bytes

This is my Python code transpiled to Ruby. I should write more answers in Ruby. It's a decent language to golf in.

Edit: I forgot that functions don't need to be named in this question.

Edit: Since this answer doesn't pollute the global namespace, I get the 5% bonus, according to wizzwizz4 here.

->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 == "-"
else if char == "+"
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

• Is this code dual-licensed under a code license? I'd like to produce a derivative work that's released under the GPL (although any GPL-compatible license will work with this). It's currently released under CC BY-SA 3.0. – wizzwizz4 Mar 27 '17 at 19:39
• @wizzwizz4 Chat here: chat.stackexchange.com/rooms/56405/… – Sherlock9 Apr 1 '17 at 6:20

# JavaScript (ES6), 227 - 20% : 181.6 bytes

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()}  Trying to get the 5% bonus 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 bigger

Less golfed

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
}
}
return t.replace(/ +$/mg,'').trim() // to get the 20% bonus }  Test 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>

• Would it be worth adding vars to get the 5% bonus? – wizzwizz4 Apr 6 '16 at 16:41
• var s,x,y,u,v,t,p,q,n,h no it's not worth @wizzwizz4 – edc65 Apr 6 '16 at 17:04
• You can just put var before the first use of each... Oh, that's even worse. – wizzwizz4 Apr 6 '16 at 17:11
• @wizzwizz4 all in all, maybe you have a point... i'm trying ... no. Too bad – edc65 Apr 6 '16 at 17:20