Coder Social home page Coder Social logo

cube-puzzle's Introduction

Cube Puzzle

Found this puzzle and realized I was doing a depth first search trying to solve it. So I wrote a program in ClojureScript to do it.

The puzzle is a chain of 27 cubes that when solved forms a 3x3x3 cube. Each cube freely rotates along the axes connecting it to its adjacent cubes. We can visualize the chain's structure by laying it out flat (shown below on the left). The solved form is on the right.

Open index.html in a browser and view the console to see the steps for solving.

Build

  1. Install Leiningen.

  2. In a terminal, run the auto-compiler from the project directory:

    lein cljsbuild auto
    
  3. Open "index.html" in your browser.

  4. Open the developer console to see the results.

Source Code

All of the relevant code is in src/cube/core.cljs, printed below:

(ns cube.core)

(enable-console-print!)

(def dir-names {[ 0  0  1] "forward"
                [ 0  0 -1] "back"
                [ 0  1  0] "up"
                [ 0 -1  0] "down"
                [ 1  0  0] "right"
                [-1  0  0] "left"})

(def dirs (keys dir-names))

(def initial-segs [2 2 2 2 1 1 1 2 2 1 1 2 1 2 1 1 2])
(def initial-pos [0 0 0])
(def initial-dir [0 0 1])
(def initial-cube #{initial-pos})

(defn log [x] (js/console.log (pr-str x)))

(defn write-seg
  "Get a new cube with the given segment filled, or nil if not possible."
  [[x y z] [dx dy dz] len cube]
  (let [new-pos [(+ x dx) (+ y dy) (+ z dz)]
        new-cube (conj cube new-pos)]
  (cond
    (zero? len) cube
    (contains? cube new-pos) nil
    :else (recur new-pos [dx dy dz] (dec len) new-cube))))

(defn dim-width
  "Get the dimension width of the given axis."
  [cube i]
  (let [xs (map #(nth % i) cube)]
    (js/Math.abs (- (apply min xs) (apply max xs)))))

(defn valid-cube?
  "Determine if the given potential cube is within valid boundaries."
  [cube]
  (and (<= (dim-width cube 0) 2)
       (<= (dim-width cube 1) 2)
       (<= (dim-width cube 2) 2)))

(defn get-dir-axis
  "Get the axis index of the given direction vector."
  [dir]
  (->> dir
       (map-indexed vector)
       (remove #(zero? (second %)))
       (first)
       (first)))

(defn get-dir-options
  "Get the potential next directions from the current direction (perpendicular)."
  [dir]
  (let [i (get-dir-axis dir)]
    (filter #(zero? (nth % i)) dirs)))

(defn search
  "Get a path to fill the given cube with the given segments, or nil if impossible."
  [pos dir cube segs]
  (if-not (seq segs)
    []
    (when-let [new-cube (write-seg pos dir (first segs) cube)]
      (when (valid-cube? new-cube)
        (let [new-pos (mapv (fn [a da] (+ a (* da (first segs)))) pos dir)
              dirs (get-dir-options dir)
              search-next #(search new-pos % new-cube (rest segs))]
          (when-let [success-path (some search-next dirs)]
            (conj success-path (get dir-names dir))))))))

(log (reverse (search initial-pos
                      initial-dir
                      initial-cube
                      initial-segs)))

cube-puzzle's People

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.