I didn't do #90, so I'll put my answer here. This is a really stupid, slow, "just works" algorithm. It checks every single possible path. I guess it's around O(n3)?
(Language is Haskell).
dataMove=D|DL|DRderiving(Show)typeSize=InttypeRow=InttypeCol=InttypePos=(Row,Col)isInSquare::Size->Pos->BoolisInSquaren(r,c)=allid[r>=0,r<n,c>=0,c<n]executeMove::Move->Pos->PosexecuteMoveD(r,c)=(r+1,c)executeMoveDL(r,c)=(r+1,c-1)executeMoveDR(r,c)=(r+1,c+1)validMove::Size->Pos->Move->BoolvalidMovenpm=isInSquaren$executeMovemppossibleMoves::Size->Pos->[Move]possibleMovesnp=filter(validMovenp)[D,DL,DR]generatePaths::Size->Pos->[[Move]]generatePathsnp|fstp==n-1=[[]]|otherwise=possibleMovesnp>>=nextMoveswherenextMoves::Move->[[Move]]nextMovesm=generatePathsn(executeMovemp)>>=\ms->[m:ms]-- Middle spot of an even array is defined as the right middle for simplicity. middlen|oddn=n`div`2|otherwise=n`div`2access::[[a]]->Pos->aaccessxss(r,c)=xss!!r!!csumIn::(Numa)=>[[a]]->Pos->[Move]->asumInxssstartpath=letps=scanl(flipexecuteMove)startpathinsum$map(accessxss)psmaxBy::(Ordb)=>(a->b)->[a]->amaxByf=foldl1maxOfwheremaxOfmx=if(fx>fm)thenxelsembestPath::(Orda,Numa)=>Size->[[a]]->([Move],a)bestPathnxss=letstart=(0,middlen)paths=generatePathsnstartinmaxBysnd$zippaths$map(sumInxssstart)paths
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 didn't do #90, so I'll put my answer here. This is a really stupid, slow, "just works" algorithm. It checks every single possible path. I guess it's around O(n3)?
(Language is Haskell).