The Daily WTF: Curious Perversions in Information Technology

2009-09-03 Reply Admin

private static int[] moves = new int[] { { 1, 3 }, { 0, 2, 4 }, { 1, 5 }, { 0, 4, 6 }, { 1, 3, 5, 7 }, { 2, 4, 8}, { 3, 7 }, { 4, 6, 8 }, { 5, 7 } };

private static int[] solve(int[] board) {
Random rand=new Random();

// Find the Empty Square and number of correct squares
int emptyIx=0, correct=0;

for (int i=0; i<board.length; i++) {
  if (board[i]==0) emptyIx=i;
  else if (board[i]==(i+1)) correct++;
}

while (correct!=8) {
  // Pick one Move at random
  int sourceIx=moves[emptyIx][rand.nextInt(moves[emptyIx].length)];
  
  // Make The Move
  board[emptyIx]=board[sourceIx];
  
  // correct->wrong, // wrong->correct , // wrong->wrong
  if (board[emptyIx]==(emptyIx+1)) correct++;
  else if (board[sourceIx]==(sourceIx+1)) correct--;
                    
  board[sourceIx]=0;
  emptyIx=sourceIx;
}

return board;

}

2009-09-03 Reply Admin

In pseudocode:

// run this for a long time - eventually it will find all optimal solutions

do
	initialize
		set to solved puzzle
		empty move-list
	do
		move a piece semi-randomly and prepend to move-list
		query DB for state and return move-list
		is the state represented in the DB?
		yes
			is it a worse solution (i.e. longer) than what is there?
			yes
				break out of inner do loop
			no
				is it a better solution (i.e. shorter) than what is there?
				yes
					update DB with better solution (state, move-list)
		no
			insert new solution into DB (state, move-list)
	while true

while true


// to solve a puzzle

query DB for state and return move-list!

EvanED · 2009-09-03 Reply Admin

Hatterson:
Even in computer science an algorithm is called 'efficient' when it performs reasonably well in comparison with other options, regardless of its actual running time.

This isn't universally true; in the more theoretical branches of CS, "efficient" is often a synonym for "polynomial time".

Thus many problems have no efficient solution.

RogerInHawaii · 2009-09-03 Reply Admin

I have to wonder why this kind of programming "problem" is still included in computer programming courses. I looked through the course descriptions for a local university (University of Hawaii) recently and it mentions that students will learn sorting and linked-list algorithms. What the hell ? At what job would you ever have to do that? How about using real-world, practical examples in class so students get a feel for what programming is really like? Aaarrrggghh!

2009-09-03 Reply Admin

Dr. Ian Parberry assigned this to a LARC student back in the 1993-1995 timeframe, he wrote the DOS program "GifPuz" which solved an NxN version of this on-screen. Dr. Parberry claimed that the algorithm was provably within 7x of the optimal solution.

It worked by solving first for the upper-left corner, then the 2nd from left on the top row, then the 3rd from left, etc., until it solved the top row. Then the rows and column indices were switched and the solver solved the left-most column. Now it had a (N-1)x(N-1) square to solve. It continued this way until it was 2x2 and then rotated the last few squares into place.

It was deterministic and always worked.

2009-09-03 Reply Admin

Here’s a solution in Scheme:

;; Contract: terminal? : list -> boolean

;; Purpose: Returns whether the given puzzle state is terminal or not.  termLst is a helper definition definint the terminal state.

;; Example: (terminal? '(1 2 3 4 0 6 7 8 9) )
;; #t

;; Example: (terminal? '(1 2 3 0 4 6 7 8 9) )
;; #f

;; Definition:

(define termLst
  '(1 2 3 4 0 6 7 8 9))

(define terminal? 
  (lambda (state)
    (let loop ((state state) (termLst termLst))
    (cond
      ((null? state) #t)
      ((= (car state) (car termLst)) (loop (cdr state) (cdr termLst)))
      (else #f)
      ))))
    

(define list-ref
  (lambda (n ls)
    (let loop ((x 1) (ls ls))
      (cond
        ((null? ls) -1)
        ((= x n) (car ls))
        (else (loop (+ x 1) (cdr ls)))))))


;; Contract: list-index : atom list -> atom

;; Purpose: Returns the 1-based index position of an atom in a list

;; Example: (list-index  3 '(1 2 3 4 0 6 7 8 9) )
;; 3

;; Definition:
(define list-index
  (lambda (a ls)  ;;There's got to be a better, cleaner way, but this will do
    (let loop ((x 1) (ls ls))
      (cond
        ((null? ls) -1)
        ((equal? a (car ls)) x)
        (else (loop (+ x 1) (cdr ls)))))
))



;; Contract: swap : atom atom list -> list

;; Purpose: Returns a puzzle state with the given 1-based index positions in 
;; the puzzle-state list exchanged.

;; Example: (swap  3 2 '(1 2 3 4 0 6 7 8 9) )
;; (1 3 2 4 0 6 7 8 9)

;; Definition:
(define swap
  (lambda (p1 p2 state)
    (if (> p1 p2) (swap p2 p1 state)
    (let loop ((p1 p1) (p2 p2) (stateLst state) (n 1))
      (cond
        ((= n p1) (cons (list-ref p2 state) (loop p1 p2 (cdr stateLst) (+ 1 n))))
        ((= n p2) (cons (list-ref p1 state) (cdr stateLst)))
        (else
         (cons (car stateLst) (loop p1 p2 (cdr stateLst) (+ 1 n)))))))))

;; Contract: blankpos : list -> atom

;; Purpose: Returns the 1-based index position of the blank (the '0) position in the
;; puzzle-state list.

;; Example: (blankpos '(1 2 3 4 0 6 7 8 9) )
;; 5

;; Definition:
(define blankpos
  (lambda (state)
      (list-index '0 state))
  )

;; Contract: move : atom list -> list

;; Purpose: Returns the puzzle-state list after the given movement has been applied.

;; Example: (move 'U '(1 2 3 4 0 6 7 8 9) )
;; (1 0 3 4 2 6 7 8 9)

;; Definition:
(define move 
  (lambda (pos state)
    (cond
      ((equal? pos 'U) (swap (- (blankpos state) 3) (blankpos state) state))
      ((equal? pos 'R) (swap (blankpos state) (+ (blankpos state) 1) state))
      ((equal? pos 'D) (swap (blankpos state) (+ (blankpos state) 3) state))
      ((equal? pos 'L) (swap (- (blankpos state) 1) (blankpos state) state))
)))

;; Contract: possMoves : list -> list

;; Purpose: Returns a list of possible moves based upon the given puzzle-state list

;; Example: (possMoves '(1 2 3 4 0 6 7 8 9) )
;; (u r d l)

;; Definition:
(define possMoves
  (lambda (state)
    (list-ref (blankpos state) '(  (R D) (  R D L) (  D L)
                                 (U R D) (U R D L) (U D L) 
                                 (U R  ) (U R   L) (U   L)))
))


;; Contract: expand : list list -> list

;; Purpose: Applies a list of moves to a tuple, returning a list of tuples, 
;; where each tuple contains a puzzle-state list and a list of the moves
;; made to get there.

;; Example: (expand '(u l) '( (1 2 3 4 0 6 7 8 9) () ) )
;; (((1 0 3 4 2 6 7 8 9) (u)) ((1 2 3 0 4 6 7 8 9) (l)))

;; Definition:
(define expand
  (lambda (moves tuple)
    (let loop ((moves moves) (tuple tuple) (result '() ))
    (cond
      ((null? moves) result)
      (else 
         (loop 
          (cdr moves) 
          tuple 
           (append 
           result
           (list (list (move (car moves) (car tuple)) (append (cadr tuple) (list (car moves))) ) 
           ))
          )                                
       )
))))
 

;; Contract: contains : list atom -> boolean

;; Purpose: Returns whether an atom is within a list or not.

;; Example: (contains '(a b c) 'b)
;; #t

;; Definition:
;; Checks to see if atmB is in lstA
(define contains
  (lambda (lstA atmB)
    (cond
      ((null? lstA) #f)
      ((equal? (car lstA) atmB) #t )
      (else
           (contains (cdr lstA) atmB)))))


;; Contract: solve : list list list -> list

;; Purpose: Takes a list of processed (used) states, a tuple to begin with,
;; and a queue of tuples.  It returns a list of moves to bring the puzzle-state
;; list to the terminal state.  (Or, at least, tries to do so.)

;; Notes:
;;  "used" is a list of processed states
;;  "current" is the currently being process tuple
;;  "queue" is a queue of tuples to process

;; Example: (solve '() '((1 2 3 0 4 6 7 8 9) ()) '(((1 0 3 4 2 6 7 8 9) (u)) ((1 2 3 0 4 6 7 8 9) (l))) )
;; (u d)

;; Definition:
(define solve
  (lambda (used current queue)
    (cond
      ;; Is the current state the terminal one?  If so, return its movelist
      ((terminal? (car current)) (cadr current)) 
      ((contains used (car current))
       (solve used (car queue) (append (cdr queue) (expand (possMoves (caar queue)) (car queue))  ) ))
      (else
       (solve 
        (append current used) 
        (car queue) 
        (append (cdr queue) (expand (possMoves (caar queue)) (car queue)) ) ))
)))

;; Contract: contains : list list -> list

;; Purpose: Takes a puzzle-list state and returns a list of moves to bring a 
;; puzzle-state list to terminal state.
;; (Acts as a bootstrapping mechanism for "solve".)

;; Example: (solver '(1 2 3 0 4 6 7 8 9))
;; (r)

;; Definition:
(define solver
  (lambda (startState)
    (solve 
     '() 
     (list startState '()) 
     (append (expand (possMoves startState) (list startState '() )) '() ) 
    )
))

(define thing  '(1 2 3 
                 4 0 6 
                 7 8 9))
(define thing2 '(1 2 3 0 4 6 7 8 9))
(define thing3 '(0 1 3
                 4 2 6
                 7 8 9))
(define thing4 '(1 3 6
                 4 0 2
                 7 8 9))
                 
(solver thing2)
(solver thing3)
(solver thing4)

mol1111 · 2009-09-03 Reply Admin

Ugly, slow, Python 3k solution:

def swap(s, i, j):
    return s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:]  

def solve(start):
    old_states = []
    target_state = '123456780'
    to_go = [(start,[])]
    while len(to_go) > 0:
        start, way = to_go.pop(0)
        if start == target_state:
            way.append(start)
            return way
        if start in old_states:
            continue
        else:
            old_states.append(start)
        i = start.find('0')
        way = way[:] # copy
        way.append(start)
        if i not in (0, 3, 6):
            to_go.append((swap(start, i-1, i), way))
        if i not in (2, 5, 8):
            to_go.append((swap(start, i, i+1), way))
        if i > 2:
            to_go.append((swap(start, i-3, i), way))
        if i < 6:
            to_go.append((swap(start, i, i+3), way))
    print ("Solution not found!")
    return []

for i in (solve('132546780')):
    print ("{}\n{}\n{}\n".format(i[:3], i[3:6], i[6:]))

2009-09-03 Reply Admin

You know, in looking at this I had an interesting idea for the hardest one:

Why not use a variant of Dijkstra's Algorithm, by representing moves as edges and states as vertices?

2009-09-04 Reply Admin

SR:
These coding challenge things produce herds* of WTFs.

what is the collective noun for WTFs? I'll open the bidding with a PHB of WTFs.

Playing on "herd", a horrid of WTFs?

2009-09-04 Reply Admin

EngleBart:
Bonus 1: What IS the maximum number/depth of scrambles? Bonus 2: How many different starting positions exist at this depth?

28 and 18.

Go Figure:
Buzzard:
I should send the requirements to our Indian outsourcing team... Those fuckers write ( read cut 'n paste ) beautiful solutions and get it right first time!!!!!!!!!!!!
Another racist pig scared for his pathetic job

To be fair, s/he was not speaking of generic Indians, but specifically of an Indian outsourcing team s/he has experience with. So you can't necessarily conclude racism.

2009-09-04 Reply Admin

Weighing in at .5Kb, in non-golfed, idiomatic Perl:

#!/usr/bin/perl -wl
use strict;
my @new = '12345678_';
my %seen = ( $new[0] => '' );
while (my @curr = splice @new) {
	for my $board (@curr) {
		for my $xfrm ( qr/(.)(..)(_)/, qr/(_)(..)(.)/, qr/(_)()(.)/, qr/(.)()(_)/ ) {
			( my $b = $board ) =~ s/$xfrm/$3$2$1/;
			$seen{$b} = $board, push @new, $b if ! exists $seen{$b};
		}
	}
}

while ( print('Starting position (e.g. 8765_4321):'), my $board=<> ) {
	chomp $board;
	print 'Not solvable' unless $seen{$board};
	print $board while $board = $seen{$board};
}

2009-09-04 Reply Admin

[quote user="ysth"][quote user="EngleBart"] [quote user="Go Figure"][quote user="Buzzard"]I should send the requirements to our Indian outsourcing team... Those fuckers write ( read cut 'n paste ) beautiful solutions and get it right first time!!!!!!!!!!!![/quote] Another racist pig scared for his pathetic job[/quote]To be fair, s/he was not speaking of generic Indians, but specifically of an Indian outsourcing team s/he has experience with. So you can't necessarily conclude racism.[/quote]

If there hadn't been racism, there wouldn't have been any need to mention that the team was Indian.

SpaceDog · 2009-09-04 Reply Admin

Eh, I'm missing some subtle sarcasm here. Yes? Please?

Aside from the fact that there are plenty of jobs where you might have to understand and even implement that sort of code -- not everyone has enough space to have libraries to fall back on.

And ignoring that fact that questions like that form the backbone of many technical interviews.

The basic fact is that software engineers should understand how all the basics work even if they never need to use them.

Next you'll be saying that people shouldn't worry about memory allocation and cleaning up afterwards because it can all be done for you ...

2009-09-04 Reply Admin

Anonymous:
Carl:
I just to annoy my older brother by removing and swapping two tiles from my 15 puzzle and watching him struggle...

You accidentally a word here.

No, he thought 'used' is written 'just', used as some people think 'should've' is written 'should of'.

2009-09-04 Reply Admin

I have found an elegant solution which solves this problem in less than polynomial time but this box is too small to write it down.

2009-09-04 Reply Admin

An dirty, yet surprisingly fast VBScript implementation

input="1,X,2,5,6,3,4,7,8" Dim board(3,3)

init() print()

tries=0 done=False

While Not done 'Find Empty Square - 'X' For i=1 To 3 For j=1 To 3 If board(i,j)="X" Then open=i&","&j WScript.Echo "Open Spot= "& open End If Next Next

'Find a place to move (e.g. neighbors)

mover=getNeighbor() WScript.Echo "Move Spot= " & mover

swap() print()

If board(1,1)="1" And board(1,2)="2" And board(1,3)="3" And board(2,1)="4" And board(2,2)="5" And board(2,3)="6" And board(3,1)="7" And board(3,2)="8" Then WScript.Echo "Solution Found in " &tries+1& " moves" done=True print() End If

tries=tries+1 If tries >= 1000 Then WScript.Echo "No Solution Found, Exiting" done=True End If Wend

Function swap() a1=Left(open,1) a2=Right(open,1) b1=Left(mover,1) b2=Right(mover,1) 'WScript.Echo a1,a2,b1,b2 temp1=board(a1,a2) temp2=board(b1,b2) board(a1,a2)=temp2 board(b1,b2)=temp1 End Function

Function init() count=1 For i=1 To 3 For j=1 To 3 temp=Mid(input,count,1) board(i,j)=temp count=count+2 Next Next End Function

Function getNeighbor() Randomize n=Rnd() * 1000 Select Case open Case "1,1" If board(1,2) <> "2" then getNeighbor="1,2" Else getNeighbor="2,1" End If

 Case "1,2"
  If board(1,1) <> "1" Then	
   getNeighbor="1,1"
  ElseIf board(1,3) <> "3" Then
   getNeighbor="1,3"
  Else
   getNeighbor="2,2"
  End If
  	 
 Case "1,3"
  If board(1,2) <> "2" Then	 
   getNeighbor="1,2"
  Else
   getNeighbor="2,3"	 
  End If
 
 Case "2,1"
  If board(1,1) <> "1" Then	
   getNeighbor="1,1"
  ElseIf n Mod 2 = 0 Then	
   getNeighbor="2,2"
  Else	 
   getNeighbor="3,1"
  End If
   	
 Case "2,2"
  If board(1,2) <> "2" then
   getNeighbor="1,2"
  ElseIf board(2,1) <> "4" Then
   getNeighbor="2,1"
  ElseIf board(2,3) <> "6" Then
   getNeighbor="2,3"
  Else	
   getNeighbor="3,2"
  End If	    
 
 Case "2,3"
  If board(1,3) <> "3" Then
   getNeighbor="1,3"
  ElseIf n Mod 2 = 0 Then
   getNeighbor="2,2"
  Else	 
   getNeighbor="3,3"
  End If	 
 
 Case "3,1"
  If board(2,1) <> "4" Then	  
   getNeighbor="2,1"
  Else
   getNeighbor="3,2"
  End If		 
 
 Case "3,2"
  If board(2,2) <> "5" Then	
   getNeighbor="2,2"
  ElseIf n Mod 2 = 0 Then	
   getNeighbor="3,1"
  Else	 
   getNeighbor="3,3"
  End If	 
 
 Case "3,3"
  If board(2,3) <> "6" Then
   getNeighbor="2,3"
  Else
   getNeighbor="3,2"
  End If

End Select End Function

mol1111 · 2009-09-04 Reply Admin

C=64 is best:

10 CLS
20 INPUT "ENTER THE STATE", A$
30 IF A$="12345678" THEN GOTO 60
40 PRINT "WRONG!! MAKE YOUR MOVE"
50 GOTO 20
60 PRINT "CORRECT!!"
70 END

One would expect that with such name you would use C64 BASIC. So no CLS, but PRINT "shift+home" to clear screen and semicolon instead of comma in the INPUT line.

2009-09-04 Reply Admin

Hey, could someone post a solution to this problem in Ada? I'm working on a special project to write games for legacy systems. Oh, and it needs to be thread-safe and multi-user because the specs call for collaborative games. Is there an Erlang mod for Ada?

:)

plural · 2009-09-04 Reply Admin

A compact Python solution below. Input is a list of 8 integers and a '_'. The program will go into an infinite loop if the solution is unsolvable for any reason (e.g. being in an unsolvable configuration or having an invalid set of components in the input)

import random def s(b): def w(m):b[m[0]],b[m[1]]=b[m[1]],b[m[0]] while b!=[1,2,3,4,5,6,7,8,'_']:w([[0,1],[1,2],[3,4],[4,5],[6,7],[7,8],[0,3],[1,4],[2,5],[3,6],[4,7],[5,8]][random.randint(0,11)]) return b

The above solution takes up 219 bytes. (Bytes of Python source code, not binary)

Addendum (2009-09-04 14:02): Also, to visualize the above (although this will probably cause the script to take forever to converge), use:

import random def s(b): def w(m):b[m[0]],b[m[1]]=b[m[1]],b[m[0]] while b!=[1,2,3,4,5,6,7,8,'_']: print('',b[0:3],'\n',b[3:6],'\n',b[6:9],'\n') w([[0,1],[1,2],[3,4],[4,5],[6,7],[7,8],[0,3],[1,4],[2,5],[3,6],[4,7],[5,8]][random.randint(0,11)]) return b

Addendum (2009-09-04 14:04): Now, with whitespace!

import random
def s(b):
    def w(m):b[m[0]],b[m[1]]=b[m[1]],b[m[0]]
    while b!=[1,2,3,4,5,6,7,8,'_']:w([[0,1],[1,2],[3,4],[4,5],[6,7],[7,8],[0,3],[1,4],[2,5],[3,6],[4,7],[5,8]][random.randint(0,11)])
    return b

Addendum (2009-09-04 14:27): Whee, under 200 bytes (194):

import random
a=[0,1,1,2,3,4,4,5,6,7,7,8,0,3,1,4,2,5,3,6,4,7,5,8]
def s(b):
 def w(m):b[a[m]],b[a[m+1]]=b[a[m+1]],b[a[m]]
 while b!=[1,2,3,4,5,6,7,8,'_']:w(random.randint(0,11)*2)
 return b

2009-09-04 Reply Admin

It's not NP-complete, since it's not a decision problem. Maybe you mean NP-hard.

2009-09-04 Reply Admin

C++ solution to the 'Difficult' problem using Dijkstra's Algorithm


#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>

struct path {
		long long unsigned int len;
		std::map< long long unsigned int, std::vector<std::vector<char>[3][3]> > route;
		friend bool operator<( const path& x, const path& y) {
				if(x.len > y.len ) 
						return true;
				if(x.len == y.len)
						return false;
		}

};

std::string crunchPath( const path& input ) {
		std::string output = "";

		for ( std::map< long long unsigned int, std::vector<std::vector<char>[3]>[3] >::const_iterator i = input.route.begin(); i != input.route.end(); ++i ) {
				if ( i == input.route.begin() ) {
						output += crunchBoard( i->second );
				} else {
						output += "to:\n\n";
						output += crunchBoard( i->second );
				}
		}
		return( output );
}

std::string crunchBoard( std::vector<std::vector<char>[3]>[3] board ) {
		std::string output = "";
		for ( int i = 0; i <= 2; ++i ) {
				for ( int j = 0; j <= 2; ++j ) {
						output += board[i][j];
				}
				output += '\n';
		}
		output += "\n\n";
		return( output );
}

std::vector<std::vector<char>[3] swapify( std::vector<std::vector<char>[3] orig, int h1, int h2; int t1, int t2 ) {
		orig[h1][h2] = orig[t1][t2];
		orig[t1][t2] = '0';
		return( orig );
}

std::list<std::vector<std::vector<char>[3]>[3]> getNextMoves( std::vector<std::vector<char>[3]>[3] state ) {
		std::list<std::vector<std::vector<char>[3]>[3]> output;
		if ( state[0][0] == '0' ) {
				output.push( swapify( state, 0, 0, 0, 1) );
				output.push( swapify( state, 0, 0, 1, 0) );
		} else if ( state[0][1] == '0' ) {
				output.push( swapify( state, 0, 1, 0, 0) );
				output.push( swapify( state, 0, 1, 1, 1) );
				output.push( swapify( state, 0, 1, 0, 2) );
		} else if ( state[0][2] == '0' ) {
				output.push( swapify( state, 0, 2, 0, 1) );
				output.push( swapify( state, 0, 2, 1, 2) );
		} else if ( state[1][0] == '0' ) {
				output.push( swapify( state, 1, 0, 0, 0) );
				output.push( swapify( state, 1, 0, 1, 1) );
				output.push( swapify( state, 1, 0, 2, 0) );
		} else if ( state[1][1] == '0' ) {
				output.push( swapify( state, 1, 1, 0, 1) );
				output.push( swapify( state, 1, 1, 1, 0) );
				output.push( swapify( state, 1, 1, 1, 2) );
				output.push( swapify( state, 1, 1, 2, 1) );
		} else if ( state[1][2] == '0' ) {
				output.push( swapify( state, 1, 2, 0, 2) );
				output.push( swapify( state, 1, 2, 1, 1) );
				output.push( swapify( state, 1, 2, 2, 2) );
		} else if ( state[2][0] == '0' ) {
				output.push( swapify( state, 0, 2, 1, 0) );
				output.push( swapify( state, 0, 2, 2, 1) );
		} else if ( state[2][1] == '0' ) {
				output.push( swapify( state, 2, 1, 2, 0) );
				output.push( swapify( state, 2, 1, 1, 1) );
				output.push( swapify( state, 2, 1, 2, 2) );
		} else if ( state[2][2] == '0' ) {
				output.push( swapify( state, 2, 2, 1, 2) );
				output.push( swapify( state, 2, 2, 2, 1) );
		}
		return( output );
}


path dijkstra( std::vector<std::vector<char>[3]>[3] first, std::vector<std::vector<char>[3] last ) {
		std::priority_queue< path > paths;

		path initial;
		initial.route[0] = first;
		initial.len = 0;
		paths.push( initial );

PATH:		while ( ! paths.empty() ) {
				path current = paths.top();
				paths.pop();

				if ( current.route[current.len] == last ) {
						return( current );
				}
				for( std::map< long long unsigned int, std::vector<std::vector<char>[3]>[3] >::iterator i = current.route.begin(); i != current.route.end(); ++i ) {
						if ( ( current.route[current.len] == i->second ) && ( i->first < current.len ) ) {
//								std::cout << "Looped on path " << crunchPath( current ) << std::endl;
								goto PATH;
						}
				}

				std::list<std::vector<std::vector<char>[3]>[3]> options = getNextMoves( current.route[current.len] );
				for ( std::list<std::vector<std::vector<char>[3]>[3]>::iterator i = options.begin(); i != options.end(); ++i ) {
						path tmp_current = current;
						tmp_current.route[++(tmp_current.len)] = *i;
						paths.push( tmp_current );
				}
		}
		path error;
		error.len = 0;
		return( error );
}

int main( int argc, char* argv[] ) {
		std::vector<std::vector<char>[3]>[3] start;
		std::cout << "Please enter a 3x3 board state, with tiles" << std::endl
				<< "separated by spaces and newlines. Use 0" << std::endl
				<< "to represent the hole." << std::endl;
		std::cin >> start[0][0] >> start[0][1] >> start[0][2]
				>> start[1][0] >> start[1][1] >> start[1][2]
				>> start[2][0] >> start[2][1] >> start[2][2];
		std::cout << "Now again for the desired end state..." << std::endl;
		std::vector<std::vector<char>[3]>[3] end;
		std::cout << "Please enter a 3x3 board state, with tiles" << std::endl
				<< "separated by spaces and newlines. Use 0" << std::endl
				<< "to represent the hole." << std::endl;
		std::cin >> end[0][0] >> end[0][1] >> end[0][2]
				>> end[1][0] >> end[1][1] >> end[1][2]
				>> end[2][0] >> end[2][1] >> end[2][2];

		path result = dijkstra( start, end, graph );
		if ( result.len = 0 ) {
				std::cout << "No solution!" << std::endl;
				return( 1 );
		}
		std::cout << "Found shortest route (cost " << result.len << ") from\n\n" << start << "\n\nto\n\n" << end << "\nvia path\n\n" << crunchPath( result ) << std::endl;
		return( 0 );
}

2009-09-04 Reply Admin

Whoops, my solution will claim that there's no solution if the start and end states are the same since path.len would be 0. Insert a check to compare them in main() where appropriate. Also, remove the parameters to main() - they're an accidental leftover from the original use of this code (finding paths on graphs of weighted edges between string vertices).

2009-09-04 Reply Admin

I was pretty sure you were wrong about all starting solutions being OK. So I checked with Wikipedia: "A simple parity argument shows that half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made. This is done by considering a function of the tile configuration that is invariant under any valid move, and then using this to partition the space of all possible labeled states into two equivalence classes of reachable and unreachable states." (http://en.wikipedia.org/wiki/Fifteen_puzzle)

However, if you allow the final order to be either the normal left-to-right or right to left, I think the other starting positions all go that way.

2009-09-05 Reply Admin

http://cplus.about.com/od/programmingchallenges/a/challenge16.htm

Programming Challenge 16 was to solve 1000 Puzzles (4x4) You'll find 2 solutions at the bottom of the page...

My A* Program didn't do much for me, so i skipped it...

2009-09-05 Reply Admin

Scala. You can specify an arbitrary end position, too. Finds a shortest path.

object slide {

  case class Pos(pos:String) {
    lazy val neighbors = {
      val p = pos.indexOf('0');  val x = p % 3;  val y = p / 3
      def swap(xn:Int, yn:Int):Option[Pos] =
      if((xn+1) % 4 == 0 || (yn+1) %4 == 0) None
      else {
        val tiles = pos.toArray
        val temp = tiles(p); tiles(p) = tiles(xn+3*yn); tiles(xn+3*yn) = temp
        Some(Pos(new String(tiles)))
      }
      List(swap(x-1,y), swap(x+1,y), swap(x,y-1),swap(x,y+1)).flatMap(s => s)
    }
  }

  def solve(p1:Pos, p2:Pos):List[Pos] = {

    def hull(list:List[Set[Pos]]):List[Set[Pos]] = {
      val second = if (list.tail.isEmpty) Set[Pos]() else list.tail.head
      list.head.foldLeft(Set[Pos]())((s,p) => s ++ p.neighbors.filter{
          n => ! list.head.contains(n) && ! second.contains(n)}) :: list
    }

    def reconstructPath(path:List[Pos], hulls:List[Set[Pos]]):List[Pos] =
      hulls match {
         case Nil => path
         case head :: tail =>
           reconstructPath(head.find(path.head.neighbors.contains(_)).get :: path, tail)
    }

    def solve(list1:List[Set[Pos]], list2:List[Set[Pos]]):List[Pos] =
    list1.head.find(list2.head.contains(_)) match {
      case None =>  val lenIsEqual = list1.length == list2.length
        solve(if (lenIsEqual) hull(list1) else list1,
              if (lenIsEqual) list2 else hull(list2))
      case Some(link) =>  
        reconstructPath(List(link),list1.tail) :::
        reconstructPath(List(link),list2.tail).reverse.tail
    }
    solve(List(Set(p1)),List(Set(p2)))
  }

  def main(args:Array[String]) {
    val time = System.currentTimeMillis
    solve(Pos("738046512"), Pos("123456780")).foreach(println)
    println("" + (System.currentTimeMillis-time) + "ms")
  }
}

2009-09-05 Reply Admin

Alex Elsayed:
You know, in looking at this I had an interesting idea for the hardest one:
Why not use a variant of Dijkstra's Algorithm, by representing moves as edges and states as vertices?

Well, yes ... at which point you get a variant of A*, which is the great thing about this sort of problem. (It still doesn't prevent the hardest one from being NP-complete or NP-hard, whichever.)

Frankly, I'd far rather hire somebody who thinks this way (algorithms, Dijkstra, representation) than somebody who churns out an insta-solution in lingo-of-choice.

Sadly, that's not the way the powers that be hire, these days. If indeed it ever was.

2009-09-05 Reply Admin

RogerInHawaii:
I have to wonder why this kind of programming "problem" is still included in computer programming courses. I looked through the course descriptions for a local university (University of Hawaii) recently and it mentions that students will learn sorting and linked-list algorithms. What the hell ? At what job would you ever have to do that? How about using real-world, practical examples in class so students get a feel for what programming is really like? Aaarrrggghh!

Good question, although you have the wrong, er, lemma.

This sort of crap is designed for supercilious interviewers who already know the two or three best answers, and get warm fuzzy feelings when you (the interviewer) get them slightly wrong. Many college professors also fall into this category.

Your mistaken lemma, however, is to assume, simply because a college student will never need to write their own sort or linked-list algorithm, that the exercise will not help them learn what programming is "really like."

Whatever that is.

I'd posit that, if you've not gone through the pain of writing your own quicksort in language of choice (and the particular algorithm in question is irrelevant and amenable to substitution), then you're gonna be a thoroughly useless pain in the ass when you program "as it is really like."

Think of it (loosely) as Civil Engineering. Nobody who builds a bridge really needs to know what a catenary is, because there are tools to solve that problem for you.

On the other hand, it would be quite nice to know when the program gets it wrong.

2009-09-05 Reply Admin

Kris:
How many almost-identical versions of the "12345678" "solution" are we going to see before people realise it's not that funny?

Twelve million, three hundred and forty five thousand, six hundred and seventy eight.

2009-09-06 Reply Admin

Actually, half of all the combinations are impossible to solve. Here's a short "proof" of why (we learnt this is undegrad Algebra course):

Start with your random configuration, and move the empty box, "9", to the bottom right - it's original location. This is always possible, and it just simplifies the proof.

First note that every move you make is a "transpose" - where you swap the position of "9" and some other number. So a possible configuration is simply a sequence of transpositions.

Now, since in the final and starting configuration, "9" is in the same place, this means we must have an EVEN number of "transposition". Because every time we move "9" up, we must eventually move "9" down again and vice verse.

Now for the maths. With out starting configuration, we calculate the "permutation" that generates this configuration from the original one. This basically means we look at the function which maps the original numbers to the new numbers.

And a permutation can be either odd or even. An even permutation basically can be decomposed to an even number of tranpositions. Hence, we have the requirement that the permutation of the random configuration must be even for the 9 box to be possible.

Hope that made sense :)

something like that...

2009-09-06 Reply Admin

Bim Job:
Alex Elsayed:
You know, in looking at this I had an interesting idea for the hardest one:
Why not use a variant of Dijkstra's Algorithm, by representing moves as edges and states as vertices?
Well, yes ... at which point you get a variant of A*, which is the great thing about this sort of problem. (It still doesn't prevent the hardest one from being NP-complete or NP-hard, whichever.)

Frankly, I'd far rather hire somebody who thinks this way (algorithms, Dijkstra, representation) than somebody who churns out an insta-solution in lingo-of-choice.

Sadly, that's not the way the powers that be hire, these days. If indeed it ever was.

On the other hand, that might give you "inventive" solutions to well known problems.

2009-09-06 Reply Admin

Since Hertzfeld's program probably won't run on modern Macs, and certainly touch anything Microsoft, I decided to spend some of my weekend writing a Windows version of his game.

I went for 4x4, as the original did, but I don't have a 128k to find out what happens when you win. Also, the PE file format is sadly limiting, so the result is an enormous 1184 bytes, but it's 753 compressed!

http://erato.co.uk/Puzzle.zip

Have fun!

2009-09-07 Reply Admin

FYI: The original story about the Puzzle desk accessory is found here:

http://www.folklore.org/StoryView.py?project=Macintosh&story=Puzzle.txt

About desk accessories in general: http://www.folklore.org/StoryView.py?project=Macintosh&story=Desk_Ornaments.txt&topic=User%20Interface

The history about that is quite fun to read.

2009-09-07 Reply Admin

I used perl to hack the code for generating all possible solutions. Basically work backwards from the solution:

#!/usr/bin/perl

use strict;
use warnings;

my $moves_at_index = {
    0 => [1,3],
    1 => [0,2,4],
    2 => [1,5],
    3 => [0,4,6],
    4 => [1,3,5,7],
    5 => [2,4,8],
    6 => [3,7],
    7 => [4,6,8],
    8 => [5,7],
};


my $start = "12345678-";
my $solutions = {};
my $counter = 0;
do_moves($start,"");

use Data::Dumper;
print(Dumper($solutions));

sub do_moves{
    my ($numbers,$path) = @_;
    if(length($path) > 31){
        return;
    }
    if(!defined $solutions->{$numbers}){
        $solutions->{$numbers} = $path;
    }
    elsif(defined $solutions->{$numbers} && length($solutions->{$numbers}) > length($path)){
        $solutions->{$numbers} = $path;
    }
    else{
        #if we are not the shortest path to this number then don't bother continuing.
        return;
    }

    my $i = index($numbers,'-');
    my @moves = @{$moves_at_index->{$i}};
    foreach my $move (@moves){
        my $alter =$numbers;
        my $digit = substr($alter,$move,1);
        substr($alter,$move,1,'-');
        substr($alter,$i,1,$digit);
        do_moves($alter,"$path$digit");
    }
}

2009-09-07 Reply Admin

Hmmm it did not like my second half of the solution (I kept getting spam messages)... Basically make a html page with all of the solutions cached. Then the javascript just looks up the solution and draws it on the page. It was especially wtf'ed as :

It would be quicker to solve than to get it from the cache.
The hash in javascript seems to have a limit of on the number of keys as such I put all the solutions in divs and looked them up by id.

2009-09-07 Reply Admin

It's look that's it couldn't be solved as random, in a short period of time, somebody have a similar behaviour ? Or perhaps I WTF ^^, see code in C#:

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace Sliding { class Slider { public delegate void MoveDelegate();

    const byte SIZE = 3;
    const byte EMPTY_CELL = 0;

    byte[] slide = new byte[SIZE * SIZE];
    byte empty;

    MoveDelegate[] possibleMove; 

    public Slider()
    {
        this.possibleMove = new MoveDelegate[] { this.moveFromLeft, this.moveFromRight, this.moveFromUp, this.moveFromDown };

        for (byte i = 0; i < SIZE * SIZE - 1; i++)
            this.slide[i] = Convert.ToByte(i + 1);

        this.slide[SIZE * SIZE - 1] = EMPTY_CELL;
        this.empty = SIZE * SIZE - 1;
    }

    public void moveFromLeft()
    {
        if ((empty % SIZE)==0) throw new Exception("Unallowed move.");
        slide[empty] = slide[empty - 1];
        empty--;
        slide[empty] = EMPTY_CELL; 
    }
    public void moveFromRight()
    {
        if (((empty+1) % SIZE)==0) throw new Exception("Unallowed move.");
        slide[empty] = slide[empty + 1];
        empty++;
        slide[empty] = EMPTY_CELL;
    }
    public void moveFromDown()
    {
        if (empty / SIZE > SIZE - 1) throw new Exception("Unallowed move.");
        slide[empty] = slide[empty + SIZE];
        empty += SIZE;
        slide[empty] = EMPTY_CELL;
    }
    public void moveFromUp()
    {
        if (empty / SIZE < 1) throw new Exception("Unnallowed move.");
        slide[empty] = slide[empty - SIZE];
        empty -= SIZE;
        slide[empty] = EMPTY_CELL;
    }

    public void mix()
    {
        Random rand = new Random();
        int maxRand = rand.Next(1, 10); 

        for (int i = 0; i < 100*maxRand; i++)
        {
            int move2do = rand.Next(0, possibleMove.Length - 1);

            try
            {
                this.possibleMove[move2do]();
            }
            catch { }
        }
    }

    public String write()
    {
        StringBuilder ret = new StringBuilder("") ; 
        int place = (SIZE*SIZE-1).ToString().Length;

        for (int i = 0; i < SIZE*SIZE; i++)
        {
            if(i%SIZE == 0) ret.Append("\r\n");

            ret.Append(slide[i].ToString().PadLeft(place, ' ') + " ");  
        }

        return ret.ToString(); 
    }

    public bool isOrdered() 
    {
        for(int i = 0; i < SIZE*SIZE-1; i++)
            if(this.slide[i] != i+1)
                return false ; 

        return true ; 
    }

    public void solveByRand() 
    {
        Random rand = new Random();
        while(! this.isOrdered()) {
            int move2do = rand.Next(0, possibleMove.Length - 1);

            try
            {
                this.possibleMove[move2do]();
            }
            catch { }
        }
    }


}

}

2009-09-08 Reply Admin

A bruteforce solution in JavaScript. I know it doesn't meet the specification - it doesn't exactly accept input, instead it randomizes the puzzle itself... I just wanted to make certain that the input is solveable.

Random832 · 2009-09-10 Reply Admin

Wait a minute. Everyone knows the puzzle application that shipped with the mac had fifteen pieces on a 4x4 grid. What gives? I mean, anonymization is one thing, but it's not like this is exactly a detail you can change. I can see the point of changing it for the problem (since the 4x4 version has unsolvable starting positions), but you also changed it in the description of the real puzzle desk accessory.

Pope · 2009-09-11 Reply Admin

SR:
* what is the collective noun for WTFs? I'll open the bidding with a PHB of WTFs.

Would you say that is a plethora of WTFs?

Three Amigos dance

2009-09-11 Reply Admin

175 bytes of Python. I expect it's a one-liner in APL variants. Usage example:

python puzzle.py 1234_5786

import sys,random
r=random.randint
b=list(sys.argv[1])
while b!=sorted(b):
 p,q=r(0,8),r(0,8)
 if'%d%d'%(p,q)in'543012587410367'and'_'in b[p]+b[q]:b[p],b[q]=b[q],b[p]
print b

2009-09-12 Reply Admin

Pope, you will die like dogs... :) I vote for a lurch or a stun... but then have we agreed on what the plural actually is? WTFs or WsTF?

2009-09-13 Reply Admin

Down to 164 bytes.

import sys,random
b=list(sys.argv[1])
while b!=sorted(b):
 p,q=divmod(0x727bdc3c39c9/10**random.randint(0,13)%100,10)
 if'_'in b[p]+b[q]:b[p],b[q]=b[q],b[p]
print b

2009-09-16 Reply Admin

As far as I'm aware, there are no impossible starting configurations and your function should be able to process any series of nine numbers.

If I remember correctly, half of the possible configurations are unsolvable.

You remember correctly, in a way. I'd have to dig it out but this is a basic, classic CIS-101 type of problem (where did YOU go to school?) in Topology, and it's easily demonstrated that any configuration shows a kind of "handedness" -- "even or odd" at any point, and it is impossible by simple movement to change the handedness of a configuration. Any even handed config cannot become an odd handed config (and vice-versa) without removing a piece from the system to change the config's handedness directly. Simple sliding movements won't transpose that.

2009-09-16 Reply Admin

How many almost-identical versions of the "12345678" "solution" are we going to see before people realise it's not that funny?

Hey!!

No fair corrupting the data pool!!

You can't ASK the question and then get a valid answer. Observational interaction kicks in and skews the result.

And, as proof that computers don't have AI yet ("Skynet")... here is what would be a proper solution to the puzzle, were the computer to have true AI:

/* Solves the puzzle in the fastest possible time *

Its even written in C to make it fasterestimente */

#include <stdio.h>

#include <stdlib.h>

int main(char argc, char**argv){

printf("Go away and stop wasting my time with a dumbass puzzle like this. You want it solved, go solve it yourself, lazy human kaaaniggit!\n";

return 0;

}

2009-09-17 Reply Admin

Java Solution (depth first)

http://pastebin.be/20950

2009-09-27 Reply Admin

How do you know he's not racially Indian himself?

He should be scared, everyday we are getting undercut and outsourced, maybe you would have the same opinion if it happened to you?

Marxist twat.

2013-04-01 Reply Admin

HTML/Javascript. Firefox only. Zoom in to 10x for a larger puzzle.

<a rel="nofollow" href="data:text/html,<title>Sliders</title><style>%23r{border:inset 2px;height:108;width:108;float:left;padding:1;position:relative;cursor:inherit}.s{border:outset 2px;background:buttonface;text-align:center;line-height:30px;height:30;width:30;float:left;margin:1}</style><body onload="with(m=String.prototype){m.b=substring;m.i=indexOf;m.M=match;m.r=replace;m.s=split}with(m=Array.prototype){m.c=concat;m.j=join;m.p=push}(m=Event.prototype).p=m.preventDefault;D=document;B=D.body;E=function(e){return D.getElementById(e)};M=Math;Ma=M.abs;Mf=M.floor;Mr=M.random;MR=M.round;W=window;pI=parseInt;T=true;F=!T;sT=setTimeout;u=typeof a;ab='absolute';im='image/png';na='not-allowed';co='cover';=function(e){return D.createElement(e)};J=function(){try{l=[0,0,0,0,0,0,0,0,i=0%5D;while(T)l[MR(((s=E('s'+i)).offsetTop3+s.offsetLeft)/36)%5D=++i}catch(e){}};K=function(s){if(typeof d!=u)return F;if(s instanceof Event)s=this;if(typeof s!='object'||!(s instanceof HTMLDivElement))s=E('s'+s);J();l=l.j('');j=l.i(0);k=l.i(s.id.b(1)1+1);x=k%253;y=Mf(k/3);X=j%253;Y=Mf(j/3);if(Ma(X-x)+Ma(Y-y)>1){s.style.cursor=na;return F}m=U%3Fna:(X-x>0%3F'e':X-x<0%3F'w':Y-y>0%3F's':'n')+'-resize';if((s=s.style).cursor!=m)s.cursor=m;return T};A=function(){B.onmousemove=B.onmouseup=B.style.cursor='';if(typeof d==u)return;if(Ma(d.offsetLeft-X)+Ma(d.offsetTop-Y)!=36){s.left=X-1;s.top=Y-1}else O.value+=(O.value.i('\n')<0%3F'\n':' ')+(d.id.b(1)1+1);d=void(0);G()};G=function(){J();for(j=x=0;j<l.length-1;++j)if(l[j%5D!=j+1){++x;for(k=j+1;k<l.length;++k)if(l[k%5D==j+1){m=l[j%5D;l[j%5D=l[k%5D;l[k%5D=m;k=l.length}}J();j=l.j('').i(0);y=j%253+(j-j%253)/3;n=x==0%3F'green':((x+y)%252>0)%3F'red':'yellow';if((s=b.style).borderColor!=n)s.borderColor=n;return n!='red'};Q=function(j){if(typeof j=='string')j=j.s(/[ ,%5D+/);if(typeof j!=u&&j.length==1)j=j[0%5D.s('');for(k=0;typeof j==u||k<j.length;++k){s=E('s'+(typeof j==u%3Fk:j[k%5D-1));if(s!=null){(s=s.style).left=k%25336+1;s.top=(k-k%253)12+1}else if(typeof j==u)j=[%5D}J();O.value=l.j('')+(G()%3F'':'\nUnsolveable')};S=function(){a=arguments;J();if(typeof U==u||!U){O.value=l.j('');U=T;z=[%5D;o=[%5D;for(n=D.forms[j=0%5D.elements;j<n.length;++j)n[j%5D.disabled=n[j%5D.type.i('x')<0}m=T;for(j=0;j<l.length;m=!l[++j%5D||l[j%5D==j+1);if(m)O.value+=(O.value.M(/[\n%5D$/)==null%3F'\n':'')+'Done in '+z.length+' moves';if(m||a.length&&a[0%5D==F){U=F;for(n=D.forms[j=0%5D.elements;j<n.length;n[j++%5D.disabled='');G();return}if(o.length+z.length==0)if(a.length)o=a[0%5D;else return H(l.j(''),S);if(o.length){z.p(n=o.shift());O.value+=(O.value.M(/[\n %5D$/)==null%3F' ':'')+n;I(n-1,S)}else G()};H=function(){a=arguments;if(a.length==2){L=a[N=0%5D;V=[[[%5D,a[0%5D%5D%5D;P={};C=a[1%5D}f=new Date();while(V.length&&(new Date())-f<100){m=V.shift();if(typeof P[m[1%5D%5D==u){++N;P[m[1%5D%5D=T;j=m[1%5D.i(n=0);l=m[1%5D.s('');for(k=T;n<l.lengthk;++n)k=l[n%5D==0||l[n%5D==n+1;if(k){O.value=L+'\n';V=[%5D;C(m[0%5D);return}else{if(j>2)V.p([m[0%5D.c(l[j-3%5D),m[1%5D.r(l[j%5D,l[j-3%5D).r(l[j-3%5D,l[j%5D)%5D);if(j<6)V.p([m[0%5D.c(l[j+3%5D),m[1%5D.r(l[j+3%5D,l[j%5D).r(l[j%5D,l[j+3%5D)%5D);if(j%253>0)V.p([m[0%5D.c(l[j-1%5D),m[1%5D.r(l[j%5D,l[j-1%5D).r(l[j-1%5D,l[j%5D)%5D);if(j%253<2)V.p([m[0%5D.c(l[j+1%5D),m[1%5D.r(l[j+1%5D,l[j%5D).r(l[j%5D,l[j+1%5D)%5D)}}}O.value=L+((V.length>0&&sT(H,1)||C(F))%3F'\nTrying solutions of '+V[0%5D[0%5D.length+' moves':'\nNo solution exists.')+'\nPermutations: '+N};I=function(n,k){if(typeof d==u||!d){K(n);d=E('s'+n);C=k;p=X-x;q=Y-y;r=pI((Z=d.style).left)+36p;t=pI(Z.top)+36q}if(pI(Z.left)!=r||pI(Z.top)!=t){Z.left=pI(Z.left)+p;Z.top=pI(Z.top)+q;sT(I,10)}else{d=void(0);sT(C,10)}};O=D.forms[j=0%5D.output;U=F;b=E('r');for(s=D.getElementsByClassName('s');j<s.length;++j){s[j%5D.onmousemove=K;s[j%5D.onmousedown=function(e){if(typeof d!=u||K(this)==F)return F;d=this;B.style.cursor=d.style.cursor='none';x=e.clientX(X-x);X=d.offsetLeft;y=e.clientY(Y-y);Y=d.offsetTop;B.onmousemove=function(e){if(e.buttons<1||typeof d==u)return A();j=x!=0%3Fe.clientX-Ma(x):0;k=y!=0%3Fe.clientY-Ma(y):0;if(Ma(j=jx>0)>36)j=Ma(j)/j36;if(Ma(k=ky>0)>36)k=Ma(k)/k36;(s=d.style).left=X+j-1;s.top=Y+k-1;if(Ma(j)+Ma(k)>=36)A()};B.onmouseup=A;J();if(O.value.i('D')>0)O.value=l.j('');return false};s[j%5D.style.position=ab;s[j%5D.id='s'+j}Q()"ondragover="if((e=event).dataTransfer.types.contains('Files'))e.p()"ondrop="if(!((j=(f=(e=event).dataTransfer).types).contains('application/x-moz-file')||j.contains('text/uri-list')))return;i=('img');if((k=f.files).length){g=k[0%5D;if(!g.type.M(/image./))return;e.p();R=new FileReader();R.onload=(function(i){return function(e){i.src=e.target.result;i.onload=function(e){i=e.target;if(i.height<i.width)i.width=i.naturalWidth/i.naturalHeight(i.height=440);else i.height=i.naturalHeight/i.naturalWidth(i.width=440);c=('canvas');c.width=M.min(w=i.width,h=i.height);c.height=M.min(w,h);x=c.getContext('2d');x.drawImage(i,w>h%3F(h-w)/2:0,h>w%3F(w-h)/2:0,w,h);n=('canvas');n.width=n.height=120;for(j=0;j<8;++j){n.getContext('2d').putImageData(x.getImageData(16+j%253144,16+(j-j%253)48,120,120),0,0);x.clearRect(8+j%253144,8+(j-j%253)48,136,136);s=E('s'+j);(k=s.style).backgroundImage='url('+n.toDataURL(im)+')';k.backgroundSize=co;k.backgroundPosition=s.innerHTML=''}(k=b.style).backgroundImage='url('+c.toDataURL(im)+')';k.backgroundSize=co;k.backgroundPosition='';sT(G,1)}}})(i);R.readAsDataURL(g)}else{e.p();i.src=f.getData('text/uri-list');i.onload=function(e){i=e.target;(s=b.style).backgroundImage='url('+i.src+')';s.backgroundSize=co;v=w=j=0;if(i.width>i.height){v=MR(55-55/i.heighti.width);i.width=(i.height=110)/i.naturalHeighti.naturalWidth}else{w=MR(55-55/i.widthi.height);i.height=(i.width=110)/i.naturalWidthi.naturalHeight}for(console.log(s.backgroundPosition=v+'px '+w+'px');j<8;++j){s=E('s'+j);(k=s.style).backgroundImage='url('+i.src+')';console.log(k.backgroundSize=i.width+'px '+i.height+'px');console.log(k.backgroundPosition=v-4-j%25336+'px '+(w-4-(j-j%253)12)+'px');s.innerHTML='';if(E('h'+j)==null){m=_('div');(k=m.style).background='white';k.position=ab;k.display='block';k.height=k.width=34;k.left=2+j%25336;k.top=2+(j-j%253)12;k.zIndex=0;m.id='h'+j;(n=s.parentNode).insertBefore(m,n.firstChild)}}};if(i.complete){i.onload({target:i});i.onload=null}}">

1

2

3

4

5

6

7

8

<form><input type=button value=Scramble onclick="l=[%5D;n=[0,1,2,3,4,5,6,7,8%5D;while(n.length>0)l.p(n.splice(Mf(Mr()*n.length),1)[0%5D);Q(l);while(!G()){j=Mf(Mr()*9);k=Mf(Mr()*8);m=l[j%5D;l[j%5D=l[k+=k>j%5D;l[k%5D=m;Q(l)}"> <input type=button value=Set... onclick="J();Q(prompt('Enter %23s (the solved state is 123456780)',l.j('')))"> <input type=button value=Solve onclick=S()>
<textarea name=output rows=7 style=width:100%25 readonly>" target="blank" title="data:text/html,<title>Sliders</title><style>%23r{border:inset 2px;height:108;width:108;float:left;padding:1;position:relative;cursor:inherit}.s{border:outset 2px;background:buttonface;text-align:center;line-height:30px;height:30;width:30;float:left;margin:1}</style><body onload="with(m=String.prototype){m.b=substring;m.i=indexOf;m.M=match;m.r=replace;m.s=split}with(m=Array.prototype){m.c=concat;m.j=join;m.p=push}(m=Event.prototype).p=m.preventDefault;D=document;B=D.body;E=function(e){return D.getElementById(e)};M=Math;Ma=M.abs;Mf=M.floor;Mr=M.random;MR=M.round;W=window;pI=parseInt;T=true;F=!T;sT=setTimeout;u=typeof a;ab='absolute';im='image/png';na='not-allowed';co='cover';=function(e){return D.createElement(e)};J=function(){try{l=[0,0,0,0,0,0,0,0,i=0%5D;while(T)l[MR(((s=E('s'+i)).offsetTop3+s.offsetLeft)/36)%5D=++i}catch(e){}};K=function(s){if(typeof d!=u)return F;if(s instanceof Event)s=this;if(typeof s!='object'||!(s instanceof HTMLDivElement))s=E('s'+s);J();l=l.j('');j=l.i(0);k=l.i(s.id.b(1)1+1);x=k%253;y=Mf(k/3);X=j%253;Y=Mf(j/3);if(Ma(X-x)+Ma(Y-y)>1){s.style.cursor=na;return F}m=U%3Fna:(X-x>0%3F'e':X-x<0%3F'w':Y-y>0%3F's':'n')+'-resize';if((s=s.style).cursor!=m)s.cursor=m;return T};A=function(){B.onmousemove=B.onmouseup=B.style.cursor='';if(typeof d==u)return;if(Ma(d.offsetLeft-X)+Ma(d.offsetTop-Y)!=36){s.left=X-1;s.top=Y-1}else O.value+=(O.value.i('\n')<0%3F'\n':' ')+(d.id.b(1)1+1);d=void(0);G()};G=function(){J();for(j=x=0;j<l.length-1;++j)if(l[j%5D!=j+1){++x;for(k=j+1;k<l.length;++k)if(l[k%5D==j+1){m=l[j%5D;l[j%5D=l[k%5D;l[k%5D=m;k=l.length}}J();j=l.j('').i(0);y=j%253+(j-j%253)/3;n=x==0%3F'green':((x+y)%252>0)%3F'red':'yellow';if((s=b.style).borderColor!=n)s.borderColor=n;return n!='red'};Q=function(j){if(typeof j=='string')j=j.s(/[ ,%5D+/);if(typeof j!=u&&j.length==1)j=j[0%5D.s('');for(k=0;typeof j==u||k<j.length;++k){s=E('s'+(typeof j==u%3Fk:j[k%5D-1));if(s!=null){(s=s.style).left=k%25336+1;s.top=(k-k%253)12+1}else if(typeof j==u)j=[%5D}J();O.value=l.j('')+(G()%3F'':'\nUnsolveable')};S=function(){a=arguments;J();if(typeof U==u||!U){O.value=l.j('');U=T;z=[%5D;o=[%5D;for(n=D.forms[j=0%5D.elements;j<n.length;++j)n[j%5D.disabled=n[j%5D.type.i('x')<0}m=T;for(j=0;j<l.length;m=!l[++j%5D||l[j%5D==j+1);if(m)O.value+=(O.value.M(/[\n%5D$/)==null%3F'\n':'')+'Done in '+z.length+' moves';if(m||a.length&&a[0%5D==F){U=F;for(n=D.forms[j=0%5D.elements;j<n.length;n[j++%5D.disabled='');G();return}if(o.length+z.length==0)if(a.length)o=a[0%5D;else return H(l.j(''),S);if(o.length){z.p(n=o.shift());O.value+=(O.value.M(/[\n %5D$/)==null%3F' ':'')+n;I(n-1,S)}else G()};H=function(){a=arguments;if(a.length==2){L=a[N=0%5D;V=[[[%5D,a[0%5D%5D%5D;P={};C=a[1%5D}f=new Date();while(V.length&&(new Date())-f<100){m=V.shift();if(typeof P[m[1%5D%5D==u){++N;P[m[1%5D%5D=T;j=m[1%5D.i(n=0);l=m[1%5D.s('');for(k=T;n<l.lengthk;++n)k=l[n%5D==0||l[n%5D==n+1;if(k){O.value=L+'\n';V=[%5D;C(m[0%5D);return}else{if(j>2)V.p([m[0%5D.c(l[j-3%5D),m[1%5D.r(l[j%5D,l[j-3%5D).r(l[j-3%5D,l[j%5D)%5D);if(j<6)V.p([m[0%5D.c(l[j+3%5D),m[1%5D.r(l[j+3%5D,l[j%5D).r(l[j%5D,l[j+3%5D)%5D);if(j%253>0)V.p([m[0%5D.c(l[j-1%5D),m[1%5D.r(l[j%5D,l[j-1%5D).r(l[j-1%5D,l[j%5D)%5D);if(j%253<2)V.p([m[0%5D.c(l[j+1%5D),m[1%5D.r(l[j+1%5D,l[j%5D).r(l[j%5D,l[j+1%5D)%5D)}}}O.value=L+((V.length>0&&sT(H,1)||C(F))%3F'\nTrying solutions of '+V[0%5D[0%5D.length+' moves':'\nNo solution exists.')+'\nPermutations: '+N};I=function(n,k){if(typeof d==u||!d){K(n);d=E('s'+n);C=k;p=X-x;q=Y-y;r=pI((Z=d.style).left)+36p;t=pI(Z.top)+36q}if(pI(Z.left)!=r||pI(Z.top)!=t){Z.left=pI(Z.left)+p;Z.top=pI(Z.top)+q;sT(I,10)}else{d=void(0);sT(C,10)}};O=D.forms[j=0%5D.output;U=F;b=E('r');for(s=D.getElementsByClassName('s');j<s.length;++j){s[j%5D.onmousemove=K;s[j%5D.onmousedown=function(e){if(typeof d!=u||K(this)==F)return F;d=this;B.style.cursor=d.style.cursor='none';x=e.clientX(X-x);X=d.offsetLeft;y=e.clientY(Y-y);Y=d.offsetTop;B.onmousemove=function(e){if(e.buttons<1||typeof d==u)return A();j=x!=0%3Fe.clientX-Ma(x):0;k=y!=0%3Fe.clientY-Ma(y):0;if(Ma(j=jx>0)>36)j=Ma(j)/j36;if(Ma(k=ky>0)>36)k=Ma(k)/k36;(s=d.style).left=X+j-1;s.top=Y+k-1;if(Ma(j)+Ma(k)>=36)A()};B.onmouseup=A;J();if(O.value.i('D')>0)O.value=l.j('');return false};s[j%5D.style.position=ab;s[j%5D.id='s'+j}Q()"ondragover="if((e=event).dataTransfer.types.contains('Files'))e.p()"ondrop="if(!((j=(f=(e=event).dataTransfer).types).contains('application/x-moz-file')||j.contains('text/uri-list')))return;i=_('img');if((k=f.files).length){g=k[0%5D;if(!g.type.M(/image./))return;e.p();R=new FileReader();R.onload=(function(i){return function(e){i.src=e.target.result;i.onload=function(e){i=e.target;if(i.height<i.width)i.width=i.naturalWidth/i.naturalHeight(i.height=440);else i.height=i.naturalHeight/i.naturalWidth(i.width=440);c=('canvas');c.width=M.min(w=i.width,h=i.height);c.height=M.min(w,h);x=c.getContext('2d');x.drawImage(i,w>h%3F(h-w)/2:0,h>w%3F(w-h)/2:0,w,h);n=('canvas');n.width=n.height=120;for(j=0;j<8;++j){n.getContext('2d').putImageData(x.getImageData(16+j%253144,16+(j-j%253)48,120,120),0,0);x.clearRect(8+j%253144,8+(j-j%253)48,136,136);s=E('s'+j);(k=s.style).backgroundImage='url('+n.toDataURL(im)+')';k.backgroundSize=co;k.backgroundPosition=s.innerHTML=''}(k=b.style).backgroundImage='url('+c.toDataURL(im)+')';k.backgroundSize=co;k.backgroundPosition='';sT(G,1)}}})(i);R.readAsDataURL(g)}else{e.p();i.src=f.getData('text/uri-list');i.onload=function(e){i=e.target;(s=b.style).backgroundImage='url('+i.src+')';s.backgroundSize=co;v=w=j=0;if(i.width>i.height){v=MR(55-55/i.heighti.width);i.width=(i.height=110)/i.naturalHeighti.naturalWidth}else{w=MR(55-55/i.widthi.height);i.height=(i.width=110)/i.naturalWidthi.naturalHeight}for(console.log(s.backgroundPosition=v+'px '+w+'px');j<8;++j){s=E('s'+j);(k=s.style).backgroundImage='url('+i.src+')';console.log(k.backgroundSize=i.width+'px '+i.height+'px');console.log(k.backgroundPosition=v-4-j%253*36+'px '+(w-4-(j-j%253)12)+'px');s.innerHTML='';if(E('h'+j)==null){m=_('div');(k=m.style).background='white';k.position=ab;k.display='block';k.height=k.width=34;k.left=2+j%25336;k.top=2+(j-j%253)*12;k.zIndex=0;m.id='h'+j;(n=s.parentNode).insertBefore(m,n.firstChild)}}};if(i.complete){i.onload({target:i});i.onload=null}}">

1

2

3

4

5

6

7

8

<form><input type="button" value="Scramble" onclick="l=[%5D;n=[0,1,2,3,4,5,6,7,8%5D;while(n.length>0)l.p(n.splice(Mf(Mr()*n.length),1)[0%5D);Q(l);while(!G()){j=Mf(Mr()*9);k=Mf(Mr()*8);m=l[j%5D;l[j%5D=l[k+=k>j%5D;l[k%5D=m;Q(l)}"/> <input type="button" value="Set..." onclick="J();Q(prompt('Enter %23s (the solved state is 123456780)',l.j('')))"/> <input type="button" value="Solve" onclick="S()"/> <textarea name="output" rows="7" style="width:100%25" readonly="">">data:...</a> <pre><html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <title>Sliders</title> <style type="text/css"> div#rect { border: inset 2px; height: 108px; width: 108px; float: left; padding: 1px; position: relative; cursor: inherit; } span#move { cursor: move; } div.sq { border: outset 2px; background: buttonface; text-align: center; line-height: 30px; height: 30px; width: 30px; float: left; margin: 1px; } </style> <script type="text/javascript"> function setup() { var divs = document.getElementsByClassName("sq"); var loc = []; for (var d = 0; d < divs.length; ++ d) { divs[d].onmousemove = canMove; divs[d].onmousedown = beginMove; divs[d].style.position = "absolute"; divs[d].id = "sq" + (d + 1); } <pre><code>moveAll(); </code></pre> } function getList() { var num = document.getElementsByClassName("sq").length; var list = [0, 0, 0, 0, 0, 0, 0, 0, 0]; for (var i = 1; i <= num; ++ i) { var x = Math.round((document.getElementById("sq" + i).offsetLeft - 2) / 36); var y = Math.round((document.getElementById("sq" + i).offsetTop - 2) / 36); list[y * 3 + x] = i; } return list; } function canMove(div) { if (typeof window["moving"] != "undefined") return false; <pre><code>if (div instanceof Event) div = this; if (typeof div != "object" || !(div instanceof HTMLDivElement)) div = document.getElementById("sq" + div); var list = getList(), n = Number(div.id.split("sq")[1]); var w = Math.sqrt(list.length); for (var i = 0, blank, click; i < list.length; ++ i) { if (list[i] == 0) blank = i; else if (list[i] == n) click = i; } var x = click % w, y = Math.floor(click / w); var x2 = blank % w, y2 = Math.floor(blank / w); if (Math.abs(x2 - x) + Math.abs(y2 - y) != 1) { div.style.cursor = "not-allowed"; return false; //not next to the blank space } var cur = solve.underway ? "not-allowed" : ((x2 - x) > 0 ? "e" : (x2 - x) < 0 ? "w" : (y2 - y) > 0 ? "s" : "n") + "-resize"; if (div.style.cursor != cur) div.style.cursor = cur; return [x, y, x2, y2]; </code></pre> } function beginMove(e) { if (solve.underway) return false; <pre><code>var x, y, x2, y2; [x, y, x2, y2] = canMove(this); if (typeof x == "undefined") return false; document.body.style.cursor = "none"; document.getElementById("move").style.cursor = "none"; this.style.cursor = "none"; window["moving"] = this.id; window["startX"] = e.clientX * (x2 - x); window["startXo"] = this.offsetLeft; window["startY"] = e.clientY * (y2 - y); window["startYo"] = this.offsetTop; document.body.onmousemove = midMove; document.body.onmouseup = endMove; if (document.forms[0].output.value.indexOf("Done") > 0) document.forms[0].output.value = getList().join(""); return false; </code></pre> } function midMove(e) { if (e.buttons == 0 || typeof window["moving"] == "undefined") return endMove(); <pre><code>var Xo = 0, Yo = 0; if (window["startX"] != 0) Xo = e.clientX - Math.abs(window["startX"]); if (window["startY"] != 0) Yo = e.clientY - Math.abs(window["startY"]); if (Xo * window["startX"] < 0) Xo = 0; if (Yo * window["startY"] < 0) Yo = 0; var div = document.getElementById(window["moving"]); if (Math.abs(Xo) > 36) Xo = Math.abs(Xo) / Xo * 36; if (Math.abs(Yo) > 36) Yo = Math.abs(Yo) / Yo * 36; div.style.left = window["startXo"] + Xo - 1 + "px"; div.style.top = window["startYo"] + Yo - 1 + "px"; if (Math.abs(Xo) + Math.abs(Yo) >= 36) endMove(); </code></pre> } function endMove() { document.body.onmousemove = void(0); document.body.onmouseup = void(0); document.body.style.cursor = ""; document.getElementById("move").style.cursor = ""; <pre><code>if (typeof window["moving"] == "undefined") return; //check move for validity var div = document.getElementById(window["moving"]); var Xo = div.offsetLeft - window["startXo"]; var Yo = div.offsetTop - window["startYo"]; if (Math.abs(Xo) + Math.abs(Yo) != 36) { div.style.left = window["startXo"] - 1 + "px"; div.style.top = window["startYo"] - 1 + "px"; } else { document.forms[0].output.value += (document.forms[0].output.value.indexOf("\n") < 0 ? "\r\n" : " ") + window["moving"].substring(2); } window["moving"] = void(0); compute(); </code></pre> } function compute() { var list = getList(), parity = 0, temp; for (var i = 0; i < list.length - 1; ++ i) if (list[i] != i + 1) { ++ parity; for (var j = i + 1; j < list.length; ++ j) if (list[j] == i + 1) { temp = list[i]; list[i] = list[j]; list[j] = temp; j = list.length; } } var list = getList(), dist = 0; for (var i = 0; i < list.length; ++ i) if (list[i] == 0) { var x = i % 3, y = (i - x) / 3; dist = x + y - 4; i = list.length; } <pre><code>var res = "yellow"; if (parity == 0) res = "green"; else if ((parity + dist) % 2 != 0) res = "red"; if (document.getElementById("rect").style.borderColor != res) document.getElementById("rect").style.borderColor = res; return res != "red"; </code></pre> } function moveAll(list) { //list may be an arrays of numbers or a string (with or without commas) //does not check for validity (numbers 0-8 should be found exactly once) if (typeof list == "string") list = list.split(/[ ,]+/); if (typeof list != "undefined" && list.length == 1) list = list[0].split(""); <pre><code>for (var i = 0; typeof list == "undefined" || i < list.length; ++ i) { var sq = document.getElementById("sq" + (typeof list == "undefined" ? i + 1 : list[i])); if (sq != null) { sq.style.left = i % 3 * 36 + 1 + "px"; sq.style.top = (i - i % 3) * 12 + 1 + "px"; } else if (typeof list == "undefined") list = []; } document.forms[0].output.value = getList().join("") + (compute() ? "" : "\r\nUnsolveable"); </code></pre> } </script> <script type="text/javascript"> //automatic scramble & solve function scramble() { var list = [], l2 = [0, 1, 2, 3, 4, 5, 6, 7, 8]; while (l2.length > 0) { var i = Math.floor(Math.random() * l2.length); list.push(l2.splice(i, 1)[0]); } moveAll(list); <pre><code>while (!compute()) { //unsolveable, switch 2 tiles to fix it var i = Math.floor(Math.random() * 9); var j = Math.floor(Math.random() * 8); if (j >= i) ++ j; var temp = list[i]; list[i] = list[j]; list[j] = temp; moveAll(list); } </code></pre> } function solve() { var output = document.forms[0].output; <pre><code>var list = getList(); if (typeof solve.underway == "undefined" || !solve.underway) { output.value = list.join("") + "\r\n"; solve.underway = true; solve.solution = []; solve.moves = []; for (var e = document.forms[0].elements, i = 0; i < e.length; ++ i) if (e[i].type == "button") e[i].disabled = true; } for (var i = 0, solved = true, moveable = []; i < list.length; ++ i) if (list[i] != 0) { if (canMove(list[i]) != false) moveable.push(list[i]); if (list[i] != i + 1) solved = false; } if (solved) document.forms[0].output.value += (output.value.match(/[\r\n]$/) == null ? "\r\n" : "") + "Done in " + solve.solution.length + " moves"; if (solved || arguments.length > 0 && arguments[0] == false) { solve.underway = false; for (var e = document.forms[0].elements, i = 0; i < e.length; ++ i) e[i].disabled = ""; compute(); return; } //enumerates every possible series of moves, beginning with 1 move and growing progressively longer, //until the shortest solution is found. reject moves which return the puzzle to a previous state, as //the first path to any state is guaranteed to be the shortest sequence of moves to reach that state. //note that this finds the ideal solution, but probably does so with less-than-ideal efficiency. if (solve.moves.length + solve.solution.length == 0) { if (arguments.length > 0) solve.moves = arguments[0]; else return pleaseSolve(list.join(""), solve); } if (solve.moves.length > 0) { var n = solve.moves.shift(); solve.solution.push(n); output.value += (output.value.match(/[\r\n ]$/) == null ? " " : "") + n; move(n, solve); } else compute(); </code></pre> } function pleaseSolve(/list, callback/) { //attempts to solve a given list. runs iteratively rather than recursively and displays //status, politely exiting now and then to give the user interface a chance to update. //when a solution is found, callback is called with the list of moves. var i, l, m, n, solved, count = 0; if (arguments.length == 2) { pleaseSolve.list = arguments[0]; pleaseSolve.moves = [[[], arguments[0]]]; pleaseSolve.prev = {}; pleaseSolve.c = 0; pleaseSolve.callback = arguments[1]; } <pre><code>var t = new Date(); while (pleaseSolve.moves.length > 0 && (new Date()) - t < 100) { m = pleaseSolve.moves.shift(); if (typeof pleaseSolve.prev[m[1]] == "undefined") { ++ pleaseSolve.c; pleaseSolve.prev[m[1]] = true; i = m[1].indexOf(0); l = m[1].split(""); solved = true; for (n = 0; n < l.length; ++ n) if (l[n] != 0 && l[n] != n + 1) { solved = false; n = l.length; } if (solved) { document.forms[0].output.value = pleaseSolve.list + "\r\n"; pleaseSolve.moves = []; pleaseSolve.callback(m[0]); return; } else { //pleaseSolve.moves contains the queue of possible moves, each being [moves[], newlist] //where moves[] is the list of moves to get to that point and newlist is the list after //that move. array.concat and string.replace are used to add the new move and swap two //items in the list without modifying either of the originals. var move; if (i > 2) pleaseSolve.moves.push([m[0].concat(l[i - 3]), m[1].replace(l[i], l[i - 3]).replace(l[i - 3], l[i])]); if (i < 6) pleaseSolve.moves.push([m[0].concat(l[i + 3]), m[1].replace(l[i + 3], l[i]).replace(l[i], l[i + 3])]); if (i % 3 > 0) pleaseSolve.moves.push([m[0].concat(l[i - 1]), m[1].replace(l[i], l[i - 1]).replace(l[i - 1], l[i])]); if (i % 3 < 2) pleaseSolve.moves.push([m[0].concat(l[i + 1]), m[1].replace(l[i + 1], l[i]).replace(l[i], l[i + 1])]); } } } //not done searching yet: print a status update and set a timeout to resume //searching where we left off after the user interface has a chance to update. if (pleaseSolve.moves.length > 0) { document.forms[0].output.value = pleaseSolve.list + "\r\nTrying solutions of " + pleaseSolve.moves[0][0].length + " moves\r\nPermutations: " + pleaseSolve.c; setTimeout(pleaseSolve, 1); //we'll be back } else { document.forms[0].output.value = pleaseSolve.list + "\r\nNo solution exists.\r\nPermutations: " + pleaseSolve.c; pleaseSolve.callback(false); } </code></pre> } function move(n, callback) { //animates moving a piece of the puzzle and calls callback when finished if (typeof move.moving == "undefined" || !move.moving) { move.moving = document.getElementById("sq" + n); move.callback = callback; [move.x, move.y, move.x2, move.y2] = canMove(n); move.xo = move.x2 - move.x; move.yo = move.y2 - move.y; //parseInt stops when it reaches "px" at the end of each value move.destX = parseInt(move.moving.style.left, 10) + 36 * move.xo + "px"; move.destY = parseInt(move.moving.style.top, 10) + 36 * move.yo + "px"; } <pre><code>if (move.moving.style.left != move.destX || move.moving.style.top != move.destY) { move.moving.style.left = parseInt(move.moving.style.left, 10) + move.xo + "px"; move.moving.style.top = parseInt(move.moving.style.top, 10) + move.yo + "px"; setTimeout(move, 10); //we must exit to let the browser repaint } else { move.moving = undefined; setTimeout(move.callback, 10); //finished - call callback to tell it we're done } </code></pre> } </script> <script type="text/javascript"> /* drag & drop */ function allowDrop(e) { if (!e.dataTransfer.types.contains("Files")) return; e.preventDefault(); } function drop(e) { //accepts a local image file or an image dragged from the web if (!(e.dataTransfer.types.contains("application/x-moz-file") || e.dataTransfer.types.contains("text/uri-list"))) return; <pre><code>var img = document.createElement("img"); if (e.dataTransfer.files.length > 0) { //local file - load onto canvas and chop var file = e.dataTransfer.files[0]; if (!file.type.match(/image.*/)) return; e.preventDefault(); var reader = new FileReader(); reader.onload = (function (img) { return function (e) { img.src = e.target.result; img.onload = process; }; })(img); reader.readAsDataURL(file); } else { //remote image files can't be loaded into a canvas due to cross-domain safety //restrictions. instead, set backgroundImage and use backgroundPosition to crop e.preventDefault(); var uriList = e.dataTransfer.getData("text/uri-list"); img.src = uriList; img.onload = function (e) { var img = e.target; document.getElementById("rect").style.backgroundImage = "url(\"" + img.src + "\")"; document.getElementById("rect").style.backgroundSize = "cover"; var x = 0, y = 0; if (img.width > img.height) { x = Math.round((110 - 110 / img.height * img.width) / 2); img.height = 110; img.width = 110 / img.naturalHeight * img.naturalWidth; } else if (img.height > img.width) { y = Math.round((110 - 110 / img.width * img.height) / 2); img.height = 110 / img.naturalWidth * img.naturalHeight; img.width = 110; } document.getElementById("rect").style.backgroundPosition = x + "px " + y + "px"; for (var i = 0; i < 8; ++ i) { var sq = document.getElementById("sq" + (i + 1)); sq.style.backgroundImage = "url(\"" + img.src + "\")"; sq.style.backgroundSize = img.width + "px " + img.height + "px"; sq.style.backgroundPosition = x - 4 - i % 3 * 36 + "px " + (y - 4 - (i - i % 3) * 12) + "px"; sq.innerHTML = ""; if (document.getElementById("h" + (i + 1)) == null) { var div = document.createElement("div"); div.style.background = "white"; div.style.position = "absolute"; div.style.display = "block"; div.style.height = "34px"; div.style.width = "34px"; div.style.left = 2 + i % 3 * 36 + "px"; div.style.top = 2 + (i - i % 3) * 12 + "px"; div.style.zIndex = "0"; div.id = "h" + (i + 1); sq.parentNode.insertBefore(div, sq.parentNode.firstChild); } } }; if (img.complete) { img.onload({target: img}); //cached image won't fire the onload event img.onload = null; } } </code></pre> } function process(e) { //process a local file - load onto canvas, chop, and use as backgroundImage var img = e.target; //drawImage uses nearest-neighbor to resize, and it looks bad. make size 4x larger than necessary to compensate. //it will be scaled back down to the correct size with backgroundSize, yielding a much better-looking result. var size = 440; if (img.height < img.width) { //scale smallest dimension to size img.height = size; img.width = img.naturalWidth / img.naturalHeight * size; } else { img.width = size; img.height = img.naturalHeight / img.naturalWidth * size; } <pre><code>//create a square canvas & center image on it var canvas = document.createElement("canvas"); canvas.width = Math.min(img.width, img.height); canvas.height = Math.min(img.width, img.height); var context = canvas.getContext("2d"); context.drawImage(img, img.width > img.height ? (img.height - img.width) / 2 : 0, img.height > img.width ? (img.width - img.height) / 2 : 0, img.width, img.height); //this canvas will hold a single piece of the image, again 4x larger than necessary var canvas2 = document.createElement("canvas"); canvas2.width = 120; canvas2.height = 120; var context2 = canvas2.getContext("2d"); for (var sq, i = 0; i < 8; ++ i) { sq = context.getImageData( 16 + i % 3 * 144, 16 + (i - i % 3) * 48, 120, 120); context.clearRect( 8 + i % 3 * 144, 8 + (i - i % 3) * 48, 136, 136); context2.putImageData(sq, 0, 0); sq = document.getElementById("sq" + (i + 1)); dataURL = canvas2.toDataURL("image/png"); sq.style.backgroundImage = "url(\"" + dataURL + "\")"; sq.style.backgroundSize = "cover"; sq.style.backgroundPosition = ""; sq.innerHTML = ""; } var dataURL = canvas.toDataURL("image/png"); document.getElementById("rect").style.backgroundImage = "url(\"" + dataURL + "\")"; document.getElementById("rect").style.backgroundSize = "cover"; document.getElementById("rect").style.backgroundPosition = ""; setTimeout(compute, 1); </code></pre> } </script> </head> <body onload="setup();" ondragover="allowDrop(event);" ondrop="drop(event);"> <div id="rect"><span id="move"> <div class="sq">1</div> <div class="sq">2</div> <div class="sq">3</div> <div class="sq">4</div> <div class="sq">5</div> <div class="sq">6</div> <div class="sq">7</div> <div class="sq">8</div> </div> <br clear="both"/> <form> <input type="button" value="Scramble" onclick="scramble();"/> <input type="button" value="Set..." onclick="moveAll(prompt('Enter #s (the solved state is 123456780)',getList().join('')));"/> <input type="button" value="Solve" onclick="solve();"/> <textarea name="output" rows="7" style="width:100%;" readonly></textarea> </form> </body> </html></pre> </textarea></form>

Sliding Around

Leave a comment on “Sliding Around”