6
\$\begingroup\$

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:

  1. There are at least 3 people.
  2. The first person is at position (0, 0).
  3. The second person is at position (x, 0) for some x > 0.
  4. 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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user202729 Oct 21 '17 at 15:36
  • \$\begingroup\$ @user202729 I don't understand. Can you elaborate? \$\endgroup\$ – orlp Oct 21 '17 at 16:18
  • \$\begingroup\$ 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. \$\endgroup\$ – user202729 Oct 21 '17 at 16:21
  • \$\begingroup\$ @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. \$\endgroup\$ – orlp Oct 21 '17 at 16:43
  • \$\begingroup\$ 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 for 0.5^2, instead of [[0,0],[4,0]] or [[0,0],[5,0]] where in the worst case it wrong for 1. \$\endgroup\$ – user202729 Oct 21 '17 at 23:40
2
\$\begingroup\$

R, score = 4.708859

require(vegan)
solve_mmds<-function(dpf,noise=0,wgs=rep(1,nrow(dpf))){
  #MMDS
  v = wcmdscale(dpf+noise,2,add=TRUE,w=wgs)
  
  #center on first point
  v = sweep(v,2,v[1,])
  
  #rotate to adjust second point
  alpha = atan2(v[,2],v[,1])
  alpha_rot = alpha - alpha[2]
  radius = sqrt(apply(v^2,1,sum))
  v = cbind(cos(alpha_rot), sin(alpha_rot))*radius
  
  #flip to adjust third point
  if(v[3,2]<0){
    v[,2]=-v[,2]
  }
  
  #return
  v
}


N_input = length(input_data)
err_runs = rep(0,N_input)

for(i_input in c(1:N_input)){
  
  p = matrix(input_data[[i_input]],ncol=2,byrow=TRUE)
  n = nrow(p)
  
  dp = as.matrix(dist(p,upper=TRUE,diag=TRUE))
  dpf = floor(dp)
  
  v = solve_mmds(dpf)
  err_runs[i_input] = mean(apply( (p-v)^2, 1, sum))

  cat("test #", i_input," MSE:", err_runs[i_input],"\n")
}

cat("Average error: ", mean(err_runs)," \n")

Try it online

The core of the program is based on the Metric Multi-Dimensional Scaling (MDS) approach, which solves precisely the problem described by the OP. The idea is to start from a collection of dissimilarities between entities and infer the coordinates of the system. Some post-processing is required to rotate, translate and flip the solution.

There are at least three functions available in R to perform MDS. There is also one in sklearn in Python, in case. In the code above I settled for the weighted mds variant (function wcmdscale), mostly due to the possibility to add weights and to a slightly better performing correction for negative eigenvalues. There is a core function in R, called cmdscale, which could be used instead, and would result in a score of 5.77.

The code provided is predisposed to accept weights, as well as noise in the floored distance matrix. After testing, it seemed best to not use any of these options.

Sadly, the package "vegan" is not available on TIO. So, no live demonstration: my apologies for this inconvenience. Works on TIO like a charm.

Interestingly, the program significantly underperforms on the last two examples. Adding noise can help, but it worsens the performance on every other test case. It would be interesting to find out what makes these two test cases particularly difficult.

\$\endgroup\$
  • \$\begingroup\$ So what is the score for each tests? Also you can ask Dennis to add language / language feature to TIO at talk.tryitonline.net . \$\endgroup\$ – user202729 Oct 28 '17 at 12:45
  • \$\begingroup\$ TIO works now. The sample code prints out the scores for each test. \$\endgroup\$ – NofP Oct 28 '17 at 15:02
1
\$\begingroup\$

C++ (gcc), score = 5.94258

#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif // _GLIBCXX_DEBUG

#include <iostream> //{ and more includes
#include <vector>
#include <string>
#include <sstream>
#include <array>
#include <cstdio>
#include <cmath>
#include <random>
#include <cassert>
#include <limits>
//}

template <typename T>
struct point { //{
    T x, y;
    point () {};
    point (T x1, T y1) : x (x1), y (y1) {};
    point operator+(point p) const { return point(x+p.x, y+p.y); }
    void operator+=(point p)       { x+=p.x; y+=p.y; }
    point operator-(point p) const { return point(x-p.x, y-p.y); }
    void operator-=(point p)       { x-=p.x; y-=p.y; }
    point operator*(T a)     const { return point(x*a, y*a);}
    void operator*=(T a)           { x *= a; y *= a; }
    T norm()                 const { return x * x + y * y; }
    T dot  (point p)         const { return x*p.x + y*p.y; }
    T cross(point p)         const { return x*p.y - y*p.x; }
    bool operator==(point<T> p1) const { return x==p1.x && y==p1.y;}
    bool operator!=(point<T> p1) const { return ! (*this == p1);}
    bool operator<(point<T> p1)  const {
        if (x != p1.x) return x < p1.x;
        return y < p1.y;
    }
    template <typename T1>
    operator point<T1> () const {
        return point<T1>(x, y);
    }
};

template <typename T>
std::istream& operator>> (std::istream& str, point<T>& pt) {
    str >> pt.x >> pt.y;
    return str;
}

template <typename T>
std::ostream& operator<< (std::ostream& str, point<T> pt) {
    str << "(" << pt.x << ", " << pt.y << ")";
    return str;
}//}

typedef point<double> pt;

//{ Additional functions, for point<real_type> only (specialize for double here)
double angle(pt p) {
	return std::atan2(p.y, p.x);
}

pt rotate(pt p, double angle) {
	double sin = std::sin(angle), cos = std::cos(angle);
	return pt(p.x * cos - p.y * sin, p.x * sin + p.y * cos);
}

pt normalize(pt p) {
	return p * (1/std::sqrt(p.norm()));
}
//}

std::array<bool, 0x80> const valid_double_start = [](){
	std::array<bool, 0x80> valid_double_start;
	for (size_t i = 0; i < valid_double_start.size(); ++i)
		valid_double_start[i] = false;
	for (char c = '0'; c <= '9'; ++c)
		valid_double_start[c] = true;
	valid_double_start['-'] = valid_double_start['.'] = true;
	// there are also 'e' and probably 'p' but they are not at
	// the begin of a double value string representation
	return valid_double_start;
}();

double score(std::vector<pt>const& pts1, std::vector<pt>const& pts2) {
	double result = 0;
	for (size_t i = 0; i < pts1.size(); ++i)
		result += (pts1[i] - pts2[i]).norm();
	return (result / pts1.size());
}

std::vector<std::vector<double>> distmatrix (std::vector<pt>const& pts) {
	std::vector<std::vector<double>> result (pts.size(), std::vector<double>(pts.size()));
	for (size_t i = 0; i < pts.size(); ++i) {
		for (size_t j = 0; j < i; ++j)
			result[i][j] = result[j][i] =
			std::floor(std::sqrt((pts[i] - pts[j]).norm()));
//		result[i][i] = 0; // implicit when initialize 'result' vector
	}
	return result;
}

std::vector<pt> normalize (std::vector<pt> pts) {
	for (size_t i = 1; i < pts.size(); ++i) pts[i] -= pts[0];
	pts[0] = {0, 0};
	double angle = - ::angle(pts[1]);
	for (size_t i = 1; i < pts.size(); ++i) pts[i] = rotate(pts[i], angle);
	pts[1].y = 0;
	if (pts[2].y < 0)
		for (size_t i = 2; i < pts.size(); ++i) pts[i].y = -pts[i].y;
	return pts;
}

unsigned nDiff (std::vector<std::vector<double>> mat1, std::vector<std::vector<double>> mat2, double eps = 1e-10) {
	unsigned result = 0;
	assert(mat1.size() == mat2.size());
	for (size_t i = 1; i < mat1.size(); ++i)
		for (size_t j = 0; j < i; ++j)
			result += std::abs(mat1[i][j] - mat2[i][j]) > eps;
	return result;
}

std::vector<pt> pts; // use global variable to print progress

int constexpr n_iteration = 200;
std::vector<pt> solve_with_seed (
	std::vector<std::vector<double>>const& distmatrix, int seed
) {

	std::mt19937 engine (seed);
	std::vector<pt> result; result.reserve(distmatrix.size());
	std::uniform_real_distribution<double> dist (-100, 100);
	for (size_t i = 0; i < distmatrix.size(); ++i)
		result.emplace_back(dist(engine), dist(engine));

	for (int iteration = 0; iteration < n_iteration; ++iteration) {
		#ifndef NDEBUG
		if (iteration % 10 == 0) {
			auto norm_result = normalize(result);
			std::clog << "Iteration " << iteration << "; "
			<< "score = " << score(norm_result, pts) << '\n';
			std::clog << "[";
			for (pt p : norm_result) std::clog << p << ", ";
			std::clog << "\b\b]";

			std::clog << " (nDiff = " << nDiff(distmatrix, ::distmatrix(norm_result)) << ")\n";
		}
		#endif
		for (size_t i = 1; i < pts.size(); ++i)
			for (size_t j = 0; j < i; ++j) {
				pt vec_IJ = result[j] - result[i];
				double dist = std::sqrt(vec_IJ.norm()),
				floor_expected = distmatrix[i][j];
				double ndist = (dist + (floor_expected + .5)) / 2;
				ndist = std::max(floor_expected, ndist);
				ndist = std::min(floor_expected + 1, ndist);

				double delta_dist = (dist - ndist) / 2;
				vec_IJ = normalize(vec_IJ) * delta_dist;
				result[i] += vec_IJ;
				result[j] -= vec_IJ;

//				std::clog << "Numerical error = " << std::sqrt((result[i] - result[j]).norm()) - ndist << '\n';
			}
	}
	return normalize(result);
}

std::vector<pt> solve (
	std::vector<std::vector<double>>const& distmatrix
) {
	// just going to try some random values of seed.
	std::vector<pt> result; int minDiff = std::numeric_limits<int>::max();
	for (int seed : {123456789,987654321,69850,68942,4162,12012}) {
		std::vector<pt> r = solve_with_seed(distmatrix, seed);
		int d = nDiff(distmatrix, ::distmatrix(r));
		if (d < minDiff) {
			minDiff = d;
			result = r;
		}
	}
	return result;
}

int main() {
	std::string str;
	double sumscore = 0; unsigned ntest = 0;
	while (std::getline(std::cin, str)) {
		if (str.empty()) break;
		std::stringstream sst (str);
		std::vector<double> values;
		while (true) {
			int c = sst.peek();
			while (c != EOF && !valid_double_start[c]) {
				sst.get();
				c = sst.peek();
			}
			if (c == EOF ) break;
			double val;
			if (!(sst >> val)) {
				std::clog << "Invalid input. Stop reading.\n";
				break;
			}
			values.push_back(val);
		}
		if (values.size() % 2 != 0) {
			std::clog << "Number of double values is odd: " << values.size()
			<< ". Assuming the last value (" << values.back() << ") is redundant.\n";
			values.pop_back();
		}

		pts.resize(values.size() / 2);
		for (size_t i = 0; i < pts.size(); ++i) {
			pts[i].x = values[2*i];
			pts[i].y = values[2*i+1];
		}

		if (pts.size() < 3) {
			std::clog << "Need at least 3 points. Ignore input.\n";
			continue;
		}

		auto distmatrix = ::distmatrix(pts);

		std::vector<pt> result_pts = solve(distmatrix);

		double score = ::score(pts, result_pts);
		std::cout << "Test #" << ++ntest << " score: " << score << ", "
		<< "number of difference in distance matrix: " << nDiff(distmatrix, ::distmatrix(result_pts)) << '\n';
		sumscore += score;
	}

	std::cout << "Final score = " << (sumscore / ntest) << '\n';
}


Try it online!

The main part of the code is the solve function, which is given a floored distance matrix (as a 2D vector of double) and output a vector of point<double>. The rest of the code are score-calculator.

Idea: Start with a (seeded) random set of points, loop n_iteration = 200 times the operation: For each pairs of point, get their current distance and expected distance (which is estimated to be equal to the distance in the floored input matrix + 0.5), and then change the position of those two points to an appropriate position nearer to the expected distance.

For this program, the new length is calculated as min(max((old_length + expected_length) / 2, expected_length + 0.5), expected_length - 0.5, which is twice closer to the expected_length if the old_length is sufficiently close, and force it to change such that the absolute difference between new length and expected_length is no more than 1 if old_length is more than 2 units apart from the expected_length.

It also tries multiple seeds, and then pick the seed which gives least error in the resulting distance matrix.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.