Automatically Fill and Sort Grid Rows From Sizes According to a maxRowSum

automatically-fill-and-sort-grid-rows-from-sizes-according-to-a-maxrowsum.markdown

Automatically Fill and Sort Grid Rows From Sizes According to a maxRowSum

A Pen by Christopher James Curtin on CodePen.

License.

index.html

<h1>Autofill Rows Accoring to Max Row Sum</h1>
<div class="info">
  <span style="color:#FFF;">takes a list of sizes:</span><br/> <span class="SizesList" style="letter-spacing:0"></span> <br/>
  <span style="color:#FFF;margin-top:15px;display:block;">and a max row sum:</span><span class="maxSum"></span>
  <span style="color:#FFF;display:block;max-width:400px;margin:0 auto;margin-top:15px;">and returns a 2-dimensional Array <em>(row sums grouped largset to smallest with best possible scenario for filling in entire rows)</em>:</span><br/><span class="result" style="letter-spacing:0"></span>
</div>

<br/>

<div class="sliders maxRowSum"  style="border-top:1px solid #343434;padding-top:25px"><strong>max row sum : </strong><input type="range" min="1" max="50" step="1"><label></label></div>
<div class="sliders maxItemSize"><strong>max item size : </strong><input type="range" min="1" max="50"><label></label></div>
<div class="sliders maxItemLength"><strong>No. of items : </strong><input type="range" min="1" max="50"><label></label></div>

<div class="info" style="color:#FFF">numbers indicate <span style="color:#ff497d;">item size</span>, <span style="color: #999; font-size:11px;">total item count</span>, and <span style="border: 1px solid #338b8c; color: #338b8c; background: #1e1f26; padding:2px 8px">row sum</span></div>
<div class="info" style="color:#999; font-size:11px;font-style:italic; letter-spacing:0;margin-top:25px;">sizes that exceed the <code>maxRowSum</code> will be prepended to the result</div>
<div class="info" style="color:#999; font-size:11px;font-style:italic; letter-spacing:0;margin-top:25px;">row sums below <code>maxRowSum</code> will be appended to the result</div>

<div id="app"></div>

script.js

// NOT PART OF MODULE
// ********************************************************************************
const randomListOfNumbers = (length = 12, max = 12) => {
  return Array.from({length: length}, () => Math.floor(Math.random() * (max - 1 + 1) + 1))
}
// ********************************************************************************

// // EDIT THESE VARIABLES
// // ---------------------------------------------------------------------------------------------
// const maxRowSum = 11;
// const SizesList = randomListOfNumbers(12, maxRowSum-1) // ex: [1, 1, 0, 0, 7, 1, 6, 7, 6, 0, 6, 2]
// // ---------------------------------------------------------------------------------------------

/**
 *
 * @param {number[]} arr List of numbers
 * @return {number}
 */
const sum = (arr) => arr.reduce((a, c) => a + c, 0);

/**
 * Removes each of the values from arr
 * @param {array} arr
 * @param {array} values
 * @return {array}
 */
const removeValuesFromArray = (arr, values) => {
  const newArr = [...arr];
  for (const value of values) {
    const index = newArr.indexOf(value);
    index !== -1 && newArr.splice(index, 1);
  }
  return newArr;
};

/**
 * Get ordered list of indices where `val` occurs.
 * @example:
     // find the index values for the number 3
     getValueIndexes([1,2,3,3,4,50,6,3,4,2], 3) --> [2,3,7]
 * @return {number[]}
 */
const getValueIndexes = (arr, val) => {
  const indexes = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === val) {
      indexes.push(i);
    }
  }
  return indexes;
};

/**
 * Maps number sets to their index locations from a list of sizes
 * @param {number[]} numbers List of sizes, ex: [5,4,3,3,2,2,2,1]
 * @param {array[number]} numberSets a list of numberSet values which we want to map, ex: [ [5], [4,1], [3,2] [3,2], [2] ]
 * @return {array[number]} ex: [ [0], [1,7], [2,4] [3,5], [6] ]
 */
const createIndexSets = (numbers, numberSets) => {
  // used to keep count of the amount of times a size has already been mapped from
  const mappedNumbers = [];
  return numberSets.map((numberSet) => {
    return numberSet.map((num) => {
      // how many times has num been extracted from original numbers?
      const numOfTimesUsed = mappedNumbers.filter((x) => x === num).length;
      // get the next index location for num
      const numberIndex = getValueIndexes(numbers, num)[numOfTimesUsed];
      // keep count of size used
      mappedNumbers.push(num);
      return numberIndex;
    });
  });
};

/**
 *
 * @param {number} size The size to be inserted into a row
 * @param {number[]} sizeList A flat list of numbers containing all remaining sizes to insert
 * @param {array[]} rows Superset containing each row Array: number[]
 * @param {number} row The row index in which to insert the size
 * @param {number} maxRowSum The max sum of all sizes for a single row
 * @param {boolean} startNewRow When true, creates new row array for position `row`
 */
const insertRowSize = (
  size,
  sizeList,
  rows,
  row,
  maxRowSum,
  startNewRow = false
) => {
  if (!sizeList.length || size === 0) return rows;

  // create empty array to push row sizes into
  if (startNewRow) {
    rows[row] = [];
    // reset after new row is created
    startNewRow = false;
  }

  const currentRowSum = sum(rows[row]);
  const attemptedRowSum = currentRowSum + size;
  const rowTooLarge = attemptedRowSum > maxRowSum;
  const rowFilled = attemptedRowSum === maxRowSum;
  const rowNotFilled = attemptedRowSum < maxRowSum;

  // adding the size would exceed the current maxRowSum; try the next lowest number to fill the current row before extracting it out of sizeList
  // do not extract the size out of sizeList yet, as it may fit in another row
  // note: any size which exceeds maxRowSum on its own is not account for here, but rather prepended to the sumSets when `includeValuesExceeded = true`
  if (rowTooLarge) {
    // filter out sizeList of any same-size values to try next largest possible fit for the row
    // ..Math.max() will return `-Infinity` on an empty array; bad;
    // ...important to append a ZERO to a filtered sizeList so that we know whether or not the currently iterated size is the max size in the list,
    // meaning no more sizes and any additional sizes in sizeList should be added into their OWN row (they would all exceed maxSumSize for the row)
    size = Math.max(...sizeList.filter((s) => s < size), 0);
    // current row iteration as attempted to use all available sizes and none fit; start new row w/ next max value;
    if (size === 0 && sizeList.length > 0) {
      // reset size to max value in sizeList
      size = Math.max(...sizeList, 0);
      row++;
      startNewRow = true;
    }
  }

  // size fits in the row but does not fill the entire row; try the next lowest number to fill the current row
  if (rowNotFilled) {
    rows[row].push(size);
    // remove size from list
    sizeList = removeValuesFromArray(sizeList, [size]);
    // then get next largest size
    size = Math.max(...sizeList, 0);
  }

  // size fits perfectly into the row; start new row
  if (rowFilled) {
    startNewRow = true;
    rows[row].push(size);
    row++;
    // remove size from list
    sizeList = removeValuesFromArray(sizeList, [size]);
    // then get next largest size
    size = Math.max(...sizeList, 0);
  }

  rows = insertRowSize(size, sizeList, rows, row, maxRowSum, startNewRow);

  return rows;
};

/**
 * Generate subsets of sizeList, creating as many subset "rows" as possible, using each value only once, sorted from largest to smallest(by default)
 * Each "row" is a subset of sizeList with a total sum no greater than maxRowSum; any remaining sizes appended, and sizes that exceed maxRowSum can be prepended
 * @param {number[]} sizeList list of "widths/sizes" to generate rows from
 * @param {number} maxRowSum the max sum of a single row
 * @param {boolean} includeValuesExceeded default by true with exceeding sizes prepended to sumSets and indexSets;
 *        when false, the exceeding values are separate in the response
 */
const generateRows = (
  sizeList,
  maxRowSum,
  includeValuesExceeded = true
) => {
  // need original list to map sizes to indices
  const originalSizeList = [...sizeList];
  // for values in sizeList that exceed the maxRowSum on their own; place them in their own list separate from values that DO fit
  // each size is placed into it's own "group"; largest to smallest // [ [ 8 ], [ 5 ], [ 3 ] ]
  const valuesExceeded = sizeList
    .filter((size) => size > maxRowSum)
    .map((x) => [x]);
  // only allow sizes in the rows that are smaller or equal to the maxRowSum
  sizeList = sizeList.filter((size) => size <= maxRowSum);
  // start w/ inserting largest size first
  const size = Math.max(...sizeList, 0);
  // create superset to store row sum sets/groups
  const rows = [];
  // only create an empty starting row, if sizeList actually includes values that don't exceed maxRowSum; failsafe;
  size <= maxRowSum && rows.push([]);
  // row index to start inserting sizes
  const row = 0;
  // 2-dimensional array containing all row groups. ex: if maxRowSum = 5 -> [ [5], [4,1], [3,2], [2,2,1], ...  ]
  const sumSets = [
    // prepend all sizes which exceed maxRowSum on their own(by default)
    ...(includeValuesExceeded && valuesExceeded),
    // insert first size into grid
    ...insertRowSize(size, sizeList, rows, row, maxRowSum)
  ]
  // sort largest rows to smallest rows
  .sort((a,b) => sum(b) - sum(a))
  // the index sets for each sum set
  let indexSets = createIndexSets(originalSizeList, sumSets);
  // not used internally; just returned
  const indexSets_valuesExceeded = createIndexSets(
    originalSizeList,
    valuesExceeded
  );
  // map the indexSets over to an array of some data
  const mappedIndexSets = (data) => {
    return indexSets.map((indexSet) => indexSet.map((index) => data[index]));
  };
  // return dat sheit
  return {
    sumSets,
    indexSets,
    valuesExceeded,
    indexSets_valuesExceeded,
    mappedIndexSets,
  };
};


// DOM MANIPULATION EXAMPLE
// ========================
const generateDOM = ({maxRowSum = 20, maxItemSize = 8, maxItemLength = 26, init = false}) => {
  maxRowSum = parseInt(maxRowSum)
  maxItemSize = parseInt(maxItemSize)
  maxItemLength = parseInt(maxItemLength)
  // update UI w/ initial values
  if(init) {
    document.querySelector('.maxRowSum input').value = maxRowSum
    document.querySelector('.maxItemSize input').value = maxItemSize
    document.querySelector('.maxItemLength input').value = maxItemLength

    document.querySelector('.maxRowSum label').innerHTML = maxRowSum
    document.querySelector('.maxItemSize label').innerHTML = maxItemSize
    document.querySelector('.maxItemLength label').innerHTML = maxItemLength
  }
  // PERFORMANCE TEST
  // ================
  const SizesList = randomListOfNumbers(maxItemLength, maxItemSize);
  document.querySelector('.SizesList').innerHTML = "<code>[ " + SizesList.toString() + " ]</code>"
  document.querySelector('.maxSum').innerHTML = "<code>"+maxRowSum+"</code>"
  
  const t0 = performance.now();
  const result = generateRows(SizesList, maxRowSum);
  const t1 = performance.now();
  console.log("EXECUTION TIME : " + Math.round(1000 * (t1 - t0)) / 1000 + "ms");
  // console.log(result.sumSets);
  // console.log(result.indexSets);
  // console.log(result.remainingNumbers);

  // RESULTS TO WORK WITH
  // ===================
  // returns a two-dimensional array of the inital data list; sorted into appropriate rows from largset sizes to smallest sizes(by default), fitting as many rows as possible according to "maxRowSum"
  // Ex: [ [ indexLocation, indexLocation ], [ indexLocation ], [ indexLocation, indexLocation ] ]
  const mappedIndexSets = result.mappedIndexSets(SizesList);
  document.querySelector('.result').innerHTML = "<code>"+ JSON.stringify(mappedIndexSets) +"</code>"

  const target = document.querySelector("#app");
  target.innerHTML = ""
  const rowContainer = document.createElement("ul");
  rowContainer.classList.add("rows");
  target.insertAdjacentElement("beforeend", rowContainer);

  let itemIndex = 0
  mappedIndexSets.forEach((row, rowIndex) => {
    const rowList = document.createElement("ul");
    const rowMaxWidth = (sum(row.map((x) => x)) / maxRowSum) * 100;
    const blockSpacing = 0;
    // rowList.style.height = `${Math.floor(Math.random() * 100) + 25  }px`;
    rowList.style.maxWidth = `${rowMaxWidth}%`;
    rowList.style.marginBottom = blockSpacing + "px";
    row.forEach((size, index) => {
      const block = document.createElement("li");
      // block.style.height = '100%' // `${Math.floor(Math.random() * 200) + 25  }px`;
      block.style.margin = 0;
      block.style.maxWidth = `calc(${
        (size / sum(row.map((x) => x))) * 100 + "%"
      } - ${index === 0 ? 0 + "px" : blockSpacing + "px"})`;
      if (row.length === 1) {
        block.style.maxWidth = "100%";
      }
      itemIndex++
      block.innerHTML = size + '<span class="itemCounter">' + itemIndex + '</span>';
      rowList.insertAdjacentElement("beforeend", block);
    });
    const rowSum = document.createElement('div')
    rowSum.classList.add('rowSum')
    rowSum.innerHTML = sum(row)
    rowList.insertAdjacentElement("beforeend", rowSum);
    rowContainer.insertAdjacentHTML("beforeend", rowList.outerHTML);
  });
}

const updateGridValues = (init = false) => {
  const _maxRowSum = document.querySelector('.maxRowSum');
  const _maxItemSize = document.querySelector('.maxItemSize');
  const _maxItemLength = document.querySelector('.maxItemLength');

  const _maxRowSum_input = _maxRowSum.querySelector('input')
  const _maxItemSize_input = _maxItemSize.querySelector('input')
  const _maxItemLength_input = _maxItemLength.querySelector('input')

  const _maxRowSum_label = _maxRowSum.querySelector('label')
  const _maxItemSize_label = _maxItemSize.querySelector('label')
  const _maxItemLength_label = _maxItemLength.querySelector('label')
  
  const maxRowSum = _maxRowSum_input.value
  const maxItemSize = _maxItemSize_input.value
  const maxItemLength = _maxItemLength_input.value

  // update labels when values change
  _maxRowSum_label.innerHTML = maxRowSum
  _maxItemSize_label.innerHTML = maxItemSize
  _maxItemLength_label.innerHTML = maxItemLength

  init ? generateDOM({init}) : generateDOM({maxRowSum, maxItemSize, maxItemLength})
}

// updating w/ new values
document.querySelectorAll('input[type="range"]').forEach( input => input.addEventListener('input', (e) => {
  updateGridValues()
}))

updateGridValues(true)

style.postcss

@use postcss-nested;
body {
  display: flex;
  flex-direction: column;
  justify-content: center;
  align-items: center;
  height: 100%;
  min-height: 200px;
  font-family: helvetica;
  font-weight: 100;
  font-size: 12px;
  background: #100b12;
  color: #CCC;
}
* {
  box-sizing: border-box;
}

.rows {
  width: 800px;
  padding: 25px;
  display: flex;
  flex-direction: column;
  justify-content: center;
  align-items: center;
  ul {
    position: relative;
    margin: 0;
    padding: 0;
    width: 100%;
    display: flex;
    flex-direction: row;
    justify-content: space-between;
    align-items: center;
  }
  li {
    display: flex;
    justify-content: center;
    align-items: center;
    flex: 1;
    background: #0b070d;
    color: #ff497d;
    text-align: center;
    font-family: Roboto;
    font-size: 1.3em;
    letter-spacing: 1px;
    font-weight: 300;
    filter: drop-shadow(0px 0px 10px #ba385d2d);
    border-right: 1px solid #ba385dDd;
    border-bottom: 1px solid #ba385dDd;
    height: 50px;
    padding: 10px;
    text-shadow: 0 2px 1px #000;
    &:first-child {
      border-left: 1px solid #ba385dDd;
    }
  }
  /* top row of items */
  ul:first-child {
    li {
      border-top: 1px solid #ba385dDd;
    }
  }
}




.sliders,
.info {
  margin-top: 20px;
  color: #999;
  letter-spacing: 2px;
  display: flex;
  flex-direction: row;
  justify-content: center;
  align-items: center;
  text-align: center;
  width: 100%;
  max-width: 800px;
  strong {
    flex: 2;
    text-align: right;
    padding-right: 5px;
  }
  input {
    flex: 5;
    height: 5px;
  }
  label {
    flex: 1;
    padding-left: 10px;
  }
}

.info {
  display: block;
  line-height: 1.25;
}

.itemCounter {
  position: absolute;
  color: #999;
  font-size: 10px;
  vertical-align: top;
  top: 1em;
  left: 1em;
}

.rowSum {
  position: absolute;
  display: flex;
  justify-content: center;
  align-items: center;
  right: 0;
  transform:translateX(50%);
  height: 26px;
  width: 26px;
  padding: 10px;
  text-align: center;
  border-radius: 100px;
  border: 1px solid #338b8c60;
  font-size: 11px;
  color: #338b8c;
  background: #1e1f26;
}

code {
  font-family: monospace;
  font-weight: 100;
}

h1 {
  font-size: 3em;
  padding: 25px 0;
  font-weight: 100;
  font-family: Dosis;
  border-bottom: 1px solid #343434;
}

em {
  font-style: italic;
  font-size: 0.8em;
  color: #CCC;
}

styles

<link href="https://fonts.googleapis.com/css2?family=Dosis:wght@200&amp;family=Roboto:wght@100&amp;display=swap" rel="stylesheet" />