canReachCorner.ts

canReachCorner.spec.ts

import { calcDist, canReachCorner, getRectIntersections, intersectsCircle, intersectsRect, isPointWithinBounds, solutionsForY, solutionsForX, getCircleIntersections } from "./leet";

describe('leet', () => {

  describe('calcDist', () => {

    it('calcs dist', () => {
      expect(calcDist([0, 0], [0, 1])).toEqual(1);
    });

    it('calcs dist 2', () => {
      expect(calcDist([0, 0], [1, 1])).toEqual(Math.sqrt(2));
    });

  });

  describe('intersectsCircle', () => {

    it('intersects exactly on diagonal edge', () => {
      expect(intersectsCircle([0, 0, Math.sqrt(2)/2], [1, 1, Math.sqrt(2)/2])).toEqual(true);
    });

    it('intersects overlapping on edge', () => {
      expect(intersectsCircle([0, 0, 1], [0, 2, 1])).toEqual(true);
    });

    it('intersects overlapping inner', () => {
      expect(intersectsCircle([0, 0, 1], [1, 1, 1])).toEqual(true);
    });

    it('does not intersect', () => {
      expect(intersectsCircle([0, 0, .5], [1, 1, .5])).toEqual(false);
    });

  });


  describe('isPointWithinBounds', () => {

    it('is within bounds', () => {
      expect(isPointWithinBounds([2, 2], [1, 1])).toEqual(true);
    });

    it('is not within bounds', () => {
      expect(isPointWithinBounds([2, 2], [3, 2])).toEqual(false);
    });

    it('is lies on bounds', () => {
      expect(isPointWithinBounds([2, 2], [0, 2])).toEqual(false);
    });

  });


  describe('solutions', () => {

    it('intersects once on y = 0', () => {
      expect(solutionsForX(0, [2, 2, 2])).toEqual([2]);
    });

    it('intersects twice on y = 0', () => {
      expect(solutionsForX(0, [0, 0, 1])).toEqual([1, -1]);
    });

    it('intersects once on y = 2', () => {
      expect(solutionsForX(2, [1, 1, 1])).toEqual([1]);
    });

    it('intersects twice on y = 0', () => {
      expect(solutionsForX(0, [1, 0, 1])).toEqual([2, 0]);
    });

    it('intersects once on y = 0', () => {
      expect(solutionsForX(0, [2, 1, 1])).toEqual([2]);
    });

    it('intersects once on x = 0', () => {
      expect(solutionsForY(0, [2, 1, 1])).toEqual([]);
    });

    it('test', () => {
      expect(solutionsForX(0, [2, 2, 1])).toEqual([]);
    });

  });

  describe('getCircleIntersections', () => {

    it('circles with equal radius on same y', () => {
      expect(getCircleIntersections([10, 15, 10], [25, 15, 10])).toEqual([
        [17.5, 8.385621722338525],
        [17.5, 21.614378277661476],
      ]);
    });

    it('circles reflected across y = x', () => {
      expect(getCircleIntersections([2, 10, 7], [10, 2, 7])).toEqual([
        [3.0845240525773496, 3.0845240525773496],
        [8.91547594742265, 8.91547594742265],
      ]);
    });

  });

  describe('getRectIntersections', () => {

    it('test', () => {
      expect(getRectIntersections(15, 15, [20, 2, 13])).toEqual([
        [15, 14],
        [15, -10],
        [32.84523257866513, 0],
        [7.154767421334871, 0],
        [20, 15],
      ]);
    });

    it('test', () => {
      expect(getRectIntersections(4, 4, [2, 0, 1])).toEqual([
        [3, 0],
        [1, 0],
      ]);
    });

  });

  describe('interesectsRect', () => {

    it('intersects exactly on all edges', () => {
      expect(intersectsRect(2, 2, [1, 1, 1])).toEqual([1, 3, 4, 2]);
    });

    it('overlaps on all edges', () => {
      expect(intersectsRect(2, 2, [1, 1, 1.2])).toEqual([1, 3, 4, 2]);
    });

    it('does not intersect', () => {
      expect(intersectsRect(2, 2, [1, 1, 0.5])).toEqual([]);
    });

    it('intersects exactly on bottom edge', () => {
      expect(intersectsRect(4, 4, [2, 1, 1])).toEqual([4]);
    });

    it('intersects exactly on top edge', () => {
      expect(intersectsRect(4, 4, [2, 3, 1])).toEqual([2]);
    });

    it('intersects exactly on left edge', () => {
      expect(intersectsRect(4, 4, [1, 2, 1])).toEqual([1]);
    });

    it('intersects exactly on right edge', () => {
      expect(intersectsRect(4, 4, [3, 2, 1])).toEqual([3]);
    });

    it('intersects at top right corner y = h', () => {
      expect(intersectsRect(1, 1, [2, 1, 1])).toEqual([2]);
    });

    it('intersects at top right corner x = w', () => {
      expect(intersectsRect(1, 1, [1, 2, 1])).toEqual([2]);
    });

    it('intersects at top right corner x > w and y > h', () => {
      expect(intersectsRect(1, 1, [2, 2, Math.sqrt(2)])).toEqual([3, 2]);
    });

    it('does intersect at bottom left corner y = 0', () => {
      expect(intersectsRect(1, 1, [-1, 0, 1])).toEqual([4]);
    });

    it('does intersect at bottom left corner x = 0', () => {
      expect(intersectsRect(1, 1, [0, -1, 1])).toEqual([4]);
    });

    it('does intersect at bottom left corner x < 0 and y < 0', () => {
      expect(intersectsRect(1, 1, [-1, -1, Math.sqrt(2)])).toEqual([1, 4]);
    });

    it('x < 0 && 0 < y < h', () => {
      expect(intersectsRect(2, 2, [-1, 1, 1])).toEqual([1]);
    });

    it('y < 0 && 0 < x < w', () => {
      expect(intersectsRect(2, 2, [1, -1, 1])).toEqual([4]);
    });

    it('x > w && 0 < y < h', () => {
      expect(intersectsRect(2, 2, [3, 1, 1])).toEqual([3]);
    });

    it('y > w && 0 < x < w', () => {
      expect(intersectsRect(2, 2, [1, 3, 1])).toEqual([2]);
    });

    it('intersects bottom right edges', () => {
      expect(intersectsRect(3, 4, [2, 1, 1])).toEqual([3, 4]);
    });
  });

  describe('canReachCorner', () => {
    it('cannot reach corner 2', () => {
      expect(canReachCorner(8, 8, [[1, 4, 1], [3, 4, 1], [5, 4, 1], [7, 4, 1]])).toEqual(false);
    });

    it('cannot reach corner if second circle includes retangle', () => {
      expect(canReachCorner(4, 4, [[2, 1, 1], [2, 2, 8]])).toEqual(false);
    });

    it('cannot reach corner with overlapping circles reflected across y = x and touching all edges', () => {
      expect(canReachCorner(3, 3, [[2, 1, 1], [1, 2, 1]])).toEqual(false);
    });

    it('cannot reach corner', () => {
      expect(canReachCorner(2, 2, [[1, 1, 1]])).toEqual(false);
    });

    it('cannot reach corner if circle includes rectangle', () => {
      expect(canReachCorner(2, 2, [[1, 1, 5]])).toEqual(false);
    });

    it('cannot reach corner if circle overlaps top corner', () => {
      expect(canReachCorner(4, 4, [[5, 5, 2]])).toEqual(false);
    });

    it('can reach corner', () => {
      expect(canReachCorner(2, 2, [[1, 1, 0.5]])).toEqual(true);
    });

    it('can reach corner if circle intersects only at corner', () => {
      expect(canReachCorner(4, 4, [[5, 5, 1]])).toEqual(true);
    });

    it('can reach corner if circle exists outside bounds entirely', () => {
      expect(canReachCorner(3, 3, [[5, 5, 1]])).toEqual(true);
    });

    it('can reach corner if circle intersects bottom right only', () => {
      expect(canReachCorner(3, 4, [[2, 1, 1]])).toEqual(true);
    });

    it('cannot reach corner if circle includes entire rectangle', () => {
      expect(canReachCorner(5, 7, [[2, 2, 7]])).toEqual(false);
    });

    it('can reach corner if circle intersections are outside bounds', () => {
      expect(canReachCorner(2, 2, [[2, 10, 7], [10, 2, 7]])).toEqual(true);
    });

    it('can reach corner if circle intersections are outside bounds actual test case', () => {
      expect(canReachCorner(3, 3, [[2, 1000, 997], [1000, 2, 997]])).toEqual(true);
    });

    it('can reach corner if circle intersections on leetcode test case', () => {
      expect(canReachCorner(500000000, 500000000, [[499980000,699999999,200000000],[500020000,300000001,200000000]])).toEqual(true);
    });

    it('cannot reach corner if circle intersections on leetcode test case', () => {
      expect(canReachCorner(3, 3, [[7, 6, 5]])).toEqual(false);
    });

    it('leet case n', () => {
      expect(canReachCorner(8, 8, [[1,4,1],[3,4,1],[5,4,1],[7,4,1]])).toEqual(false);
    });

    it.skip('does not exceed time limit', () => {
      const start = new Date().getTime();
      expect(canReachCorner(1418, 1354, [[1112,300,300],[766,282,282],[1256,847,162],[1413,180,5],[973,21,21],[617,121,121],[88,550,88],[568,1059,295],[676,1133,221],[779,4,4],[101,288,101],[1127,823,291],[742,605,605],[1057,18,18],[1322,799,96],[991,395,395],[1350,421,68],[371,875,371],[1238,899,180],[1357,769,61],[425,73,73],[533,37,37],[909,352,352],[1317,241,101],[95,1257,95],[375,488,375],[71,641,71],[543,940,414],[1069,22,22],[1026,245,245],[319,974,319],[763,971,383],[980,1184,170],[580,1008,346],[1221,789,197],[1127,679,291],[1154,587,264],[847,530,530],[1368,985,50],[858,1110,244],[1018,290,290],[84,277,84],[223,29,29],[1323,754,95],[1221,609,197],[1113,429,305],[934,1304,50],[581,1341,13],[849,402,402],[640,728,626],[1067,226,226],[1003,505,415],[859,292,292],[512,483,483],[32,176,32],[1208,1288,66],[851,1039,315],[588,604,588],[268,948,268],[103,422,103],[266,128,128],[772,402,402],[60,333,60],[135,386,135],[282,150,150],[286,83,83],[216,999,216],[1222,249,196],[863,1106,248],[1141,997,277],[737,512,512],[1201,229,217],[830,136,136],[970,444,444],[1230,737,188],[810,631,608],[1091,342,327],[693,1272,82],[1298,1327,27],[976,651,442],[199,89,89],[330,349,330],[410,536,410],[242,1347,7],[154,1185,154],[913,1241,113],[749,92,92],[490,660,490],[967,1109,245],[932,609,486],[560,215,215],[1232,968,186],[982,1255,99],[445,103,103],[605,727,605],[993,1125,229],[1349,975,69],[1363,883,55],[763,261,261],[322,346,322],[1243,291,175],[1396,391,22],[1285,1326,28],[1214,442,204],[133,1008,133],[1307,648,111],[579,1184,170],[299,496,299],[799,1237,117],[1226,776,192],[300,744,300],[1150,670,268],[109,32,32],[773,998,356],[1265,386,153],[1398,904,20],[1113,750,305],[490,885,469],[968,1241,113],[816,1105,249],[62,391,62],[239,1278,76],[98,1124,98],[15,1182,15],[1165,194,194],[341,367,341],[729,1291,63],[671,330,330],[487,659,487],[185,189,185],[341,556,341],[310,60,60],[361,450,361],[1291,836,127],[481,293,293],[369,617,369],[731,1267,87],[86,524,86],[1230,855,188],[990,79,79],[1185,1062,233],[636,652,636],[436,778,436],[556,679,556],[149,836,149],[852,438,438],[653,99,99],[53,644,53],[550,220,220],[51,746,51],[739,312,312],[610,85,85],[352,1122,232],[921,65,65],[428,483,428],[1264,137,137],[771,84,84],[1303,1352,2],[559,122,122],[400,1067,287],[1108,667,310],[601,1068,286],[266,1010,266],[231,1097,231],[850,1005,349],[264,765,264],[993,294,294],[759,563,563],[887,475,475],[1386,1117,32],[1172,67,67],[313,288,288],[1032,44,44],[1219,70,70],[1285,678,133],[93,265,93],[716,471,471],[79,1120,79],[293,429,293],[24,1285,24],[221,1337,17],[1080,327,327],[1411,258,7],[475,54,54],[548,12,12],[825,1140,214],[1257,97,97],[635,1098,256],[694,481,481],[13,42,13],[1185,641,233],[572,695,572],[315,66,66],[418,955,399],[1239,298,179],[1252,691,166],[859,1094,260],[180,1180,174],[1368,655,50],[1203,371,215],[133,66,66],[789,1178,176],[104,856,104],[815,480,480],[282,761,282],[489,340,340],[627,601,601],[242,89,89],[904,1222,132],[1377,361,41],[986,473,432],[38,65,38],[127,1248,106],[469,775,469],[252,384,252],[490,1169,185],[1352,1295,59],[553,596,553],[438,768,438],[243,7,7],[568,1206,148],[560,1074,280],[10,1177,10],[229,293,229],[64,551,64],[751,1260,94],[481,267,267],[299,279,279],[978,1337,17],[474,830,474],[884,416,416],[1399,233,19],[1406,742,12],[844,921,433],[393,135,135],[1260,349,158],[184,424,184],[583,106,106],[553,90,90],[1192,1154,200],[403,1102,252],[593,911,443],[481,916,438],[1111,137,137],[707,1307,47],[1101,261,261],[1234,152,152],[1117,265,265],[1057,234,234],[310,859,310],[421,288,288],[1377,52,41],[567,538,538],[481,271,271],[865,219,219],[1117,202,202],[497,1154,200],[949,1031,323],[839,450,450],[49,448,49],[714,32,32],[500,982,372],[1104,374,314],[966,74,74],[467,676,467],[555,1118,236],[1011,517,407],[487,701,487],[743,1053,301],[871,600,547],[952,650,466],[574,76,76],[1092,1039,315],[789,658,629],[46,439,46],[1094,573,324],[895,1173,181],[246,207,207],[1094,546,324],[871,1106,248],[1161,829,257],[884,202,202],[1,158,1],[827,327,327],[515,1034,320],[899,540,519],[166,900,166],[618,702,618],[169,1261,93],[157,1285,69],[1313,141,105],[24,540,24],[345,1277,77],[1326,1139,92],[69,879,69],[530,428,428],[167,932,167],[378,550,378],[291,677,291],[250,874,250],[515,641,515],[464,649,464],[2,1341,2],[905,973,381],[1201,517,217],[951,923,431],[915,2,2],[557,251,251],[478,990,364],[1327,86,86],[1156,323,262],[1191,523,227],[666,258,258],[859,690,559],[1159,334,259],[1146,423,272],[886,1070,284],[250,754,250],[1167,1237,117],[854,900,454],[770,1024,330],[226,968,226],[434,132,132],[1029,490,389],[186,642,186],[1280,464,138],[224,614,224],[557,929,425],[372,643,372],[890,903,451],[439,719,439],[507,38,38],[460,414,414],[662,1166,188],[1258,1034,160],[226,800,226],[458,44,44],[1106,1055,299],[1355,992,63],[661,861,493],[498,1155,199],[486,311,311],[502,1010,344],[1100,909,318],[1211,786,207],[1317,1139,101],[300,835,300],[252,642,252],[583,752,583],[153,414,153],[207,1297,57],[1006,304,304],[1314,1164,104],[513,716,513],[741,1104,250],[963,562,455],[771,383,383],[616,490,490],[192,892,192],[1092,916,326],[75,958,75],[56,550,56],[474,104,104],[533,926,428],[1130,394,288],[839,219,219],[1021,1290,64],[1012,834,406],[448,1033,321],[737,700,654],[1397,330,21],[507,513,507],[496,472,472],[1031,405,387],[13,565,13],[231,1253,101],[1242,905,176],[437,700,437],[953,360,360],[1131,1149,205],[447,1289,65],[243,166,166],[891,1018,336],[159,866,159],[12,81,12],[576,570,570],[938,626,480],[542,889,465],[85,1140,85],[1023,393,393],[812,859,495],[986,510,432],[261,831,261],[654,1077,277],[515,52,52],[343,956,343],[1083,1213,141],[543,1062,292],[979,1022,332],[754,639,639],[201,819,201],[608,176,176],[18,690,18],[812,196,196],[1314,884,104],[165,329,165],[900,1243,111],[75,208,75],[789,259,259],[228,717,228],[727,45,45],[467,553,467],[170,1204,150],[756,573,573],[68,185,68],[1092,513,326],[56,1014,56],[991,435,427],[594,322,322],[1198,1176,178],[328,48,48],[1094,706,324],[480,1034,320],[29,665,29],[839,279,279],[1016,167,167],[190,18,18],[110,1136,110],[979,300,300],[96,119,96],[1179,821,239],[1277,1205,141],[187,398,187],[783,540,540],[610,897,457],[168,855,168],[484,681,484],[492,672,492],[872,1010,344],[816,583,583],[1091,1117,237],[57,917,57],[171,422,171],[959,425,425],[1030,707,388],[1218,67,67],[705,8,8],[277,227,227],[1131,820,287],[686,945,409],[194,1096,194],[420,757,420],[448,436,436],[439,795,439],[1010,119,119],[400,514,400],[357,816,357],[413,282,282],[426,343,343],[255,1093,255],[883,860,494],[988,262,262],[889,441,441],[1020,1192,162],[487,1204,150],[59,870,59],[270,359,270],[496,227,227],[823,845,509],[423,153,153],[1136,1072,282],[791,358,358],[665,28,28],[1203,697,215],[344,384,344],[457,1320,34],[871,454,454],[1048,313,313],[1335,257,83],[742,626,626],[1180,72,72],[178,199,178],[1153,1242,112],[539,351,351],[456,228,228],[904,1255,99],[62,1289,62],[1121,495,297],[1206,923,212],[677,407,407],[1160,874,258],[151,732,151],[117,452,117],[1391,225,27],[1194,576,224],[63,1244,63],[1010,1143,211],[155,1072,155],[1201,1333,21],[618,635,618],[898,1065,289],[1092,863,326],[568,1244,110],[965,430,430],[422,542,422],[948,1257,97],[1056,547,362],[1198,537,220],[856,482,482],[426,646,426],[567,457,457],[1347,1280,71],[426,934,420],[1393,969,25],[647,1344,10],[1210,169,169],[1250,54,54],[379,1088,266],[941,182,182],[349,785,349],[1001,1260,94],[963,764,455],[693,731,623],[872,1139,215],[24,320,24],[660,576,576],[800,716,618],[35,324,35],[1058,866,360],[19,1116,19],[1116,150,150],[313,409,313],[1336,82,82],[792,1297,57],[291,619,291],[325,425,325],[1180,960,238],[370,734,370],[115,165,115],[1312,936,106],[1398,492,20],[1277,269,141],[741,743,611],[269,246,246],[1178,30,30],[803,825,529],[1229,941,189],[322,322,322],[1009,134,134],[828,570,570],[1075,57,57],[235,564,235],[617,1189,165],[825,335,335],[1088,403,330],[596,697,596],[515,172,172],[588,645,588],[160,526,160],[300,572,300],[1163,395,255],[1330,1122,88],[142,1089,142],[97,953,97],[941,1275,79],[14,335,14],[483,1218,136],[1136,1067,282],[763,24,24],[383,442,383],[1182,275,236],[754,22,22],[955,690,463],[803,1127,227],[1276,124,124],[743,510,510],[498,155,155],[586,1035,319],[437,147,147],[586,332,332],[804,1099,255],[19,375,19],[1317,381,101],[207,929,207],[516,53,53],[1003,791,415],[1157,480,261],[664,841,513],[770,1337,17],[1241,736,177],[251,275,251],[543,1067,287],[837,1151,203],[880,193,193],[1208,106,106],[1285,519,133],[322,1166,188],[748,825,529],[550,872,482],[1234,1261,93],[264,1,1],[365,936,365],[1380,577,38],[1117,658,301],[1012,320,320],[642,597,597],[318,938,318],[371,945,371],[962,1252,102],[869,345,345],[89,541,89],[867,617,551],[1381,1329,25],[410,1339,15],[769,18,18],[280,1125,229],[373,938,373],[102,1328,26],[625,991,363],[1069,383,349],[377,1064,290],[406,408,406],[936,538,482],[520,905,449],[772,1166,188],[1054,1348,6],[1069,585,349],[968,898,450],[133,874,133],[779,758,596],[702,527,527],[915,414,414],[287,859,287],[1090,777,328],[103,933,103],[403,776,403],[1364,392,54],[20,1235,20],[477,892,462],[158,1144,158],[125,322,125],[309,222,222],[822,299,299],[13,200,13],[898,1220,134],[467,1317,37],[219,1057,219],[285,1183,171],[250,1306,48],[397,645,397],[417,1084,270],[202,888,202],[608,1045,309],[8,457,8],[86,109,86],[877,821,533],[714,851,503],[205,2,2],[1042,297,297],[755,301,301],[98,1351,3],[301,544,301],[632,336,336],[60,948,60],[818,678,600],[395,1296,58],[977,552,441],[1028,937,390],[828,319,319],[1333,924,85],[1041,920,377],[1096,769,322],[1254,770,164],[938,1025,329],[747,941,413],[279,359,279],[447,407,407],[1018,569,400],[1146,1126,228],[1384,913,34],[566,138,138],[899,1270,84],[179,1299,55],[1064,469,354],[175,111,111],[783,22,22],[656,668,656],[1172,671,246],[519,729,519],[51,663,51],[971,979,375],[338,757,338],[280,804,280],[555,257,257],[1339,722,79],[224,697,224],[647,838,516],[1122,9,9],[1277,1071,141],[914,688,504],[1240,1237,117],[571,42,42],[68,111,68],[20,1249,20],[734,518,518],[930,582,488],[534,969,385],[428,54,54],[1286,747,132],[737,184,184],[303,876,303],[248,294,248],[712,1054,300],[211,701,211],[276,632,276],[749,392,392],[137,50,50],[325,706,325],[417,711,417],[101,430,101],[505,145,145],[1051,657,367],[777,1263,91],[469,328,328],[396,472,396],[191,406,191],[934,760,484],[1351,331,67],[719,184,184],[185,1272,82],[779,836,518],[826,153,153],[210,919,210],[797,1164,190],[1066,842,352],[58,363,58],[588,691,588],[729,117,117],[558,1247,107],[402,1048,306],[1157,439,261],[265,1105,249],[1031,162,162],[174,721,174],[1345,1353,1],[394,749,394],[1100,151,151],[1397,1315,21],[1039,594,379],[964,959,395],[1184,996,234],[184,576,184],[537,883,471],[143,1223,131],[966,407,407],[1380,442,38],[673,6,6],[798,627,620],[163,882,163],[319,767,319],[1211,1230,124],[1095,1038,316],[1231,1149,187],[70,472,70],[352,677,352],[1274,106,106],[71,370,71],[1268,1179,150],[275,898,275],[399,388,388],[1259,525,159],[122,949,122],[1401,1309,17],[251,1067,251],[34,747,34],[1232,516,186],[586,1243,111],[644,743,611],[482,1093,261],[1148,120,120],[1095,282,282],[1249,1108,169],[569,495,495],[1077,1255,99],[170,459,170],[1009,986,368],[600,653,600],[182,878,182],[1038,157,157],[641,598,598],[1240,786,178],[1371,1036,47],[479,752,479],[30,1351,3],[732,833,521],[22,1,1],[578,573,573],[1286,1086,132],[1307,49,49],[54,1182,54],[1249,280,169],[128,1344,10],[1157,393,261],[1205,1064,213],[187,811,187],[389,819,389],[938,1245,109],[280,121,121],[1059,776,359],[935,142,142],[364,327,327],[456,402,402],[476,251,251],[420,757,420],[11,1115,11],[371,925,371],[493,222,222],[222,868,222],[1279,51,51],[310,875,310],[1165,446,253],[873,1030,324],[711,449,449],[456,930,424],[888,281,281],[118,1220,118],[1344,700,74],[918,579,500],[813,523,523],[1248,1252,102],[26,1341,13],[940,405,405],[1249,114,114],[619,997,357],[608,104,104],[526,282,282],[418,332,332],[196,27,27],[425,916,425],[1168,88,88],[181,488,181],[104,1136,104],[439,371,371],[1353,283,65],[709,190,190],[127,612,127],[1123,480,295],[187,960,187],[1386,625,32],[768,1151,203],[1004,883,414],[996,532,422],[913,989,365],[834,1069,285],[1094,61,61],[90,1021,90],[719,156,156],[309,826,309],[338,989,338],[262,163,163],[412,737,412],[1115,549,303],[1376,551,42],[1016,871,402],[717,648,648],[140,1065,140],[623,1093,261],[1111,806,307],[433,272,272],[1208,882,210],[999,1308,46],[932,999,355],[137,64,64],[808,355,355],[373,1204,150],[991,735,427],[998,1017,337],[749,445,445],[411,1134,220],[87,813,87],[127,519,127],[18,681,18],[1007,979,375],[1197,1211,143],[1292,231,126],[987,340,340],[663,306,306],[919,704,499],[492,849,492],[210,1058,210],[1411,589,7],[923,1186,168],[1284,1164,134],[773,502,502],[1274,248,144],[213,1195,159],[898,959,395],[1362,158,56],[966,240,240],[5,1119,5],[714,312,312],[367,76,76],[716,136,136],[379,204,204],[230,838,230],[1165,316,253],[1120,580,298],[302,1265,89],[631,489,489],[1191,1256,98],[1344,1252,74],[791,1206,148],[332,1142,212],[1105,209,209],[543,381,381],[4,1014,4],[869,978,376],[791,916,438],[518,461,461],[278,990,278],[920,597,498],[197,992,197],[1287,1175,131],[38,901,38],[683,242,242],[1260,1227,127],[831,331,331],[1390,512,28],[1039,868,379],[125,57,57],[181,554,181],[1021,142,142],[1295,952,123],[874,640,544],[346,447,346],[527,781,527],[664,980,374],[605,651,605],[261,266,261],[618,727,618],[994,580,424],[530,692,530],[1211,312,207],[747,1148,206],[292,460,292],[107,1341,13],[869,143,143],[837,617,581],[371,205,205],[504,243,243],[980,1304,50],[1399,82,19],[968,1250,104],[1253,1344,10],[505,1322,32],[1375,670,43],[582,431,431],[1400,27,18],[836,608,582],[1267,798,151],[209,1175,179],[1273,477,145],[111,101,101],[157,1071,157],[756,110,110],[450,107,107],[993,262,262],[725,663,663],[929,54,54],[571,103,103],[496,337,337],[1161,328,257],[1302,76,76],[910,353,353],[1002,438,416],[472,789,472],[89,1213,89],[1146,257,257],[677,209,209],[772,489,489],[1149,48,48],[1366,591,52],[360,86,86],[426,1270,84],[456,273,273],[389,763,389],[452,28,28],[156,22,22],[903,624,515],[36,722,36],[664,846,508],[948,828,470],[1100,1309,45],[1014,1292,62],[36,61,36],[833,458,458],[412,1294,60],[1218,162,162],[1021,476,397],[673,719,635]]))
        .toEqual(false);
      const end = new Date().getTime();
      const time = end - start;
      console.log(`time: ${time}ms`);
    });

    it.skip('does not exceed time limit on even larger input', () => {
      const start = new Date().getTime();
      expect(canReachCorner(1000000000, 1000000000, [[1000,2000,1000],[1001,2001,1000],[1002,2002,1000],[1003,2003,1000],[1004,2004,1000],[1005,2005,1000],[1006,2006,1000],[1007,2007,1000],[1008,2008,1000],[1009,2009,1000],[1010,2010,1000],[1011,2011,1000],[1012,2012,1000],[1013,2013,1000],[1014,2014,1000],[1015,2015,1000],[1016,2016,1000],[1017,2017,1000],[1018,2018,1000],[1019,2019,1000],[1020,2020,1000],[1021,2021,1000],[1022,2022,1000],[1023,2023,1000],[1024,2024,1000],[1025,2025,1000],[1026,2026,1000],[1027,2027,1000],[1028,2028,1000],[1029,2029,1000],[1030,2030,1000],[1031,2031,1000],[1032,2032,1000],[1033,2033,1000],[1034,2034,1000],[1035,2035,1000],[1036,2036,1000],[1037,2037,1000],[1038,2038,1000],[1039,2039,1000],[1040,2040,1000],[1041,2041,1000],[1042,2042,1000],[1043,2043,1000],[1044,2044,1000],[1045,2045,1000],[1046,2046,1000],[1047,2047,1000],[1048,2048,1000],[1049,2049,1000],[1050,2050,1000],[1051,2051,1000],[1052,2052,1000],[1053,2053,1000],[1054,2054,1000],[1055,2055,1000],[1056,2056,1000],[1057,2057,1000],[1058,2058,1000],[1059,2059,1000],[1060,2060,1000],[1061,2061,1000],[1062,2062,1000],[1063,2063,1000],[1064,2064,1000],[1065,2065,1000],[1066,2066,1000],[1067,2067,1000],[1068,2068,1000],[1069,2069,1000],[1070,2070,1000],[1071,2071,1000],[1072,2072,1000],[1073,2073,1000],[1074,2074,1000],[1075,2075,1000],[1076,2076,1000],[1077,2077,1000],[1078,2078,1000],[1079,2079,1000],[1080,2080,1000],[1081,2081,1000],[1082,2082,1000],[1083,2083,1000],[1084,2084,1000],[1085,2085,1000],[1086,2086,1000],[1087,2087,1000],[1088,2088,1000],[1089,2089,1000],[1090,2090,1000],[1091,2091,1000],[1092,2092,1000],[1093,2093,1000],[1094,2094,1000],[1095,2095,1000],[1096,2096,1000],[1097,2097,1000],[1098,2098,1000],[1099,2099,1000],[1100,2100,1000],[1101,2101,1000],[1102,2102,1000],[1103,2103,1000],[1104,2104,1000],[1105,2105,1000],[1106,2106,1000],[1107,2107,1000],[1108,2108,1000],[1109,2109,1000],[1110,2110,1000],[1111,2111,1000],[1112,2112,1000],[1113,2113,1000],[1114,2114,1000],[1115,2115,1000],[1116,2116,1000],[1117,2117,1000],[1118,2118,1000],[1119,2119,1000],[1120,2120,1000],[1121,2121,1000],[1122,2122,1000],[1123,2123,1000],[1124,2124,1000],[1125,2125,1000],[1126,2126,1000],[1127,2127,1000],[1128,2128,1000],[1129,2129,1000],[1130,2130,1000],[1131,2131,1000],[1132,2132,1000],[1133,2133,1000],[1134,2134,1000],[1135,2135,1000],[1136,2136,1000],[1137,2137,1000],[1138,2138,1000],[1139,2139,1000],[1140,2140,1000],[1141,2141,1000],[1142,2142,1000],[1143,2143,1000],[1144,2144,1000],[1145,2145,1000],[1146,2146,1000],[1147,2147,1000],[1148,2148,1000],[1149,2149,1000],[1150,2150,1000],[1151,2151,1000],[1152,2152,1000],[1153,2153,1000],[1154,2154,1000],[1155,2155,1000],[1156,2156,1000],[1157,2157,1000],[1158,2158,1000],[1159,2159,1000],[1160,2160,1000],[1161,2161,1000],[1162,2162,1000],[1163,2163,1000],[1164,2164,1000],[1165,2165,1000],[1166,2166,1000],[1167,2167,1000],[1168,2168,1000],[1169,2169,1000],[1170,2170,1000],[1171,2171,1000],[1172,2172,1000],[1173,2173,1000],[1174,2174,1000],[1175,2175,1000],[1176,2176,1000],[1177,2177,1000],[1178,2178,1000],[1179,2179,1000],[1180,2180,1000],[1181,2181,1000],[1182,2182,1000],[1183,2183,1000],[1184,2184,1000],[1185,2185,1000],[1186,2186,1000],[1187,2187,1000],[1188,2188,1000],[1189,2189,1000],[1190,2190,1000],[1191,2191,1000],[1192,2192,1000],[1193,2193,1000],[1194,2194,1000],[1195,2195,1000],[1196,2196,1000],[1197,2197,1000],[1198,2198,1000],[1199,2199,1000],[1200,2200,1000],[1201,2201,1000],[1202,2202,1000],[1203,2203,1000],[1204,2204,1000],[1205,2205,1000],[1206,2206,1000],[1207,2207,1000],[1208,2208,1000],[1209,2209,1000],[1210,2210,1000],[1211,2211,1000],[1212,2212,1000],[1213,2213,1000],[1214,2214,1000],[1215,2215,1000],[1216,2216,1000],[1217,2217,1000],[1218,2218,1000],[1219,2219,1000],[1220,2220,1000],[1221,2221,1000],[1222,2222,1000],[1223,2223,1000],[1224,2224,1000],[1225,2225,1000],[1226,2226,1000],[1227,2227,1000],[1228,2228,1000],[1229,2229,1000],[1230,2230,1000],[1231,2231,1000],[1232,2232,1000],[1233,2233,1000],[1234,2234,1000],[1235,2235,1000],[1236,2236,1000],[1237,2237,1000],[1238,2238,1000],[1239,2239,1000],[1240,2240,1000],[1241,2241,1000],[1242,2242,1000],[1243,2243,1000],[1244,2244,1000],[1245,2245,1000],[1246,2246,1000],[1247,2247,1000],[1248,2248,1000],[1249,2249,1000],[1250,2250,1000],[1251,2251,1000],[1252,2252,1000],[1253,2253,1000],[1254,2254,1000],[1255,2255,1000],[1256,2256,1000],[1257,2257,1000],[1258,2258,1000],[1259,2259,1000],[1260,2260,1000],[1261,2261,1000],[1262,2262,1000],[1263,2263,1000],[1264,2264,1000],[1265,2265,1000],[1266,2266,1000],[1267,2267,1000],[1268,2268,1000],[1269,2269,1000],[1270,2270,1000],[1271,2271,1000],[1272,2272,1000],[1273,2273,1000],[1274,2274,1000],[1275,2275,1000],[1276,2276,1000],[1277,2277,1000],[1278,2278,1000],[1279,2279,1000],[1280,2280,1000],[1281,2281,1000],[1282,2282,1000],[1283,2283,1000],[1284,2284,1000],[1285,2285,1000],[1286,2286,1000],[1287,2287,1000],[1288,2288,1000],[1289,2289,1000],[1290,2290,1000],[1291,2291,1000],[1292,2292,1000],[1293,2293,1000],[1294,2294,1000],[1295,2295,1000],[1296,2296,1000],[1297,2297,1000],[1298,2298,1000],[1299,2299,1000],[1300,2300,1000],[1301,2301,1000],[1302,2302,1000],[1303,2303,1000],[1304,2304,1000],[1305,2305,1000],[1306,2306,1000],[1307,2307,1000],[1308,2308,1000],[1309,2309,1000],[1310,2310,1000],[1311,2311,1000],[1312,2312,1000],[1313,2313,1000],[1314,2314,1000],[1315,2315,1000],[1316,2316,1000],[1317,2317,1000],[1318,2318,1000],[1319,2319,1000],[1320,2320,1000],[1321,2321,1000],[1322,2322,1000],[1323,2323,1000],[1324,2324,1000],[1325,2325,1000],[1326,2326,1000],[1327,2327,1000],[1328,2328,1000],[1329,2329,1000],[1330,2330,1000],[1331,2331,1000],[1332,2332,1000],[1333,2333,1000],[1334,2334,1000],[1335,2335,1000],[1336,2336,1000],[1337,2337,1000],[1338,2338,1000],[1339,2339,1000],[1340,2340,1000],[1341,2341,1000],[1342,2342,1000],[1343,2343,1000],[1344,2344,1000],[1345,2345,1000],[1346,2346,1000],[1347,2347,1000],[1348,2348,1000],[1349,2349,1000],[1350,2350,1000],[1351,2351,1000],[1352,2352,1000],[1353,2353,1000],[1354,2354,1000],[1355,2355,1000],[1356,2356,1000],[1357,2357,1000],[1358,2358,1000],[1359,2359,1000],[1360,2360,1000],[1361,2361,1000],[1362,2362,1000],[1363,2363,1000],[1364,2364,1000],[1365,2365,1000],[1366,2366,1000],[1367,2367,1000],[1368,2368,1000],[1369,2369,1000],[1370,2370,1000],[1371,2371,1000],[1372,2372,1000],[1373,2373,1000],[1374,2374,1000],[1375,2375,1000],[1376,2376,1000],[1377,2377,1000],[1378,2378,1000],[1379,2379,1000],[1380,2380,1000],[1381,2381,1000],[1382,2382,1000],[1383,2383,1000],[1384,2384,1000],[1385,2385,1000],[1386,2386,1000],[1387,2387,1000],[1388,2388,1000],[1389,2389,1000],[1390,2390,1000],[1391,2391,1000],[1392,2392,1000],[1393,2393,1000],[1394,2394,1000],[1395,2395,1000],[1396,2396,1000],[1397,2397,1000],[1398,2398,1000],[1399,2399,1000],[1400,2400,1000],[1401,2401,1000],[1402,2402,1000],[1403,2403,1000],[1404,2404,1000],[1405,2405,1000],[1406,2406,1000],[1407,2407,1000],[1408,2408,1000],[1409,2409,1000],[1410,2410,1000],[1411,2411,1000],[1412,2412,1000],[1413,2413,1000],[1414,2414,1000],[1415,2415,1000],[1416,2416,1000],[1417,2417,1000],[1418,2418,1000],[1419,2419,1000],[1420,2420,1000],[1421,2421,1000],[1422,2422,1000],[1423,2423,1000],[1424,2424,1000],[1425,2425,1000],[1426,2426,1000],[1427,2427,1000],[1428,2428,1000],[1429,2429,1000],[1430,2430,1000],[1431,2431,1000],[1432,2432,1000],[1433,2433,1000],[1434,2434,1000],[1435,2435,1000],[1436,2436,1000],[1437,2437,1000],[1438,2438,1000],[1439,2439,1000],[1440,2440,1000],[1441,2441,1000],[1442,2442,1000],[1443,2443,1000],[1444,2444,1000],[1445,2445,1000],[1446,2446,1000],[1447,2447,1000],[1448,2448,1000],[1449,2449,1000],[1450,2450,1000],[1451,2451,1000],[1452,2452,1000],[1453,2453,1000],[1454,2454,1000],[1455,2455,1000],[1456,2456,1000],[1457,2457,1000],[1458,2458,1000],[1459,2459,1000],[1460,2460,1000],[1461,2461,1000],[1462,2462,1000],[1463,2463,1000],[1464,2464,1000],[1465,2465,1000],[1466,2466,1000],[1467,2467,1000],[1468,2468,1000],[1469,2469,1000],[1470,2470,1000],[1471,2471,1000],[1472,2472,1000],[1473,2473,1000],[1474,2474,1000],[1475,2475,1000],[1476,2476,1000],[1477,2477,1000],[1478,2478,1000],[1479,2479,1000],[1480,2480,1000],[1481,2481,1000],[1482,2482,1000],[1483,2483,1000],[1484,2484,1000],[1485,2485,1000],[1486,2486,1000],[1487,2487,1000],[1488,2488,1000],[1489,2489,1000],[1490,2490,1000],[1491,2491,1000],[1492,2492,1000],[1493,2493,1000],[1494,2494,1000],[1495,2495,1000],[1496,2496,1000],[1497,2497,1000],[1498,2498,1000],[1499,2499,1000],[1500,2500,1000],[1501,2501,1000],[1502,2502,1000],[1503,2503,1000],[1504,2504,1000],[1505,2505,1000],[1506,2506,1000],[1507,2507,1000],[1508,2508,1000],[1509,2509,1000],[1510,2510,1000],[1511,2511,1000],[1512,2512,1000],[1513,2513,1000],[1514,2514,1000],[1515,2515,1000],[1516,2516,1000],[1517,2517,1000],[1518,2518,1000],[1519,2519,1000],[1520,2520,1000],[1521,2521,1000],[1522,2522,1000],[1523,2523,1000],[1524,2524,1000],[1525,2525,1000],[1526,2526,1000],[1527,2527,1000],[1528,2528,1000],[1529,2529,1000],[1530,2530,1000],[1531,2531,1000],[1532,2532,1000],[1533,2533,1000],[1534,2534,1000],[1535,2535,1000],[1536,2536,1000],[1537,2537,1000],[1538,2538,1000],[1539,2539,1000],[1540,2540,1000],[1541,2541,1000],[1542,2542,1000],[1543,2543,1000],[1544,2544,1000],[1545,2545,1000],[1546,2546,1000],[1547,2547,1000],[1548,2548,1000],[1549,2549,1000],[1550,2550,1000],[1551,2551,1000],[1552,2552,1000],[1553,2553,1000],[1554,2554,1000],[1555,2555,1000],[1556,2556,1000],[1557,2557,1000],[1558,2558,1000],[1559,2559,1000],[1560,2560,1000],[1561,2561,1000],[1562,2562,1000],[1563,2563,1000],[1564,2564,1000],[1565,2565,1000],[1566,2566,1000],[1567,2567,1000],[1568,2568,1000],[1569,2569,1000],[1570,2570,1000],[1571,2571,1000],[1572,2572,1000],[1573,2573,1000],[1574,2574,1000],[1575,2575,1000],[1576,2576,1000],[1577,2577,1000],[1578,2578,1000],[1579,2579,1000],[1580,2580,1000],[1581,2581,1000],[1582,2582,1000],[1583,2583,1000],[1584,2584,1000],[1585,2585,1000],[1586,2586,1000],[1587,2587,1000],[1588,2588,1000],[1589,2589,1000],[1590,2590,1000],[1591,2591,1000],[1592,2592,1000],[1593,2593,1000],[1594,2594,1000],[1595,2595,1000],[1596,2596,1000],[1597,2597,1000],[1598,2598,1000],[1599,2599,1000],[1600,2600,1000],[1601,2601,1000],[1602,2602,1000],[1603,2603,1000],[1604,2604,1000],[1605,2605,1000],[1606,2606,1000],[1607,2607,1000],[1608,2608,1000],[1609,2609,1000],[1610,2610,1000],[1611,2611,1000],[1612,2612,1000],[1613,2613,1000],[1614,2614,1000],[1615,2615,1000],[1616,2616,1000],[1617,2617,1000],[1618,2618,1000],[1619,2619,1000],[1620,2620,1000],[1621,2621,1000],[1622,2622,1000],[1623,2623,1000],[1624,2624,1000],[1625,2625,1000],[1626,2626,1000],[1627,2627,1000],[1628,2628,1000],[1629,2629,1000],[1630,2630,1000],[1631,2631,1000],[1632,2632,1000],[1633,2633,1000],[1634,2634,1000],[1635,2635,1000],[1636,2636,1000],[1637,2637,1000],[1638,2638,1000],[1639,2639,1000],[1640,2640,1000],[1641,2641,1000],[1642,2642,1000],[1643,2643,1000],[1644,2644,1000],[1645,2645,1000],[1646,2646,1000],[1647,2647,1000],[1648,2648,1000],[1649,2649,1000],[1650,2650,1000],[1651,2651,1000],[1652,2652,1000],[1653,2653,1000],[1654,2654,1000],[1655,2655,1000],[1656,2656,1000],[1657,2657,1000],[1658,2658,1000],[1659,2659,1000],[1660,2660,1000],[1661,2661,1000],[1662,2662,1000],[1663,2663,1000],[1664,2664,1000],[1665,2665,1000],[1666,2666,1000],[1667,2667,1000],[1668,2668,1000],[1669,2669,1000],[1670,2670,1000],[1671,2671,1000],[1672,2672,1000],[1673,2673,1000],[1674,2674,1000],[1675,2675,1000],[1676,2676,1000],[1677,2677,1000],[1678,2678,1000],[1679,2679,1000],[1680,2680,1000],[1681,2681,1000],[1682,2682,1000],[1683,2683,1000],[1684,2684,1000],[1685,2685,1000],[1686,2686,1000],[1687,2687,1000],[1688,2688,1000],[1689,2689,1000],[1690,2690,1000],[1691,2691,1000],[1692,2692,1000],[1693,2693,1000],[1694,2694,1000],[1695,2695,1000],[1696,2696,1000],[1697,2697,1000],[1698,2698,1000],[1699,2699,1000],[1700,2700,1000],[1701,2701,1000],[1702,2702,1000],[1703,2703,1000],[1704,2704,1000],[1705,2705,1000],[1706,2706,1000],[1707,2707,1000],[1708,2708,1000],[1709,2709,1000],[1710,2710,1000],[1711,2711,1000],[1712,2712,1000],[1713,2713,1000],[1714,2714,1000],[1715,2715,1000],[1716,2716,1000],[1717,2717,1000],[1718,2718,1000],[1719,2719,1000],[1720,2720,1000],[1721,2721,1000],[1722,2722,1000],[1723,2723,1000],[1724,2724,1000],[1725,2725,1000],[1726,2726,1000],[1727,2727,1000],[1728,2728,1000],[1729,2729,1000],[1730,2730,1000],[1731,2731,1000],[1732,2732,1000],[1733,2733,1000],[1734,2734,1000],[1735,2735,1000],[1736,2736,1000],[1737,2737,1000],[1738,2738,1000],[1739,2739,1000],[1740,2740,1000],[1741,2741,1000],[1742,2742,1000],[1743,2743,1000],[1744,2744,1000],[1745,2745,1000],[1746,2746,1000],[1747,2747,1000],[1748,2748,1000],[1749,2749,1000],[1750,2750,1000],[1751,2751,1000],[1752,2752,1000],[1753,2753,1000],[1754,2754,1000],[1755,2755,1000],[1756,2756,1000],[1757,2757,1000],[1758,2758,1000],[1759,2759,1000],[1760,2760,1000],[1761,2761,1000],[1762,2762,1000],[1763,2763,1000],[1764,2764,1000],[1765,2765,1000],[1766,2766,1000],[1767,2767,1000],[1768,2768,1000],[1769,2769,1000],[1770,2770,1000],[1771,2771,1000],[1772,2772,1000],[1773,2773,1000],[1774,2774,1000],[1775,2775,1000],[1776,2776,1000],[1777,2777,1000],[1778,2778,1000],[1779,2779,1000],[1780,2780,1000],[1781,2781,1000],[1782,2782,1000],[1783,2783,1000],[1784,2784,1000],[1785,2785,1000],[1786,2786,1000],[1787,2787,1000],[1788,2788,1000],[1789,2789,1000],[1790,2790,1000],[1791,2791,1000],[1792,2792,1000],[1793,2793,1000],[1794,2794,1000],[1795,2795,1000],[1796,2796,1000],[1797,2797,1000],[1798,2798,1000],[1799,2799,1000],[1800,2800,1000],[1801,2801,1000],[1802,2802,1000],[1803,2803,1000],[1804,2804,1000],[1805,2805,1000],[1806,2806,1000],[1807,2807,1000],[1808,2808,1000],[1809,2809,1000],[1810,2810,1000],[1811,2811,1000],[1812,2812,1000],[1813,2813,1000],[1814,2814,1000],[1815,2815,1000],[1816,2816,1000],[1817,2817,1000],[1818,2818,1000],[1819,2819,1000],[1820,2820,1000],[1821,2821,1000],[1822,2822,1000],[1823,2823,1000],[1824,2824,1000],[1825,2825,1000],[1826,2826,1000],[1827,2827,1000],[1828,2828,1000],[1829,2829,1000],[1830,2830,1000],[1831,2831,1000],[1832,2832,1000],[1833,2833,1000],[1834,2834,1000],[1835,2835,1000],[1836,2836,1000],[1837,2837,1000],[1838,2838,1000],[1839,2839,1000],[1840,2840,1000],[1841,2841,1000],[1842,2842,1000],[1843,2843,1000],[1844,2844,1000],[1845,2845,1000],[1846,2846,1000],[1847,2847,1000],[1848,2848,1000],[1849,2849,1000],[1850,2850,1000],[1851,2851,1000],[1852,2852,1000],[1853,2853,1000],[1854,2854,1000],[1855,2855,1000],[1856,2856,1000],[1857,2857,1000],[1858,2858,1000],[1859,2859,1000],[1860,2860,1000],[1861,2861,1000],[1862,2862,1000],[1863,2863,1000],[1864,2864,1000],[1865,2865,1000],[1866,2866,1000],[1867,2867,1000],[1868,2868,1000],[1869,2869,1000],[1870,2870,1000],[1871,2871,1000],[1872,2872,1000],[1873,2873,1000],[1874,2874,1000],[1875,2875,1000],[1876,2876,1000],[1877,2877,1000],[1878,2878,1000],[1879,2879,1000],[1880,2880,1000],[1881,2881,1000],[1882,2882,1000],[1883,2883,1000],[1884,2884,1000],[1885,2885,1000],[1886,2886,1000],[1887,2887,1000],[1888,2888,1000],[1889,2889,1000],[1890,2890,1000],[1891,2891,1000],[1892,2892,1000],[1893,2893,1000],[1894,2894,1000],[1895,2895,1000],[1896,2896,1000],[1897,2897,1000],[1898,2898,1000],[1899,2899,1000],[1900,2900,1000],[1901,2901,1000],[1902,2902,1000],[1903,2903,1000],[1904,2904,1000],[1905,2905,1000],[1906,2906,1000],[1907,2907,1000],[1908,2908,1000],[1909,2909,1000],[1910,2910,1000],[1911,2911,1000],[1912,2912,1000],[1913,2913,1000],[1914,2914,1000],[1915,2915,1000],[1916,2916,1000],[1917,2917,1000],[1918,2918,1000],[1919,2919,1000],[1920,2920,1000],[1921,2921,1000],[1922,2922,1000],[1923,2923,1000],[1924,2924,1000],[1925,2925,1000],[1926,2926,1000],[1927,2927,1000],[1928,2928,1000],[1929,2929,1000],[1930,2930,1000],[1931,2931,1000],[1932,2932,1000],[1933,2933,1000],[1934,2934,1000],[1935,2935,1000],[1936,2936,1000],[1937,2937,1000],[1938,2938,1000],[1939,2939,1000],[1940,2940,1000],[1941,2941,1000],[1942,2942,1000],[1943,2943,1000],[1944,2944,1000],[1945,2945,1000],[1946,2946,1000],[1947,2947,1000],[1948,2948,1000],[1949,2949,1000],[1950,2950,1000],[1951,2951,1000],[1952,2952,1000],[1953,2953,1000],[1954,2954,1000],[1955,2955,1000],[1956,2956,1000],[1957,2957,1000],[1958,2958,1000],[1959,2959,1000],[1960,2960,1000],[1961,2961,1000],[1962,2962,1000],[1963,2963,1000],[1964,2964,1000],[1965,2965,1000],[1966,2966,1000],[1967,2967,1000],[1968,2968,1000],[1969,2969,1000],[1970,2970,1000],[1971,2971,1000],[1972,2972,1000],[1973,2973,1000],[1974,2974,1000],[1975,2975,1000],[1976,2976,1000],[1977,2977,1000],[1978,2978,1000],[1979,2979,1000],[1980,2980,1000],[1981,2981,1000],[1982,2982,1000],[1983,2983,1000],[1984,2984,1000],[1985,2985,1000],[1986,2986,1000],[1987,2987,1000],[1988,2988,1000],[1989,2989,1000],[1990,2990,1000],[1991,2991,1000],[1992,2992,1000],[1993,2993,1000],[1994,2994,1000],[1995,2995,1000],[1996,2996,1000],[1997,2997,1000],[1998,2998,1000],[1999,2999,1000]]))
        .toEqual(true);
      const end = new Date().getTime();
      const time = end - start;
      console.log(`time: ${time}ms`);
    });


  });
});

canReachCorner.ts

export class DisjointSet { 

  private rank: Record<string, number> = {};
  private parent: Record<string, number> = {};
  private n: number = 0;  

  has(item: number): boolean {
    return this.parent[item] !== undefined;
  }

  add(item: number): number {
    this.n++;
    this.parent[item] = item;
    return this.n;
  }

	find(x: number) { 
		if (this.parent[x] !== x) { 
			this.parent[x] = this.find(this.parent[x]); 
		} 
		return this.parent[x]; 
	} 

	unify(x: number, y: number, cb?: (x: number, y: number) => void) { 
		let xset = this.find(x); 
		let yset = this.find(y); 

		if (xset === yset) {
      return;
    }; 

		if (this.rank[xset] < this.rank[yset]) { 
			this.parent[xset] = yset; 
		} else if (this.rank[xset] > this.rank[yset]) { 
			this.parent[yset] = xset; 
		} else { 
			this.parent[yset] = xset; 
			this.rank[xset] = this.rank[xset] || xset;
		} 

    if (cb) {
      cb(xset, yset);
    }
	} 
} 

export function calcDist(a: [number, number], b: [number, number]): number {
  const [aX, aY] = a;
  const [bX, bY] = b;
  const val = Math.sqrt(Math.pow(aX - bX, 2) + Math.pow(aY - bY, 2));
  return val;
}

export function intersectsCircle(a: number[], b: number[]): boolean {
  const [aX, aY, aR] = a;
  const [bX, bY, bR] = b;
  const dist = calcDist([aX, aY], [bX, bY]);
  return (aR + bR) >= dist;
}

export function getCornerVertices(w: number, h: number): number[][] {
  /** Corners vertices of the bounds */
  const corners = [
    [0, 0],
    [w, 0],
    [w, h],
    [0, h],
  ];
  return corners;
}

export function includesRectangle(w: number, h: number, circle: number[]): boolean {
  const [x, y, r] = circle;
  const vertices = getCornerVertices(w, h);
  return vertices.every(([i, j]) => r >= calcDist([i, j], [x, y]));
}

export function solutionsForX(y: number, circle: number[]): number[] {
  const [i, j, r] = circle;
  // Formula for Circle
  // (x - i)^2 + (y - j)^2 = r^2
  // x^2 - 2xi + i^2 + y^2 - 2yj + j^2 - r^2 = 0

  // Quadratic Formuala
  // a(x^2) + b(x) + c
  // a = 1
  // b = -2i
  // c = i^2 + y^2 - 2yj + j^2 - r^2
  const a = 1;
  const b = -2 * i;
  const c = Math.pow(i, 2) + Math.pow(y, 2) - (2 * y * j) +  Math.pow(j, 2) - Math.pow(r, 2);
  // Quadratic Formula
  // -b +/- √(b^2 - 4ac)
  // -------------------
  //       2a
  const modifier = [1, -1];
  const solutions = modifier.map(m => {
    const top = -b + m * (Math.sqrt(Math.pow(b, 2) - (4 * a * c)));
    const bottom = 2 * a;
    return top / bottom;
  }).filter(n => !Number.isNaN(n));
  return Array.from(new Set(solutions));
}

export function solutionsForY(x: number, circle: number[]): number[] {
  const [i, j, r] = circle;
  return solutionsForX(x, [j, i, r]).filter(n => !Number.isNaN(n));
}

export function isPointWithinBounds([w, h]: number[], [x, y]: number[]): boolean {
  return 0 < x && x < w && 0 < y && y < h;
}

export function getCircleIntersections(a: number[], b: number[]): number[][] {
  const [x_a, y_a, r_a] = a;
  const [x_b, y_b, r_b] = b;
  const base = r_b - (r_b + r_a - calcDist([x_a, y_a], [x_b, y_b])) / 2;
  const hypotenuse = r_b;
  const angleDelta = Math.acos(base / hypotenuse);
  const angleBase = x_a > x_b ? 0 : Math.PI;
  const angleStart = angleBase + Math.atan((y_a - y_b) / (x_a - x_b));
  const modifiers = [1, -1];
  const intesections = modifiers.map(m => {
    const angle = angleStart + m * angleDelta;
    const x = r_b * Math.cos(angle) + x_b;
    const y = r_b * Math.sin(angle) + y_b;
    return [x, y];
  });
  return intesections;
}

export function isIntersectionWithinBounds(w: number, h: number, a: number[], b: number[]): boolean {
  const intersections = getCircleIntersections(a, b);
  for (const intersection of intersections) {
    if (isPointWithinBounds([w, h], intersection)) {
      return true;
    }
  }
  return false;
}

export function getRectIntersections(w: number, h: number, circle: number[]) {
  return [
    ...solutionsForY(0, circle).map(y => [0, y]),
    ...solutionsForY(w, circle).map(y => [w, y]),
    ...solutionsForX(0, circle).map(x => [x, 0]),
    ...solutionsForX(h, circle).map(x => [x, h]),
  ];
}

export function getCornerIntersections(w: number, h: number, circle: number[]): number[] {
  const [x, y, r] = circle;
  const sides: number[] = [];
  if (r >= calcDist([0, 0], [x, y])) {
    sides.push(1, 4);
  }
  if (r >= calcDist([w, h], [x, y])) {
    sides.push(2, 3);
  }
  return sides;
}

// Left, Top, Right, Bottom numbered 1, 2, 3, 4
export function intersectsRect(w: number, h: number, circle: number[]): number[] {
  const sides: number[] = [];
  const intersections = getRectIntersections(w, h, circle);
  for (const [x, y] of intersections) {
    // Check left x bound inclusive
    // if (x === 0 && 0 < y && y <= h) {
    if (x === 0 && 0 < y && y <= h) {
      sides.push(1);
    }
    // Check y top bound exclusive
    if (y === h && 0 < x && x < w) {
      sides.push(2);
    }
    // Check right x bound exclusive
    if (x === w && 0 < y && y < h) {
      sides.push(3);
    }
    // Check bottom y bound inclusive
    if (y === 0 && 0 <= x && x < w) {
      sides.push(4);
    }
  }
  // If it did not intersect with sides,
  // then check for corner intersections.
  // This is because a path can be created
  // if the circle intersects with a corner
  // and a side, but not if it intersects with
  // only a corner.
  if (sides.length === 0) {
    for (const [x, y] of intersections) {
      if (x === 0 && y === 0) {
        sides.push(1, 4);
      } else if (x === w && y === h) {
        sides.push(2, 3);
      }
    }
  }
  return Array.from(new Set(sides));
}

export function isPathBlocked(set: DisjointSet): boolean {
  const paths = [
    [1, 3],
    [2, 4],
    [2, 3],
    [1, 4],
  ];
  for (const [source, destination] of paths) {
    const a = set.find(source);
    const b = set.find(destination);
    if (a === b) {
      return true;
    }
  }
  return false;
}

export function addUnion([w, h]: number[], set: DisjointSet, idx: number, circle: number[]): void {
  const intersections = intersectsRect(w, h, circle);
  for (const side of intersections) {
    set.unify(idx, side);
  }
}

export function compareRadius(a: number[], b: number[]) {
  const [_aX, _aY, aR] = a;
  const [_bX, _bY, bR] = b;
  return bR - aR;
}

export function canReachCorner(w: number, h: number, _circles: number[][]): boolean {
  if (_circles.length === 0) {
    return true;
  }
  const circles = _circles.sort(compareRadius);
  const dsjSet = new DisjointSet();
  const visited = new Set();
  dsjSet.add(1);
  dsjSet.add(2);
  dsjSet.add(3);
  dsjSet.add(4);
  for (let _idx = 0; _idx < circles.length; _idx++) {
    const circle_i = circles[_idx];
    const idx = _idx + 4 + 1;
    if (!dsjSet.has(idx)) {
      dsjSet.add(idx);
    }
    if (includesRectangle(w, h, circle_i)) {
      return false;
    }
    if (!visited.has(idx)) {
      addUnion([w, h], dsjSet, idx, circle_i);
      visited.add(idx);
    }
    if (isPathBlocked(dsjSet)) {
      return false;
    }
    for (let _jdx = _idx + 1; _jdx < circles.length; _jdx++) {
      const circle_j = circles[_jdx];
      const jdx = _jdx + 4 + 1;
      if (!dsjSet.has(jdx)) {
        dsjSet.add(jdx);
      }
      if (includesRectangle(w, h, circle_j)) {
        return false;
      }
      if (!visited.has(jdx)) {
        addUnion([w, h], dsjSet, jdx, circle_j);
        visited.add(jdx);
      }
      if (intersectsCircle(circle_i, circle_j) 
        && isIntersectionWithinBounds(w, h, circle_i, circle_j)
      ) {
        dsjSet.unify(idx, jdx);
      }
      if (isPathBlocked(dsjSet)) {
        return false;
      }
    }
  }
  return true;
}