const MAX_WIDTH = 10 ** 9; // set to 10**9 to match constraints 

const MIN_PILLARS = 1;

const MAX_PILLARS = 25; // 2000; // 2000 default

const MIN_CIRCLES = MIN_PILLARS;

const MAX_CIRCLES = MAX_PILLARS;

const MIN_RADIUS = 1;

const MAX_RADIUS = 10 ** 9;

const MIN_PRICE = 1;

const MAX_PRICE = 10 ** 6;

/*

​

Constraints

2 <= W <= 10**9

0 <= Xk <= 10**9

1 <= Yk < W

1 <= Ri <= 10**9

1 <= Ci <= 10**6

​

easy:    1 <= N, M <= 50

medium:  1 <= N, M <= 400

special: 1 <= N, M <= 2000 && Xk==0 FOR EACH PILLAR

*/

const TIME_DELAY_MS = 5; // slows things down

const canvW = 600;

const canvH = 400;

const canyonMargin = 55;

var mouseDiv;

var canyon_width;

var max_x_val;

var the_pillar_amt;

var amt_circles;

var pillars;

var algochoice;

​

function setup() {

  createCanvas(canvW, canvH);

  algochoice = createRadio();

  algochoice.option('1', 'algo 1 - noname');

  algochoice.option('2', 'algo 2 - noname');

  algochoice.option('3', 'algo 3 - noname');

  algochoice.selected('1')

  algochoice.style('width', '140px');

  mouseDiv = createElement('mouseDivvy', '');

  noCursor();

  runSim();

}

​

function mouseClicked() {

  if (mouseButton === LEFT) {

    runSim();

  }

}

​

function mouseMoved() {

  if (mouseDiv == null) {

    mouseDiv = createElement('hi');

  } else {

    // the mouse should be mapped to the canyon region, taking

    // the assigned width into account.

    var xStart = canyonMargin;

    var yStart = canyonMargin;

    var yEnd = canvH - canyonMargin;

    var mappedMouseX = round(map(mouseX, xStart, canvW, 0, max_x_val));

    var mappedMouseY = round(map(mouseY, yEnd, yStart, 0, canyon_width));

    mouseDiv.html(`${mappedMouseX} ${mappedMouseY}`);

    // set the mouse div overlay position

    mouseDiv.position(mouseX, mouseY);

  }

}

​

function drawOverlay() {

  // vertical line (width)

  // canyon borders

  drawingContext.setLineDash([]);

  strokeWeight(1);

  stroke(0)

  line(0, canyonMargin, canvW, canyonMargin);

  line(0, canvH - canyonMargin, canvW, canvH - canyonMargin);

  fill(160, 82, 45);

  rect(0, canvH - canyonMargin, canvW, canyonMargin);

  rect(0, canyonMargin, canvW, -canyonMargin);

  // text and stuff

  drawingContext.setLineDash([7]);

  line(canyonMargin, canyonMargin, canyonMargin, canvH - canyonMargin);

  strokeWeight(0);

  fill(0);

  drawingContext.setLineDash([]); // THIS *****S up text too REEE

  textAlign(CENTER);

  text("Canyon", canyonMargin / 2, 185);

  text("Width", canyonMargin / 2, 200);

  text(`${round(canyon_width)}`, canyonMargin / 2, 215);

  text(`Canyon Length : ${round(max_x_val)}`, (canvW / 2), (canvH - canyonMargin) + 25)

  text(`Amt of pillars : ${the_pillar_amt}`, (canvW / 2), (canvH - canyonMargin) + 45)

  textAlign(LEFT);

  text("click to assign new values", 5, 15);

  text("North Rim", 15, canyonMargin - 5);

  text("South Rim", 15, (canvH - canyonMargin) + 15);

}

​

function mapRtoC(r) {

  // TODO WHY DOESNT THIS WORK

  console.assert( r < canyon_width, "wtf radius of circle larger than width? should not be allowed in this thingy ");

  return map(r, MIN_RADIUS, canyon_width, 1, canvH-(canyonMargin));

}

​

function mapXtoC(x) {

  return map(x, 0, max_x_val, canyonMargin, canvW);

}

​

function mapYtoC(y) {

  return map(y, 2, canyon_width, (canvH - canyonMargin), canyonMargin);

}

​

function sleep(millisecondsDuration) {

  return new Promise((resolve) => {

    setTimeout(resolve, millisecondsDuration);

  })

}

async function runjustnvmthiswhathever() {

  /* yeah uhh this function should not be named like this.

  it's meant to just generate a situation with a single best

  solution. there should still be another funciton that generates

  situations without solutions.

  */

  background(225);

  var width_W = round(random(MIN_WIDTH, MAX_WIDTH));

  canyon_width = width_W;

  var num_pillars_N = round(random(0, MAX_PILLARS));

  the_pillar_amt = num_pillars_N;

  amt_circles = round(random(MIN_CIRCLES, MAX_CIRCLES));

  //...whats gonna be the furthest pillar on the X thingy

  // WARNING, this is NOT how we get the values and this might

  // REALLY screw up if we think this is how it works so just ehh

  // WATCHOUT I CANT AEXPLAIN

  max_x_val = round(random(10, 10 ** 9));

  console.log(`Canyon of width ${width_W},`);

  console.log(`with ${the_pillar_amt} pillars and`);

  console.log(`a length of ${max_x_val}`);

  drawOverlay();

  stroke('blue');

  console.log(`Trying to build a ${the_pillar_amt} pillar single solution map `);

  circles = [];

  for (var i = 0; i < amt_circles; i++) {

    cr = round(random(MIN_RADIUS, canyon_width));

    cp = round(random(MIN_PRICE, MAX_PRICE));

    circles.push([cr, cp]);

  }

  //sort 

  circles = circles.sort(function(a, b) {

    return a[1] > b[1];

  })

  for (const b of circles) {

    console.log(`${b[0]} ${b[1]}`)

  }

  pillars = [];

  solution = [];

  solved = false;

  var max_solve_try = 100000;

  var tries = 0

  // generate the solution path

  console.log('trying to create solution');

  while (!solved && tries < max_solve_try) {

    var startX = random(0, max_x_val);

    var someCircle = circles[Math.floor(Math.random() * circles.length)];

    // bruteforce find better circles lol

    // this just wants to take the hugest circles, obv.. ;/

    var better = someCircle;

    for (var tmp = 0; tmp < circles.length; tmp++) {

      if (circles[tmp][0] >= better[0] && circles[tmp][1] <= better[1]) {

        better = circles[tmp];

      }

    }

    var startY = better[0];

    circle(mapXtoC(startX), mapYtoC(startY), mapRtoC(better[1]));

    tries++;

  }

  // generate extra pillars that dont make the solution more efficient

  console.log('generated single solution map I think, i hope');

  drawOverlay();

}

​

function sortedIndex(array, value) {

  // thanks thanks thanks thanks thanks https://stackoverflow.com/a/21822316/6934388

  var low = 0,

    high = array.length;

  while (low < high) {

    var mid = (low + high) >>> 1;

    if (array[mid] < value) low = mid + 1;

    else high = mid;

  }

  return low;

}

​

​

async function runSim() {

  background(225);

  var width_W = round(random(MIN_WIDTH, MAX_WIDTH));

  canyon_width = width_W;

  var num_pillars_N = round(random(MIN_PILLARS, MAX_PILLARS));

  the_pillar_amt = num_pillars_N;

  amt_circles = round(random(MIN_CIRCLES, MAX_CIRCLES));

  //...whats gonna be the furthest pillar on the X thingy

  // WARNING, this is NOT how we get the values and this might

  // REALLY screw up if we think this is how it works so just ehh

  // WATCHOUT I CANT AEXPLAIN

  max_x_val = round(random(10, 10 ** 9));

  console.log(`Canyon of width ${width_W},`);

  console.log(`with ${the_pillar_amt} pillars and`);

  console.log(`a length of ${max_x_val}`);

  drawOverlay();

  stroke('blue');

  computer = new CanyonComputer();

  console.log('creating all circles');

  circles = [];

  for (var i = 0; i < amt_circles; i++) {

    cr = round(random(MIN_RADIUS, canyon_width));

    cp = round(random(MIN_PRICE, MAX_PRICE));

    circles.push([cr, cp]);

  }

  console.log('sorting all circles');

​

  computer.addCircles(circles);

  console.log('added all circles');

  console.log(`generating ${the_pillar_amt} pillars now`);

  for (var i = 0; i < num_pillars_N; i++) {

    var px = random(0, max_x_val)

    var py = random(2, width_W);

    var mpx = mapXtoC(px);

    var mpy = mapYtoC(py);

    computer.addPillar([px, py]);

    sleep(i * TIME_DELAY_MS).then(function h(){ 

      strokeWeight(3);

      point(mpx, mpy);

    });

  }

  console.log('added all pillars');

  drawOverlay();

  await computer.solve();

}

​

​

​

class CanyonComputer {

  constructor(N, W, M) {

    this.N = N;

    this.W = W;

    this.M = M;

    this.maxR = -Infinity;

    this.pillars = [];

    this.circlesSmallFirst = [];

    this.circlesCheapFirst = [];

    this.furthest = [-Infinity, -Infinity];

    this.closest = [Infinity, Infinity];

    this.algo = algochoice.value();

    console.log(`algo choice: ${this.algo}`)

  }

​

async solveAlgo1NoNameYetLol() {

  var cc = this.circlesSmallFirst;

  var mmrr = this.maxR;

  var mr = mapRtoC(this.maxR);

  console.log(`Solving with nonamed algo thing 1 mess hhhhh`);

  console.log(`there are: ${this.pillars.length} pillars`);

  console.log(`there are: ${cc.length} circles`);

  console.log(`first: ${cc[0][0]} for ${canyon_width}`);

  console.log(`first: ${cc[0][1]} `);

  noFill();

  var had = new Set();

  for (const p of this.pillars){

    for (const l of this.pillars){

      had.add([p,l]);

      if (had.has([l,p])){continue;}

      if (p==l){continue;}

      stroke(0,0,200,100);

      if (dist(p[0],p[1],l[0],l[1]) < this.maxR){

        //console.log(`${dist(p[0],p[1],l[0],l[1])} < ${mr}`)

        await sleep(0).then(function drawline(){

          strokeWeight(1);

          if (!had.has(p)){

            drawingContext.setLineDash([4]);

          stroke(0,0,200,100);

          line(mapXtoC(p[0]),mapYtoC(p[1]),

               mapXtoC(l[0]),mapYtoC(l[1]))

          }

          stroke(0,155,200,55);

          if (!had.has(p)){

          drawingContext.setLineDash([2]);

            fill(0,0,100,20);

          circle(mapXtoC(p[0]),mapYtoC(p[1]), mr);

            }

          had.add(p);

        });

      }

    }

  }

  drawingContext.setLineDash([]);

  strokeWeight(3);

  stroke(0,220,0,220);

  line(mapXtoC(this.furthest[0]),mapYtoC(this.furthest[1]),

      mapXtoC(this.furthest[0]),canyonMargin)

  line(mapXtoC(this.closest[0]),mapYtoC(this.closest[1]),

      mapXtoC(this.closest[0]),mapYtoC(0))

  drawOverlay();

}

  solve() {

    switch (this.algo) {

      case '1':

        this.solveAlgo1NoNameYetLol();

        break;

      case '2':

        break;

      case '3':

        break;

      default:

        console.log(`algo ${this.algo} doesnt exist`);

        break;

    }

  }

  addPillar(p) {

    if (p[1] > this.furthest[1]) {

      this.furthest = p;

    }

    if (p[1] < this.closest[1]) {

      this.closest = p;

    }

    this.pillars.push(p);

  }

  addCircles(circles){

    this.circlesSmallFirst = circles.slice();

    this.circlesSmallFirst.sort(function(a, b) {

    return a[0] > b[0];

  })

    this.circlesCheapFirst = circles.slice();

    this.circlesCheapFirst.sort(function(a, b) {

    return a[1] > b[1];

  })

    this.maxR = max(this.circlesSmallFirst[this.circlesSmallFirst.length-1][0]);

    console.log(`max R ; ${this.maxR}`)

​

  }

}