3
1
Calculate the maximum number of circles of radius r that can fit in a rectangle with width x and height y. Write a function that take r, x and y as input and returns the number of circles that fit in the rectangle.
Mohamed Hadari
Posted 2018-11-03T15:31:26.773
Reputation: 55
12I would suggest to add some testcases so that we can know if any answer is correct. – tsh – 2018-11-03T15:44:08.463
5It appears to me that one could fit at least one more circle, by expanding the second-to-last row to have 10 circles in it, such that the last three rows touch each other orthogonally. Do we not have to handle such cases? – ETHproductions – 2018-11-03T15:56:10.230
5Would it make sense to just normalise and say
ris always1? This way there are only 2 inputs - I believe every answer will divide through byr. – Jonathan Allan – 2018-11-03T15:58:24.823@ETHproductions I was thinking about fitting more in too, but note that the description states "the circles touch each other in triangular shape". – Jonathan Allan – 2018-11-03T16:13:17.970
I want a test case for x=2, r=1. I think the right solution would be circles with a massive gap between, because there has to be place for a potential row between, but the row between is not filled, because x is to small. – Black Owl Kai – 2018-11-03T16:31:30.960
2Do we have to support floats or are x,y,r guaranteed to be whole numbers? – Black Owl Kai – 2018-11-03T16:34:48.673
@BlackOwlKai the description states "the circles touch each other in triangular shape" I believe this means a uniform triangular packing (which matches what is shown in the image). – Jonathan Allan – 2018-11-03T16:38:35.057
Is it guaranteed that a side of the rectangle is parallel to a side on the triangular grid? – user202729 – 2018-11-03T16:38:57.597
I suggest putting the challenge in sandbox before posting on main so possible issues can be resolved.
– user202729 – 2018-11-03T16:39:46.053@JonathanAllan Did you mean "so no"? – user202729 – 2018-11-03T16:40:33.463
2
Without the "triangular lattice" restriction we have https://math.stackexchange.com/questions/701/how-many-circles-of-a-given-radius-can-be-packed-into-a-given-rectangular-box , which is unsolved.
– user202729 – 2018-11-03T16:45:18.1271
Arbitrary rotation of the grid appears to be very complex (optimal pack of 3 circles in a square, they forms a triangular lattice) and probably not what OP intended. Temporarily VTC as unclear.
– user202729 – 2018-11-03T16:53:10.443@user202729 Ah, true - I suppose they do mean one side must be aligned but had not thought to that point - this certainly needs addressing. – Jonathan Allan – 2018-11-03T16:57:45.727
The title of the question "number of circles in a rectangle" takes precedence over "the circles touch each other in triangular shape". A user is not restricted from composing code which interprets the latter as a description of the image at the OP (base case) literally, and discarding that description where the number of circles can be optimized to exceed the base case, else the number of circles at the image at OP cannot be exceeded at all, nullifying the title of the question. – guest271314 – 2018-11-03T16:59:11.110
I think it’s a lovely question if there is no restriction on how the circles are packed. It’s also hard so maybe code-golf is not appropriate? – Anush – 2018-11-03T20:06:12.277
clear, but maybe hard to check currentcy. Suggest max contain then code golf – l4m2 – 2018-11-04T09:12:19.210
@guest271314 We don't have a rule that all restrictions must be put in the title (and obviously we should not, otherwise the title will become very long) – user202729 – 2018-11-04T11:25:04.237
@Ourous Why was the edit approved? – user202729 – 2018-11-04T11:25:58.573
@Anush except that we won't know if a solution is correct without a new paper on the topic :) – Jonathan Allan – 2018-11-04T15:51:48.783
@JonathanAllen Details, details...:) Maybe an optimization version would work where your have to output the largest packing you can make with a code golf tie break. – Anush – 2018-11-05T15:24:47.807