Skip to content

Instantly share code, notes, and snippets.

@xojoc

xojoc/002.rkt

Created April 16, 2020 16:19
Show Gist options
  • Save xojoc/2f869d206a3c7ae199b463ff5d37b4ad to your computer and use it in GitHub Desktop.
Save xojoc/2f869d206a3c7ae199b463ff5d37b4ad to your computer and use it in GitHub Desktop.
Download ZIP
Fill a NxN grid with numbers from 1 to N. Starting from 1 the next cell can be either two places apart vertically or horizontally or one cell apart diagonally.
Raw
002.rkt
#lang typed/racket
(require math/array)
(: possible-moves ((Array Fixnum) Indexes -> (Listof Indexes)))
(define (possible-moves arr idx)
(let ((shape (array-shape arr)))
(cast
(filter (λ ([i : (Vector Integer Integer)]) (and (< -1 (vector-ref i 0) (vector-ref shape 0))
(< -1 (vector-ref i 1) (vector-ref shape 1))
(zero? (array-ref arr i))))
(map (λ ([off : (Vector Integer Integer)])
(vector (+ (vector-ref idx 0) (vector-ref off 0))
(+ (vector-ref idx 1) (vector-ref off 1))))
(list #(-2 0) #(-1 -1) #(-1 1) #(0 -2) #(0 2) #(1 -1) #(1 1) #(2 0))))
(Listof Indexes))))
(: solve ((Mutable-Array Fixnum) Indexes Fixnum Fixnum -> (U Void (Array Fixnum))))
(define (solve arr idx n target)
(if (= n target)
arr
(let ((n (cast (+ n 1) Fixnum)))
(let l ((moves (possible-moves arr idx)))
(unless (empty? moves)
(array-set! arr (car moves) n)
(let ((solution (solve arr (car moves) n target)))
(if (void? solution)
(begin
(array-set! arr (car moves) 0)
(l (cdr moves)))
solution)))))))
(define shape #(10 10))
(: grid (Mutable-Array Fixnum))
(define grid (array->mutable-array (make-array shape 0)))
(define target (cast (* (vector-ref shape 0) (vector-ref shape 1)) Fixnum))
(display target)
(newline)
(array-set! grid #(0 0) 1)
(display (solve grid #(0 0) 1 target))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment