6
1
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.
Problem: If the program result produce the exact same distance matrix as the test case, it is impossible to determine whether the result is correct. I suggest calculate the difference between the distance matrices instead. – user202729 – 2017-10-21T15:36:29.367
@user202729 I don't understand. Can you elaborate? – orlp – 2017-10-21T16:18:53.740
Assume that the program find coordinates A, and the input coordinates is B (B is different from A), which happens to have the same floored distance matrix. In that case I think the program should not be punished because "guessed" the input coordinates wrongly. – user202729 – 2017-10-21T16:21:21.863
@user202729 Well, I disagree. The whole point of this challenge is to make an algorithm that figures out the best possible guess for the input coordinates with limited information. The fact that there are potential 'false positives' changes nothing about this, in fact it makes the problem more complicated and interesting. – orlp – 2017-10-21T16:43:59.513
You means, the program have to find the position that minimize the maximize possible error? Like, if the (floored) matrix is
[[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. – user202729 – 2017-10-21T23:40:26.180@user202729 If your answer would be optimal, yes it would account for that. – orlp – 2017-10-22T00:19:18.260
I have the feeling that even with the constraints on the position of the first three people, when the input are only pairwise distances, the solution may be correct up to a rotation transformation. How should we account for that? – NofP – 2017-10-26T08:24:34.237
@NofP The fact that the second person is guaranteed to be at (x, 0) for some x > 0 eliminates all rotational symmetry. – orlp – 2017-10-26T18:10:19.893