x86 machine code, 155 bytes
Hexdump:
60 8b fa 51 b0 20 f3 aa 59 51 b0 5f 03 c9 f3 aa
5e b0 0a aa 57 5f 57 b7 2f 8d 14 36 8b ce 2b ca
75 03 80 f7 73 7d 02 f7 d1 51 b0 20 f3 aa 59 8a
c7 aa 8b ee 53 6b d9 fe 8d 5c b3 ff 53 6b de fc
8b 5c 1f fe 8b 47 fe 80 fc 5f 74 23 8a c4 34 73
3c 2f 75 0a 80 ff 5f 74 3e 80 ff 5c 74 37 c1 eb
08 66 81 fb 2f 5c 74 2f 0f c7 f3 d1 eb 72 24 aa
3c 5f 75 01 4d 5b 4b 75 c3 5b 85 ed 75 97 32 c7
3c 73 75 91 b0 20 f3 aa b0 0a aa 4a 75 8e 88 17
5f 61 c3 b3 5f 8a fb 8a c7 eb d4
Explanation:
It's a fastcall function. It takes the size of the hexagon, n, in ecx, and a pointer to output string in edx.
First of all, it prints the first line: a few spaces and a few underscores. Then, it goes into a double loop: outer loop of lines, and inner loop of chars.
Each line starts with a few spaces and a border char (either / or \, depending on whether we are in upper or lower half of the output). Last chars in each line are spaces and a newline byte. The chars in the middle are generated according to the following rules. They guarantee that the output is a valid tiling.
If previous char is _, current char must be the same as the one to the left of it:
(case 1) /_/
(case 2) \_\
If previous char is \ and upper char is _, current char must be _:
_
\_
If previous and upper chars are \, current char must be equal to upper-left char:
(case 1) _\
\_
(case 2) /\
\/
If upper char is / and upper-right char is \, current char must be \:
/\
\
If none of the above holds, choose one of the following two possibilities for current char randomly:
- Underscore
_
- Slash with opposite direction from the previous slash:
/\ or \/
To implement these rules, it loads 4 bytes from the upper line into ebx and 4 bytes from current line into eax. Then, ah is the previous char, while al is the one preceding it. Also, bl is the upper-left char, bh is the upper char, and the byte in ebx above bh is the upper-right char. After taking into account the upper-left char, it shifts ebx right by 8 bits so the upper-right char becomes accessible in bh.
To flip the direction of a slash, it does XOR with 0x73.
After finishing a line, it checks two conditions:
- Last char must be a slash in the appropriate direction (opposite to the direction of the first slash in line)
- There must be exactly
n underscores in the line
If either condition is violated, it starts over from first line. So for large n, the output will be very slow, because successful execution requires luck in each line. The following example output for n = 8 takes about a minute to calculate:
________________
/_/_/_/\_\_\_\_\_\
/_/_/_/\/_/\_\_\_\_\
/_/_/\_\/\_\/_/_/_/\_\
/_/_/\/\_\/_/_/_/_/\/_/\
/_/\_\/\/_/_/_/\_\_\/_/\/\
/\_\/\_\/_/\_\_\/_/_/_/\/\/\
/\/_/\/_/\_\/_/\_\_\_\_\/\/\/\
/\/\_\/_/\/_/\_\/_/_/\_\_\/\/\/\
\/\/_/\_\/\_\/\_\_\_\/\_\_\/\/\/
\/_/\/_/\/\_\/_/_/_/\/_/\_\/\/
\_\/_/\/\/_/_/_/\_\/_/\/_/\/
\_\_\/\/_/\_\_\/\_\_\/_/\/
\_\_\/_/\/\_\_\/_/_/_/\/
\_\_\_\/\/_/_/_/_/_/\/
\_\_\_\/_/\_\_\_\_\/
\_\_\_\_\/_/_/_/_/
Here is assembly source code mixed with disassembly. I took it while stopped at a breakpoint in Visual Studio.
pushad;
10014190 60 pushad
mov edi, edx;
10014191 8B FA mov edi,edx
push ecx;
10014193 51 push ecx
mov al, ' ';
10014194 B0 20 mov al,20h
rep stosb;
10014196 F3 AA rep stos byte ptr es:[edi]
pop ecx;
10014198 59 pop ecx
push ecx;
10014199 51 push ecx
mov al, '_';
1001419A B0 5F mov al,5Fh
add ecx, ecx;
1001419C 03 C9 add ecx,ecx
rep stosb;
1001419E F3 AA rep stos byte ptr es:[edi]
pop esi; // esi = n
100141A0 5E pop esi
mov al, '\n';
100141A1 B0 0A mov al,0Ah
stosb;
100141A3 AA stos byte ptr es:[edi]
push edi;
100141A4 57 push edi
again:
pop edi;
100141A5 5F pop edi
push edi;
100141A6 57 push edi
mov bh, '/'; // bh = first char in line
100141A7 B7 2F mov bh,2Fh
lea edx, [esi + esi]; // edx = line index
100141A9 8D 14 36 lea edx,[esi+esi]
line_loop:
mov ecx, esi;
100141AC 8B CE mov ecx,esi
sub ecx, edx;
100141AE 2B CA sub ecx,edx
jnz skip1;
100141B0 75 03 jne doit+25h (100141B5h)
xor bh, '\\' ^ '/';
100141B2 80 F7 73 xor bh,73h
skip1:
jge skip2;
100141B5 7D 02 jge doit+29h (100141B9h)
not ecx; // ecx = spaces before and after chars
100141B7 F7 D1 not ecx
skip2:
push ecx;
100141B9 51 push ecx
mov al, ' ';
100141BA B0 20 mov al,20h
rep stosb;
100141BC F3 AA rep stos byte ptr es:[edi]
pop ecx;
100141BE 59 pop ecx
mov al, bh;
100141BF 8A C7 mov al,bh
stosb;
100141C1 AA stos byte ptr es:[edi]
mov ebp, esi; // ebp = underscore counter
100141C2 8B EE mov ebp,esi
push ebx;
100141C4 53 push ebx
imul ebx, ecx, -2;
100141C5 6B D9 FE imul ebx,ecx,0FFFFFFFEh
lea ebx, [ebx + 4 * esi - 1]; // ebx = char counter
100141C8 8D 5C B3 FF lea ebx,[ebx+esi*4-1]
i_loop:
push ebx;
100141CC 53 push ebx
imul ebx, esi, -4;
100141CD 6B DE FC imul ebx,esi,0FFFFFFFCh
mov ebx, [edi + ebx - 2];
100141D0 8B 5C 1F FE mov ebx,dword ptr [edi+ebx-2]
mov eax, [edi - 2];
100141D4 8B 47 FE mov eax,dword ptr [edi-2]
cmp ah, '_';
100141D7 80 FC 5F cmp ah,5Fh
je x_done;
100141DA 74 23 je doit+6Fh (100141FFh)
mov al, ah;
100141DC 8A C4 mov al,ah
xor al, '/' ^ '\\';
100141DE 34 73 xor al,73h
cmp al, '/';
100141E0 3C 2F cmp al,2Fh
jne al_diff;
100141E2 75 0A jne doit+5Eh (100141EEh)
cmp bh, '_';
100141E4 80 FF 5F cmp bh,5Fh
je mov_al_bh;
100141E7 74 3E je skip5+22h (10014227h)
cmp bh, '\\';
100141E9 80 FF 5C cmp bh,5Ch
je mov_al_bl;
100141EC 74 37 je skip5+20h (10014225h)
al_diff:
shr ebx, 8;
100141EE C1 EB 08 shr ebx,8
cmp bx, '\\' << 8 | '/';
100141F1 66 81 FB 2F 5C cmp bx,5C2Fh
je mov_al_bh;
100141F6 74 2F je skip5+22h (10014227h)
rdrand ebx;
100141F8 0F C7 F3 rdrand ebx
shr ebx, 1;
100141FB D1 EB shr ebx,1
jc mov_al_underscore;
100141FD 72 24 jb skip5+1Eh (10014223h)
x_done:
stosb;
100141FF AA stos byte ptr es:[edi]
cmp al, '_';
10014200 3C 5F cmp al,5Fh
jne skip5;
10014202 75 01 jne skip5 (10014205h)
dec ebp;
10014204 4D dec ebp
skip5:
pop ebx;
10014205 5B pop ebx
dec ebx;
10014206 4B dec ebx
jnz i_loop;
10014207 75 C3 jne doit+3Ch (100141CCh)
pop ebx;
10014209 5B pop ebx
test ebp, ebp;
1001420A 85 ED test ebp,ebp
jne again;
1001420C 75 97 jne doit+15h (100141A5h)
xor al, bh;
1001420E 32 C7 xor al,bh
cmp al, '/' ^ '\\';
10014210 3C 73 cmp al,73h
jne again;
10014212 75 91 jne doit+15h (100141A5h)
mov al, ' ';
10014214 B0 20 mov al,20h
rep stosb;
10014216 F3 AA rep stos byte ptr es:[edi]
mov al, '\n';
10014218 B0 0A mov al,0Ah
stosb;
1001421A AA stos byte ptr es:[edi]
dec edx;
1001421B 4A dec edx
jne line_loop;
1001421C 75 8E jne doit+1Ch (100141ACh)
mov [edi], dl; // terminating zero byte
1001421E 88 17 mov byte ptr [edi],dl
pop edi;
10014220 5F pop edi
popad;
10014221 61 popad
ret;
10014222 C3 ret
mov_al_underscore:
mov bl, '_';
10014223 B3 5F mov bl,5Fh
mov_al_bl:
mov bh, bl;
10014225 8A FB mov bh,bl
mov_al_bh:
mov al, bh;
10014227 8A C7 mov al,bh
jmp x_done;
10014229 EB D4 jmp doit+6Fh (100141FFh)
Here is C++ code which I used to develop my assembly code:
#include <stdio.h>
#include <iostream>
#include <random>
#include <set>
#include <string>
#define MY 1
std::random_device rd;
std::mt19937 gen(rd());
std::bernoulli_distribution distr(0.5);
#if MY
__declspec(naked) void __fastcall doit(int, char*)
{
_asm {
pushad;
mov edi, edx;
push ecx;
mov al, ' ';
rep stosb;
pop ecx;
push ecx;
mov al, '_';
add ecx, ecx;
rep stosb;
pop esi; // esi = n
mov al, '\n';
stosb;
push edi;
again:
pop edi;
push edi;
mov bh, '/'; // bh = first char in line
lea edx, [esi + esi]; // edx = line index
line_loop:
mov ecx, esi;
sub ecx, edx;
jnz skip1;
xor bh, '\\' ^ '/';
skip1:
jge skip2;
not ecx; // ecx = spaces before and after chars
skip2:
push ecx;
mov al, ' ';
rep stosb;
pop ecx;
mov al, bh;
stosb;
mov ebp, esi; // ebp = underscore counter
push ebx;
imul ebx, ecx, -2;
lea ebx, [ebx + 4 * esi - 1]; // ebx = char counter
i_loop:
push ebx;
imul ebx, esi, -4;
mov ebx, [edi + ebx - 2];
mov eax, [edi - 2];
cmp ah, '_';
je x_done;
mov al, ah;
xor al, '/' ^ '\\';
cmp al, '/';
jne al_diff;
cmp bh, '_';
je mov_al_bh;
cmp bh, '\\';
je mov_al_bl;
al_diff:
shr ebx, 8;
cmp bx, '\\' << 8 | '/';
je mov_al_bh;
rdrand ebx;
shr ebx, 1;
jc mov_al_underscore;
x_done:
stosb;
cmp al, '_';
jne skip5;
dec ebp;
skip5:
pop ebx;
dec ebx;
jnz i_loop;
pop ebx;
test ebp, ebp;
jne again;
xor al, bh;
cmp al, '/' ^ '\\';
jne again;
mov al, ' ';
rep stosb;
mov al, '\n';
stosb;
dec edx;
jne line_loop;
mov [edi], dl; // terminating zero byte
pop edi;
popad;
ret;
mov_al_underscore:
mov bl, '_';
mov_al_bl:
mov bh, bl;
mov_al_bh:
mov al, bh;
jmp x_done;
}
}
#else // not MY
void doit(int n, char* s)
{
for (int i = 0; i < n; ++i)
*s++ =' ';
for (int i = 0; i < n * 2; ++i)
*s++ ='_';
*s++ ='\n';
char* save = s;
again:
for (int line = 2 * n; line > 0; --line)
{
int spaces = n - line;
char border1 = '\\';
if (n - line < 0)
{
border1 = '/';
spaces = ~spaces;
}
for (int i = 0; i < spaces; ++i)
*s++ = ' ';
*s++ = border1;
int check = n;
for (int i = 4 * n - 1 - 2 * spaces; i; --i)
{
char al = s[-2];
char ah = s[-1];
char bl = s[-4 * n - 2];
char bh = s[-4 * n - 1];
char bk = s[-4 * n - 0];
if (ah == '_')
goto x_done;
al = ah ^ '/' ^ '\\';
if (al != '/')
goto al_diff;
if (bh == '_')
{
al = bh;
goto x_done;
}
else if (bh == '\\')
{
al = bl;
goto x_done;
}
al_diff:
bl = bh;
bh = bk;
if (bl == '/' && bh == '\\')
{
al = bh;
}
else if (distr(gen))
{
al = '_';
}
x_done:
*s++ = al;
if (al == '_')
--check;
}
if (check)
{
s = save;
goto again;
}
if (s[-1] != (border1 ^ '/' ^ '\\'))
{
s = save;
goto again;
}
for (int i = 0; i < spaces; ++i)
*s++ = ' ';
*s++ ='\n';
}
*s++ ='\0';
}
#endif // MY
int main(void)
{
char s[1000];
std::set<std::string> results;
while (true)
{
doit(3, s);
if (!results.count(s))
{
puts(s);
results.insert(s);
std::cout << results.size() << '\n';
}
}
}
For N ≤ 4, your submission must produce a tiling within 1 minute at least 80% of the time.too easy: 80% of time the same, basic tiling, otherwise I find another tiling in whatever time I want \$\endgroup\$