math_marathon_2020_task_3

<!DOCTYPE html>
<html>
<head>
  <title>math marathon 2020 task 3</title>
</head>
<body>


<canvas id="canvas" width=10000 height=10000 >
</canvas>
<script>
  var ctx = document.getElementById('canvas').getContext('2d')

  var circle = function (x, y, radius, color, fillCircle=true) {
  ctx.beginPath();
  ctx.arc(x, y, radius, 0, Math.PI * 2, false);
  if (fillCircle) {
    ctx.fillStyle = color;
    ctx.fill();
  } else {
    ctx.strokeStyle = color;
    ctx.stroke();
  }
};


/**
 * Возвращает строку длины n состоящую из символов s
 * Имеет логарифмическую сложность.
 *
 * @param   {String} s
 * @returns {String}
 */
function repeat(s, n) {
    let ans = s;
    let len = 1;

    while (n / len > 1) {
        ans += ans;
        n -= len;
        len *= 2;
    }
    if (n > 1) {
        ans += ans.substr(0, n - 1);
    }
    return ans;
}

function shift(line, move){
    move = -move % line.length;
    if (move == 0) {
        return line;
    }

    move = (move < 0) ? line.length + move : move;
    var result = [],
        index;
    for (var i = 0; i < line.length; i++) {
        index = (i + move) % line.length;
        result[i] = line[index];
    }
    return result.join('');
}

function reverseString(str) {

  return str.split("").reverse().join("");

}

String.prototype.replaceAt=function(index, replacement) {
    return this.substr(0, index+1
      ) + replacement+ this.substr(index + replacement.length);
}


// тех. параметры

r1 = 25 // радиус внутреннего кольца
r2 = 50 // радиус внешнего кольца

// координаты центра призмы
center_x = 200
center_y = 200

// сгенерируем граф: N-призму
N=5

// маленькие числа - внутреннее кольцо
// большие числа - внешнее кольцо

// коориданты точек
var points = {}

// отношения между точками
var graph = {}

// генерация внутреннего и внешнего кольца
var step = Math.PI*2/N

for (var i=0; i < N; i++) {
    // направление луча
    var angle = i*step

  // точка внутреннего кольца
  var x1 = center_x + Math.cos(angle)*r1;
  var y1 = center_y + Math.sin(angle)*r1;
  points[String(i)] = {"x": x1, "y": y1};

  // точка внешнего кольца
  var x2 = center_x + Math.cos(angle)*r2;
  var y2 = center_y + Math.sin(angle)*r2;
  points[String(i+N)] = {"x": x2, "y": y2};

  // добавим их в граф
  graph[String(i)] = []
  graph[String(i+N)] = []
}

//print(graph)

// построим рёбра графа
// проход по обоим кольцам одновременно
for (var i=0; i < N-1; i++) {
  // ребро между кольцами
  graph[String(i)].push(String(i+N))
  graph[String(i+N)].push(String(i))

  // ребро-сегмент внутреннего кольца
  graph[String(i)].push(String(i+1))
  graph[String(i+1)].push(String(i))

  // ребро-сегмент внешнего кольца
  graph[String(i+N)].push(String(i+N+1))
  graph[String(i+N+1)].push(String(i+N))
}

// последнее ребро
b = 0
e = N-1

graph[String(b)].push(String(e))
graph[String(e)].push(String(b))

graph[String(e)].push(String(e+N))
graph[String(e+N)].push(String(e))

graph[String(b+N)].push(String(e+N))
graph[String(e+N)].push(String(b+N))

right_ways = []
unique_right_ways = []
super_unique_right_ways = []

var time_1 = 0
var time_2 = 0
var time_3 = 0

var s_time = performance.now()

// кодирование раскраски графа будет таким:
// 0 - белый, 1 - черный, нумерация вершин с нуля
// пример раскраски: 010101 (первая, третья и пятая - белые, остальные - черные)

// перебираем все раскраски
for (var i=0; i < Math.pow(2, N*2)+1; i++) {
  var good = true
  // получаем номер текущей раскраски
  var painting = (i).toString(2)

  if (painting.length < N*2) {
    painting = repeat('0', (N*2 - painting.length)) + painting
  }
  // проходим по каждой вершине
  for (var j=0; j < painting.length; j++) {
    vex_color = painting[j]
    other_colors = new Set() // цвета соседей


    // пройдём по её соседям
    for (var k in graph[String(j)]) {
      // цвет соседа
      other_color = painting[Number(graph[String(j)][k])]
      other_colors.add(other_color)
    }
    if (other_colors.size == 1) {
      good = false
      break
    }
  }

  //if (painting == '111000') {
    //console.log(painting, good)
  //}

  if (good) {
    right_ways.push(painting)
  }
}

time_1= performance.now() - s_time

var get_rotations = function(way) {
  var rotated_ways = []
  // идём по первой половине
  for (var i=0; i < way.length/2; i++) {
    rotated_way = way.slice(i,N) + way.slice(0,i) + way.slice(i+N,N+N) + way.slice(N,i+N)
    rotated_ways.push(rotated_way)
  }

  return rotated_ways
}

var get_symmetricals = function(way) {
  symmetrical_ways = []
  // возвращает симметрию по каждой из осей
  // идём по вершинам - выбираем ось
  // если нечетное, то идём по всем осям
  if ( (way.length/2) % 2 == 1 ) {
    for (var i=0; i < way.length/2; i++) {
      // сдвинем так, чтобы ось была по-середине

      centered_way_1 = shift(way.slice(0, way.length/2), Math.floor(way.length/2)-i)
      centered_way_2 = shift(way.slice(way.length/2, way.length), Math.floor(way.length/2)-i)
      symmetrical_ways.push( reverseString(centered_way_1)+reverseString(centered_way_2) )
      symmetrical_ways.push(centered_way_1+centered_way_2)

    }
  } else {
    // ЗДЕСЬ НАДО ДОРАБОТАТЬ!!!

    for (var i=0; i < way.length/4; i++) {
      // идём по половие первой половины
      // четвёрки
      four_1 = way.slice(0, way.length/4)
      four_2 = way.slice(way.length/4, way.length/2)
      four_3 = way.slice(way.length/2, way.length/4*3)
      four_4 = way.slice(way.length/4*3, way.length)

     // console.log(four_1, four_2, four_3, four_4)

      // оси в каждой четвёрке
      axis_1 = four_1.split('').splice(i, 1)
      axis_2 = four_2.split('').splice(i, 1)
      axis_3 = four_3.split('').splice(i, 1)
      axis_4 = four_4.split('').splice(i, 1)

      four_1 = four_1.slice(0, i)+four_1.slice(i+1, four_1.length)
      four_2 = four_2.slice(0, i)+four_2.slice(i+1, four_2.length)
      four_3 = four_3.slice(0, i)+four_3.slice(i+1, four_3.length)
      four_4 = four_4.slice(0, i)+four_4.slice(i+1, four_4.length)

      symmetrical_ways.push( four_1.replaceAt(i-1, axis_1) + four_2.replaceAt(i-1, axis_2) + four_3.replaceAt(i-1, axis_3) + four_4.replaceAt(i-1, axis_4) )

      symmetrical_ways.push( reverseString(four_1+four_2).replaceAt(i-1, axis_1).replaceAt(i+way.length/4-1, axis_2) + reverseString(four_3+four_4).replaceAt(i-1, axis_3).replaceAt(i+way.length/4-1, axis_4))


    }
  }

  return symmetrical_ways
}

var draw_way = function(way, x, y) {
  // рисуем рёбра
  ctx.beginPath()
  for (var i=0; i < N; i++) {
    ctx.moveTo(x + Math.cos(i*step)*(r1+0), y + Math.sin(i*step)*(r1+0))
    ctx.lineTo(x + Math.cos((i+1)*step)*(r1+0), y + Math.sin((i+1)*step)*(r1+0))

    ctx.moveTo(x + Math.cos(i*step)*(r2+0), y + Math.sin(i*step)*(r2+0))
    ctx.lineTo(x + Math.cos((i+1)*step)*(r2+0), y + Math.sin((i+1)*step)*(r2+0))
  }


  ctx.stroke()

  // рисуем вершины
  for (var i=0; i < N; i++) {
    ctx.beginPath()
    ctx.moveTo(x + Math.cos(i*step)*(r1+10), y + Math.sin(i*step)*(r1+10))
    ctx.lineTo(x + Math.cos(i*step)*r2, y + Math.sin(i*step)*r2)
    ctx.stroke()
    // определяем цвет
    if (way[i] == '0') {
      circle(x + Math.cos(i*step)*r1, y + Math.sin(i*step)*r1, 10, 'white', true)
      circle(x + Math.cos(i*step)*r1, y + Math.sin(i*step)*r1, 10, 'black', false)
    } else {
      circle(x + Math.cos(i*step)*r1, y + Math.sin(i*step)*r1, 10, 'white', true)
      circle(x + Math.cos(i*step)*r1, y + Math.sin(i*step)*r1, 10, 'black', true)
    }

    // определяем цвет
    if (way[i+N] == '0') {
      circle(x + Math.cos(i*step)*r2, y + Math.sin(i*step)*r2, 10, 'white', true)
      circle(x + Math.cos(i*step)*r2, y + Math.sin(i*step)*r2, 10, 'black', false)
    } else {
      circle(x + Math.cos(i*step)*r2, y + Math.sin(i*step)*r2, 10, 'white', true)
      circle(x + Math.cos(i*step)*r2, y + Math.sin(i*step)*r2, 10, 'black', true)
    }
  }
}

var x_row = 12;
var y_row = 6;

var draw_all_ways = function(ways) {
  // 400 x 400
  for (var i=0; i < ways.length; i++) {
    // определяем позицию
    x = (i % x_row)*1.5
    y = Math.floor(i / x_row) * 1.5

    draw_way(ways[i], x*100+100, y*100+75)
  }
}

var s_time = performance.now()

for (var i in right_ways) {
  // изначально считаем, что эта раскраска уникальная
  var unique = true

  var way = right_ways[i]
  // перебор всех вариантов поворота (перебор первой половины)
  var rotated_ways = get_rotations(way)

  for (var j in rotated_ways) {

    if ( unique_right_ways.indexOf(rotated_ways[j]) != -1 ) {
      unique = false
      break
    }
  }

  if (unique) {
    unique_right_ways.push(way)
  }
}


time_2 = performance.now() - s_time


var s_time = performance.now()

for (var i in unique_right_ways) {
  var unique = true;
  var way =  unique_right_ways[i]
  var symmetrical_ways = get_symmetricals(way);

  for (var j in symmetrical_ways) {
    var sym_rot_ways = get_rotations(symmetrical_ways[j])
    for (var k in sym_rot_ways) {
      if ( super_unique_right_ways.indexOf(sym_rot_ways[k]) != -1 ) {
        unique = false
        break
      }
    }
  }

  if (unique) {
    super_unique_right_ways.push(way)
  }
}

time_3 = performance.now() - s_time

console.log( right_ways.length )
console.log(unique_right_ways.length)
console.log(super_unique_right_ways.length)

console.log( time_1.toFixed(2)+'/'+time_2.toFixed(2)+'/'+time_3.toFixed(2)+' ms' )

// отрисовка командой draw_all_ways()

//draw_all_ways(super_unique_right_ways); // варианты с учетом поворота и симметрии
//draw_all_ways(unique_right_ways) // варианты с учетом поворота
//draw_all_ways(right_ways) // все правильные варианты, т.е. варианты без учёта поворота и симметрии
//console.log(right_ways.length)

//draw_all_ways(get_symmetricals("10001011"))

</script>

</body>
</html>