This challenge is similar to my previous one, but has a twist that makes it significantly more difficult.
There are n people on a 2D plane. Using distances between them we're going to find their positions. You may make four assumptions:
- There are at least 3 people.
- The first person is at position (0, 0).
- The second person is at position (x, 0) for some x > 0.
- The third person is at position (x, y) for some y > 0.
However, all distances are floored to integers! For example, if the actual distance between two people is 4.7 units, your program will see the distance 4 as input instead.
So your challenge is to write a program or function that given a 2D array of floored distances (where D[i][j]
gives the distance between person i
and j
) returns a list of their coordinates.
The challenge here is that you have incomplete information, and must try to extract as much precision as possible. Therefore this challenge is not a code golf, instead it's a code challenge, and the winner is the answer that returns the most accurate results.
Scoring
I will provide a series of arrays of coordinates. It is up to you to turn these arrays into 2D distance matrices and flooring each element in these matrices (if I were to do that here this question would get way too large).
For a certain input use your answer to predict the coordinates of each person. Then, for each person calculate the squared distance between the prediction and actual position. Sum all these and divide by the number of people in the input. That is your score for this input.
The total score of your answer is the average score you get for all of the following inputs:
[(0, 0), (0.046884, 0), (-4.063964, 0.922728), (-3.44831, -6.726776), (-0.284375, -0.971985)]
[(0, 0), (0.357352, 0), (-1.109721, 1.796241), (-7.894467, -3.086608), (-3.74066, -1.528463)]
[(0, 0), (6.817717, 0), (-6.465707, 0.705209), (-2.120166, 3.220972), (-2.510131, 8.401557)]
[(0, 0), (0.394603, 0), (-4.097489, 0.957254), (-5.992811, 1.485941), (-2.724543, -3.925886)]
[(0, 0), (6.686748, 0), (6.088099, 0.22948), (8.211626, -4.577765), (-1.98268, -4.764555)]
[(0, 0), (2.054625, 0), (0.75308, 0.497376), (6.987932, -5.184446), (0.727676, -5.065224)]
[(0, 0), (6.283741, 0), (-1.70798, 5.929428), (2.520053, 6.841456), (-2.694771, -1.816297)]
[(0, 0), (1.458847, 0), (5.565238, 7.756939), (-4.500271, 4.443), (-0.906575, 3.654772)]
[(0, 0), (0.638051, 0), (-2.37332, 0.436265), (-8.169133, -0.758258), (-7.202891, -2.804207)]
[(0, 0), (1.101044, 0), (-1.575317, 6.717197), (-2.411958, -7.856072), (-4.395595, 2.884473)]
[(0, 0), (7.87312, 0), (-0.320791, 2.746919), (-1.4003, 0.709397), (-0.530837, -0.220055), (-3.492505, -7.278485), (2.401834, 2.493873), (0.911075, -5.916763), (4.086665, -5.915226), (2.801287, 5.409761)]
[(0, 0), (0.304707, 0), (-1.709252, 0.767977), (-0.00985, -0.356194), (-2.119593, 3.353015), (1.283703, 9.272182), (6.239, -0.455217), (7.462604, 1.819545), (0.080977, -0.026535), (-0.282707, 6.55089)]
[(0, 0), (3.767785, 0), (0.133478, 0.19855), (-0.185253, -5.208567), (-6.03274, 6.938198), (5.142727, -1.586088), (0.384785, 0.532957), (3.479238, -1.472018), (3.569602, 8.153945), (-0.172081, 2.282675)]
[(0, 0), (0.445479, 0), (-3.3118, 8.585734), (0.071695, -0.079365), (2.418543, 6.537769), (1.953448, 0.511852), (-1.662483, -5.669063), (0.01342, 0.097704), (0.919935, 1.697316), (2.740839, -0.041325)]
[(0, 0), (3.281082, 0), (-6.796642, 5.883912), (-3.579981, -2.851333), (-1.478553, 6.720389), (3.434607, -9.042404), (7.107112, 2.763575), (-4.571583, 1.100622), (-1.629668, 1.235487), (-3.199134, 0.813572)]
[(0, 0), (5.278497, 0), (-4.995894, 3.517335), (-0.012135, 3.444023), (0.364605, -0.49414), (1.73539, 1.265443), (-7.289383, -3.305504), (-7.921606, 5.089785), (-1.002743, -0.554163), (-8.99757, -3.572637)]
[(0, 0), (2.331494, 0), (1.83036, 2.947165), (-5.520626, 1.519332), (5.021139, -4.880601), (-0.318216, -0.063634), (-5.204892, -5.395327), (-0.92475, -0.090911), (-0.19149, -2.188813), (-0.035878, 0.614552)]
[(0, 0), (2.981835, 0), (-3.909667, 2.656816), (-0.261224, -2.507234), (-7.35511, -3.65201), (1.198829, 5.328221), (-5.139482, -4.320811), (-3.253523, 2.367497), (6.254513, 1.565134), (3.13451, 4.595651)]
[(0, 0), (1.059838, 0), (-0.849461, 7.87286), (2.108681, 0.717389), (-0.065587, -0.007163), (2.818824, 5.529878), (2.413443, 4.102863), (-3.050506, -2.541446), (-1.215169, -4.818011), (-1.671743, 2.539397)]
[(0, 0), (5.036602, 0), (-1.627921, 1.813918), (-9.285855, 1.277063), (2.271804, -0.51118), (-7.070704, 2.252381), (6.125956, -4.278879), (1.000949, -1.38177), (-0.67657, -2.747887), (2.820677, -5.718695)]
[(0, 0), (0.733516, 0), (6.619559, 1.368964), (-0.047351, 0.545139), (-4.518243, -7.506885), (3.31011, -4.329671), (3.885474, -1.535834), (-3.952488, -1.94899), (1.402441, 7.538954), (2.385809, 4.042365), (-6.403547, 3.623895), (3.742502, 0.025475), (1.944868, -2.972475), (-0.514566, -1.015531), (-0.08634, 5.140751)]
[(0, 0), (2.374024, 0), (-1.016305, 1.31073), (2.176473, -1.357629), (0.181825, 2.107476), (-0.978214, -3.436398), (0.828254, -0.39516), (2.981311, -6.761157), (1.517599, 5.009197), (8.063442, 0.930487), (4.628231, 7.749696), (3.810604, 4.671208), (1.158015, 2.914197), (-9.230353, -0.473591), (-9.031469, -4.206725)]
[(0, 0), (5.733822, 0), (1.394054, 1.432354), (1.556614, 5.691443), (3.665168, 7.199478), (-0.670337, 0.396217), (4.144468, 2.959243), (-6.129783, -7.048069), (-3.230162, 3.116924), (-6.365913, 3.727042), (-0.174385, 0.253418), (-0.454495, -4.415929), (5.815488, 1.443031), (-4.288448, 0.619174), (1.957015, 0.784202)]
[(0, 0), (6.550779, 0), (-8.592692, 1.728506), (-6.460692, 2.344509), (8.359129, 4.578714), (3.593451, -4.172634), (8.697976, -2.379752), (4.27242, 5.296418), (2.920394, -4.520174), (0.662004, 2.171769), (1.879771, -1.873537), (0.769374, 3.570321), (-3.438699, -3.255416), (3.23342, -3.220256), (-0.002136, -5.646753)]
[(0, 0), (5.013665, 0), (-0.543516, 9.981648), (8.378266, 5.33164), (4.759961, -2.007708), (2.88554, 1.069445), (-6.110542, -6.253516), (0.292062, -0.052982), (-4.869896, -1.251445), (1.61841, 7.980471), (-0.313257, 0.515709), (8.673848, -2.269644), (-0.446207, -0.568228), (3.015721, -2.819861), (1.160386, -5.897356)]
[(0, 0), (0.437257, 0), (-3.127834, 8.941175), (0.785858, 1.99155), (2.005894, -6.723433), (1.332636, -6.214795), (3.149412, 7.17296), (-5.350834, -5.106189), (1.447561, 0.910621), (3.032259, -7.977927), (1.520669, 5.121877), (-1.075969, 0.098313), (1.015673, -5.244922), (3.575391, 5.270148), (-9.160492, 2.943283)]
[(0, 0), (3.63663, 0), (5.448045, 8.287277), (1.314494, -0.164441), (-1.941398, 4.223086), (5.025181, 0.495811), (-8.466786, -2.933392), (-0.139755, 0.730451), (-0.098497, -0.587856), (-3.337111, -1.238969), (2.142947, 2.521078), (0.352537, 5.4194), (-4.49191, 5.261929), (2.198984, -3.781113), (3.525393, 1.150581)]
[(0, 0), (4.540155, 0), (-7.248917, 2.368607), (2.434071, 1.763899), (3.990914, 1.135211), (-5.422214, -5.785259), (0.526037, -0.888364), (-0.370255, 8.515669), (0.77125, 4.48859), (3.9838, -2.3101), (-2.993973, -0.775446), (-1.731491, -1.028441), (-0.184254, 0.281876), (0.048732, 0.222435), (0.108646, -0.344878)]
[(0, 0), (4.934251, 0), (7.472259, 4.693888), (0.057108, -0.038881), (-0.276457, -0.157808), (-6.745232, -0.357168), (5.979037, -0.653591), (-3.969328, -6.050715), (4.19821, -1.883165), (-4.294607, -0.407446), (-6.11544, 0.480539), (1.193587, -1.028919), (-0.387421, 2.036394), (5.78394, 1.333821), (4.178077, 4.286095)]
[(0, 0), (7.547164, 0), (0.989783, 1.074185), (0.192979, 0.210046), (6.528904, 0.400088), (5.602168, 5.791553), (4.058506, 3.995028), (-1.033977, -5.44405), (5.767663, -6.702417), (4.401684, -3.097193), (-0.821263, 4.624133), (6.031465, 6.544092), (7.188866, 1.599597), (5.327328, 3.51571), (1.305662, 7.488827)]
[(0, 0), (0.638053, 0), (7.279348, 5.416438), (-6.495944, -1.385692), (5.348119, 6.89312), (-5.145817, -5.640294), (2.909321, -3.139983), (7.052144, 3.902919), (2.467506, 1.362787), (3.469895, -7.977336), (7.598683, -5.947955), (-0.679492, 9.140908), (-3.310304, 3.134427), (-0.83399, 5.797306), (4.08935, 0.830119), (-7.764758, -4.403114), (5.183087, -8.528744), (-0.75072, 6.163092), (-0.692329, -0.225665), (2.0628, -2.008365)]
[(0, 0), (9.468635, 0), (2.005581, 2.669352), (3.416536, 6.9941), (-3.293394, 0.864229), (-1.044833, 2.243219), (6.011018, 4.014313), (-0.959567, 9.620265), (-1.855409, 1.890371), (-0.629015, -1.383614), (4.087875, -2.203917), (3.286183, -7.748879), (-7.781181, -5.295325), (3.28653, -0.930535), (3.973893, -1.784441), (-7.7541, 4.355823), (1.522453, -1.960952), (5.085025, -1.511887), (8.401342, -2.139507), (-1.727888, 0.7952)]
[(0, 0), (8.617779, 0), (-7.012573, 5.883927), (-3.508725, -6.838323), (6.676063, 6.884947), (8.297052, -0.134775), (7.416737, 5.915766), (-5.10108, -7.183776), (-4.651823, 5.434926), (-1.099239, -0.238062), (-0.313045, 0.354853), (-7.592061, 5.408053), (0.566482, 0.652099), (-3.551817, -3.365006), (8.514655, 4.653756), (-4.249357, -2.130864), (1.181348, -1.22839), (2.469081, 1.110794), (1.831897, -1.552467), (-5.892299, -1.919411)]
[(0, 0), (2.407206, 0), (-6.771008, 0.810524), (-3.840048, -0.152269), (7.109171, -5.609477), (-7.391481, 5.639112), (-8.670299, 2.742321), (0.586435, 4.542551), (-0.442438, 0.107817), (4.31145, -1.409808), (-4.534678, -1.504437), (4.680038, -3.080315), (-4.973063, 5.638478), (6.127056, -7.491446), (2.291953, -2.357609), (3.510856, -9.171005), (3.971143, -8.515823), (0.049413, -5.842664), (1.058161, -0.21883), (7.093364, -3.604422)]
[(0, 0), (6.969461, 0), (4.338403, 5.197497), (0.369553, -0.770371), (8.882643, 1.450294), (2.124852, -1.210185), (-3.046623, -4.395661), (7.716904, 4.60951), (-0.83271, -0.854575), (-2.333383, -0.308884), (-6.347966, 3.124373), (0.832848, -1.892136), (1.446553, 1.613845), (-2.241092, -6.53878), (5.004282, 5.401177), (3.31202, 0.432188), (0.164548, 1.23087), (9.860844, -0.125136), (0.133559, -0.202543), (2.686551, 1.013555)]
[(0, 0), (9.107655, 0), (5.455882, 3.54979), (-0.681513, 2.950275), (7.369848, 4.050426), (5.320211, -8.288623), (-5.315311, 4.632769), (-2.801207, -3.00623), (2.502035, -2.085464), (-0.645319, -4.854856), (3.639806, -8.669185), (-0.732853, 2.379454), (-8.722855, 2.483643), (-0.03048, 1.845021), (-6.904949, -2.596416), (0.685437, 1.042775), (-5.182001, -2.617796), (1.595501, 0.885512), (-8.567463, -0.607195), (-5.456613, 5.81163)]
[(0, 0), (1.669656, 0), (-3.385149, 6.655961), (-1.501983, -0.746686), (1.962876, -0.780073), (0.51437, -4.130592), (1.825567, 0.531272), (-4.188001, 0.514048), (-5.894689, 1.726502), (-1.429067, -3.558197), (4.605078, 2.060605), (1.670708, -8.99749), (5.44004, -5.315796), (-0.619392, 1.785159), (-2.854087, 1.696694), (4.974886, 6.291052), (-0.699939, -5.930564), (-2.35508, -0.057436), (-0.804635, -0.687497), (2.289458, 1.946817)]
[(0, 0), (3.626795, 0), (5.048495, 1.581758), (0.154465, 3.132534), (-4.862419, 7.051311), (3.927243, -0.408956), (-7.41798, -0.313768), (1.987639, -7.957834), (-1.100923, -1.442563), (1.949075, -0.382901), (5.696638, 3.400352), (-1.121574, 1.315934), (-4.37434, 4.937007), (-1.244524, -7.36647), (9.138938, 4.035956), (-0.207342, -4.257523), (-1.298235, 5.950812), (2.17008, 1.116468), (-1.410162, 4.861598), (4.69532, 2.076335)]
[(0, 0), (9.787264, 0), (-4.65872, 0.957699), (-2.813155, -1.174551), (-0.445703, 0.362518), (2.920405, 0.914672), (-1.63431, 0.048213), (-0.534393, -2.389697), (-0.105639, -1.589822), (-0.100723, 8.648806), (-6.894891, 4.8257), (7.417014, 2.868825), (-0.84031, -0.322606), (-0.802219, 1.209803), (7.808668, 1.700949), (-3.270161, -3.463587), (-1.118415, 0.713057), (4.130249, 0.824635), (4.664258, 5.993324), (2.575522, -1.031243)]
[(0, 0), (6.514721, 0), (-2.2931, 3.6007), (3.388059, 1.102576), (-1.777694, -2.809783), (3.431761, 6.534511), (-8.13158, -2.940151), (-4.856169, 2.834183), (-0.706068, -0.93294), (-0.393184, -4.989653), (4.480243, -4.107001), (1.681165, 0.611419), (4.442544, -0.536704), (4.90654, -7.356498), (-8.722645, 1.203365), (-2.067292, -4.134382), (-3.002458, 7.891842), (1.398419, -1.279873), (0.237866, 0.010691), (6.879955, -2.882286)]
[(0, 0), (1.421587, 0), (-0.615169, 0.286873), (0.848122, -2.730297), (0.220832, 0.89274), (4.588547, 8.497067), (-5.079677, -8.428552), (-3.170092, 2.418608), (1.309388, -3.658275), (1.639533, -2.364448), (-1.327656, 1.006565), (-0.475542, 0.298309), (5.430131, -8.343581), (8.430933, 4.118178), (-2.090712, -0.470172), (1.146227, -6.664852), (-0.542811, 1.909997), (0.439509, 6.112737), (0.343281, 0.630898), (-3.673348, 5.101854), (-0.072445, 5.784645), (4.895027, -7.960275), (-9.633185, -1.688371), (8.059592, -5.178718), (-2.334299, 1.217686)]
[(0, 0), (5.456611, 0), (0.181969, 2.084064), (0.89351, -2.507042), (1.570701, 1.202458), (0.814632, 1.883803), (2.790854, 5.8582), (0.699228, 2.377369), (-0.463356, 5.162464), (1.166769, 4.739348), (-4.652182, 5.553297), (-1.123396, 4.186443), (-0.327375, 0.45977), (-0.395646, -4.122381), (0.652084, -0.696313), (0.716396, 2.005553), (0.73846, -7.361414), (-1.912492, 3.937217), (-0.162445, -2.681668), (-0.133005, -0.910646), (2.194447, -4.169833), (-3.132339, -3.079166), (-3.078943, -1.410719), (-1.365236, -4.103878), (2.044671, -0.831881)]
[(0, 0), (1.382529, 0), (5.031547, 7.747151), (-0.49526, 0.019819), (-7.918566, -1.919355), (1.046601, -4.397131), (3.113731, 8.325339), (-1.700401, 1.511139), (-2.699135, -5.052298), (3.434862, -2.609676), (-4.506703, -0.424842), (0.154899, 3.782215), (1.373067, 4.412563), (4.548762, 2.096691), (-0.0275, -2.604761), (4.462809, 1.533662), (-2.016089, -3.481723), (7.024583, 6.980284), (0.254207, -7.964855), (-2.055224, -1.374547), (-3.185323, -3.753214), (-0.479636, -7.476727), (2.208698, -6.374003), (0.24381, -0.620774), (-0.551312, -3.796487)]
[(0, 0), (3.442359, 0), (-5.045461, 1.685484), (0.072923, 1.158112), (-1.347292, 2.626515), (1.982477, 4.374474), (-3.188879, -4.020849), (-0.430788, 0.118491), (0.725544, 1.992762), (-2.893352, -4.311321), (-6.871016, -2.359638), (1.406456, 1.734539), (2.029903, 6.151807), (7.565244, 1.948656), (-6.420158, 0.698035), (-4.873019, 3.593625), (9.548917, -0.45405), (-8.701737, -1.872887), (-7.941202, -1.4121), (-5.995713, 0.555241), (-5.704163, -2.868896), (-2.677936, -1.924243), (-3.460593, -8.679839), (0.631064, -0.433745), (1.18902, -1.496815)]
[(0, 0), (6.537782, 0), (-6.75348, 0.404049), (-5.348818, 5.082766), (-3.738518, -7.824984), (4.513721, -7.740162), (-7.707575, 3.393118), (-0.11626, 0.439479), (0.12586, -2.885467), (4.952966, 5.673672), (2.56597, -0.333544), (-4.60141, 2.716012), (-1.865207, 1.826155), (3.234169, -0.966176), (-5.977172, 1.660029), (-7.968728, 0.889721), (-0.028198, 0.153274), (-5.427989, 8.150441), (-3.708225, -0.777001), (3.513778, 0.529579), (6.309027, 0.399666), (0.542878, 1.900558), (-0.633748, -4.971474), (5.340487, -2.474143), (-0.805431, -8.633636)]
[(0, 0), (0.211756, 0), (3.03609, 1.381372), (1.472087, 3.505701), (-0.198393, -0.284868), (4.290257, -7.630449), (-0.120326, -0.047739), (3.167345, -1.144179), (7.791272, 6.043579), (6.125765, -6.3722), (-0.178091, 9.313027), (-4.177894, -0.704969), (-2.950708, 1.716094), (-0.016133, -0.105582), (-5.962467, 6.088385), (0.901462, 0.58075), (2.063274, -0.221478), (-0.430464, 0.9548), (4.824813, -4.037669), (0.863528, 8.321907), (2.693996, -0.380075), (0.879924, 4.243756), (-7.759599, -2.81635), (2.58409, -2.225758), (5.515442, -7.445861)]
[(0, 0), (0.958126, 0), (-0.566246, 3.074569), (2.666409, -4.784584), (-5.490386, 1.820646), (0.505378, 0.261745), (-0.122648, -9.791207), (0.569961, 1.044212), (-8.917451, -1.667965), (-7.374214, -1.193314), (-4.559765, -2.486695), (2.367622, 1.707526), (0.762113, -5.553413), (-9.62438, -2.077561), (-0.072526, -0.072188), (-2.051266, -5.410767), (-6.656983, -1.824092), (1.170361, 2.019313), (2.689391, -3.998207), (1.814094, 1.782214), (0.498034, -9.437937), (0.87507, 0.670687), (-8.114628, 4.823256), (2.693849, 6.952855), (-0.005543, -0.01139)]
[(0, 0), (1.703854, 0), (1.091391, 2.171906), (5.559313, -0.310439), (-0.396107, -0.771272), (-5.136147, 7.769235), (8.969736, 0.885092), (3.541436, -6.530927), (-0.461503, -5.877802), (-6.108795, -5.163834), (3.698654, 3.749293), (8.049228, 2.056624), (-6.022241, -0.657227), (-8.701763, 4.803845), (1.225822, -2.070325), (2.099514, 5.191076), (0.500653, -0.104261), (-0.581698, -5.755634), (-5.150133, -8.269633), (2.559925, 6.839805), (-0.149545, 4.456742), (1.43855, 1.865402), (3.439778, -4.954683), (-4.18711, 7.244959), (0.640683, 0.907557)]
[(0, 0), (6.577004, 0), (0.042196, 0.025522), (8.61361, -0.689878), (5.407545, 1.709241), (-4.724503, 3.123675), (4.329227, -5.283993), (-1.238506, -1.104368), (-0.758244, 1.882281), (3.851691, -0.571509), (-0.229269, 7.452942), (2.833834, -6.742377), (-8.49992, 1.912219), (3.102788, -9.456966), (-0.420271, 2.449342), (4.123196, -0.512152), (5.893872, -3.689055), (-3.801056, -3.486555), (-3.576364, 3.448325), (-0.397213, -0.010559), (-4.519186, 4.525627), (2.720825, 6.0414), (0.918962, -0.430301), (2.217531, -3.056907), (0.912148, -1.487924)]
[(0, 0), (0.170063, 0), (1.088807, 2.795493), (5.884358, -1.914274), (9.333625, -0.111168), (7.168328, 4.042127), (2.558513, -0.146732), (-8.011882, -2.358709), (-0.374469, -6.591334), (2.495474, 1.011467), (0.094949, -0.351228), (7.0753, 1.26426), (6.614842, 4.664073), (-2.777323, 7.287667), (3.280189, -6.811248), (-7.254853, -1.472779), (7.147915, 1.932636), (-3.431701, 3.030416), (-0.863222, -1.177363), (0.512901, -0.258635), (-5.614965, 0.462802), (3.452843, -6.869839), (7.475845, -0.353582), (0.067355, 0.298013), (4.39831, -8.5387)]
It's not allowed to optimize specifically for this set of inputs. I may change these inputs to any others at my discretion.
Lowest score wins.
[[0,4],[4,0]]
, the program should return[[0,0],[4.5,0]]
so that in the worst case it only wrong for0.5^2
, instead of[[0,0],[4,0]]
or[[0,0],[5,0]]
where in the worst case it wrong for 1. \$\endgroup\$