9
\$\begingroup\$

Marching Squares is an algorithm from computer graphics, which is used to recover 2D isocontours from a grid of samples (see also, its big brother Marching Cubes for 3D settings). The idea is to process each cell of the grid independently, and determine the contours passing through that cell based on the values at its corners.

The first step in this process is to determine which edges are connected by contours, based on whether the corners are above or below the value of the contour. For simplicity, we'll only consider contours along the value 0, such that we're interested in whether the corners are positive or negative. There are 24 = 16 cases to distinguish:

enter image description here
Image Source: Wikipedia

The identification of white and black doesn't really matter here, but for definiteness say that white is positive and black is negative. We will ignore cases where one of the corners is exactly 0.

The saddle points (cases 5 and 10) provide a little extra difficulty: it's not clear which diagonals should be used by only looking at the corners. This can be resolved by finding the average of the four corners (i.e. an approximation of the centre value), and choosing the diagonals such that the contours separate the centre from the corners with the opposite sign. If the average is exactly 0, either case can be chosen.

Normally, these 16 cases are simply stored in a lookup table. This is great for efficiency, but of course, we'd prefer the code to be short around here. So your task is to perform this lookup step and print an ASCII representation of the case in as little code as possible.

The Challenge

You're given the values of the four corners (non-zero integers) in a fixed order of your choice. You should then generate the correct layout of the contours, correctly resolving the saddle point cases.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be taken in any convenient string or list format.

The 16 cases will be represented in ASCII art using one of the following 5x5 blocks:

o---o  o---o  o---o
|   |  |   |  | | |
|   |  |---|  | | |
|   |  |   |  | | |
o---o  o---o  o---o

o---o  o---o  o---o  o---o
|/  |  |  \|  |   |  |   |
|   |  |   |  |   |  |   |
|   |  |   |  |\  |  |  /|
o---o  o---o  o---o  o---o

o---o  o---o
|/  |  |  \|
|   |  |   |
|  /|  |\  |
o---o  o---o

You must not print any leading or trailing whitespace, but you may print a single optional newline.

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

The test cases assume that input is given in order top-left, top-right, bottom-left, bottom-right. Test cases are presented in 9 groups, one corresponding to each of the 9 representations given above (in the same order, starting from the empty cell, ending with the two saddle points).

[1, 2, 1, 3]
[-9, -2, -2, -7]

[4, 5, -1, -2]
[-1, -2, 3, 4]

[7, -7, 7, -7]
[-5, 5, -5, 5]

[1, -6, -4, -1]
[-2, 3, 3, 4]

[-1, 6, -4, -1]
[2, -3, 3, 4]   

[-1, -6, 4, -1]
[2, 3, -3, 4]

[-1, -6, -4, 1]
[2, 3, 3, -4]

[3, -8, -9, 2]
[-3, 8, 9, -2]

[8, -3, -2, 9]
[-8, 3, 2, -9]

Additionally, the following test cases may return either of the saddle points (your choice):

[1, -4, -2, 5]
[-1, 4, 2, -5]
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Ruby, 201 180 176

This is an anonymous lambda function, to be called in the way shown in the ungolfed example.

This contains no variable s. In the ungolfed version a complex expression is assigned to s for clarity, before it is used. 4 bytes are saved in the golfed version by putting it inline. The only other difference between the versions is the whitespace and comments.

If it is acceptable to return the output as an array of five strings of five characters, instead of printing to stdout, one more byte can be saved.

->a{p=t=0
4.times{|i|t+=a[i]*=a[3];p+=a[i]>>9&1<<i}
q=p==6&&t>0?19:'@AC@P*10'[p].ord
puts c='o---o',(0..2).map{|i|b=p*i==3?'|---|':'|   |';b[q%4]='|/|\|/'[q%4+(i&2)];q/=4;b},c}

I'm happy with the parsing of the array, but I think there may be shorter ways to form the output.

All four elements of the input array are multiplied by the last element. This guarantees that the last element is positive, and reduces the number of cases from 16 down to 8. The elements are rightshifted 9 places, so that all positive numbers become 0 and all negative numbers become -1 (at least in the range of input given in the test cases.) They are then ANDed by 1<<array index to give a 3-bit binary number indicating the pattern (actually 4-bit, but as the last element is always positive, the 4th bit is always zero.)

This number from 0..7 is then fed to a (sigh) lookup table to determine which characters of each row are non-whitespace. It is at this stage that the two different displays for the saddle case are handled, with an alternative to the number in the lookup table being used if the total is positive (the question says to consider the "average", but as we are only interested in the sign, it doesn't matter if we consider the total instead.)

The way the display of output works is hopefully clear from the comments in the code.

ungolfed in test program

f=->a{p=t=0
  4.times{|i|                      #for each number in the input
    t+=a[i]*=a[3];                   #multiply each number by a[3]; totalize the sum in t
    p+=a[i]>>9&1<<i                  #shift right to find if negative; AND with 1<<i to build index number for pattern 
  }                                #q is a 3-digit base 4 number indicating which character of each line is non-whitespace (if any). 
  q=p==6&&t>0?19:'@AC@P*10'[p].ord #It's encoded in the magic string, except for the case of saddles with a positive total, which is encoded by the number 19.
  s=(0..2).map{|i|                 #build an array of 3 strings, indexes 0..2
    b=p*i==3?'|---|':'|   |';        #IF p is 3 and we are on row 1, the string is |---| for the horizontal line case. ELSE it is |   |.
    b[q%4]='|/|\|/'[q%4+(i&2)];      #The numbers in q indicate which character is to be modified. The characters in the string indicate the character to replace with.
    q/=4;                            #If q%4=0, the initial | is replaced by | (no change.) i&2 shifts the string index appropriately for the last row.
    b                                #divide q by 4, and terminate the loop with the expression b so that this is the object loaded into array s.  
  }
puts c='o---o',s,c}                #print the array s, capped with "o---o" above and below.


[[1, 2, 1, 3],
[-9, -2, -2, -7],

[4, 5, -1, -2],
[-1, -2, 3, 4],

[7, -7, 7, -7],
[-5, 5, -5, 5],

[1, -6, -4, -1],
[-2, 3, 3, 4],

[-1, 6, -4, -1],
[2, -3, 3, 4],

[-1, -6, 4, -1],
[2, 3, -3, 4],

[-1, -6, -4, 1],
[2, 3, 3, -4],

[3, -8, -9, 2],
[-3, 8, 9, -2],

[8, -3, -2, 9],
[-8, 3, 2, -9],

[1, -4, -2, 5],
[-1, 4, 2, -5]].each{|k|f.call(k)}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.