Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
500,000 clones get you out of a 10x10 maze (github.com/krishnanraman)
6 points by dxbydt on Dec 13, 2012 | hide | past | favorite | 4 comments


So ... I'm not familiar with path-finding algorithms, but is this the most efficient way to solve the problem?


Not by a long shot. An astar will get you out of a 10x10 maze in 10 steps since this particular maze has no barriers... I asked my wife if she were trapped in a maze how she would get out. She thought for a while and said... if I could clone myself I would fill up the whole maze with me...and one of me would be at the maze door in no time!

I thought that was a pretty radical and creative algorithm... so I coded it up


So it's more of a 10x10 room than a 10x10 maze?


adding barriers to make a room into a maze is trivial. So if you were forking my scala code, you see 4 filters -

      val res = Seq(x-1,x,x+1).map( a => Seq(y-1,y,y+1).map( b=> (a,b))).flatten
      .filterNot( ab => ab._1 == x && ab._2 == y)  // don't include me
      .filterNot( ab=> ab._1 < leftTop._1 || ab._1 > rightBottom._1) // don't include points outside the maze
      .filterNot( ab=> ab._2 < leftTop._2 || ab._2 > rightBottom._2)
      .filterNot( ab=> path.contains(ab)) // don't revisit points along your path

Now if you add 1 more filter, literally 1 more line of code, to eliminate paths that are prohibited because they intersect with a barrier, you are good to go. a room is simply a maze with zero barriers.




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: