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!

Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ x-axis extends rightwards and y-axis extends downward from the top-left corner? \$\endgroup\$ Commented 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\$ Commented Oct 23, 2017 at 13:43
  • \$\begingroup\$ @dzaima Yup. [...] \$\endgroup\$ Commented 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\$ Commented Mar 10, 2020 at 2:59
  • 1
    \$\begingroup\$ @JoKing Actually I will allow any of the four combinations. \$\endgroup\$ Commented Mar 10, 2020 at 3:30

9 Answers 9

Reset to default
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
Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Charcoal, 40 bytes

ＷＳ«≔Ｉ⪪ι ιＦ…§ι⁰§ι²«Ｊκ§ι¹ＵＭＫＤ⁻§ι³§ι¹↓§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:

ＷＳ«

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

≔Ｉ⪪ι ι

Split the line into a list of co-ordinates.

Ｆ…§ι⁰§ι²«

Loop over all the X co-ordinates.

Ｊκ§ι¹

Jump to the top of the column.

ＵＭ

Map over each of...

ＫＤ⁻§ι³§ι¹↓

... 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 Ｉ¬Σλ works here to save 1 byte.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ :| did i mess something up tio.run/… \$\endgroup\$ Commented Oct 26, 2017 at 13:46
  • \$\begingroup\$ @ASCII-only Bug in my workaround - I can print an \n instead I guess... \$\endgroup\$ Commented 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 ' ',.
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 34 \$\endgroup\$ Commented May 20, 2020 at 1:13
  • \$\begingroup\$ @Bubbler, Thank you. \$\endgroup\$ Commented 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!

Improve this answer
\$\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!

Improve this answer
\$\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.

Improve this answer
\$\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\$ Commented 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\$ Commented 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\$ Commented 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
Improve this answer
\$\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)
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.