flat assembler
Message board for the users of flat assembler.

flat assembler > Heap > New Programming Contest: Hexagonal Neighbors

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 2659
Location: dank orb
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.

_________________
utf8everywhere.org
Post 05 Nov 2018, 03:22
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2659
Location: dank orb
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?

_________________
utf8everywhere.org


Last edited by bitRAKE on 05 Nov 2018, 18:16; edited 1 time in total
Post 05 Nov 2018, 16:16
View user's profile Send private message Visit poster's website Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 7704
Location: ˛                              ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣ Posts: 6699
i am interested but this is too technical for my tiny brain i guess, i don't understand, Laughing
Post 05 Nov 2018, 16:50
View user's profile Send private message Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 206
Location: Russian Federation, Sochi
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?
Post 05 Nov 2018, 19:59
View user's profile Send private message Send e-mail Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2659
Location: dank orb
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.
Post 05 Nov 2018, 23:31
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 206
Location: Russian Federation, Sochi
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...
Post 06 Nov 2018, 10:17
View user's profile Send private message Send e-mail Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2659
Location: dank orb
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]
    add edx,1
    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]
    add [GRID.result],eax
    add al,'1'
    stosb
    mov al,','
    stosb
    retn
  .eol:
    bsf eax,[rbp]
    add [GRID.result],eax
    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:
    add rbp,1
    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...

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


Last edited by bitRAKE on 09 Nov 2018, 21:41; edited 1 time in total
Post 06 Nov 2018, 13:45
View user's profile Send private message Visit poster's website Reply with quote
ProMiNick



Joined: 24 Mar 2012
Posts: 206
Location: Russian Federation, Sochi
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).
Post 06 Nov 2018, 15:04
View user's profile Send private message Send e-mail Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4163
Location: 2018
interresting contest

maybe i'll soon have something to submit Smile
Post 09 Nov 2018, 17:07
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2018, Tomasz Grysztar.

Powered by rwasa.