flat assembler
Message board for the users of flat assembler.

 Index > Heap > New Programming Contest: Hexagonal Neighbors
Author
bitRAKE

Joined: 21 Jul 2003
Posts: 2912
Location: [RSP+8*5]
bitRAKE
http://azspcs.com/Contest/HexagonalNeighbors
Quote:
The Problem

In this contest we will fill regular hexagonal grids with positive integers so that when a cell contains some integer k, the integers 1 through k-1 will be among that cell's neighbors.
Nice bit of fun for the holiday's. I'll be posting my code when the problem entry period over, 2 Feb 2019 16:00. Yet, it doesn't seem wrong to share programming related questions/work.

For example, code which displays the solution in entry format, etc. Or references to hexagonal grid in programming: https://www.redblobgames.com/grids/hexagons/

Mostly, I learn stuff while trying at these - not really aiming for top spot. These problems are always deceptively simple to state, and have several levels of discovery. I start with pencil and paper - solve a couple small grids to get a feel for the problem.

_________________
05 Nov 2018, 03:22
bitRAKE

Joined: 21 Jul 2003
Posts: 2912
Location: [RSP+8*5]
bitRAKE
I've chosen the axial system for cell layout because I like the access of neighbors using just two registers. _CELL is the size of a cell in bytes.
Code:
```; Addressing the six neighbors of cell [RBP+RSI] (clockwise)
; (RSI is number of bytes until next line)
; o   [rbp+rsi]
; A   [rbp]
; B   [rbp+_CELL]                       A B
; C   [rbp+rsi+_CELL]       <--       F o C
; D   [rbp+2*rsi]                     E D
; E   [rbp+2*rsi-_CELL]
; F   [rbp+rsi-_CELL]    ```
Next, I increase the grid size to add guard cells. Guard cells will make it easy to limit the grid edges/corners. In a larger context this simple example shows the cell layout in memory. Here I've used a period to indicate a guard cell.
Code:
```;                        . . .
;   1 2 3          . . . 1 2 3
;  4 5 6 7         . . 4 5 6 7
; 8 9 A B C  -->   . 8 9 A B C
;  D E F G         . D E F G .
;   H I J          . H I J . .
;                  . . . .    ```
From this we can deduce the width needed for the array: 2*_HEX, where _HEX is the side length of the grid. Furthermore, this is the value of RSI when accessing neighbors: LEA RSI,[2*_HEX*_CELL].

We might ask, what is the memory requirements of the hexagonal grid? _CELL*[(2*_HEX)^2 +1] What are the other properties, and how might they be calculated? Center?

_________________

Last edited by bitRAKE on 05 Nov 2018, 18:16; edited 1 time in total
05 Nov 2018, 16:16
sleepsleep

Joined: 05 Oct 2006
Posts: 8885
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
i am interested but this is too technical for my tiny brain i guess, i don't understand,
05 Nov 2018, 16:50
ProMiNick

Joined: 24 Mar 2012
Posts: 526
Location: Russian Federation, Sochi
ProMiNick
My english too weak. I even don`t understand task.
What needed?
What conditions?

Both neighbor cells shouldn`t be equal to each other exept case when they both equal to one? or around every cell should be neighbors with all of values from one up to value equal to cell value minus one?
What sum counted - all elements of regular hexagonal grid, only neighbor elements to particular cell? only that ones with sequenced lesser relation to that cell? or to any cell?
05 Nov 2018, 19:59
bitRAKE

Joined: 21 Jul 2003
Posts: 2912
Location: [RSP+8*5]
bitRAKE
Thank you for the questions - I can further explain the task as needed.

Every cell has six neighbors: within that group the numbers [k-1,1] must be if the cell has value k. The simplest solution is all one's.
Code:
``` 1 1
1 1 1
1 1    ```
If an incorrect solution is submitted the interface will explain the error. Other values are allowed for neighbors as long as the other condition is met. For example, this is a valid solution:
Code:
``` 2 2
2 1 2
2 2    ```
I too, was confused by the neighbors to "1" - does "1" need a "1" neighbor? It does not. Not until I started submitting solutions did these details become clear.

Tomorrow I will post code to print hexagonal grid. Power has been out here most the day, and hopefully it is on.
05 Nov 2018, 23:31
ProMiNick

Joined: 24 Mar 2012
Posts: 526
Location: Russian Federation, Sochi
ProMiNick
I am understand: condition is enoght.
Code:
```   1 3 2
4 7 6 1
3 2 5 4 2
1 3 1 3
4 2 4    ```

score = 58 (sum of elements) - 19 (count of elements) = 39

The task is to fill grid with maximal as possible numbers to make its sum maximal.

around each element shold be all values from 1 to value of element minus one:
so, largest value of inner element is 7 with 6 values around, largest value of border element is 5 with 4 values around, largest value of corner element is 4 with 3 values around. ; that was I needed as condition

To find maximum sum we must place near each other 2 maximal possible elements (7 & 6) in earliest possible place and 5 near them, and then resolve dependencies with target element to place as maximal value as possible.
So all variants could be started to analize with begin pattern of upper left corner:
Code:
```   1 3 2 ...
4 7 6 ...
3 2 5 ...    ```

or
Code:
```   1 3 2 ...
4 6 7 ...
3 2 5 ...    ```

for lower part used default filler for corners - 4 and 3 numbers around.

for big grids, instead of iteration of all possible variants should be function to determine number density of blurred border grid part, if inner part is ideal- stay it as is and go iterate border and border neighbors and so on...
06 Nov 2018, 10:17
bitRAKE

Joined: 21 Jul 2003
Posts: 2912
Location: [RSP+8*5]
bitRAKE
Code:
```HexGrid_Initialize:
; [GRID.size] is the length of side
; Set guard cells and all cell values to one.
; This is the model other routines expect.

mov ebx,[GRID.size]
lea rax,[rbx-1]
imul eax,ebx
lea rax,[rax*3+1]
mov [GRID.cells],eax ; 3*i*(i-1)+1

lea rdi,[GRID]
mov eax,\$0180
lea rcx,[2*rbx]
xor edx,edx
mov esi,1
.lines:
rep stosb           ; guard block

xchg al,ah
lea rcx,[rbx+rdx]
mov rsi,rdi
rep stosb           ; data block

xchg al,ah
mov rcx,rbx
sub rcx,rdx
jnz .lines

lea rcx,[rsi-1]
lea rsi,[GRID-1]
sub rcx,rsi
.mirror:
mov al,[rsi+rcx]
stosb
loop .mirror
mov [GRID.end],rdi

; register initialization for fast access
lea rsi,[2*rbx]
lea rdi,[2*rbx]           ; next line in grid
lea rbp,[GRID+(2*rbx)]    ; actual data start
neg rsi                   ; previous line in grid
mov [GRID.data],rbp
sub [GRID.end],rdi
retn    ```
The choice of \$80 for guard cells is completely arbitrary - cells could point to, or be instances of more complex things -- with little change to the code.
Code:
```HexGrid__ToBuffer:
mov eax,[GRID.cells]
mov [GRID.result],0

lea rdi,[__BUFFER]
mov ax,\$0A0D
stosw
mov al,'('
stosb
lea rbx,[.String]
call HexGrid__MapCells
mov word [rdi-2],\$0D0D      ; overwrite ',(' assumed

; set string length
lea rax,[__BUFFER]
mov [rax-8],rdi
sub [rax-8],rax
retn

.String:
jc .eol
bsf eax,[rbp]
stosb
mov al,','
stosb
retn
.eol:
bsf eax,[rbp]
add eax,'1),(' ; NOTE: FASM byte swaps data in string
stosd
retn

HexGrid__MapCells:
; function RBX is called with each cell in grid; top-down, line-by-line
; (carry flag is set when a row/line terminates)
mov rbp,[GRID.data]
.cells:
bt dword [rbp],7+8          ; is next cell a guard?
call rbx
.skip:
test byte [rbp],\$80
jnz .skip

cmp rbp,[GRID.end]
jc .cells
retn
; NOTE: lazy method used to preserve all registers besides RBP    ```
The above routine just produces a string for submitting to problem website.

ProMiNick, you are a step ahead. I wouldn't have posted a solution to ongoing "contest" but it is of little consequence. Partial tiling only reduces the problem by a constant - the complexity is still exponential. Or as it is said, "the devil is in the details."

A density greater than a perfect tiling is possible, so there is more to discover. The 27 side length hexagonal grid already has a submitted score of 6062, for 2107 cells that is a density of 3.877...

Confusing terminology of "nodes" removed -- call them cells everywhere.

Last edited by bitRAKE on 09 Nov 2018, 21:41; edited 1 time in total
06 Nov 2018, 13:45
ProMiNick

Joined: 24 Mar 2012
Posts: 526
Location: Russian Federation, Sochi
ProMiNick
bitRAKE, for grid debugging: because values are in range from 1 to 7 (rainbow color count (at least in European Nations)) hex cells could be represented with colors from purple(1) to red(7) not with numbers - so grids became more readable and more compact.
some set of functions like grid of densities (triangle densities(0..18) or node dencities (0..21)) could result in colors format too, so they would be readable too (inner colors will be more fractioned).
06 Nov 2018, 15:04
edfed

Joined: 20 Feb 2006
Posts: 4237
Location: 2018
edfed
interresting contest

maybe i'll soon have something to submit
09 Nov 2018, 17:07
bitRAKE

Joined: 21 Jul 2003
Posts: 2912
Location: [RSP+8*5]
bitRAKE
Another way to see the problem is maximizing the dependencies to neighbors. If a cell doesn't need a neighbor then it has a linkage value of zero. If multiple needed neighbor cells have the same value then the value is (1/n). The best solutions will have the highest total linkage sum.
26 Nov 2018, 10:59
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum