Skip to content

Instantly share code, notes, and snippets.

@terribleplan
Last active August 29, 2015 14:22
Show Gist options
  • Save terribleplan/ab21de9c309d0394b930 to your computer and use it in GitHub Desktop.
Save terribleplan/ab21de9c309d0394b930 to your computer and use it in GitHub Desktop.
/r/dailyprogrammer [217]

Here is a near-ideal, overly complex, ECMA6 solution to #217. This solution is less than ideal in 3 ways:

  1. There are 2 instances when the input is looped over entirely due to the separation of parsing logic and the logic that builds the initial index. This could be fixed, but shouldn't really since the concerns are wholly separate. Theoretically this also allows for pluggable inputs (who knows, maybe in one you don't need to loop to parse the input). I don't consider the parsing in the complexity for my solution.
  2. My solution does not follow l->r t->b insertion order, except at the very beginning. To fix this there could be a binary search for an insertion position within the index the node is moving to, creating some sort of meta order to the index contents. (I may fix this if I get bored). This is potentially weird because once pile size parity is reached the increase pattern is always going to be the same, so some weird optimizations become possible (esp. since we know the insertion number in advance).
  3. It's so long, ~120 lines. OO programming is annoying. Jeez. (And no browser can even run it without transpiling.)

Also I could probably refactor it to just use one array (or even just the indexes). But really that stuff is only used in the toString logic, and there is very little reason to do it. (And it is nice to be able to simply .join to build the string)

class LogPile {
constructor(logIndex, initialCount) {
this.index = logIndex;
this.size = initialCount || 0;
this.indexEntry = this.index.addLogPile(this);
}
addLog() {
this.indexEntry.removeLogPile(this);
this.size++;
this.indexEntry = this.index.addLogPile(this);
return this;
}
}
class LogIndex {
constructor(builtIndex) {
this.index = builtIndex;
}
addLog() {
this.index[0].addLog();
}
addLogPile(pile) {
for (var i = 0; i <= this.index.length; i++) {
if (this.index.length === i || this.index[i].size > pile.size) {
var ie = IndexEntry.fromPile(pile, this);
this.index.splice(i, 0, ie);
return ie;
}
if (this.index[i].size < pile.size) {
continue;
}
return this.index[i].addLogPile(pile);
}
}
removeIndexEntry() {
this.index.splice(0, 1);
}
}
class IndexEntry {
constructor(index, pileSize, initialMembers) {
this.index = index;
this.size = pileSize;
this.members = initialMembers || [];
}
addLogPile(member) {
this.members.push(member);
return this;
}
removeLogPile() {
return this;
}
addLog() {
return this.members[0].addLog();
}
static fromPile(pile, index) {
return new IndexEntry(index, pile.size, [pile]);
}
}
class LogYard {
constructor(piles) {
this.index = new LogIndex([]);
this.piles = piles.map((row) => {
return row.map((size) => {
return new LogPile(this.index, size);
});
});
}
addLog() {
return this.index.addLog();
}
toString() {
return this.piles.map((row) => {
return row.map((pile) => {
return pile.size;
}).join("\t");
}).join("\n");
}
}
class LogYardProblemParams {
constructor(addCount, matrix) {
this.add = addCount;
this.matrix = matrix;
}
static fromString(textInput) {
var lines = textInput.split("\n");
var nonMatrix = lines.splice(0, 2);
var addCount = parseInt(nonMatrix[1]);
var inputMatrix = lines.map((line) => {
return line.trim().split(/\s+/).map((stringNumber) => {
return parseInt(stringNumber);
});
});
return new LogYardProblemParams(addCount, inputMatrix);
}
}
class LogYardSolver {
constructor(params) {
this.yard = new LogYard(params.matrix);
this.iterations = params.add;
}
run() {
for (var i = 0; i < this.iterations; i++) {
this.yard.addLog();
}
return this;
}
toString() {
return this.yard.toString();
}
}
var textInput = "12\n10000\n 9 15 16 18 16 2 20 2 10 12 15 13 \n 20 6 4 15 20 16 13 6 7 12 12 18 \n 11 11 7 12 5 7 2 14 17 18 7 19 \n 7 14 4 19 8 6 4 11 14 13 1 4 \n 3 8 3 12 3 6 15 8 15 2 11 9 \n 16 13 3 9 8 9 8 9 18 13 4 5 \n 6 4 18 1 2 14 8 19 20 11 14 2 \n 4 7 12 8 5 2 19 4 1 10 10 14 \n 7 8 3 11 15 11 2 11 4 17 6 18 \n 19 8 18 18 15 12 20 11 10 9 3 16 \n 3 12 3 3 1 2 9 9 13 11 18 13 \n 9 2 12 18 11 13 18 15 14 20 18 10 ";
var solver = new LogYardSolver(LogYardProblemParams.fromString(textInput));
console.log(solver.toString());
console.log(solver.run().toString());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment