This one was hard! I think mainly because of my non-recursive approach.
I'm gonna omit reader.js which is the same as the other solutions and jump to the point:
17-common.js
const{readFile}=require('./reader');constMAP={CLAY:'#',SAND:'.',SPRING:'+',WATER_DOWN:'|',WATER_RESTING:'~'};constDIRECTIONS={LEFT:'left',RIGHT:'right',DOWN:'down',UP:'up'};classWaterFlow{constructor({x,y,parent,left,right,down,up,cache}){this.x=x;this.y=y;this.parent=parent;this.left=left;this.right=right;this.down=down;this.up=up;}flow(map,cache){constnext=[];const{x,y,parent}=this;constsquareBelow=map[y+1][x];// If square below is empty, flow downif(squareBelow===MAP.SAND){next.push(this.flowDown(map,cache,x,y));}// If it came from its parent, then flow to the sideselseif([MAP.CLAY,MAP.WATER_RESTING].includes(squareBelow)){// Flow to the leftconst{leftmostWaterFlow,newLeftmostWaterFlow,hasReachedLeftClay}=this.flowToTheLeft(map,cache);if(!hasReachedLeftClay&&newLeftmostWaterFlow){next.push(newLeftmostWaterFlow);}// Flow to the rightconst{rightmostWaterFlow,newRightmostWaterFlow,hasReachedRightClay}=this.flowToTheRight(map,cache);if(!hasReachedRightClay&&newRightmostWaterFlow){next.push(newRightmostWaterFlow);}// If trapped on both sides, return upif(hasReachedLeftClay&&hasReachedRightClay){this.markWaterResting(map,leftmostWaterFlow,rightmostWaterFlow);constupstream=this.findUpstream(leftmostWaterFlow,rightmostWaterFlow);next.push(upstream);}}returnnext;}flowDown(map,cache,x,y){this.down=newWaterFlow({x,y:y+1,up:this,parent:DIRECTIONS.UP},cache);map[y+1][x]=MAP.WATER_DOWN;returnthis.down;}flowToTheLeft(map,cache){lethasReachedLeftClay=false;let{x,y}=this;letcurrentWaterFlow=this;letnewLeftmostWaterFlow;letnextSquare=map[y][x-1];letnextSquareBelow=map[y+1][x-1];while([MAP.SAND,MAP.WATER_DOWN,MAP.WATER_RESTING].includes(nextSquare)&&nextSquareBelow!==MAP.SAND){if(nextSquare===MAP.SAND){currentWaterFlow.left=newWaterFlow({x:x-1,y,right:currentWaterFlow,parent:DIRECTIONS.RIGHT},cache);map[y][x-1]=MAP.WATER_DOWN;}elseif(!currentWaterFlow.left){currentWaterFlow.left=getWaterFlowBySquare(cache,{x:x-1,y});currentWaterFlow.left.right=currentWaterFlow;}currentWaterFlow=currentWaterFlow.left;x--;nextSquare=map[y][x-1];nextSquareBelow=map[y+1][x-1];}if(nextSquare===MAP.CLAY){hasReachedLeftClay=true;}elseif(map[y+1][x]===MAP.WATER_DOWN){do{currentWaterFlow=currentWaterFlow.down;y++;}while(map[y+1][x]===MAP.WATER_DOWN);newLeftmostWaterFlow=currentWaterFlow;}elseif(nextSquareBelow===MAP.SAND){newLeftmostWaterFlow=currentWaterFlow.left=newWaterFlow({x:x-1,y,right:currentWaterFlow,parent:DIRECTIONS.RIGHT},cache);map[y][x-1]=MAP.WATER_DOWN;}return{hasReachedLeftClay,leftmostWaterFlow:currentWaterFlow,newLeftmostWaterFlow};}flowToTheRight(map,cache){lethasReachedRightClay=false;let{x,y}=this;letcurrentWaterFlow=this;letnewRightmostWaterFlow;letnextSquare=map[y][x+1];letnextSquareBelow=map[y+1][x+1];while([MAP.SAND,MAP.WATER_DOWN,MAP.WATER_RESTING].includes(nextSquare)&&nextSquareBelow!==MAP.SAND){if(nextSquare===MAP.SAND){currentWaterFlow.right=newWaterFlow({x:x+1,y,left:currentWaterFlow,parent:DIRECTIONS.LEFT},cache);map[y][x+1]=MAP.WATER_DOWN;}elseif(!currentWaterFlow.right){currentWaterFlow.right=getWaterFlowBySquare(cache,{x:x+1,y});currentWaterFlow.right.left=currentWaterFlow;}currentWaterFlow=currentWaterFlow.right;x++;nextSquare=map[y][x+1];nextSquareBelow=map[y+1][x+1]}if(nextSquare===MAP.CLAY){hasReachedRightClay=true;}elseif(map[y+1][x]===MAP.WATER_DOWN){do{currentWaterFlow=currentWaterFlow.down;y++;}while(map[y+1][x]===MAP.WATER_DOWN);newRightmostWaterFlow=currentWaterFlow;}elseif(nextSquareBelow===MAP.SAND){newRightmostWaterFlow=currentWaterFlow.right=newWaterFlow({x:x+1,y,left:currentWaterFlow,parent:DIRECTIONS.LEFT},cache);map[y][x+1]=MAP.WATER_DOWN;}return{hasReachedRightClay,rightmostWaterFlow:currentWaterFlow,newRightmostWaterFlow};}markWaterResting(map,leftmostWaterFlow,rightmostWaterFlow){let{x,y}=leftmostWaterFlow;letmaxX=rightmostWaterFlow.x;for(leti=x;i<=maxX;i++){map[y][i]=MAP.WATER_RESTING;}}findUpstream(leftmostWaterFlow){letsquare=leftmostWaterFlow;while(square.right&&square.parent!==DIRECTIONS.UP){square=square.right;}returnsquare[square.parent];}}constbuildMap=lines=>{constxRegex=/^x=(?<x>\d+), y=(?<y1>\d+)..(?<y2>\d+)$/;constyRegex=/^y=(?<y>\d+), x=(?<x1>\d+)..(?<x2>\d+)$/;constmap=[];letminY=Number.POSITIVE_INFINITY;letmaxY=-1;letminX=Number.POSITIVE_INFINITY;letmaxX=-1;// Marking clay squaresfor(constlineoflines){letmatch=line.match(xRegex);if(match){let{x,y1,y2}=match.groups;x=+x;y1=+y1;y2=+y2;for(leti=y1;i<=y2;i++){if(!map[i])map[i]=[];map[i][x]=MAP.CLAY;}minY=Math.min(minY,y1);maxY=Math.max(maxY,y2);minX=Math.min(minX,x);maxX=Math.max(maxX,x);}else{match=line.match(yRegex);if(match){let{y,x1,x2}=match.groups;y=+y;x1=+x1;x2=+x2;if(!map[y])map[y]=[];for(leti=x1;i<=x2;i++){map[y][i]=MAP.CLAY;}minY=Math.min(minY,y);maxY=Math.max(maxY,y);minX=Math.min(minX,x1);maxX=Math.max(maxX,x2);}}}minX--;maxX++;// Marking spring squaresmap[0]=[];map[0][500]=MAP.SPRING;// Marking sand squaresfor(leti=0;i<=maxY+1;i++){if(!map[i])map[i]=[];for(letj=minX-1;j<=maxX+1;j++){map[i][j]=map[i][j]||MAP.SAND;}}return{map,minY,maxY,minX,maxX};};constgetKey=({x,y})=>`${x},${y}`;constgetWaterFlowBySquare=(cache,square)=>cache.get(getKey(square));constsetWaterFlowBySquare=(cache,waterFlow)=>cache.set(getKey(waterFlow),waterFlow);constnewWaterFlow=(args,cache)=>{constwaterFlow=newWaterFlow(args);setWaterFlowBySquare(cache,waterFlow);returnwaterFlow;};constopenTheTap=(map,minY,maxY)=>{lethasOverflown=false;constcache=newMap();constwaterFlow=[newWaterFlow({x:500,y:0})];do{constwaterSquare=waterFlow.shift();constnewFlow=waterSquare.flow(map,cache);waterFlow.push(...newFlow.filter(flow=>flow.y<=maxY));}while(waterFlow.length>0);};constcountWater=(map,minY,maxY,minX,maxX,types=[MAP.WATER_DOWN,MAP.WATER_RESTING])=>{letsquaresCount=0;for(leti=minY;i<=maxY;i++){for(letj=minX;j<=maxX;j++){if(types.includes(map[i][j])){squaresCount++;}}}returnsquaresCount;};module.exports={MAP,buildMap,openTheTap,countWater};
17a.js
const{readFile}=require('./reader');const{buildMap,openTheTap,countWater}=require('./17-common');(async()=>{constlines=awaitreadFile('17-input.txt');const{map,minY,maxY,minX,maxX}=buildMap(lines);openTheTap(map,minY,maxY,minX,maxX);constsquaresCount=countWater(map,minY,maxY,minX,maxX);console.log(`The number of tiles the water can reach is ${squaresCount}.`);})();
17b.js
const{readFile}=require('./reader');const{MAP,buildMap,openTheTap,countWater}=require('./17-common');(async()=>{constlines=awaitreadFile('17-input.txt');const{map,minY,maxY,minX,maxX}=buildMap(lines);openTheTap(map,minY,maxY,minX,maxX);constsquaresCount=countWater(map,minY,maxY,minX,maxX,[MAP.WATER_RESTING]);console.log(`The number of remaining resting water tiles is ${squaresCount}.`);})();
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Javascript solution
This one was hard! I think mainly because of my non-recursive approach.
I'm gonna omit reader.js which is the same as the other solutions and jump to the point:
17-common.js
17a.js
17b.js