6 ms·
Show HN: I wrote a maze traversal program in Clojure
- 2000andlate 7y agoI don’t have a whole lot to say other than this looks awesome! Well done!
- 2000andlate 7y agoSeriously? Maybe if I’d spent 3,000 words picking it apart I’d be the top comment.
- dang 7y agoCan you please not post unsubstantive comments here? We're trying for a bit better than internet default on this site. If you wouldn't mind reading the site guidelines and abiding by them when posting, we'd be grateful. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- Heliosmaster 7y agoThanks for teaching me about the fn trampoline, which I had never seen/used before! Really cool project!
- netb258 7y agoYeah trampoline is kind of rare. You only see it in cases where some functions are mutually recursive.
- thom 7y agoIt's very useful. I once had a codebase where we wrote two (parallel) variants of trampoline called tramampoline and trambopoline, and I'm not even a little bit sorry.
- nick0garvey 7y agoI'm looking at the source, but I'm not sure why "without stack consumption" is true. Is this because trampoline is written such that it takes advantage of tail call optimization even if the inner function doesn't? https://github.com/clojure/clojure/blob/clojure-1.9.0/src/clj/clojure/core.clj#L6219 https://github.com/clojure/clojure/blob/clojure-1.9.0/src/cl...
- fuzz4lyfe 7y agoLooks similar to A* to my non-Clojure using eye. How has your performance been? If I use a 1000 x 1000 grid in my A* Python implementation I wrote last night it takes forever. [0]https://en.m.wikipedia.org/wiki/A*_search_algorithm https://en.m.wikipedia.org/wiki/A*_search_algorithm
- netb258 7y agoCool article. To tell you the truth I didn't really know about this algorithm. I just went at the problem function by function and this is what I ended up with.
- sdegutis 7y agoFor 20 years I couldn't make a Warcraft 2 clone because I just couldn't figure out A*. And now it turns out this Clojure program is probably doing just that! I can't wait to share this with my son. Having him help me port it to Lua might also end up teaching him a little Clojure too.
- valbaca 7y agoStay in school kids.
- thethirdone 7y agoI wouldn't expect performance to take forever (> 1 hr) for 1000x1000 in python. I know I have made not optimized path-finding that can solve 100x100 instantly (< 1 sec), and because the time complexity scales with # of vertices for planar networks that should mean that it would only take ~100 sec to solve 1000x1000.
- fuzz4lyfe 7y agoI was being hyperbolic, run time was more in the two minute range. Thank you for the numbers it seems my idea of thousands of units pathfinding over long distances isn't feasible in this way. My next idea is to "prerender" a series of interconnected waypoints across the map at the start and then pathfind to the nearest one before moving long distances using small bursts of pathfinding to move around obstacles and stay on track.
- hk__2 7y agoPSA: please use clojure.edn/read-string instead of read-string. The latter can execute code when it parses the string (try running `(read-string "#=(println \"oops\")")`.
- netb258 7y agoDone. I edited the code with this small, but important change. I want you to know that this is the most useful comment I've ever gotten. I had no idea that clojure.edn/read-string simply reads a string as literal clojure data. This is opposed to clojure.core/read-string which reads a string as executable clojure code.
- elamje 7y agoWhile you are PSAing, can you mention why this is useful, and how much it can enhance performance?
- sls 7y agoIt's useful because the read-string in core is passing a string to the reader, essentially like an eval[1]. The edn namespace is for Extensible Data Notation[2], and exports functions for reading an object from a stream and from a string without passing it to the lisp reader.[3] [1] https://clojuredocs.org/clojure.core/read-string https://clojuredocs.org/clojure.core/read-string [2] https://clojuredocs.org/clojure.edn https://clojuredocs.org/clojure.edn [3] https://clojure.github.io/clojure/clojure.edn-api.html https://clojure.github.io/clojure/clojure.edn-api.html
- todd8 7y agoPerformance differences are likely not that critical between reading small amounts of data using string I/O vs reading small amounts of data using a library routine that reads and evaluates the data. Runtime evaluation of a string as a language expression is often available in interpreted languages like Python, Ruby, or the Lisp family, and these languages are not usually used in the most performance sensitive programs. Three factors may make a difference between using the two aforementioned functions. First, performance can matter if the program is doing enough I/O. Secondly, the machinery needed to evaluate language expressions will have to be available at runtime, meaning that the executable will have to be interpreted by an interpreter capable of doing the evaluation (which Lisp, Python, etc. are—they have REPLs after all) or the executable in languages without a runtime interpreter will have to be linked statically or dynamically with code that does the evaluation, making it resulting executable larger. Third, there is the really important reason that programs should avoid reading and evaluating their inputs as expressions: security. A process runs code within a certain security context, generally with the same privileges as the user running the program. If the data input to the process can run expressions not found in the code, the program’s author can make few security guarantees about the results of running the program. Programs may receive input from the network and may even run at elevated security levels (e.g. setuid); these programs should not evaluate arbitrary input. For example, many security vulnerabilities come from database programs reading strings that are passed directly to the SQL interpreter. See the XKCD “Exploits of a Mom” [1]. [1] https://xkcd.com/327/ https://xkcd.com/327/
- _virtu 7y agoIf you're learning about mazes you'll have plenty of fun reading "Mazes for programmers". I've been reading through it and it's a nice change of pace. I've thrown a few of the algorithms on my pen plotter site https://plott.id/mazes https://plott.id/mazes. I definitely encourage you to give the book a look. Here's the source for the site: https://github.com/blakedietz/plott.id https://github.com/blakedietz/plott.id
- deleted 7y ago[deleted]
- onetom 7y agoFirst of all, thanks for sharing; it's a very educational piece of code! I have some generic coding advice though. With slightly better names you can get rid of a lot of the comments. There is a lot of repetition in the code. If you factor that out, you will have even less need for comments. I highly recommend watching some Kevlin Henney talks on such topics, for example https://youtu.be/ZsHMHukIlJY?t=487 https://youtu.be/ZsHMHukIlJY?t=487 (but he has even better talks recently) The input of the program should be supplied in a more format more natural to humans and let the computer do the transformation into whatever data structure it's comfortable with. So I would propose a simple, multi-line text as an input: xxxxxx 0x000x x*0x0x xxxx00 00000x xxxx0x Then the code would look like this: (ns maze.solver (:require [clojure.string :as str])) (def maze-filename "maze.txt") (defn parse [maze-str] (->> maze-str str/trim str/split-lines (mapv (partial into [])))) (def maze (-> maze-filename slurp parse)) You can also just hardwire a maze during development into the source file, since Clojure supports multiline strings: (def maze (parse " xxxxxx 0x000x x*0x0x xxxx00 00000x xxxx0x ")) The result of `parse` function will contain character data types instead of 1 character long strings. I think in this case it's actually more readable and more concise too: [[\x \x \x \x \x \x] [\0 \x \0 \0 \0 \x] [\x \* \0 \x \0 \x] [\x \x \x \x \0 \0] [\0 \0 \0 \0 \0 \x] [\x \x \x \x \0 \x]] Next `println` actually accepts multiple arguments and concatenates them with a space, after stringifying them, so you can drop the extra `(str ...)` wrapping around them. Then again, the comment is superfluous. It's obvious that you are printing stuff. If you really want to tell what is it, just wrap it in a well-named function. Eg: (defn report [paths] (println "The maze has" (count paths) "paths.") (println "The shortest path in the maze is:" (count (first paths)) "steps long.") (println "The path is" (first paths)) (println "The longest path in the maze is:" (count (last paths)) "steps long.") (println "The path is" (last paths))) So you can just put `(report sorted-paths)` in your `-main`.
- netb258 7y agoI am shamelessly stealing your code.
- lispm 7y agoCommon Lisp: https://gist.github.com/lispm/145fc3e0967f42ff44a11e0670be1aef https://gist.github.com/lispm/145fc3e0967f42ff44a11e0670be1a...
- danielcorin 7y agoRelated (not my repo): https://github.com/joewing/maze https://github.com/joewing/maze
- tincholio 7y agoJust a nit-picky comment... your 'can-go-left?' and 'move-left', etc. functions would probably be more idiomatic by either passing the direction as an argument, (and maybe using multi-methods, though it might be overkill for this).
- torvaney 7y agoNeat! I happened to finish a similar project in Clojure just this week: https://github.com/Torvaney/flow-solver https://github.com/Torvaney/flow-solver Although I used a much lazier strategy for doing the solving (reduction to SAT).