14
\$\begingroup\$

Inclusion-Exclusion lets you calculate the sizes of some unions and intersections between sets knowing some of the other values. I won't explain it exactly, but your challenge is to visualize inclusion-exclusion on a Venn Diagram.

Because I'm nice, you'll be using rectangles, not circles.

You will be given a list of rectangles denoted by top-left and bottom-right corner coordinates in any reasonable format (list of 4-tuples, list of pairs of pairs, list of pairs, etc). You can assume that all coordinates are non-negative and within your language's (reasonable) number range (please specify what it is if it's less than 128). You can choose to be left-inclusive or left-exclusive and right-inclusive or right-exclusive. Regardless of your chosen format, you can assume all rectangles are at least 1x1.

Then, you are to draw out each rectangle on the screen (ASCII canvas) using a single non-whitespace character k, which is yours to choose.

However, whenever two rectangles overlap, the overlapping area shall be drawn with another non-whitespace character l != k, also yours to choose.

Whenever three rectangles overlap, the overlapping area should be drawn with k, and for an odd number of rectangles covering, k, and an even number, l.

The background should be single whitespaces (0x20).

Test Cases (k = "#", l = ".")

0 0 9 9
1 1 10 10
2 2 11 11

#########  
#........# 
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
 #........#
  #########

1 1 3 3
2 2 4 4


 ## 
 #.#
  ##

1 1 9 9
2 2 8 8
3 3 7 7


 ########
 #......#
 #.####.#
 #.####.#
 #.####.#
 #.####.#
 #......#
 ########

Notes

  • Leading spaces and newlines (which occur if the minimum coordinate isn't 0, 0) must be present
  • Any trailing spaces and newlines are allowed to a reasonable extent (i.e. don't trail like 100000000 newlines, that's just annoying)
  • x- and y- axes can face either way but you must be consistent and specify which (default is x- right and y- down)
  • coordinates can be 0-, 1-, or 2- indexed.

Reference Proton Implementation

This is , so the objective is to have the shortest code. Happy golfing!

\$\endgroup\$
8
  • \$\begingroup\$ x-axis extends rightwards and y-axis extends downward from the top-left corner? \$\endgroup\$
    – DELETE_ME
    Oct 23, 2017 at 13:41
  • \$\begingroup\$ @user202729 In test cases, yes (actually ambiguous) but you may use either as long as you're consistent \$\endgroup\$
    – hyper-neutrino
    Oct 23, 2017 at 13:43
  • \$\begingroup\$ @dzaima Yup. [...] \$\endgroup\$
    – hyper-neutrino
    Oct 23, 2017 at 13:45
  • 1
    \$\begingroup\$ @JoKing yes, i will make the input format more flexible. realized that this is an old challenge and i wasn't too familiar with challenge writing yet \$\endgroup\$
    – hyper-neutrino
    Mar 10, 2020 at 2:59
  • 1
    \$\begingroup\$ @JoKing Actually I will allow any of the four combinations. \$\endgroup\$
    – hyper-neutrino
    Mar 10, 2020 at 3:30

9 Answers 9

4
\$\begingroup\$

6502 machine code routine (C64), 57 bytes

20 44 E5 A0 03 84 FB 20 9B B7 A4 FB 96 22 C6 FB 10 F5 85 FC A6 24 20 F0 E9 A4
25 B1 D1 09 01 49 02 91 D1 C8 C4 23 D0 F3 E8 E4 22 D0 E9 A9 2C C5 FC F0 D0 A5
C6 F0 FC C6 C6 4C 44 E5

This is position-independent code, put it somewhere in RAM and use the correct start address calling it with sys.

Online demo (start address $C000 / 49152).

Usage: sys<startaddress>,<x1>,<y1>,<x2>,<y2>[,<x1>,<y1>,<x2>,<y2>[,...]]

Example: sys49152,0,0,9,9,1,1,10,10,2,2,11,11

On reasonable number ranges: The natural range on this 8-bit machine is [0-255], and the program will accept this as parameters. But the C64 screen only has 40 columns and 25 rows, therefore limiting the reasonable range to [0-40] for x values and [0-25] for y values. Using other values will have unpredictable behavior.


commented disassembly listing:

20 44 E5    JSR $E544           ; clear screen
 .mainloop:
A0 03       LDY #$03            ; index for reading coordinates
84 FB       STY $FB
 .inputrect:
20 9B B7    JSR $B79B           ; read 8bit value from parameter
A4 FB       LDY $FB
96 22       STX $22,Y           ; and store to $22-$25
C6 FB       DEC $FB
10 F5       BPL .inputrect      ; parameter reading loop
85 FC       STA $FC             ; store last character
A6 24       LDX $24             ; load y1
 .rowloop:
20 F0 E9    JSR $E9F0           ; get pointer to screen row in $d1/$d2
A4 25       LDY $25             ; load x1
 .colloop:
B1 D1       LDA ($D1),Y         ; load character at screen position
09 01       ORA #$01            ; set bit 0 ( -> '#')
49 02       EOR #$02            ; toggle bit 1 (toggle between '#' and '!' )
91 D1       STA ($D1),Y         ; store character at screen position
C8          INY                 ; next x
C4 23       CPY $23             ; equals x2?
D0 F3       BNE .colloop        ; no -> repeat
E8          INX                 ; next y
E4 22       CPX $22             ; equals y2?
D0 E9       BNE .rowloop        ; no -> repeat
A9 2C       LDA #$2C            ; load ','
C5 FC       CMP $FC             ; compare with last character from parsing
F0 D0       BEQ .mainloop       ; if ',', repeat reading coordinates
 .waitkey:
A5 C6       LDA $C6             ; load input buffer size
F0 FC       BEQ .waitkey        ; and repeat until non-empty
C6 C6       DEC $C6             ; set back to empty
4C 44 E5    JMP $E544           ; clear screen
\$\endgroup\$
3
\$\begingroup\$

Python 2, 218 192 189 185 158 154 147 bytes

def f(l):_,_,a,b=map(range,map(max,zip(*l)));print'\n'.join(''.join((' '+'#.'*len(l))[sum((x<=i<X)*(y<=j<Y)for x,y,X,Y in l)]for i in a)for j in b)

Try it online!

\$\endgroup\$
0
3
\$\begingroup\$

Charcoal, 40 bytes

WS«≔I⪪ι ιF…§ι⁰§ι²«Jκ§ι¹UMKD⁻§ι³§ι¹↓§10Σλ

Try it online! Link is to verbose version of code. Will be 6 bytes shorter once @ASCII-only fixes a bug in Charcoal. Takes input as a newline-terminated list of space-separated list of co-ordinates. Explanation:

WS«

Loop over each line of input until a blank line is reached.

≔I⪪ι ι

Split the line into a list of co-ordinates.

F…§ι⁰§ι²«

Loop over all the X co-ordinates.

Jκ§ι¹

Jump to the top of the column.

UM

Map over each of...

KD⁻§ι³§ι¹↓

... all the cells in the column...

§10Σλ

... the new value is 0 if they contain 1, otherwise 1. Edit: Soon after writing this, Charcoal changed the behaviour of ¬ so that I¬Σλ works here to save 1 byte.

\$\endgroup\$
2
  • \$\begingroup\$ :| did i mess something up tio.run/… \$\endgroup\$
    – ASCII-only
    Oct 26, 2017 at 13:46
  • \$\begingroup\$ @ASCII-only Bug in my workaround - I can print an \n instead I guess... \$\endgroup\$
    – Neil
    Oct 26, 2017 at 15:31
3
\$\begingroup\$

J, 36 34 bytes

(' ','#.'$~#){~[:+/(-@]{.-~$1:)/"2

Try it online!

-2 bytes thanks to Bubbler

We take input as a list of 2x2 matrices.

  • For each of them "2, draw a box of ones 1: of the same shape $ as the element-wise difference between the top-left and bottom-right coords -~.
  • Then rotate that down and to the right with 0 fill -@]{. until the upper leftmost 1 is in the coords specified by the left arg -@[.
  • [:+/ Sum the resulting matrices element-wise. J guarantees they will be the same size by adding 0 fill to the right. This will produce a single matrix with integers 0, 1, 2, 3, etc. We'll use those to index into our ascii chars {~.
  • '#.'$~# Repeat the pattern #. cyclically $~ to the input length #, and then prepend a space ' ',.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 34 \$\endgroup\$
    – Bubbler
    May 20, 2020 at 1:13
  • \$\begingroup\$ @Bubbler, Thank you. \$\endgroup\$
    – Jonah
    May 20, 2020 at 2:07
2
\$\begingroup\$

Python 2, 181 bytes

l=input()
_,_,x,y=map(max,zip(*l))
m=eval(`[[32]*x]*y`)
for v,w,x,y in l:
 for i in range(v,x):
	for j in range(w,y):
	 m[i][j]=max(m[i][j]^1,34)
for n in m:print''.join(map(chr,n))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 205 bytes

x[999][999];a;b;c;d;j;k;l;m;n;main(i){for(;scanf("%d %d %d %d",&a,&b,&c,&d)>3;m=d>m?d:m,n=c>n?c:n)for(i=b;i<d;++i)for(j=a;j<c;++j)x[i][j]=x[i][j]^2|1;for(;k<n||++l<(k=0,puts(""),m);putchar(x[l][k++]+32));}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

R, 196 189 bytes

m=matrix
x=m(scan(file("stdin")),4)
y=m(0,max(x[3,]),max(x[4,]))
n=ncol(x)
while(n){z=x[,n]  
i=z[1]:z[3]
j=z[2]:z[4]
y[i,j]=y[i,j]+1
n=n-1}
i=!y
y=y%%2+1
y[i]=' '
cat(rbind(y,'\n'),sep='')

Try it online!

The code reads input as stdin, arranged as a x1 y1 x2 y2 tuple, where x is the column and y is the row. I am using 1 and 2 for the overlap levels, where 1 represents an even level.

Saved 7 bytes thanks to user2390246.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ A few ideas for golfing this down: 1. Is there any need to transform your matrix x? 2. Use nrow (or ncol if not transformed) instead of dim(x)[1] 3. You don't need to define i=y>0 as you only use it once. \$\endgroup\$ Oct 25, 2017 at 10:33
  • \$\begingroup\$ 4. Initialise the matrix to -1 and then just use y=y%%2 and y[y<0]=" ". \$\endgroup\$ Oct 25, 2017 at 10:38
  • \$\begingroup\$ Thank you. I included suggestion 1 and 2. Suggestions 3 and 4 would not work because: i=y>0 is used to store the levels prior to applying the modulus, and the modulus should not be sign preserving. However, that gave me the idea to use the implicit R convention that 0=FALSE, and save two extra bytes. :) \$\endgroup\$
    – NofP
    Oct 25, 2017 at 21:21
2
\$\begingroup\$

Raku, 54 bytes

{my@a;{@a[$^a..$^b;$^c..$^d]X+^=1}for $_;@a >>~|>>' '}

Try it online!

Takes input as a flat list of coordinates as inclusive coordinates, i.e. x1,y1,x2,y2,x1,y1,x2,y2... and outputs as a list of list of characters with k being 1 and l being 0.

Explanation:

{                                                    }  # Anonymous codeblock
 my@a;    # Declare an array
      {                          }for $_;    # Loop over the input
       @a[                 ]   # Indexing into @a
          $^a..$^b             # The range of rows
                  ;$^c..$^d    # And the range of columns for each
                            X        # And for each cell
                             +^=1    # Set it to itself bitwise XOR'd with 1
                         # Cells not yet accessed are numerically zero
                                         @a >>~|>>' '   # Stringwise OR each cell with a space
                         # Cells not yet accessed are stringily empty         
\$\endgroup\$
1
\$\begingroup\$

Jelly, 43 bytes

+µ>2Ḥạ
ạ1ẋ$0ẋ⁸¤;µ/€«þ/µ€z0z€0Z€Zz€0Z€ç"/o⁶Y

Try it online!

Explanation

+µ>2Ḥạ                                Helper Link; combines final rectangles (0 is blank, 1 is covered, 2 is uncovered)
+                                     add the two values
 µ                                    (with the sum...)
  >2                                  check if it's greater than two
    Ḥ                                 double the result (2 if it's 3 or 4, 0 if it's 0, 1, or 2)
     ạ                                absolute difference (0 should take whatever the other thing's value is, 1+1 and 2+2 should give 2, 1+2 and 2+1 should give 1)
ạ1ẋ$0ẋ⁸¤;µ/€«þ/µ€z0z€0Z€Zz€0Z€ç"/o⁶Y  Main Link
               µ€                     For each rectangle stored as [[x1, x2], [y1, y2]]
         µ/€                          For each of [a, b] = [x1, x2] and [y1, y2], reduce it by (in other words, use a dyad on a size-2 list)
 1ẋ$                                  repeat [1]            times
ạ                                                abs(a - b)
        ;                             and append to
    0ẋ ¤                              [0] repeated   times
      ⁸                                            a
            «þ/                       and reduce by minimum outer product table (take the outer product table, by minimum, of the x results and the y results)
                                      [NOTE] At this point, we have a list of matrices with 0s as blanks and 1 as covered
                 z0z€0Z€Zz€0Z€        Make all of the matrices the same size:
                 z0                   zip, fill with 0 (all matrices are the same length, but not width, and now are lists of row-wise lists of rows)
                   z€0                zip each, fill with 0 (all rows are the same length within their row-wise lists, and are now lists of row-wise lists of columns)
                      Z€              zip each (flip rows back to lists of row-lists of rows)
                        Z             zip (flip back to matrices); however, if a matrix is smaller on both axes, its rows will not be the same length
                         z€0          zip each, fill with 0 (all rows in each matrix are the same length and the value is now a list of transposed matrices)
                            Z€        zip each (the value is now a list of matrices, all the same length, filled with 0 (empty space))
                              ç"/     reduce by (vectorized) the relation in the Helper Link (to combine all of the final values)
                                 o⁶   logical OR with " "; replace 0s with spaces
                                   Y  join with newlines (formatting)
\$\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.