Forem: Dawid Ryłko

Przesyłanie adresów do Bing za pomocą Microsoft Bing URL Submission API i GitHub Actions

Dawid Ryłko — Wed, 18 Dec 2024 18:00:00 +0000

Dowiedz się, jak zautomatyzować proces przesyłania nowych i zaktualizowanych adresów URL do wyszukiwarki Bing za pomocą Microsoft Bing URL Submission API oraz GitHub Actions. Dzięki temu nowe treści na stronie zostaną szybciej zaindeksowane.

Czytaj dalej.

Przesyłanie adresów do Google za pomocą Indexing API i GitHub Actions

Dawid Ryłko — Wed, 14 Aug 2024 11:00:00 +0000

W artykule przedstawiono proces automatyzacji przesyłania adresów URL do Google przy użyciu Indexing API i GitHub Actions. Opisuje on krok po kroku, jak skonfigurować konto usługi w Google Cloud Console, dodać je do Google Search Console oraz zintegrować z GitHub Actions. Dzięki tej automatyzacji nowe strony internetowe będą szybciej indeksowane przez Google, co oszczędza czas i poprawia wydajność.

Czytaj dalej.

CSS Media Feature: Display Mode

Dawid Ryłko — Fri, 02 Aug 2024 18:00:00 +0000

Artykuł omawia funkcję @media (display-mode) w CSS, która pozwala na dostosowanie stylów w zależności od trybu wyświetlania aplikacji. Dowiedz się, jak działa i jak możesz z niej skorzystać.

Czytaj dalej.

CSS Media Feature: Scripting

Dawid Ryłko — Wed, 31 Jul 2024 18:00:00 +0000

Artykuł omawia funkcję @media (scripting) w CSS, która pozwala na dostosowanie stylów w zależności od dostępności skryptów w przeglądarce. Dowiedz się, jak działa i jak możesz z niej skorzystać.

Czytaj dalej.

AI w Chrome

Dawid Ryłko — Mon, 29 Jul 2024 12:00:00 +0000

Google wprowadził eksperymentalne funkcje AI w przeglądarkach Chrome dla deweloperów, umożliwiając dostęp do najnowszego wbudowanego modelu językowego Gemini Nano. W artykule przedstawiony zostanie proces instalacji, konfiguracji oraz wykorzystania nowych funkcji AI w Chrome, w tym ustawianie flag oraz korzystanie z API, takich jak createTextSession, prompt, i promptStreaming.

Czytaj dalej.

Domino tiling library

Dawid Ryłko — Sun, 21 Apr 2024 19:30:00 +0000

Projekt "Domino tiling" został odseparowany do osobnego repozytorium na GitHubie. Znajdziesz tam algorytmy, benchmarki oraz testy. Zapraszam do testowania oraz zgłaszania propozycji nowych funkcjonalności.

Czytaj dalej.

Domino tiling

Dawid Ryłko — Sun, 31 Dec 2023 02:30:00 +0000

Układanie płytek domino na kwadratowej planszy 2n x 2n nie wydaje się zbyt skomplikowane. Wyliczenie ilości możliwych układów w zależności od wymiaru planszy także nie powinno sprawić kłopotu. Problem pojawia się, gdy potrzebujemy to zrobić w rozsądnym limicie czasu.

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, 112202208776036178000000, 2444888770250892795802079170816, 548943583215388338077567813208427340288, 1269984011256235834242602753102293934298576249856

Problem

Na ile różnych sposobów można pokryć całkowicie planszę 8 x 8 płytkami domino 2 x 1?

Rozwiązanie

W celu śledzenia stanu użyjemy maski bitowej. Rozważamy dwa główne scenariusze: obecna pozycja jest zajęta, i obecna pozycja jest wolna. Gdy pozycja jest wolna, funkcja rozważa umieszczenie domino w pionie oraz poziomie.

W poszukiwaniu układów płytek

Sercem solvera jest funkcja rekurencyjna searchTileArrangements. Funkcja ta przeszukuje możliwe układy płytek domino na planszy, wykorzystując programowanie dynamiczne w celu optymalizacji.

Parametry

Parametry tej funkcji to: tilingMatrix, rowCount, colCount, rowIndex, colIndex, currentMask, nextMask.

function searchTileArrangements(params) {
  const {
    tilingMatrix,
    rowCount,
    colCount,
    rowIndex,
    colIndex,
    currentMask,
    nextMask,
  } = params;

  ...
}

Zakończenie działania funkcji

Po destrukturyzacji parametrów rozpoczynamy serię sprawdzeń. Zakończenie działania następuje, gdy rowIndex jest równy rowCount.

if (rowIndex === rowCount) {
  return;
}

Gdy colIndex osiągnie wartość większą lub równą niż colCount, następuje aktualizacja macierzy układów dla kolejnego wiersza i maski. Sposób tej aktualizacji wskazuje na wykorzystanie wcześniej obliczonych wyników w celu generowania nowych.

if (colIndex >= colCount) {
  tilingMatrix[rowIndex + 1][nextMask] += tilingMatrix[rowIndex][currentMask];
  return;
}

Obliczanie bitów

Następnie obliczamy bity reprezentujące obecną oraz następną kolumnę.

const currentBit = 1 << colIndex;
const nextBit = 1 << (colIndex + 1);

Rekurencyjne wywołanie

Gdy aktualny bit jest zajęty, rozpoczynamy rekurencyjne wywołanie z aktualizacją colIndex + 1 (płytka domino w pionie). W sytuacji przeciwnej, oprócz aktualizacji colIndex + 1, aktualizujemy również nextMask poprzez operację bitową OR (nextMask | currentBit).

currentMask & currentBit
  ? searchTileArrangements({ ...params, colIndex: colIndex + 1 })
  : searchTileArrangements({
      ...params,
      colIndex: colIndex + 1,
      nextMask: nextMask | currentBit,
    });

Pominięcie dwóch bitów

Aktualizacja colIndex + 2 następuje, gdy można pominąć dwa bity.

if (canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit)) {
  searchTileArrangements({ ...params, colIndex: colIndex + 2 });
}

Funkcja sprawdzająca, czy możliwe jest pominięcie dwóch bitów (płytka domino w poziomie), prezentuje się następująco.

function canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit) {
  return (
    colIndex + 1 < colCount &&
    !(currentMask & currentBit) &&
    !(currentMask & nextBit)
  );
}

Obliczanie ilości uładów

Wyodrębnienie funkcji calculateTotalTilingCombinations to kwestia gustu.

function calculateTotalTilingCombinations({ rowCount, colCount }) {
...
}

Potrzebne było mi miejsce, gdzie będę mógł stworzyć i zainicjalizować macierz, ustawić punkt startowy dla algorytmu, rozpocząć iteracje oraz zwrócić wynik.

Utworzenie macierzy początkowej

Funkcja createInitialTilingMatrix tworzy i inicjalizuje macierz (dwuwymiarową tablicę), która jest używana do śledzenia liczby możliwych układów płytek domino. Macierz tilingMatrix przechowuje wyniki pośrednie, umożliwiając uniknięcie powtórnego obliczania tych samych wartości.

const tilingMatrix = createInitialTilingMatrix(rowCount, colCount);

Każdy wiersz odpowiada stanowi wiersza na planszy. Każda kolumna w wierszu odpowiada możliwemu układowi płytek w danym wierszu. Reprezentacja odbywa się za pomocą maski bitowej.

function createInitialTilingMatrix(rowCount, colCount) {
  return Array.from({ length: rowCount + 1 }, () =>
    new Array(1 << colCount).fill(0),
  );
}

Ustawienie punktu startowego

Pierwszy element to lewy górny róg macierzy. 1 oznacza, że mamy jedną kombinację dla pustej planszy.

tilingMatrix[0][0] = 1;

Iteracja

Poszukiwania rozpoczynamy od dwóch pętli for. Najpierw przez wszystkie wiersze macierzy, następnie wszystkie możliwe kombinacje (maski) dla danego wiersza.

for (let rowIndex = 0; rowIndex < rowCount; ++rowIndex) {
  for (let currentMask = 0; currentMask < 1 << colCount; ++currentMask) {
    searchTileArrangements({
      tilingMatrix,
      rowCount,
      colCount,
      rowIndex,
      colIndex: 0,
      currentMask,
      nextMask: 0,
    });
  }
}

Zwrócenie wyniku

return tilingMatrix[rowCount][0];

Uruchomienie

Rolę wejścia do programu pełni funkcja __main__.

function __main__() {
  const argsSchema = { '-r': 'rowCount', '-c': 'colCount' };
  const options = parseArgs(process.argv.slice(2), argsSchema);

  if (!options.rowCount || !options.colCount) {
    console.error(
      'Usage: node dominoTilingSolver.js -r <rowCount> -c <colCount>',
    );
    process.exit(1);
  }

  const result = calculateTotalTilingCombinations(options);
  console.log(result);
  process.exit(0);
}

Funkcja odpowiedzialna jest za:

pobranie argumentów z linii komend,
przetworzenie argumentów i ustawienie opcji,
obsługę błędów,
uruchomienie solvera,
wyświetlanie wyników.

Cały program

W celu otrzymania rozwiązań na liczbach wykraczających poza zakres Integer, solver został zmodyfikowany o wersję BigInt. Funkcje pomocnicze wykorzystywane w solverach oraz testach i benchmarkach znajdują się w folderze helpers. Całe programy można znaleźć poniżej lub na moim GitHubie. W celach testowych polecam pobrać cały folder, zamiast ręcznego tworzenia plików.

Cały program `Integer` - `dominoTilingSolver.js`

dominoTilingSolver.js

Uruchomienie:

node dominoTilingSolver.js -r <rowCount> -c <colCount>

Kod:

const { parseArgs } = require('./helpers');

function canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit) {
  return (
    colIndex + 1 < colCount &&
    !(currentMask & currentBit) &&
    !(currentMask & nextBit)
  );
}

function searchTileArrangements(params) {
  const {
    tilingMatrix,
    rowCount,
    colCount,
    rowIndex,
    colIndex,
    currentMask,
    nextMask,
  } = params;

  if (rowIndex === rowCount) {
    return;
  }

  if (colIndex >= colCount) {
    tilingMatrix[rowIndex + 1][nextMask] += tilingMatrix[rowIndex][currentMask];
    return;
  }

  const currentBit = 1 << colIndex;
  const nextBit = 1 << (colIndex + 1);

  currentMask & currentBit
    ? searchTileArrangements({ ...params, colIndex: colIndex + 1 })
    : searchTileArrangements({
        ...params,
        colIndex: colIndex + 1,
        nextMask: nextMask | currentBit,
      });

  if (canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit)) {
    searchTileArrangements({ ...params, colIndex: colIndex + 2 });
  }
}

function createInitialTilingMatrix(rowCount, colCount) {
  return Array.from({ length: rowCount + 1 }, () =>
    new Array(1 << colCount).fill(0),
  );
}

function calculateTotalTilingCombinations({ rowCount, colCount }) {
  const tilingMatrix = createInitialTilingMatrix(rowCount, colCount);
  tilingMatrix[0][0] = 1;

  for (let rowIndex = 0; rowIndex < rowCount; ++rowIndex) {
    for (let currentMask = 0; currentMask < 1 << colCount; ++currentMask) {
      searchTileArrangements({
        tilingMatrix,
        rowCount,
        colCount,
        rowIndex,
        colIndex: 0,
        currentMask,
        nextMask: 0,
      });
    }
  }

  return tilingMatrix[rowCount][0];
}

function __main__() {
  const argsSchema = { '-r': 'rowCount', '-c': 'colCount' };
  const options = parseArgs(process.argv.slice(2), argsSchema);

  if (!options.rowCount || !options.colCount) {
    console.error(
      'Usage: node dominoTilingSolver.js -r <rowCount> -c <colCount>',
    );
    process.exit(1);
  }

  const result = calculateTotalTilingCombinations(options);
  console.log(result);
  process.exit(0);
}

__main__();

Cały program `BigInt` - `dominoTilingSolver-BigInt.js`

dominoTilingSolver-BigInt.js

Uruchomienie:

node dominoTilingSolver-BigInt.js -r <rowCount> -c <colCount>

Kod:

const { parseArgs } = require('./helpers');

function canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit) {
  return (
    colIndex + 1 < colCount &&
    !(currentMask & currentBit) &&
    !(currentMask & nextBit)
  );
}

function searchTileArrangements(params) {
  const {
    tilingMatrix,
    rowCount,
    colCount,
    rowIndex,
    colIndex,
    currentMask,
    nextMask,
  } = params;

  if (rowIndex === rowCount) {
    return;
  }

  if (colIndex >= colCount) {
    tilingMatrix[rowIndex + 1][nextMask] += tilingMatrix[rowIndex][currentMask];
    return;
  }

  const currentBit = BigInt(1) << BigInt(colIndex);
  const nextBit = BigInt(1) << BigInt(colIndex + 1);

  currentMask & currentBit
    ? searchTileArrangements({ ...params, colIndex: colIndex + 1 })
    : searchTileArrangements({
        ...params,
        colIndex: colIndex + 1,
        nextMask: nextMask | currentBit,
      });

  if (canSkipTwoBits(colIndex, colCount, currentMask, currentBit, nextBit)) {
    searchTileArrangements({ ...params, colIndex: colIndex + 2 });
  }
}

function createInitialTilingMatrix(rowCount, colCount) {
  return Array.from({ length: rowCount + 1 }, () =>
    new Array(1 << colCount).fill(BigInt(0)),
  );
}

function calculateTotalTilingCombinations({ rowCount, colCount }) {
  const tilingMatrix = createInitialTilingMatrix(rowCount, colCount);
  tilingMatrix[0][0] = BigInt(1);

  for (let rowIndex = 0; rowIndex < rowCount; ++rowIndex) {
    for (let currentMask = 0; currentMask < 1 << colCount; ++currentMask) {
      searchTileArrangements({
        tilingMatrix,
        rowCount,
        colCount,
        rowIndex,
        colIndex: 0,
        currentMask: BigInt(currentMask),
        nextMask: BigInt(0),
      });
    }
  }

  return tilingMatrix[rowCount][0];
}

function __main__() {
  const argsSchema = { '-r': 'rowCount', '-c': 'colCount' };
  const options = parseArgs(process.argv.slice(2), argsSchema);

  if (!options.rowCount || !options.colCount) {
    console.error(
      'Usage: node dominoTilingSolver-BigInt.js -r <rowCount> -c <colCount>',
    );
    process.exit(1);
  }

  const result = calculateTotalTilingCombinations(options);
  console.log(result.toString());
  process.exit(0);
}

__main__();

Funkcje pomocnicze - `helpers`

helpers

Poniższa funkcja (parseCommandLineArguments.js) użyta jest w dominoTilingSolver.js oraz dominoTilingSolver-BigInt.js. Pozostałe funkcje wykorzystywane są w programie testowym oraz benchmarku.

/**
 * Parses command line arguments based on a provided schema.
 * @param {string[]} args The command line arguments.
 * @param {Object} schema The schema defining argument mappings.
 * @returns {Object} Parsed options with their corresponding values.
 */
function parseCommandLineArguments(args, schema) {
  const options = {};

  for (let i = 0; i < args.length; i++) {
    const currentArg = args[i];
    const nextArg = args[i + 1];

    if (schema[currentArg] && nextArg !== void 0) {
      options[schema[currentArg]] = parseInt(nextArg, 10);
      i++;
    }
  }

  return options;
}

module.exports = parseCommandLineArguments;

Wynik

Dane testowe wykorzystywane w testRunner.js oraz benchmarkRunner.js znajdują się w katalogu test-data na GitHubie.

Test runner

Do przetestowania algorytmu utworzony został program testRunner.js.

Uruchamiamy program za pomocą komendy w konsoli:

node testRunner.js

Wynik w konsoli dla wersji podstawowej:

Starting test execution...
Executing test 1 of 7 for dominoTilingSolver.js... Passed!
Executing test 2 of 7 for dominoTilingSolver.js... Passed!
Executing test 3 of 7 for dominoTilingSolver.js... Passed!
Executing test 4 of 7 for dominoTilingSolver.js... Passed!
Executing test 5 of 7 for dominoTilingSolver.js... Passed!
Executing test 6 of 7 for dominoTilingSolver.js... Passed!
Executing test 7 of 7 for dominoTilingSolver.js... Passed!
All tests completed successfully.

Benchmark runner

Obliczanie wydajności algorytmu odbywa się za pomocą programu benchmarkRunner.js. Głównym celem przedstawionego benchmarku nie jest pomiar wydajności na konkretnym urządzeniu, ale demonstracja różnic w wynikach w zależności od rozmiarów planszy.

Uruchomienie programu odbywa się w konsoli za pomocą komendy:

node benchmarkRunner.js -n <numberOfExecutions>

Gdzie n to liczba egzekucji programu.

Wynik w konsoli dla wersji podstawowej, dla 10 egzekucji:

Starting benchmark execution with 10 executions each...
Executing benchmark 1 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_1x2.txt
Executing benchmark 2 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_2x2.txt
Executing benchmark 3 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_4x4.txt
Executing benchmark 4 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_6x6.txt
Executing benchmark 5 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_8x8.txt
Executing benchmark 6 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_10x10.txt
Executing benchmark 7 of 7 for dominoTilingSolver.js... File saved: benchmark/dominoTilingSolver.js_12x12.txt
All benchmarks completed successfully.

Zapisane wyniki znajdują się w folderze benchmark.

Benchmark `Integer` - `dominoTilingSolver.js`

Rozmiar	Średni wynik [ms]	Ilość egzekucji
1x2	24.942	1000
2x2	25.749	1000
4x4	24.876	1000
6x6	27.603	1000
8x8	35.453	1000
10x10	94.160	1000
12x12	505.818	1000

Benchmark `BigInt` - `dominoTilingSolver-BigInt.js`

Rozmiar	Średni wynik [ms]	Ilość egzekucji
1x2	28.280	1000
2x2	29.005	1000
4x4	28.594	1000
6x6	31.335	1000
8x8	44.904	1000
10x10	145.033	1000
12x12	833.903	1000
14x14	5,615.200	10
16x16	37,765.400	10
18x18	248,372.000	1
20x20	1,640,246.000	1

Źródła

Richard Kenyon (2003), "An introduction to the dimer model", arXiv:math/0310326.
The On-Line Encyclopedia of Integer Sequences (OEIS), "Number of domino tilings (or dimer coverings) of a 2n X 2n square", oeis.org/A004003.
Wikipedia, "Domino tiling", en.wikipedia.org/wiki/Domino_tiling.

Największy skarb na płaszczyźnie euklidesowej

Dawid Ryłko — Mon, 27 Nov 2023 19:26:44 +0000

Wprowadzenie

Czy kiedykolwiek zastanawialiście się, jak za pomocą jednego algorytmu można odnaleźć najcenniejsze punkty w dwuwymiarowej przestrzeni? W dzisiejszym wpisie zgłębimy to zagadnienie mające zastosowanie w dziedzinach, takich jak analiza danych, grafika komputerowa czy algorytmy optymalizacyjne.

Problem

Dany jest zbiór $P$ zawierający punkty na płaszczyźnie euklidesowej. Celem jest znalezienie $k$ -elementowego podzbioru $Q$ o maksymalnej sumie odległości między punktami.

Zdefiniowany problem możemy zapisać za pomocą wzoru:

Q^* = \underset{Q \subseteq P, |Q| = k}{\arg\max} \sum_{\lbrace u,v \rbrace \subseteq Q} d(u, v)

gdzie $d (u, v)$ to odległość między punktami $u$ i $v$ .

Algorytm

Opisany powyżej problem zostanie rozwiązany za pomocą programu napisanego w języku JavaScript.

Odległość między dwoma punktami

Pierwszym elementem składowym jest funkcja obliczająca odległość między dwoma punktami na płaszczyźnie euklidesowej. Łatwiej można to zrozumieć, wyobrażając sobie długość odcinka pomiędzy tymi punktami. Formalnie, odległość między punktem $P_1(x_1, y_1)$ , a punktem $P_2(x_2, y_2)$ możemy wyrazić wzorem:

d(P_1, P_2) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}

Funkcja calculateDistance to implementacja powyższego wzoru w języku JavaScript. Przyjmując punkty $P_1$ o współrzędnych $x_1, y_1)$ i $P_2$ o współrzędnych $x_2, y_2)$ , odległość euklidesowa między punktami to pierwiastek kwadratowy z sumy kwadratów różnic współrzędnych.

function calculateDistance(point1, point2) {
  return Math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2);
}

W powyższym kodzie:

(point1[0] - point2[0]) - oblicza różnicę współrzędnych $x$ między punktami.
(point1[1] - point2[1]) - oblicza różnicę współrzędnych $y$ między punktami.
** 2 - podnosi każdy wynik do kwadratu.
Math.sqrt(...) - oblicza pierwiastek kwadratowy z sumy kwadratów, co daje nam ostateczną odległość euklidesową między punktami point1 i point2.

Największy podzbiór

Drugą składową będzie funkcja findLargestDistanceSubset. Ma ona na celu znalezienie $k$ -elementowego podzbioru $Q$ z danego zbioru punktów $P$ . Suma odległości między każdą parą punktów ma być jak największa.

function findLargestDistanceSubset(points, k) {
  const n = points.length;
  const Q = [];
  const distances = new Array(n);

  // Obliczanie sum odległości...

  return { distanceSum, selectedIndexes: Q };
}

W powyższym kodzie:

n - liczba punktów w zbiorze $P$ .
Q - początkowo pusty zbiór, który będzie przechowywał wybrane punkty.
distances - tablica, w której distances[i] jest sumą odległości punktu $i$ od pozostałych punktów.

Algorytm zwraca obiekt zawierający sumę odległości (distanceSum) oraz indeksy wybranych punktów (Q).

Obliczanie sum odległości

Dla każdego punktu $i$ w zbiorze $P$ , obliczamy sumę odległości od wszystkich innych punktów. Wartość ta zostaje zapisana w tablicy distances[i].

\text{distances}[i] = \sum_{j=0}^{n-1} d(\text{points}[i], \text{points}[j])

gdzie $d(P_1, P_2)$ to odległość euklidesowa między punktami $P_1$ i $P_2$ , co jest obliczane za pomocą funkcji calculateDistance.

for (let i = 0; i < n; i++) {
  let distanceSum = 0;
  for (let j = 0; j < n; j++) {
    distanceSum += calculateDistance(points[i], points[j]);
  }
  distances[i] = distanceSum;
}

Wybieranie punktów do $Q$

Algorytm iteracyjnie dodaje do zbioru $Q$ punkt, który maksymalizuje wzrost sumy odległości w $Q$ .

while (Q.length < k) {
  let maxIncrease = -1;
  let bestPoint = null;

  // Wzrost sumy odległości...

  if (bestPoint !== null) {
    Q.push(bestPoint);
  } else {
    break;
  }
}

W powyższym kodzie:

maxIncrease - zmienna przechowująca dotychczasowy maksymalny wzrost sumy odległości.
bestPoint - indeks punktu, który jest najlepszym kandydatem do dodania do $Q$ .

Wzrost sumy odległości

Dla każdego punktu $i$ spoza $Q$ , obliczamy wzrost sumy odległości, jaki byłby uzyskany po dodaniu punktu $i$ do $Q$ .

\text{increase} = \sum_{j=0}^{k-1} \left( \text{distances}[i] - d(\text{points}[i], \text{points}[Q[j]]) \right)

Jeśli increase jest większe od maxIncrease, wtedy aktualizujemy maxIncrease i bestPoint.

for (let i = 0; i < n; i++) {
  if (!Q.includes(i)) {
    let increase = 0;

    for (let j = 0; j < Q.length; j++) {
      increase += distances[i] - calculateDistance(points[i], points[Q[j]]);
    }

    if (increase > maxIncrease) {
      maxIncrease = increase;
      bestPoint = i;
    }
  }
}

Obliczanie sumy odległości w $Q$

Po wybraniu $k$ punktów, obliczamy sumę odległości między każdą parą punktów w $Q$ .

\text{distanceSum} = \sum*{i=0}^{k-1} \sum*{j=i+1}^{k-1} d(\text{points}[Q[i]], \text{points}[Q[j]])

let distanceSum = 0;
for (let i = 0; i < Q.length; i++) {
  for (let j = i + 1; j < Q.length; j++) {
    distanceSum += calculateDistance(points[Q[i]], points[Q[j]]);
  }
}

Cała funkcja

function findLargestDistanceSubset(points, k) {
  const n = points.length;
  const Q = [];
  const distances = new Array(n);

  for (let i = 0; i < n; i++) {
    let distanceSum = 0;
    for (let j = 0; j < n; j++) {
      distanceSum += calculateDistance(points[i], points[j]);
    }
    distances[i] = distanceSum;
  }

  while (Q.length < k) {
    let maxIncrease = -1;
    let bestPoint = null;

    for (let i = 0; i < n; i++) {
      if (!Q.includes(i)) {
        let increase = 0;
        for (let j = 0; j < Q.length; j++) {
          increase += distances[i] - calculateDistance(points[i], points[Q[j]]);
        }

        if (increase > maxIncrease) {
          maxIncrease = increase;
          bestPoint = i;
        }
      }
    }

    if (bestPoint !== null) {
      Q.push(bestPoint);
    } else {
      break;
    }
  }

  let distanceSum = 0;
  for (let i = 0; i < Q.length; i++) {
    for (let j = i + 1; j < Q.length; j++) {
      distanceSum += calculateDistance(points[Q[i]], points[Q[j]]);
    }
  }

  return { distanceSum, selectedIndexes: Q };
}

Uruchomienie

Do uruchomienia potrzebujemy funkcji main, która pełni rolę wejścia do programu.

function main() {
  const args = process.argv.slice(2);
  let options = {};

  for (let i = 0; i < args.length; i++) {
    if (args[i] === '-f' && i + 1 < args.length) {
      options.file = args[i + 1];
      i++;
    } else if (args[i] === '-k' && i + 1 < args.length) {
      options.k = parseInt(args[i + 1]);
      i++;
    }
  }

  if (!options.file || !options.k) {
    console.log('Usage: node prog.js -f <file> -k <k>');
    return;
  }

  const data = fs.readFileSync(options.file, 'utf-8');
  const points = data
    .trim()
    .split('\n')
    .map(line => {
      const [x, y] = line.split(',').map(Number);
      return [x, y];
    });

  if (points.length < options.k) {
    console.log('The value of k is larger than the number of points.');
    return;
  }

  const result = findLargestDistanceSubset(points, options.k);

  console.log(result.distanceSum.toFixed(2));
  console.log(result.selectedIndexes.join(', '));
}

Jest odpowiedzialna za:

pobranie argumentów z linii komend,
przetworzenie argumentów i ustawienie opcji,
obsługę błędów,
odczytanie danych z pliku,
przetworzenie danych,
wywołanie algorytmu,
wyświetlanie wyników.

Cały program można znaleźć tu, a przykładowe punkty znajdują się tu.

Aby skorzystać z programu, należy go uruchomić z odpowiednimi parametrami, na przykład:

node prog.js -f points.txt -k 4

node prog.js - uruchamia program napisany w języku JavaScript. Wymagany NodeJS.
-f points.txt - określa plik, w którym znajdują się dane z punktami.
-k 4 - określa rozmiar poszukiwanego podzbioru punktów.

Wynik

Program wypisuje sumę odległości między punktami w wybranym podzbiorze oraz indeksy tych punktów. Przykład dla danych testowych z points.txt:

59.82
0, 91, 9, 99

Oznacza to, że punkty $Q$ o współrzędnych $(0, 0)$ , $(9, 1)$ , $(0, 9)$ , i $(9, 9)$ tworzą podzbiór, dla którego suma odległości między punktami jest największa spośród wszystkich możliwych 4-elementowych podzbiorów. Wartość tej sumy wynosi $59.82$ .

Złożoność czasowa algorytmu wynosi $O(n2+k⋅n)O(n^2 + k \cdot n)$ , gdzie $n$ to liczba punktów w zbiorze $P$ . Algorytm iteracyjnie dodaje punkty do zbioru, wybierając te, które maksymalizują sumę odległości.

Kwiaty czy zioła?

Dawid Ryłko — Fri, 17 Nov 2023 00:00:00 +0000

Problem programowania liniowego z maksymalizacją liniowej funkcji celu jest matematycznym zadaniem optymalizacyjnym, w którym celem jest znalezienie optymalnych wartości zmiennych decyzyjnych, tak aby zwiększyć lub osiągnąć maksymalną wartość określonej liniowej funkcji celu. W tym kontekście, optymalizuje się alokację zasobów, by osiągnąć najlepsze możliwe wyniki, jednocześnie spełniając liniowe ograniczenia związane z danym problemem.

Problem

Rolnik dysponuje obszarem o powierzchni 100 hektarów, na którym planuje uprawiać kwiaty i zioła wykorzystywane do produkcji kosmetyków. W sezonie każdy hektar ziół wymaga 4 godzin pracy i 60 zł kapitału, natomiast każdy hektar kwiatów wymaga 16 godzin pracy i 120 zł kapitału. W ciągu sezonu rolnik chce przepracować maksymalnie 800 godzin oraz dysponuje kapitałem w wysokości 74000 zł. Zysk z hektara ziół wynosi 240 zł, a z kwiatów 300 zł. Jakie ilości hektarów ziół i kwiatów powinien uprawiać, aby maksymalizować zysk?

Rozwiązanie

W celu rozwiązania zadania, można sformułować problem jako zadanie optymalizacyjne.

Wpierw wypiszmy założenia (zmienne), które będziemy rozpatrywać:

$x$ - ilość hektarów, na których uprawiane są zioła
$y$ - ilość hektarów, na których uprawiane są kwiaty

Teraz można przejść do opisu problemu.

Maksymalizujemy funkcję zysku :

$Z (x, y) = 240 x + 300 y$

Dodajemy ograniczenia :

$\leq 800$ - ograniczenie ilości godzin pracy

$\leq 74000$ - ograniczenie kapitału

Ograniczenia dodatkowe :

$\geq 0$ - ilość hektarów, na których uprawiane są zioła nie może być ujemna

$\geq 0$ - ilość hektarów, na których uprawiane są kwiaty nie może być ujemna

Rozwiązanie matematyczne

$\leq 800$

$\leq 74000$

$\geq 0$

Rozwiązaniem jest układ nierówności. Rozwiązując ten układ nierówności, możemy znaleźć optymalne wartości $x$ i $y$ .

Rozwiązanie programistyczne

Czas na konkrety. Jakie wartości kryją się pod $x$ i $y$ ?

Do rozwiązania powyższego problemu możemy użyć darmowego roziązania CLP , z pakietu OR-Tools od Google.

Route. Schedule. Plan. Assign. Pack. Solve.

from ortools.linear_solver import pywraplp

def main():
    solver = pywraplp.Solver.CreateSolver("CLP")
    if not solver:
        return

    x = solver.NumVar(0, 100, "Herbs")
    y = solver.NumVar(0, 100, "Flowers")

    print("Number of variables =", solver.NumVariables())

    solver.Add(x + y <= 100)
    solver.Add(4 * x + 16 * y <= 800)
    solver.Add(60 * x + 120 * y <= 74000)

    print("Number of constraints =", solver.NumConstraints())

    solver.Maximize(240 * x + 300 * y)

    print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print("Solution:")
        print("Max profit =", solver.Objective().Value())
        print("Area for growing herbs =", x.solution_value())
        print("Area for growing flowers =", y.solution_value())
    else:
        print("The problem does not have an optimal solution.")

if __name__ == " __main__":
    main()

Wynik w konsoli:

Number of variables = 2
Number of constraints = 3
Solving with Clp 1.17.7
Solution:
Max profit = 26000.0
Area for growing herbs = 66.66666666666666
Area for growing flowers = 33.333333333333336

Może nie piękne, ale praktyczne. Sami o sobie piszą tak:

OR-Tools to pakiet oprogramowania typu open source do optymalizacji zaprojektowany w celu rozwiązania najtrudniejszych na świecie problemów z routingiem, przebiegami, programowaniem liczb całkowitych i liniowych oraz programowaniem ograniczeń.

Przydatne linki

ortools.linear_solver.pywraplp

Zakres zmiennych, hoisting – co warto wiedzieć?

Dawid Ryłko — Mon, 04 Sep 2017 00:00:00 +0000

Koniec wakacji, czas brać się do roboty 🙂 W tym wpisie postaram się krótko i treściwie omówić zakres zmiennych i hoisting w JavaScript.

Zakres zmiennych

Zakres zmiennych w JavaScript, to temat nieco skomplikowany. Programista, który dopiero zaczyna swoją przygodę z JSem, może być w niemałym szoku próbując okiełznać tajniki sztuki.

for (var a = 0; a < 5; a++) {}
console.log(a); // 5

Na początek stwórzmy standardową pętlę for, w której deklarujemy zmienną a = 0. Poniżej odwołujemy się do tej zmiennej i jako rezultat dostajemy 5.

Wniosek: Deklaracja zmiennej poprzez słowo kluczowe var powoduje zalokowanie miejsca w pamięci i zachowanie stanu pomimo zakończenia pętli. Zmienna jest widoczna w kontekście funkcji.

Na ratunek `let` i `const`

W standardzie ECMAScript 2015 (ES6) wprowadzone zostały nowe słowa kluczowe let i const. Służą do tego samego co var, ale mają ograniczony zasięg.

let is the new var.

for (let a = 0; a < 5; a++) {}
console.log(a); // Uncaught ReferenceError: a is not defined

Jak widzimy w powyższym przykładzie, zamiana var na let daje wymierny skutek. Nie mamy dostępu do zmiennej poza blokiem for. O to nam chodziło... wykorzystujemy zmienną z kontekstu blokowego.

Jak się ma do tego const?

Deklaruje nazwaną stałą tylko do odczytu - MDN

Nie możemy ponownie przypisać wartości do const:

const a = 7;
a = 5; // Uncaught TypeError: Assignment to constant variable.

Nie możemy też ponownie zadeklarować stałej:

const a = 7;
const a = 5; // Uncaught SyntaxError: Identifier 'a' has already been declared

JS ma jednak swoje wymagania, a const może sporadycznie piszących w tym języku wprowadzić w błąd.

const a = [];
console.log(a); // []
a.push(2);
console.log(a); // [2]
a.push({ a: 3 });
console.log(a); // [2, {a: 3}]

W JavaScript const NIE oznacza deklaracji stałej wartości , lecz deklarację stałej referencji. W przypadku typów prymitywnych const zachowuje się tak jak oczekujemy. Przy typach złożonych mamy możliwość podmiany zawartości.

Idealnie obrazuje to przykład powyżej. Tworzymy stałą a = [], następnie poprzez metodę push dodajemy pierwszy element tablicy, itd.

Hoisting

Temat hoistingu jest często poruszany, zarówno na branżowych spotkaniach jak i rozmowach kwalifikacyjnych. To jeden z feature'ów JSa, o którym wszyscy słyszeli lub wkrótce usłyszą.

Hoisting, spolszczona nazwa windowanie, to mechanizm pozwalający na przeniesienie deklaracji zmiennych oraz metod na początek funkcji.

a = 5;
var a;
console.log(a); // 5

simpleFunction(); // hoisting

function simpleFunction() {
  console.log('hoisting');
}

W przykładzie pierwszym do zmiennej a przypisujemy 5, następnie ją deklarujemy. Log w konsoli daje rezultat 5. Drugi przykład, to wywołanie metody przed deklaracją. Rezultat taki sam jak wcześniej. Hoisting zadziałał.

Przy deklaracji zmiennych za pomocą słowa kluczowego let, hoisting zachowuje się bardziej przewidywalnie.

a = 5;
let a; // ReferenceError: a is not defined

Strict mode

Strict mode (tryb ścisły) to jeden z feature'ów ES5. Wprowadza kilka zmian do domyślnej semantyki JavaScript:

Pozwala wyeliminować ciche błędy (ang. silent errors).
Pozwala wyeliminować błędy, które uniemożliwiają optymalizację JSa przez przeglądarki.
Uniemożliwia stosowanie składni mogącej wystąpić w kolejnych odsłonach ECMAScript.

Temat został pobieżnie wywołany, przy okazji hoistingu, nie bez przyczyny. Strict mode nie zezwala na skorzystanie ze zmiennej, dopóki nie zostanie zadeklarowana.

Warto przeczytać:

ECMAScript 2016 – ES7 – zaczynamy!

Dawid Ryłko — Mon, 19 Sep 2016 00:00:00 +0000

ECMAScript to standard programistyczny i wyrocznia dla wielu języków skryptowych (m.in. JavaScriptu). Ukończony w czerwcu tego roku ECMAScript 2016 (ES7) jest najnowszą wersją owych standardów. Póki co pozostaje tylko ciekawostką i punktem zaczepnym dla geeków programowania.

Mimo, że poprzednia wersja ECMAScript została wydana już rok temu, to do tej pory nie doczekała pełnego wsparcia ze strony przeglądarek. Kod jest najczęściej przetwarzany do wersji ES5, która zapewnia, większą stabilność aplikacji.

ES7 - szybki przegląd

Wersja siódma standardu, znana pod oficjalną nazwą ECMAScript 2016 została sfinalizowana w czerwcu tego roku. Nie wnosi ona tak ogromnych zmian jak poprzednia wersja, nie ma tutaj tak przełomowych rozwiązań jak na przykład arrow function (=>). Są za to proste rozwiązania, które z łatwością będzie można wykorzystać w codziennej pracy. Wyjście specyfikacji ES7 jest także odpowiedzią na błędy zgłaszane prze community. Trend wyraźnie wskazuje na to, iż wpierw należy zapewnić pełne wsparcie przeglądarek oraz rozwiązać istniejące problemy, a dopiero później wprowadzać kolejne nowinki.

ECMAScript 2016 - Features

Dobrą wiadomościa dla ludzi zagubionych w czeluściach JavaScriptu jest fakt, że wersja ECMAScript 2016 wprowadza tylko dwie zasadnicze zmiany: Array.prototype.includes() oraz exponentiation operator (**).

Array.prototype.includes()

Metoda includes() sprawdza czy tablica zawiera zadany element.

Array.prototype.includes(value);

[1, 2, 3].includes(2); // true
[1, 2, 3].includes(4); // false
[1, 2, 3].includes(3, 3); // false
[1, 2, 3].includes(3, -1); // true
[1, 2, NaN].includes(NaN); // true

Exponentiation operator (`**`)

Exponentation operator zwraca taki sam wynik jak znana wszystkim metoda Math.pow(x, y). Pierwszy argument zostaje podniesiony do potęgi, która jest zadeklarowana w drugim argumencie.

2 ** 3; // 8
3 ** 2; // 9
3 ** 2.5; // 15.588457268119896
10 ** -1; // 0.1
NaN ** 2; // NaN

2 ** (3 ** 2); // 512
2 ** (3 ** 2); // 512
(2 ** 3) ** 2; // 64

Dokąd zmierzamy

Mnogość zmian oraz szeroki wachlarz możliwości jakie daje ECMAScript 6 budzi różnorakie emocje. Sceptycy twierdzą, że jest to przerost formy nad treścią i JS nigdy nie zostanie "prawdziwym" językiem programowania. Innych z kolei przeraża ogrom zmian. Ludzie związani z szeroko rozumianym front-endem często zaś popadają w huraoptymizm widząc jakie możliwości dają coraz to nowsze wersje specyfikacji ECMA. Pamiętajmy jednak o tym, że tak długo jak przeglądarki nie będą w stu procentach kompatybilne ze standardem, tak długo nie będziemy mogli korzystać z dobrodziejstw jakie zostają na dostarczone (chyba, że bezustannie będziemy korzystać z kompilatorów).

Źródła:

ECMAScript Next support in Mozilla - JavaScript | MDN [Wayback Machine]

Flexbox Layout – część 2 – children items

Dawid Ryłko — Sun, 05 Jun 2016 18:23:04 +0000

Rozdysponowanie elementów wewnątrz kontenera wcale nie jest takie proste. Czas na drugi wpis z serii Flexbox Layout , tym razem poświęcony potomkom kontenera – czyli children items.

Artykuł stanowi kontynuację serii. Pierwszy artykuł możesz przeczytać, klikając w: Flexbox Layout – część 1 – parent container.

Flex items to wszystkie obiekty wewnątrz kontenera z zadeklarowaną wartością flex. To właśnie operacje na potomkach oraz przypisanie im odpowiednich styli sprawiają, że cały układ zachowa się w możliwie najlepszy (co za tym idzie najbardziej optymalny) sposób.

Właściwości potomka (children items)

Flexbox Layout – Order

.item {
  order: NUMBER; /* default 0 */
}

Standardowo elementy w kontenerze są ułożone w kolejności występowania w pliku HTML. Kolejnością można jednak bez problemu sterować poprzez zastosowanie właściwości order.

Flexbox Layout – Flex grow

.item {
  flex-grow: NUMBER; /* default 0 */
}

Właściwość flex-grow umożliwia elementom powiększenie się, jeśli tego potrzebują. Przedstawiona właściwość przyjmuje wartość numeryczną. Wartość ta jest proporcją , zadeklarowanego dla elementu miejsca, względem całego wykorzystanego miejsca wewnątrz kontenera flex.

Jeśli wszystkim elementom wewnątrz kontenera zostanie przyporządkowana właściwość flex-grow: 1, to kontener rozdysponuje miejsce w taki sposób, aby wszystkie elementy dostały tyle samo miejsca. Jeśli zadeklarujemy wybranemu elementowi flex-grow: 2, a pozostałym flex-grow: 1, to wybrany element dostanie dwie wartości przypadające z podziału.

Ujemne wartości zostają oznaczone jako błędne.

Flexbox Layout – Flex shrink

.item {
  flex-shrink: NUMBER; /* default 1 */
}

Właściwość flex-shrink pozwala elementom na zmniejszanie się, jeśli jest to potrzebne.

Ujemne wartości zostają oznaczone jako błędne.

Flexbox Layout – Flex basis

.item {
  flex-basis: auto | SIZE; /* default auto */
}

Podstawową wielkość elementu wewnątrz flexible container uzyskujemy dzięki właściwości flex-basis. Brak zadeklarowanej wartości oznacza przyjęcie domyślnej – czyli auto. Inne wykorzystanie tej właściwości to podanie długości – np. 200px, 20em, 20% itp.

Flexbox Layout – Flex

.item {
  flex: none | [FLEX_GROW FLEX_SHRINK || FLEX_BASIS];
}

flex jest skrótem dla flex-grow, flex-shrink oraz flex-basis. Wg rekomendacji W3C zaleca się używanie właśnie tej właściwości, zamiast deklarowania wszystkich powyższych. Ponadto, przy niezadeklarowaniu wszystkich właściwości, skrót flex uzupełnia je automatycznie (kolejno 0 1 auto).

Kolejny wpis z tej serii poświęcony będzie wyrównaniu kontenera i elementów znajdujących się wewnątrz niego.

Forem: Dawid Ryłko

Przesyłanie adresów do Bing za pomocą Microsoft Bing URL Submission API i GitHub Actions

Przesyłanie adresów do Google za pomocą Indexing API i GitHub Actions

CSS Media Feature: Display Mode

CSS Media Feature: Scripting

AI w Chrome

Domino tiling library

Domino tiling

Problem

Rozwiązanie

W poszukiwaniu układów płytek

Parametry

Zakończenie działania funkcji

Obliczanie bitów

Rekurencyjne wywołanie

Pominięcie dwóch bitów

Obliczanie ilości uładów

Utworzenie macierzy początkowej

Ustawienie punktu startowego

Iteracja

Zwrócenie wyniku

Uruchomienie

Cały program

Cały program Integer - dominoTilingSolver.js

Cały program BigInt - dominoTilingSolver-BigInt.js

Funkcje pomocnicze - helpers

Wynik

Test runner

Benchmark runner

Benchmark Integer - dominoTilingSolver.js

Benchmark BigInt - dominoTilingSolver-BigInt.js

Źródła

Największy skarb na płaszczyźnie euklidesowej

Wprowadzenie

Problem

Algorytm

Odległość między dwoma punktami

Największy podzbiór

Obliczanie sum odległości

Wybieranie punktów do QQQ

Wzrost sumy odległości

Obliczanie sumy odległości w QQQ

Cała funkcja

Uruchomienie

Wynik

Kwiaty czy zioła?

Problem

Rozwiązanie

Rozwiązanie matematyczne

Rozwiązanie programistyczne

Przydatne linki

Zakres zmiennych, hoisting – co warto wiedzieć?

Zakres zmiennych

Na ratunek let i const

Hoisting

Strict mode

Warto przeczytać:

ECMAScript 2016 – ES7 – zaczynamy!

ES7 - szybki przegląd

ECMAScript 2016 - Features

Array.prototype.includes()

Exponentiation operator (**)

Dokąd zmierzamy

Źródła:

Flexbox Layout – część 2 – children items

Właściwości potomka (children items)

Flexbox Layout – Order

Flexbox Layout – Flex grow

Flexbox Layout – Flex shrink

Flexbox Layout – Flex basis

Flexbox Layout – Flex

Cały program `Integer` - `dominoTilingSolver.js`

Cały program `BigInt` - `dominoTilingSolver-BigInt.js`

Funkcje pomocnicze - `helpers`

Benchmark `Integer` - `dominoTilingSolver.js`

Benchmark `BigInt` - `dominoTilingSolver-BigInt.js`

Wybieranie punktów do $Q$

Obliczanie sumy odległości w $Q$

Na ratunek `let` i `const`

Exponentiation operator (`**`)