RDM 2 Editorials

The problems for this round were designed in a way that allowed the solutions to the previous problems to be partially reused in the next ones without losing the independence of the problems.

For example the solution to the easy one could be used to create a visualizer for the medium problem. The solution to the medium problem could be extended to implement the search functionality for the hard problem.

The submissions for each problem were reviewed automatically using automated testers. The submitters were given sample submissions and sample testers to get a feel of how the automatic review works and to ramp up with faster with the needed Docker setup. They could extend the sample submissions with the required functionality but they also had freedom in choosing the frameworks/technologies for their submission.

Upon submitting, the automatic review generates reports and submitters could see some feedback that helped them improve their submissions before submitting again.

Easy | Brian Sets up a Home Office

For the first problem, a web page with some simple functionality was needed. No design was required, just a way to add items of the 4 types on the room floorplan, rotation and drag and drop functionality so the items could be moved around to be checked how they fit in the room. There were some restrictions like using only inline styles and using specific CSS properties for rotation and drag and drop. This allowed the automatic tester implementation to be simple and removed ambiguity from the requirements.

An example submission that passes all test cases: https://drive.google.com/file/d/1iDkbEJydNkjqPImyqf1vYljIxpw-DsJT/view?usp=sharing

It uses JQuery to load the input data

1
2
3
4
5
$.ajax({
      type: "GET",
      url: "items.csv",
      dataType: "text",
      success: (data) => {

and JQuery UI to implement the drag and drop functionality

1
2
3
4
5
6
7
8
9
10
11
12
const itemDiv = $('<div class="draggable" style="position: absolute; text-align: center;" />');
$('#room')
  .append(itemDiv);
itemDiv.text($('#items option:selected')
    .text())
  .attr('id', selectedItem.id)
  .css('left', '100px')
  .css('top', '100px')
  .width(dims[1] * 3)
  .height(dims[0] * 3)
  .css('background-color', bgColors[itemTypes.indexOf(selectedItem.type)]);
itemDiv.draggable();

Medium | Brian Sets up a Home Office

For this problem, a CLI app was required and the submitters had freedom in choosing the programming language as long as they could convert it to a shell command using the Dockerfile. The competitors received sample submissions and setups for 4 languages: Python, Javascript, Java and Go.

The algorithm used by the reference solution is presented below.

We have a list of N items of 4 possible types (sofa, desk, wardrobe, bookcase). We need to find all valid (sofa, desk, wardrobe, bookcase) tuples/combinations that can be formed using the items from that list. A combination is valid if each of its items can be placed against a different wall with the long side touching the wall in such a way that the items don’t overlap each other or the door area. Multiple positions might be possible for a combination. For this problem we only care if at least one is possible.

We can start by generating all combinations of items of the 4 types.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function generateCombinations(itemsPerType) {
  const combinations = [];
  const types = Object.keys(itemsPerType);
  for (let idx1 = 0; idx1 < itemsPerType[types[0]].length; idx1++) {
    const type1Element = itemsPerType[types[0]][idx1];
    for (let idx2 = 0; idx2 < itemsPerType[types[1]].length; idx2++) {
      const type2Element = itemsPerType[types[1]][idx2];
      for (let idx3 = 0; idx3 < itemsPerType[types[2]].length; idx3++) {
        const type3Element = itemsPerType[types[2]][idx3];
        for (let idx4 = 0; idx4 < itemsPerType[types[3]].length; idx4++) {
          const type4Element = itemsPerType[types[3]][idx4];
          combinations.push([type1Element, type2Element, type3Element, type4Element]);

        }
      }
    }
  }
  return combinations;
}

The next step will be to implement a function that checks if a combination is valid. There are 4 * 3 * 2 * 1 ways in which one can assign/arrange the 4 items to the 4 walls. E.g arrangement: sofa on the left wall, bookcase on the door wall, wardrobe on the right wall and desk on the against-the-door wall. If we check all 24 of the arrangements, then we can use the following greedy approach to position the items on the assigned walls:

(A) For each of the 24 arrangements:
(B) For each item in the arrangement:
(1) place the item in one of the wall corners
(2) try to place the next item as close as possible to the previous item without overlapping anything and do step (2) for the 2 remaining items
(3) If we could successfully place the items in this way, the combination is valid and we can exit loop (A). If not, we try the same algorithm starting from step (1) with the first item placed in the other wall corner.

The greedy approach of choosing a corner for the first item and then placing the other items as close as possible to each other doesn’t leave out valid intermediary positions on the wall.

Suppose the only valid position for an item on the chosen wall is not in a corner but somewhere on the middle of the wall. That means at least one of the adjacent items needs space towards that wall.

E.g. the wardrobe in the screenshot below cannot be in a corner, this position is the only valid one for this wall assignment

Since those corners in which the adjacent items need space cannot be used for other items, the adjacent items can be moved towards the corners until they touch the wall of the first item.

This way they free up space that might be needed by the 4th item in the opposite corners.

We now have an arrangement with at least one item in a corner (e.g. the desk in the screenshot above) and the other ones are placed as close to each other as possible. The algorithm above guarantees that this case will be checked because each item gets its turn to be the first one placed in a corner and for each item, each of the 2 possible wall corners are checked.

Another aspect that needs to be checked is whether the vis-a-vis items overlap.

The reference solution in Node.js that passes all test cases can be found here: https://drive.google.com/file/d/1tnQYI7fkrACHdGlSDEtvGSUzDCKtmoSP/view?usp=sharing

Hard | Brian needs to visualize the office

The hard problem required creating a web app for searching and visualizing valid furniture combinations (sofa, desk, bookcase, wardrobe). The solution for the medium problem could be reused here to calculate the valid combinations but there were some extra requirements that made the problem more difficult, like the filters that restricted certain furniture types on certain walls. E.g. “sofa on the left wall” and/or “desk on the door walls” and the search performance (at most 1 second per search + render). The users were allowed 15 seconds to pre-process data before the searching functionality was tested.

The reference solution calculates all possible arrangements (assignment of walls) for each furniture combination as a first step when the server starts so they are available in memory for filtering and sorting when a search request hits the server.

E.g. for combination (sofa1, desk1, bookcase1, wardrobe1) we could have the following valid arrangements (maximum 24 arrangements - see the medium problem reference solution):

• sofa1 on the left wall, desk1 on the right wall, bookcase1 on the door wall, wardrobe1 on the against-the-door wall

• sofa1 on the right wall, desk1 on the left wall, bookcase1 on the door wall, wardrobe1 on the against-the-door wall

• sofa1 on the against-the-door wall, desk1 on the right wall, bookcase1 on the door wall, wardrobe1 on the left wall

If we prepare all the valid arrangements for each valid combination, when a request with filter “sofa on the left wall” comes, we just need to filter all the arrangements to get the ones that have the sofa on the left wall, no need to run the algorithm again for different filters. In our example, we have a valid arrangement for (sofa1, desk1, bookcase1, wardrobe1) with the sofa on the left wall:

• sofa1 on the left wall, desk1 on the right wall, bookcase1 on the door wall, wardrobe1 on the against-the-door wall

Another challenging requirement was rendering the floorplans for the valid combinations. One thing is to get all the valid furniture combinations and another thing is to actually render one of the valid set of positions on the floorplan.

The reference solution uses a room object that maps the walls to the items and each wall contains info about the position of the item on that wall.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function getEmptyRoom() {
  return [
    {
      wallLength: roomDepth,
      remainingLengthRight: roomDepth,
      remainingLengthLeft: roomDepth,
      hasDoor: true,
      smallWall: true,
      occupiedDepth: 0
       },
    {
      wallLength: roomWidth,
      remainingLengthRight: roomWidth,
      remainingLengthLeft: roomWidth,
      hasDoor: false,
      smallWall: false,
      occupiedDepth: 0
       },
    {
      wallLength: roomDepth,
      remainingLengthRight: roomDepth,
      remainingLengthLeft: roomDepth,
      hasDoor: false,
      smallWall: true,
      occupiedDepth: 0
       },
    {
      wallLength: roomWidth,
      remainingLengthRight: roomWidth,
      remainingLengthLeft: roomWidth,
      hasDoor: true,
      smallWall: false,
      occupiedDepth: 0
       }
   ];
}

After populating the empty room object, we need to map the walls to DOM elements:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function generateItemDivs(room) {
  let res = '';
  if (room[0].item) {
    res += `<div id="$\{room[0].item.type\}" class="draggable" style="position: absolute; text-align: center; background-color: #eee;
           width: $\{Number(room[0].item.dimensions.split(' x ')[1]) * 3\}px;
           height: $\{Number(room[0].item.dimensions.split(' x ')[0]) * 3\}px;
           left: 0px;
           top: $\{room[0].remainingLengthLeft * 3\}px;">$\{room[0].item.name\}, $\{room[0].item.price\}</div>`;
  }
  if (room[1].item) {
    res += `<div id="$\{room[1].item.type\}" class="draggable" style="position: absolute; text-align: center; background-color: #eee;
           width: $\{Number(room[1].item.dimensions.split(' x ')[0]) * 3\}px;
           height: $\{Number(room[1].item.dimensions.split(' x ')[1]) * 3\}px;
           left: $\{room[1].remainingLengthRight * 3\}px;
           top: 0px;">$\{room[1].item.name\}, $\{room[1].item.price\}</div>`;
  }
  if (room[2].item) {
    res += `<div id="$\{room[2].item.type\}" class="draggable" style="position: absolute; text-align: center; background-color: #eee;
           width: $\{Number(room[2].item.dimensions.split(' x ')[1]) * 3\}px;
           height: $\{Number(room[2].item.dimensions.split(' x ')[0]) * 3\}px;
           left: $\{(roomWidth - room[2].occupiedDepth) * 3\}px;
           top: $\{room[2].remainingLengthRight * 3\}px;">$\{room[2].item.name\}, $\{room[2].item.price\}</div>`;
  }
  if (room[3].item) {
    res += `<div id="$\{room[3].item.type\}" class="draggable" style="text-align: center; background-color: #eee; opacity: 0.6; position: absolute;
           width: $\{Number(room[3].item.dimensions.split(' x ')[0]) * 3\}px;
           height: $\{Number(room[3].item.dimensions.split(' x ')[1]) * 3\}px;
           left: $\{room[3].remainingLengthLeft * 3\}px; 
           top: $\{(roomDepth - room[3].occupiedDepth) * 3\}px;">$\{room[3].item.name\}, $\{room[3].item.price\}</div>`;
  }
  return res;
}

The reference solution in Node.js that passes all test cases can be found here: https://drive.google.com/file/d/1Ai2_BT_l0McSUjZLnJXr7nPv8CP3UeYl/view?usp=sharing