I got mine done but it runs really slowly (~50s)...I'm pretty sure I did something dumb here. There's a lot of loops and I suspect I accidentally went O(n2) or possibly even O(n3)
importfs=require('fs');constsolve=(lines:string[]):number=>{leti=1;constp1=[];constp2=[];while(lines[i]!==''){p1.push(parseInt(lines[i]));i++;}i++;// skip the blank linei++;// skip the headerwhile(lines[i]!==''){p2.push(parseInt(lines[i]));i++;}constwinning_deck:number[]=conflict(p1,p2);returnwinning_deck.map((card,idx)=>card*(winning_deck.length-idx)).reduce((total,value)=>total+value,0);};consttestInput=['Player 1:','9','2','6','3','1','','Player 2:','5','8','4','7','10',''];// export const testInput = ['Player 1:', '43', '19', '', 'Player 2:', '2', '29', '14', ''];constconflict=(p1:number[],p2:number[],game_num=1):number[]=>{constturns=[];while(p1.length!==0&&p2.length!==0){// recursive checkif(turn_happened_before(turns,p1,p2)){returnp1;}turns.push([[...p1],[...p2]]);constp1card=p1.shift();// removesconstp2card=p2.shift();// removesif(p1card<=p1.length&&p2card<=p2.length){// recurse to determine winnerconstsubp1=p1.slice(0,p1card);constsubp2=p2.slice(0,p2card);conflict(subp1,subp2,game_num+1);// subp1 and subp2 get mutatedif(subp1.length===0){// p2 wonp2.push(p2card);p2.push(p1card);}else{// p1 wonp1.push(p1card);p1.push(p2card);}}elseif(p1card>p2card){p1.push(p1card);p1.push(p2card);}else{p2.push(p2card);p2.push(p1card);}}if(p1.length===0)returnp2;elsereturnp1;};constturn_happened_before=(turns:[number[],number[]][],p1:number[],p2:number[]):boolean=>{returnturns.some((turn)=>arr_eq(turn[0],p1)&&arr_eq(turn[1],p2));};constarr_eq=(a1:number[],a2:number[]):boolean=>a1.every((val,idx)=>val===a2[idx]);constmain=()=>{constlines=getLinesFromFile();console.log(solve(lines));};constgetLinesFromFile=()=>{constfname=`inputs/day22.txt`;returnfs.readFileSync(fname,'utf8').split('\n');};main();
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.
I got mine done but it runs really slowly (~50s)...I'm pretty sure I did something dumb here. There's a lot of loops and I suspect I accidentally went O(n2) or possibly even O(n3)