The Daily WTF: Curious Perversions in Information Technology

2009-09-02 Reply Admin

What is that horrible language JAVA 6 has posted in? Looks a bit like c#, but isn't. Java, maybe?

I'd like to know so I can avoid RIDICULOUS ANONYMOUS FLAMEBAITERS in my online life.

2009-09-02 Reply Admin

I rather liked my solution, which simulates reality by randomly moving the blank square around until you happen upon a solved puzzle.

Only took it 68 seconds real time the first time to solve it!

Code Dependent · 2009-09-02 Reply Admin

DailyWTF people (Alex, et al): I respect you for this. If I was unemployed, I would probably try to solve these puzzles just to put my skilz out there. As it is, I do have a job, and therefore cannot devote my time to this trivia. Sorry.

Addendum (2009-09-02 17:51): Sorry also for those who can.

2009-09-02 Reply Admin

I'm not going to lie, if I didn't have an existing (provably optimal) solution sitting around, I wouldn't be solving trivia problems either.

2009-09-02 Reply Admin

Pascal rocks, its just a lot better than C as language. And the Delphi compiler generates smallest and faster binaries than the C++ compiler. I had to say it, benchmarks dont lie.

2009-09-02 Reply Admin

He is leet ... the rest of us only understand XOR swap !

Code Dependent · 2009-09-02 Reply Admin

big brain:
Pascal rocks, its just a lot better than C as language. And the Delphi compiler generates smallest and faster binaries than the C++ compiler. I had to say it, benchmarks dont lie.

I gotcher benchmark right here.

evilspoons · 2009-09-02 Reply Admin

One of the solutions on page 2 made my browser (firefox 3.0.x, haven't upgraded to 3.5 because it crashes thanks to my workplace's "monitoring" software) show a huge black square instead of the person's post, which turns into readable text sometimes if you do a select all. Weird.

Moss · 2009-09-02 Reply Admin

I bet none of you can solve this in LOGO. By having the turtle draw the entire thing.

Code Dependent · 2009-09-02 Reply Admin

Keith Brawner:
I'm not going to lie, if I didn't have an existing (provably optimal) solution sitting around, I wouldn't be solving trivia problems either.

Gotta respect you even more for that, Keith.

2009-09-02 Reply Admin

I prefer a Pandora of WTFs; it sounds inappropriately erudite.

2009-09-02 Reply Admin

Dividius:
What is that horrible language JAVA 6 has posted in? Looks a bit like c#, but isn't. Java, maybe?
I'd like to know so I can avoid RIDICULOUS ANONYMOUS FLAMEBAITERS in my online life.

2009-09-02 Reply Admin

This finds the optimal solution by a width-first search.

Because many boards have no solution, the generateInput() method creates a board by starting with a solved board and sliding up to 50 times at random.

Sample output:

START FROM |1|2|3| |4|5|6| |7|8|-|

RANDOMIZE INPUT |8|1|-| |4|2|5| |3|6|7| ------- -> (33 moves) 8,5,2,3,6,2,3,6,2,8,5,3,6,1,4,6,1,2,8,1,3,7,6,3,2,8,1,5,7,6,3,4,8,1 OUTPUT |1|2|3| |4|5|6| |7|8|-| ------- -> (21 moves) 5,2,6,3,4,8,1,5,2,6,3,7,6,3,8,4,7,8,5,2,3,6

Code:

package byoc;

import java.util.HashSet;
import java.util.Random;
import java.util.TreeMap;

public class NumberSlider {
	final static char SLIDER_C = '-';
	final static String GOAL = "12345678"+SLIDER_C;
	final static int BOARD_SIZE = GOAL.length();
	final static int META_DATA_INDEX = BOARD_SIZE+1;
	final static int[][] legalMoves = new int[][]{
		{1,3},{0,2,4},{1,5},{0,4,6},{1,3,5,7},{2,4,8},{3,7},{4,6,8},{7,5}
	};
	public static void main(String[] args) {
		System.err.println("START FROM");
		printBoard(GOAL);
		String input = generateInput();
		System.err.println("RANDOMIZE INPUT");
		printBoard(input);
		String output = solve(input.substring(0,9));
		System.err.println("OUTPUT");
		printBoard(output);
	}
	private static String generateInput() {
		String input = GOAL;
		Random r = new Random(System.currentTimeMillis());
		int position = GOAL.indexOf(SLIDER_C);
		int oldPosition = position;
		int newPosition;
		for (int i = 0; i < 50; i++) {
			newPosition = legalMoves[position][r.nextInt(legalMoves[position].length)];
			if (newPosition != oldPosition) {
				input = slide(input,position,newPosition);
				oldPosition = position;
				position = newPosition; 
			}
		}
		return input;
	}
	private static String solve(String board) {
		HashSet<String> examinedBoards = new HashSet<String>();
		TreeMap<Double,String> unexaminedBoards = new TreeMap<Double,String>();
		int i = 0;
		unexaminedBoards.put(qualityScore(board, i++), board);
		while (!board.startsWith(GOAL)) {
			board = unexaminedBoards.remove(unexaminedBoards.firstKey());
			final int position = board.indexOf(SLIDER_C);
			for (int newPosition : legalMoves[position]) {
				final String newBoard = slide(board,position,newPosition);
				final String newBoardKey = newBoard.substring(0,BOARD_SIZE);
				if (examinedBoards.contains(newBoardKey)) {
					continue;
				}
				examinedBoards.add(newBoardKey);
				unexaminedBoards.put(qualityScore(newBoard,i++),newBoard);
			}
		}
		return board;
	}
	private static double qualityScore(String board, int dec) {
		int unmatchedPieces = BOARD_SIZE;
		for (int i = 0; i < BOARD_SIZE; i++) {
			if (board.charAt(i) == GOAL.charAt(i)) {
				unmatchedPieces--;
			}
		}
		unmatchedPieces += 1000*board.length();
		return Double.parseDouble(unmatchedPieces+"."+dec);
	}
	private static String slide(String board, int position, int newPosition) {
		char[] c = board.toCharArray();
		c[position] = c[newPosition];
		c[newPosition] = SLIDER_C;
		return new String(c) + "," + c[position];
	}
	private static void printBoard(String board) {
		System.err.println("|"+board.charAt(0)+"|"+board.charAt(1)+"|"+board.charAt(2)+"|");
		System.err.println("|"+board.charAt(3)+"|"+board.charAt(4)+"|"+board.charAt(5)+"|");
		System.err.println("|"+board.charAt(6)+"|"+board.charAt(7)+"|"+board.charAt(8)+"|");
		System.err.println("-------" + (board.length() > BOARD_SIZE ? " -> (" + board.substring(META_DATA_INDEX).length()/2 + " moves) " + board.substring(META_DATA_INDEX): ""));
	}
}

mol1111 · 2009-09-02 Reply Admin

evilspoons:
One of the solutions on page 2 made my browser (firefox 3.0.x, haven't upgraded to 3.5 because it crashes thanks to my workplace's "monitoring" software) show a huge black square instead of the person's post, which turns into readable text sometimes if you do a select all. Weird.

Quite normal for Firefox. It does that often on such long pages.

2009-09-02 Reply Admin

the real WTF is why are you putting exercises on this website? Create a new category, stick them in there, and keep up with the real WTF.

atrophic · 2009-09-02 Reply Admin

For an interesting experiment I first tried solving this using the "methinks it's a weasel" sort of evolution simulation, but I couldn't find a good way of scoring the comparisons well. They kept getting stuck in a situation where all of the spots surrounding the blank were solved so it'd move away from that and then right back to it; there was no incentive to deviate further away from the solution in order to get it solved.

Anyway, abandoned that eventually and made an inefficient iterative optimal path algorithm. So it's "DIFFICULT" but not "FAST". It does at least make sure it's not repeating its work.

This is the single character variable names version that keeps a bit of formatting but still sneaks in under 800 bytes ;)

Ruby:

def solve(x)
  p "Puzzle: #{x}"
  z="12345678 "
  t=Hash.new
  t[x]=""
  a=[x]
while (a.index(z)==nil && a.size > 0)
b=[]
a.each do |p|
v=[]
i=p.index(" ")
v << "U" if i < 6
v << "D" if i > 2
v << "L" if (i+1) % 3 != 0
v << "R" if i % 3 != 0
v.each do |d|
n=p.dup
i=n.index(" ")
n[i], n[i+3]=n[i+3], n[i] if d=="U"
n[i], n[i-3]=n[i-3], n[i] if d=="D"
n[i], n[i+1]=n[i+1], n[i] if d=="L"
n[i], n[i-1]=n[i-1], n[i] if d=="R"
if t[n]==nil
t[n]=t[p] + d
b << n
end
end
end
a=b
end
t=t[z]
raise "Impossible puzzle." if t==nil
p "#{t.length} steps: #{t}"
end
solve(ARGV[0])
#solve(" 87654321")

2009-09-02 Reply Admin

me:
the real WTF is why are you putting exercises on this website? Create a new category, stick them in there, and keep up with the real WTF.

the real WTF is to write something before reading anything

...

Sliding Around 2009-09-02 by Alex Papadimoulis in Bring Your Own Code

2009-09-02 Reply Admin

Bim Job:
See, the thing about NP-complete problems is that they admit of brute-force solutions ... up to a problem size of about ten or twenty.
And the other thing about NP-complete problems is that brute-force suddenly hits brick wall and stops working for a small increment of the problem size.

Brute force solutions don't magically stop working....they just require exponentially more and more time as the solution space grows larger.

Further, you seem to be dividing solutions into 2 categories polynomial-time (efficient) and brute force. This is nowhere close to reality. Many advanced search techniques cut dramatically down on the algorithmic complexity, but still remain non-polynomial time. Specifically I can think of several SAT solvers that can return, in a matter of minutes solutions that would take a brute force algorithm several universelifes to stumble upon.

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.

2009-09-02 Reply Admin

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

Quickly hashed together code gives me these answers.

When the empty tile is in one of the 4 corners, then the maximum depth is 31 moves, and there are 2 starting states at this depth. As there are 4 corners, then this means 8 starting states.

When the empty tile is in one of the 4 edges, then the maximum depth is 31 moves, and there are 2 starting states at this depth. As there are 4 edges, then this means 8 starting states.

When the empty tile is in the center square, then the maximum depth is 30 moves, and there are 26 starting positions at this depth.

2009-09-02 Reply Admin

I hate replying to myself, but I just noticed these ...

8 = 3^2 - 1 26 = 3^3 - 1

I wonder if this is a formula for stating states that could be expanded to larger dimensions like 4x4 and 5x5 ? Maybe something to do with the distance that the empty square is from the center of the puzzle ?

2009-09-02 Reply Admin

Here's a slowish Python program that finds the shortest solution. If the starting position is unsolvable, it transposes the goal.

def slide(s):
assert len(s) == 9 and set('12345678.') == set(s)
parity = sum(s[i] < s[j]
for i in range(8)
for j in range(i+1,9)
if s[i] != '.' != s[j])
if parity & 1: goal = list('14725836.')
else: goal = list('12345678.')
g = list(s)
if g == goal: return []
def bfs(g):
edge = [(g, g.index('.'), [])]
found = set([tuple(g)])
while edge:
ne = []
for g, ep, moves in edge:
deltas = []
if ep >= 3: deltas.append(-3)
if ep <  6: deltas.append(3)
if ep % 3 != 0: deltas.append(-1)
if ep % 3 != 2 : deltas.append(1)
for d in deltas:
ng = g[:]; ng[ep] = g[ep + d]; ng[ep + d] = '.'
tg = tuple(ng)
if tg not in found:
nxt = ng, ep + d, moves + [ep + d]
if ng == goal: return nxt[2]
ne.append(nxt)
found.add(tg)
edge = ne
raise Exception('Logic error')
path = bfs(g)
ep = g.index('.')
for i in [ep] + path:
g[ep] = g[i]; g[i] = '.'; ep = i
print(3 * '%s%s%s\n' % tuple(g))
def random():
import random
lst = list('12345678.')
random.shuffle(lst)
s = ''.join(lst)
slide(s)

2009-09-02 Reply Admin

big brain:
Pascal rocks, its just a lot better than C as language. And the Delphi compiler generates smallest and faster binaries than the C++ compiler. I had to say it, benchmarks dont lie.

Which C++ compiler? There are a great many.

2009-09-02 Reply Admin

Mathematical proof that there are impossible starting configurations:

We will impose a linear ordering upon the pieces in the puzzle: we'll treat it as a paragraph of text, reading row by row top-to-bottom, left-to-right within each row. The solved puzzle state can be read as "123/456/78#". With this order, we can naturally say that the "3" piece comes "before" the "4" or the "6", but not the "2"; and we can say that the "5" is "inbetween" the "2" and the hole.

For any state of the sliding puzzle, you can give a "score" to an unordered pair of two pieces as follows: if the lower-numbered piece comes "before" the higher-numbered one, the pair has a score of 1; otherwise, it has a score of 0.

We define the score of a 3-by-3 puzzle state as the sum of the scores of the 28 pairs. For example, the solution state "123/456/78#" has a score of 28. The puzzle state "876/543/21#" has a score of 0, and the puzzle state "135/7#2/468" has a score of 22.

If I transition from state P to state Q by a single horizontal slide, then each of the 28 pairs in state P is in exactly the same scoring orientation as the 28 pairs in state Q. For example, "123/456/78#" has the same score as "123/456/7#8".

Now consider the transition from state P to state Q by a single vertical slide of piece A. In state P, there are two pieces "inbetween" piece A and the hole; call them B and C. Both of the pairs (A,B) and (A,C) flip their scoring orientation between states P and Q; the other 26 pairs keep their scoring orientation.

Therefore, if one can move from state P to state Q as the result of a single slide, then the difference "score(P)-score(Q)" must be one of -2, 0, or 2.

Therefore, as the result of any number of slides, the score of the initial state and the score of the final state must have the same parity modulo 2.

As shown earlier, the solution state's score is 28.

The score of the state "123/456/87#" is 27.

Therefore, no sequence of slides can convert "123/456/87#" to "123/456/78#".

2009-09-02 Reply Admin

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!!!!!!!!!!!!

2009-09-02 Reply Admin

Here's a python version that's under 800 bytes. Sample usage: python unscramble.py '67143528 '

import sys

def unscramble(s):
    n_idx = ((1,3),(0,2,4),(1,5),(0,4,6),(1,3,5,7),(2,4,8),(3,7),(4,6,8),(5,7))
    queue = [s]
    prev = {s: 0}
    while queue:
        x = queue.pop(0)
        i = x.find(' ')
        for j in n_idx[i]:
            y = list(x)
            y[i] = y[j]
            y[j] = ' '
            y = ''.join(y)
            if y not in prev:
                prev[y] = x
                if y=='12345678 ' or y=='12345687 ':
                    path = []
                    while y:
                        path.insert(0,y)
                        y = prev[y]
                    return path
                queue.append(y)
    return []

if __name__ == '__main__':
    path = unscramble(sys.argv[1])
    if path:
        for step in path:
            print(step)

Eternal Density · 2009-09-02 Reply Admin

I propose the collective noun for WTFs should be 'swamp'.

2009-09-02 Reply Admin

One way of solving it is to see that the numbers can still be in the right order, only rotated. Reading clockwise 1, 2, 3, 6, 8, 7, 4 around the edges with 5 in the center is almost completly solved. 4,1,2, 7,5,3, 8,_,6, is almost totally solved.

Once an edge row or col. has been finished. It can be left alone.

You can use the center to store a peice and then insert it (counter)clockwise of the proper piece. (Note: my puzzle has a gap in the top left, not bottom right. And its a frog. The clockwise order is 1,2,5,8,7,6,3, with 4 in center) _,7,6, 8,1,5, 4,3,2,

7,6,5, 8,_,1, #1 and 2 and now in order. 4,3,2

5 is not in the best spot right now, so I'll go for 8 I slide 8 into the center.

7,6,5, _,8,1, 4,3,2,

then free up the spot clockwise of 2.

7,6,5, 4,8,1, 3,_,2,

and slide 8 in

7,6,5, 4,_,1, 3,8,2,

remember I want the order to be 1,2,5,8,7,6,3 6 will fit in nicely now.

7,_,5, 4,6,1, 3,8,2,

7,5,1, 4,6,2, 3,_,8,

7,5,1, 4,_,2, 3,6,8,

5 is now is a spot where it can slide into the center.

7,_,1, 4,5,2, 3,6,8,

I want the order to be 1,2,5,8,7,6,3 so

7,1,2, 4,_,5, 3,6,8,

Almost there, I have one vertical row done. (2,5,8) I can leave this intact and only move the 5 pieces on the right

I bring 1 and 4 to the top and leave them there while I fix the other pieces

7,1,2, _,4,5, 3,6,8,

1,4,2, 7,_,5, 3,6,8,

I rotate the three bottom left pieces untill they are like this

1,4,2, 3,_,5, 6,7,8,

I bring down 1 and 4 to finish

_,1,2, 3,4,5, 6,7,8,

Now I'm off to try and get that to work in python.

2009-09-02 Reply Admin

RBoy:
Shredder:
By the way what is this "Bring your own code"? I was sue that it was called Programming Praxis before.

Well, now you are Shredder, not Sue, and it's called Bring Your Own Code, not Programming Praxis.

That must have been a Freudian typo! I just remembered that I read that some guy threatened to sue Alex for using the name Programming Praxis, which must be why he changed it.

captcha: zucchinifelatio

2009-09-03 Reply Admin

The function assumes a string input of the numbers 1-8, and a 0 representing the empty spot. It outputs which number you should slide. Using an iterative version of a BFS (it did say write a function, not functions :) it finds the fastest way to solve the entered puzzle.

And yes, it's in C#. THE HORROR!

    public static string SolveNineSlider(string input)
    {
        string solution = "123456780";

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

        List<string> Visited = new List<string>();

        Dictionary<string, string> Actives = new Dictionary<string, string>();

        Actives.Add(input, string.Empty);

        while (!Actives.ContainsKey(solution))
        {
            Dictionary<string, string> TempActives = new Dictionary<string, string>();
            foreach (KeyValuePair<string, string> kvp in Actives)
            {
                int index = kvp.Key.IndexOf('0');
                int[] spots = spotshifts[index];
                for (int i = 0; i < spots.Length; i++)
                {
                    string next = kvp.Key.Clone().ToString();
                    string nextpath = kvp.Value.Clone().ToString();
                    char c = next[spots[i]];
                    next = next.Replace('0', '*');
                    next = next.Replace(c, '0');
                    next = next.Replace('*', c);
                    nextpath += c;
                    if (!Visited.Contains(next))
                    {
                        if (TempActives.ContainsKey(next))
                        {
                            if (TempActives[next].Length > nextpath.Length)
                                TempActives[next] = nextpath;
                        }
                        else
                            TempActives.Add(next, nextpath);
                    }
                }
                Visited.Add(kvp.Key);
            }

            Actives.Clear();
            foreach (KeyValuePair<string, string> kvp in TempActives)
                Actives.Add(kvp.Key, kvp.Value);
        }

        return Actives[solution];
    }
}

2009-09-03 Reply Admin

Imho recommending a less structured programming language to someone because they don't understand the syntax of a more modern language is bad advice.

In the realm of practical languages, Excluding any esolang and parser written for fun, a more interesting question is why would someone bother to write a syntactic construct like that ?

How did they manage to convince anyone else to use it ?

Perhaps the problem is common enough and someone else has thought about it before ?

What were they thinking ?

2009-09-03 Reply Admin

Well, I didn't bring my own code, but anyway, this one is from Bratko's Prolog programming for AI. The heuristic is simple but pretty good, so I guess it falls into the difficult category.

% Figure 12.6  Problem-specific procedures for the eight 
% puzzle, to be used in best-first search of Figure 12.3.


/* Problem-specific procedures for the eight puzzle

Current situation is represented as a list of positions of the tiles, 
with first item in the list corresponding to the empty square.

Example:

                           This position is represented by:
3        1    2    3
2        8         4       [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]
1        7    6    5
          
         1    2    3

"Empty' can move to any of its neighbours which means 
that "empty' and its neighbour interchange their positions.
*/

% s( Node, SuccessorNode, Cost)

s( [Empty | Tiles], [Tile | Tiles1], 1)  :-  % All arc costs are 1
  swap( Empty, Tile, Tiles, Tiles1).         % Swap Empty and Tile in Tiles 

swap( Empty, Tile, [Tile | Ts], [Empty | Ts] )  :-
  mandist( Empty, Tile, 1).                  % Manhattan distance = 1

swap( Empty, Tile, [T1 | Ts], [T1 | Ts1] )  :-
  swap( Empty, Tile, Ts, Ts1).

mandist( X/Y, X1/Y1, D)  :-          % D is Manhhattan dist. between two squares
  dif( X, X1, Dx),
  dif( Y, Y1, Dy),
  D is Dx + Dy.

dif( A, B, D)  :-              % D is |A-B|
  D is A-B, D >= 0, !
  ;
  D is B-A.

% Heuristic estimate h is the sum of distances of each tile
% from its "home' square plus 3 times "sequence' score

h( [Empty | Tiles], H)  :-
  goal( [Empty1 | GoalSquares] ), 
  totdist( Tiles, GoalSquares, D),      % Total distance from home squares
  seq( Tiles, S),                       % Sequence score
  H is D + 3*S.

totdist( [], [], 0).

totdist( [Tile | Tiles], [Square | Squares], D)  :-
  mandist( Tile, Square, D1),
  totdist( Tiles, Squares, D2),
  D is D1 + D2.

% seq( TilePositions, Score): sequence score

seq( [First | OtherTiles], S)  :-
  seq( [First | OtherTiles ], First, S).

seq( [Tile1, Tile2 | Tiles], First, S)  :-
  score( Tile1, Tile2, S1),
  seq( [Tile2 | Tiles], First, S2),
  S is S1 + S2.

seq( [Last], First, S)  :-
  score( Last, First, S).

score( 2/2, _, 1)  :-  !.              % Tile in centre scores 1

score( 1/3, 2/3, 0)  :-  !.            % Proper successor scores 0
score( 2/3, 3/3, 0)  :-  !.
score( 3/3, 3/2, 0)  :-  !.
score( 3/2, 3/1, 0)  :-  !.
score( 3/1, 2/1, 0)  :-  !.
score( 2/1, 1/1, 0)  :-  !.
score( 1/1, 1/2, 0)  :-  !.
score( 1/2, 1/3, 0)  :-  !.

score( _, _, 2).                       % Tiles out of sequence score 2

% goal( [2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2] ).  % The original goal squares for tiles
goal( [3/1,1/3,2/3,3/3,1/2,2/2,3/2,1/1,2/1] ).  % TDWTF goal squares for tiles

% Display a solution path as a list of board positions

showsol( [] ).

showsol( [P | L] )  :-
  showsol( L),
  nl, write( '---'),
  showpos( P).

% Display a board position

showpos( [S0,S1,S2,S3,S4,S5,S6,S7,S8] )  :-
  member( Y, [3,2,1] ),                           % Order of Y-coordinates
  nl, member( X, [1,2,3] ),                       % Order of X-coordinates
  member( Tile-X/Y,                               % Tile on square X/Y
          [' '-S0,1-S1,2-S2,3-S3,4-S4,5-S5,6-S6,7-S7,8-S8] ),
  write( Tile),
  fail                                            % Backtrack to next square
  ;
  true.                                           % All squares done

% Starting positions for some puzzles

start1( [2/2,1/3,3/2,2/3,3/3,3/1,2/1,1/1,1/2] ).  

start2( [2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3] ).  

start3( [2/2,2/3,1/3,3/1,1/2,2/1,3/3,1/1,3/2] ).  

% An example query: ?- start1( Pos), bestfirst( Pos, Sol), showsol( Sol).

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

% Figure 12.3  A best-first search program.
% bestfirst( Start, Solution): Solution is a path from Start to a goal

bestfirst( Start, Solution) :-
  expand( [], l( Start, 0/0),  9999, _, yes, Solution).
	%  Assume 9999 is greater than any f-value

% expand( Path, Tree, Bound, Tree1, Solved, Solution):
%   Path is path between start node of search and subtree Tree,
%   Tree1 is Tree expanded within Bound,
%   if goal found then Solution is solution path and Solved = yes

%  Case 1: goal leaf-node, construct a solution path

expand( P, l( N, _), _, _, yes, [N|P])  :-
   goal(N).

%  Case 2: leaf-node, f-value less than Bound
%  Generate successors and expand them within Bound.

expand( P, l(N,F/G), Bound, Tree1, Solved, Sol)  :-
  F  =<  Bound,
  (  bagof( M/C, ( s(N,M,C), not member(M,P) ), Succ), 
     !,                                    % Node N has successors
     succlist( G, Succ, Ts),               % Make subtrees Ts
     bestf( Ts, F1),                       % f-value of best successor
     expand( P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol)
     ;
     Solved = never                        % N has no successors - dead end
  ) .

%  Case 3: non-leaf, f-value less than Bound
%  Expand the most promising subtree; depending on 
%  results, procedure continue will decide how to proceed

expand( P, t(N,F/G,[T|Ts]), Bound, Tree1, Solved, Sol)  :-
  F  =<  Bound,
  bestf( Ts, BF), min( Bound, BF, Bound1),          % Bound1 = min(Bound,BF)
  expand( [N|P], T, Bound1, T1, Solved1, Sol),
  continue( P, t(N,F/G,[T1|Ts]), Bound, Tree1, Solved1, Solved, Sol).

%  Case 4: non-leaf with empty subtrees
%  This is a dead end which will never be solved

expand( _, t(_,_,[]), _, _, never, _) :- !.

%  Case 5:  f-value greater than Bound
%  Tree may not grow.

expand( _, Tree, Bound, Tree, no, _)  :-
  f( Tree, F), F > Bound.

% continue( Path, Tree, Bound, NewTree, SubtreeSolved, TreeSolved, Solution)

continue( _, _, _, _, yes, yes, Sol).

continue( P, t(N,F/G,[T1|Ts]), Bound, Tree1, no, Solved, Sol)  :-
  insert( T1, Ts, NTs),
  bestf( NTs, F1),
  expand( P, t(N,F1/G,NTs), Bound, Tree1, Solved, Sol).

continue( P, t(N,F/G,[_|Ts]), Bound, Tree1, never, Solved, Sol)  :-
  bestf( Ts, F1),
  expand( P, t(N,F1/G,Ts), Bound, Tree1, Solved, Sol).

% succlist( G0, [ Node1/Cost1, ...], [ l(BestNode,BestF/G), ...]):
%   make list of search leaves ordered by their F-values

succlist( _, [], []).

succlist( G0, [N/C | NCs], Ts)  :-
  G is G0 + C,
  h( N, H),                             % Heuristic term h(N)
  F is G + H,
  succlist( G0, NCs, Ts1),
  insert( l(N,F/G), Ts1, Ts).

% Insert T into list of trees Ts preserving order w.r.t. f-values

insert( T, Ts, [T | Ts])  :-
  f( T, F), bestf( Ts, F1),
  F  =<  F1, !.

insert( T, [T1 | Ts], [T1 | Ts1])  :-
  insert( T, Ts, Ts1).


% Extract f-value

f( l(_,F/_), F).        % f-value of a leaf

f( t(_,F/_,_), F).      % f-value of a tree

bestf( [T|_], F)  :-    % Best f-value of a list of trees
  f( T, F).

bestf( [], 9999).       % No trees: bad f-value
  
min( X, Y, X)  :-
  X  =<  Y, !.

min( X, Y, Y).

Mike5

2009-09-03 Reply Admin

Collective noun

A ==== of WTFs

puddle mess crapload sadness woeful

2009-09-03 Reply Admin

Bim Job:
It's not helped by pointy-headed professors, either. Given the requirement ("the professor gave us a starting position"), this code is an A, not an F.

Yeah, that's why you should not only fire people who can't read requirements, you also need to fire people who can't write requirements.

2009-09-03 Reply Admin

A* with ruby:

class Puzzle
    def initialize(tiles)
        @tiles = tiles
        @hole = [0, 0]
        @moves = 0
    end

    def nextStates
        dx = [-1, 1, 0, 0]
        dy = [0, 0, 1, -1]
        (0..3).map { |d| move(dx[d], dy[d]) }.compact
    end

    def finished?
        @tiles == [[nil, 1, 2], [3, 4, 5], [6, 7, 8]]
    end

    def move(dx, dy)
        p = Marshal.load(Marshal.dump(self))

        x = p.hole[0] + dx
        y = p.hole[1] + dy

        if x >= 0 and y >= 0 and x < 3 and y < 3
            p.tiles[y][x], p.tiles[hole[1]][hole[0]] = [p.tiles[hole[1]][hole[0]], p.tiles[y][x]]
            p.hole = [x, y]
            p.moves += 1
            return p
        end
    end

    def goalDistance
        distance = 0
        0.upto(2) { |y|
            0.upto(2) { |x|
                n = (@tiles[y][x] or 0)
                distance += (x - (n % 3))**2 + (y - (n / 3))**2
            }
        }
        return distance
    end

    def hash
        @tiles.flatten.inject(0) { |h, x| h * 9 + (x or 0) }
    end

    attr_accessor :tiles, :hole, :moves
end

def shuffle(p)
    500.times {
        n = p.nextStates
        p = n[rand(n.length)]
    }
    p.moves = 0
    return p
end

def solve(initState)
    queue = [[initState, initState.goalDistance]]

    visited = Hash.new
    loop {
        p = queue.shift[0]
        return nil if not p
        return p if p.finished?
        if not visited[p.hash]
            p.nextStates.each { |s| queue << [s, s.moves + s.goalDistance] }
            queue = queue.sort_by { |x| x[1] }
            visited[p.hash] = true
        end
    }
end

initState = shuffle(Puzzle.new([[nil, 1, 2], [3, 4, 5], [6, 7, 8]]))
startTime = Time.now
goal = solve(initState)
if goal
    puts "Solved in #{goal.moves} moves (#{Time.now - startTime} seconds)"
end

2009-09-03 Reply Admin

In my AI class we had to solve this. The professor gave us a starting position. We also had to demo our code to the class. One clever student was called on.

The clever student just taught the professor something: the importance of writing good specifications.

Teaching the professor something always gets you an F.

2009-09-03 Reply Admin

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

2009-09-03 Reply Admin

Easy.

He didn't have to write the algorithm for solving the thing.

2009-09-03 Reply Admin

This should work.... Puzzle class not included, but you'll get the idea.

public class SmartSolver implements Runnable
{
	/**
	 * Width an height of the puzzle.
	 */
	private int WIDTH, HEIGHT;
	
	/**
	 * Current puzzle.
	 */
	private Puzzle p;
	
	/**
	 * These hold the calculation step and the output speed.
	 */
	private int calculations;
	
	/**
	 * Constructor. Initiates the number of calculations,
	 * sets the starting puzzle, sets the width and height
	 * 
	 * @param p
	 */
	public SmartSolver(Puzzle p)
	{
		this.p = p;
		calculations = 0;
		WIDTH = p.getWidth();
		HEIGHT = p.getHeight();
	}

	/**
	 * Moves the hole of the puzzle in the given
	 * direction.
	 * 
	 * @param d
	 */
	private void move(Direction d)
	{
		calculations++;
		p.moveHole(d);
	}

	/**
	 * Moves a certain number in the puzzle to the
	 * gives coordinates without disturbing the rows
	 * above or equal to the row of the coordinate.
	 * 
	 * @param number	Number to move
	 * @param y			Y coordinate
	 * @param x			X coordinate
	 */
	private void moveNumber(int number, int y, int x)
	{
		int num_x = 0, num_y = 0;
		boolean stop = false;
		//find position of number and store the goal coordinates
		//in num_x and num_y
		for(int n_x = 0; n_x < WIDTH && !stop; n_x++) {
			for(int n_y = 0; n_y < HEIGHT && !stop; n_y++) {
				if(p.getNumber(n_x, n_y) == number) {
					num_x = n_x;
					num_y = n_y;
					stop = true;
				}
			}
		}

		//move down to not disturb any pieces
		if(num_x < x && p.getHoleY() == y) {
			move(Direction.DOWN);
		}

		//move the number to the left side
		while(num_x > x) {
		    if(p.getHoleY() == num_y && p.getHoleX() > num_x) {
		        if(num_y == HEIGHT - 1) {
		        	move(Direction.UP); 
		        } else {
		        	move(Direction.DOWN);
		        }
		    }
		    //move blank to the correct position
		    while(p.getHoleX() >= num_x)  move(Direction.LEFT);
		    while(p.getHoleX() < num_x - 1) move(Direction.RIGHT);
		    while(p.getHoleY() < num_y)   move(Direction.DOWN);
		    while(p.getHoleY() > num_y)   move(Direction.UP);
		    //do the move move
		    move(Direction.RIGHT);
		    num_x--;
		}

		//move the numer to the right side
		while(num_x < x) {
		    if(p.getHoleY() == num_y && p.getHoleX() < num_x) {
		        if(num_y == HEIGHT - 1) {
		        	move(Direction.UP); 
		        } else {
		        	move(Direction.DOWN);
		        }
		    }
		    //move the blank to te corect position
		    while(p.getHoleX() <= num_x)    move(Direction.RIGHT);
		    while(p.getHoleX() > num_x + 1) move(Direction.LEFT);
		    while(p.getHoleY() < num_y)     move(Direction.DOWN);
		    while(p.getHoleY() > num_y)     move(Direction.UP);
		    //do the move
		    move(Direction.LEFT);
		    num_x++;
		}
		
		//move number up
		while(num_y > y) {
		    if(y < num_y - 1) {
		    	//when to lower than one row under the goal position
		        while(p.getHoleY() < num_y - 1) move(Direction.DOWN);
		        if(p.getHoleX() == num_x) {
		        	if(num_x == WIDTH - 1) {
		        		move(Direction.LEFT);
		        	} else {
		        		move(Direction.RIGHT);
		        	}
		        }
		        //move blank to the correct position
		        while(p.getHoleY() > num_y - 1) move(Direction.UP);
		        while(p.getHoleX() < num_x)   move(Direction.RIGHT);
		        while(p.getHoleX() > num_x)   move(Direction.LEFT);
		        //do the move
		        move(Direction.DOWN);
		    } else {
		    	//when the number is one row under the goal position
		        if(num_x != WIDTH - 1) {
		        	//when the goal position is not in the last column 
		            if(p.getHoleY() == num_y && num_y != HEIGHT - 1) {
		            	move(Direction.DOWN);
		            }
		            //move blank to the cocrect position
		            while(p.getHoleX() < num_x + 1) move(Direction.RIGHT);
		            while(p.getHoleX() > num_x + 1) move(Direction.LEFT);
		            while(p.getHoleY() > num_y - 1) move(Direction.UP);
		            while(p.getHoleY() < num_y - 1) move(Direction.DOWN);
		            //do the move
		            move(Direction.LEFT);
		            move(Direction.DOWN);
		        } else {
		        	//when the goal position is in the last column
		            if(p.getHoleY() < num_y && p.getHoleX() == num_x) {
		            	//when you're lucky
		                while(p.getHoleY() < num_y)     move(Direction.DOWN);
		            } else {
		            	//place blank in the correct position
		                while(p.getHoleY() > num_y + 1) move(Direction.UP);
		                while(p.getHoleY() < num_y + 1) move(Direction.DOWN);
		                while(p.getHoleX() < num_x)     move(Direction.RIGHT);
		                while(p.getHoleX() > num_x)     move(Direction.LEFT);
		                //make a complicated sequence of moves to place the 
		                //number in the last column.
		                move(Direction.UP);
		                move(Direction.UP);
		                move(Direction.LEFT);
		                move(Direction.DOWN);
		                move(Direction.RIGHT);
		                move(Direction.DOWN);
		                move(Direction.LEFT);
		                move(Direction.UP);
		                move(Direction.UP);
		                move(Direction.RIGHT);
		                move(Direction.DOWN);
		            }
		        }
		    }
		    num_y--;
		}
		
		//move blank down
		while(num_y < y) {
		    if(p.getHoleX() == num_x && p.getHoleY()<num_y){
		        if(num_x == WIDTH-1) {
		        	move(Direction.LEFT);
		        } else {
		        	move(Direction.RIGHT);
		        }
		    }
		    //move blank to the correct position
		    while(p.getHoleY() > num_y+1) move(Direction.UP);
		    while(p.getHoleY() < num_y+1) move(Direction.DOWN);
		    while(p.getHoleX() < num_x)   move(Direction.RIGHT);
		    while(p.getHoleX() > num_x)   move(Direction.LEFT);
		    //do the move
		    move(Direction.UP);
		    num_y++;
		}
	}

	/**
	 * Solve a puzzle on a structured way without searching
	 * for the solution.
	 * 
	 * This method will be called when the thread is started.
	 */
	public void run() {
		//start with the first number
        int number = 1;
        //solve to the top rows without the bottom two rows
        for(int r = 0; r < HEIGHT - 2; r++) {
            for(int c = 0; c < WIDTH; c++) {
            	moveNumber(number + c, r, c);
            }
            number += WIDTH;
        }
        //solve the bottom two rows without the last two by two square
        for(int c = 0; c < WIDTH - 2; c++) {
        	moveNumber(number, HEIGHT - 2, c);
            if(p.getHoleX() == c) {
            	move(Direction.RIGHT);
            }
            if(p.getNumber((number + WIDTH - 1) % WIDTH, (number + WIDTH - 1) / WIDTH) != (number + WIDTH)) {
            	moveNumber(number + WIDTH, HEIGHT - 1, c + 1);
                if(p.getHoleY() != HEIGHT - 1) {
                    //A.X or AX.
                    //XBX    XBX
                    if(p.getHoleX() == c + 1) {
                    	move(Direction.RIGHT);
                    }
                    move(Direction.DOWN);
                }
                //AXX
                //XB.
                while(p.getHoleX() > c + 2)  move(Direction.LEFT);
                move(Direction.LEFT);
                move(Direction.LEFT);
                move(Direction.UP);
                move(Direction.RIGHT);
                move(Direction.DOWN);
                move(Direction.RIGHT);
                move(Direction.UP);
                move(Direction.LEFT);
                move(Direction.LEFT);
                move(Direction.DOWN);
                move(Direction.RIGHT);
            }
            number++;
        }
        //solve the last two by two square
        if(p.getHoleX() < WIDTH - 1)  move(Direction.RIGHT);
        if(p.getHoleY() < HEIGHT - 1) move(Direction.DOWN);
        number = (WIDTH * HEIGHT - 1) - WIDTH;
        if(p.getNumber((number - 1) % WIDTH, (number - 1) / WIDTH) == number + 1) {
        	move(Direction.UP);
        	move(Direction.LEFT);
        	move(Direction.DOWN);
        	move(Direction.RIGHT);
        }
        if(p.getNumber((number - 1) % WIDTH, (number - 1) / WIDTH) == number + WIDTH) {
        	move(Direction.LEFT);
        	move(Direction.UP);
        	move(Direction.RIGHT);
        	move(Direction.DOWN);
        }
	}
}

2009-09-03 Reply Admin

"interesting"

2009-09-03 Reply Admin

dijkstra in c++

#include <stdio.h>
#include <queue>
#include <map>
#include <set>
int d[]={-1, 1, -3, 3};

std::set<int> visited;
std::map<int, int> prev;
std::queue<int> q;

int getPos(int num, int x)
{
	for(int i=0; i<9; i++)
	{
		if(num%10 == x) return i;
		num/=10;
	}
	return 10;
}

int swap0(int num, int pos0, int posx)
{
	if(posx<0||posx>8) return 0;
	if(posx/3 != pos0/3 && posx%3!=pos0%3) return 0;
	int x=num;
	int sub=1;
	for(int i=0; i<posx; i++)
	{
		sub*=10;
		x/=10;
	}
	x=x%10;
	int add=1;
	for(int i=0; i<pos0; i++)
	{
		add*=10;
	}
	return num+(add-sub)*x;
}

int main()
{
	int num = 123456780;

	int a,b,c, finish;
	scanf("%d%d%d", &a, &b, &c);
	finish=a*1000000+b*1000+c;

	for(int i=0; i<9; i++)
	{
		if(getPos(finish, i) == 10) 
		{
			printf("invalid number\n");
			return 1;
		}
	}
	q.push(num);
	while(!q.empty())
	{
		num=q.front();
		q.pop();
		
		if(visited.count(num)) continue;
		visited.insert(num);

		if(num==finish)
		{
			while(num!=123456780) 
			{
				printf("\n%03d\n%03d\n%03d\n", prev[num]/1000000, prev[num]/1000%1000, prev[num]%1000);
				num=prev[num];
			}
			getchar();getchar();
			return 0;
		}
		int pos0=getPos(num, 0);

		for(int i=0;i<4;i++)
		{
			int next=swap0(num, pos0, pos0+d[i]);
			if(next && !prev[next]) {
				prev[next]=num;
				q.push(next);
			}
		}
	}

	printf("unsolvable\n");
	getchar();getchar();
	return 2;
}
</pre>

2009-09-03 Reply Admin

So what are the chances of Alex sending a WTF mug to the first person to offer a solution using Brainfuck? ;)

2009-09-03 Reply Admin

Alfredo:
dijkstra in c++

I meant BFS, of course

2009-09-03 Reply Admin

Harrow:
SR:
...what is the collective noun for WTFs?...
Cluster.

:oD I like cluster!

2009-09-03 Reply Admin

Moss:
I bet none of you can solve this in LOGO. By having the turtle draw the entire thing.

My turtle's hard at work on the problem right now. I'll let you know how he gets on when he's finished in around 215 years' time.

2009-09-03 Reply Admin

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

2009-09-03 Reply Admin

Even using INT21h? You're doing it wrong. Shouldn't be more than about 20-30B, compiled. Or about 80 bytes of source.

2009-09-03 Reply Admin

So how fast do these "optimal" solutions go?

I've done an A* implementation in C++ which completes in 0.34 seconds. Is that good or bad?

2009-09-03 Reply Admin

How fast your solution goes is highly dependent on your processor and how far away the solution is away from the goal.

.34 seconds is about on par for an A*, IIRC. I want to say that I've seen .16 worst time for the 3x3. A better test, however, is to test your solution on a 21x21.

halcyon1234 · 2009-09-03 Reply Admin

I'm too lazy to see if this works in all cases, so I'll do what MS does:

Here's the public release, and it will be the richest and most secure Sliding Problem solution ever. (Service Pack 1 to follow)

In SQL.

SET NOCOUNT ON

-- User defined variables DECLARE @GiveUp int -- When to give up DECLARE @OpeningPosition varchar(9)

-- Making-life-easier variables DECLARE @ZeroPos int -- Current position of the space DECLARE @CurrVal varchar(255) -- The current board DECLARE @LastMove int -- The last move taken (so you don't just move the same piece over and over) DECLARE @moveNum int -- The current move number (loop variable)

-- Play history DECLARE @CharBoard table (vals varchar(9), lastMove int, moveNum int identity (0,1) primary key) -- feel free to turn this into a perm table to use an index on vals

-- Set variables here SET @GiveUp = 50 -- how many moves to try before the program gives up SET @OpeningPosition = '123456708' -- The initial position of the 3x3 board, from top left, with 0 being the empty space

-- Initilize board

INSERT INTO @CharBoard values(@OpeningPosition, 0)

SET @LastMove = 0 set @moveNum = 0

-- If we haven't given up, and a solved board doesn't exist yet WHILE @moveNum < @GiveUp and not exists (select top 1 1 from @Charboard where vals = '123456780' order by moveNum desc) BEGIN

SELECT top 1 @CurrVal =  vals, @LastMove = lastMove, @MoveNum = moveNum from @Charboard order by moveNum desc
SELECT @ZeroPos = CHARINDEX('0', @CurrVal)

-- Order of preference of spot selection, most desirable to least
-- Piece can be moved into it's own spot
-- The closest piece to the spot can be moved (high wins ties) without being moved out of it's own spot
-- The highest number piece moves

-- use this to switch 0 and the value at position pos
INSERT INTO @CharBoard (vals, lastMove)
--set @moveNum = 99
select top 1 replace(replace(replace(@CurrVal, val, 'X'), '0', val), 'X', '0'), val
from
(
	select val, pos, abs(@ZeroPos-val) as distance,
		case	when val = @ZeroPos then 1
				when val = @LastMove then 4
				when val = pos then 5
				else 2
			end as [desire]
	from
	(
		SELECT cast(substring(@CurrVal, @ZeroPos-3,1) as int) as [Val], @ZeroPos-3 as [Pos]
		UNION
		SELECT cast(substring(@CurrVal, @ZeroPos+3,1) as int), @ZeroPos+3
		UNION
		SELECT case when @ZeroPos not in (1,4,7) then cast(substring(@CurrVal, @ZeroPos-1,1) as int) else 0 end, @ZeroPos-1
		UNION
		SELECT case when @zeroPos not in (3,6,9) then cast(substring(@CurrVal, @ZeroPos+1,1) as int) else 0 end, @ZeroPos+1
	) side
	where 
			 val > 0
) desire
order by desire, distance, val desc

END

select case when @MoveNum >= @GiveUp then 'Fuck it, I''m done' else 'Victory is mine!' end as [Result] select moveNum as [Move Number], lastMove as [Piece moved], vals as [Resulting board] from @CharBoard

2009-09-03 Reply Admin

Using breadth-first search:

#include <string>
#include <iostream>
#include <queue>
#include <set>
#include <cstdio>
#include <cmath>

using namespace std;

class Nine {

public:

  typedef pair<Nine, string> bfsqitem_t;
  typedef queue<bfsqitem_t>  bfs_queue_t;
  typedef vector<bfsqitem_t>  bfs_vec_t;

  Nine(const string &in, size_t _dim=3) :
    dim(_dim),
    size(dim*dim),
    board(new char[size+1])
  {
    if (in.length() != size) {
      dim=size=0;
      return;
    }
    for (size_t i=0; i<size; i++) {
      board[i] = in.at(i);
      if (board[i]=='0')
	zpos=i;
    }
    board[size]=0;
  }

  ~Nine() {
  }

  static string search(Nine &b) {
    set<string> seen;
    bfs_queue_t q;
    q.push( bfs_queue_t::value_type(b,"") );
    while (q.size()) {
      bfs_queue_t::value_type f = q.front();
      q.pop();
      
      bfs_vec_t nextq;
      try_moves(f, nextq);

      for (bfs_vec_t::iterator i=nextq.begin();
	   i != nextq.end();
	   i++) {
	if (i->first.completed())
	  return i->second;
	if (seen.find(i->first.board) != seen.end()) 
	  continue;
	q.push(*i);
	seen.insert(i->first.board);
      }
      
      
    }
    return "";
  }

  static void try_moves( const bfsqitem_t &f,
			 bfs_vec_t &q ) {
    string how=f.second;    
    if (f.first.zpos % f.first.dim != 0) {
      q.push_back( bfs_vec_t::value_type(Nine(f.first, 
					      f.first.zpos-1),
					 how+'L') );
    }

    if ((f.first.zpos+1) % f.first.dim != 0) {
      q.push_back( bfs_vec_t::value_type(Nine(f.first, 
					      f.first.zpos+1),
					 how+'R') );
    }

    if (f.first.zpos >= f.first.dim) {
      q.push_back( bfs_vec_t::value_type(Nine(f.first, 
					      f.first.zpos-f.first.dim),
					 how+'U') );
    }

    if (f.first.zpos < f.first.size-f.first.dim) {
      q.push_back( bfs_vec_t::value_type(Nine(f.first, 
					      f.first.zpos+f.first.dim),
					 how+'D') );
    }
  }


  Nine(const Nine &other, int swap) :
    zpos(other.zpos),
    dim(other.dim),
    size(other.size),
    board(new char[size+1])
  {
    for (size_t i=0; i<size; i++) {
      board[i]=other.board[i];
    }
    board[zpos]=other.board[swap];
    board[swap]='0';
    zpos=swap;
    board[size]=0;
  }

  bool completed() {
    static const char* soln="123456789abcdefghijklmnopqrstuvwxyz";
    return ! strncmp(soln, board, size-1);
  }

  size_t zpos;
  size_t dim;
  size_t size;
  char *board;
};


int main (int argc, char *argv[]) {
  if (argc<2)
    exit(-1);

  Nine b(argv[1], (int)sqrt(strlen(argv[1])));
  cout << Nine::search(b) << endl;
  return 0;
}
</pre>
Using best-first search:
#include <string>
#include <iostream>
#include <queue>
#include <set>
#include <cstdio>
#include <cmath>

using namespace std;

class NineSearchItem;

class Nine {

public:

  typedef vector<NineSearchItem>  bfs_vec_t;

  Nine(const string &in, size_t _dim=3) :
    dim(_dim),
    size(dim*dim),
    board(new char[size+1])
  {
    if (in.length() != size) {
      dim=size=0;
      return;
    }
    for (size_t i=0; i<size; i++) {
      board[i] = in.at(i);
      if (board[i]=='0')
	zpos=i;
    }
    board[size]=0;
  }

  ~Nine() {
  }

  Nine(const Nine &other, int swap) :
    zpos(other.zpos),
    dim(other.dim),
    size(other.size),
    board(new char[size+1])
  {
    for (size_t i=0; i<size; i++) {
      board[i]=other.board[i];
    }
    board[zpos]=other.board[swap];
    board[swap]='0';
    zpos=swap;
    board[size]=0;
  }

  bool completed() {
    static const char* soln="123456789abcdefghijklmnopqrstuvwxyz";
    return ! strncmp(soln, board, size-1);
  }

  size_t zpos;
  size_t dim;
  size_t size;
  char *board;
};

class NineSearchItem : public Nine {
public:
  typedef priority_queue<NineSearchItem> bfs_pq_t;

  NineSearchItem(const string &in,
		 size_t _dim=3,
		 string _how="") :
    Nine(in, _dim),
    how(_how)
  {
    fitness = eval_fitness();
  }

  NineSearchItem(const NineSearchItem &other,
		 int swap,
		 string _how)
    : Nine(other, swap),
      how(_how)
  {
    fitness = eval_fitness();
  }

  void try_moves( bfs_vec_t &q ) {
    if (zpos % dim != 0) {
      q.push_back( NineSearchItem(*this, 
				  zpos-1,
			  how+'L') );
    }

    if ((zpos+1) % dim != 0) {
      q.push_back( NineSearchItem(*this, 
				  zpos+1,
				  how+'R') );
    }

    if (zpos >= dim) {
      q.push_back( NineSearchItem(*this,
				  zpos-dim,
				  how+'U') );
    }

    if (zpos < size-dim) {
      q.push_back( NineSearchItem(*this,
				  zpos+dim,
				  how+'D') );
    }
  }

  int eval_fitness() {
    static const char* soln="123456789abcdefghijklmnopqrstuvwxyz";
    int f = 0;
    int d = dim;
    for (int i=0; i<(int)size; i++) {
      int place;
      if (board[i]=='0')
	place=size-1;
      else
	place=strchr(soln,board[i])-soln;
      f -= abs(i%d-place%d)+abs(i/d-place/d);
    }
    return f;
  }

  string search() {
    set<string> seen;
    bfs_pq_t q;
    q.push( *this );
    while (q.size()) {
      NineSearchItem f = q.top();
      q.pop();
      bfs_vec_t nextq;
      f.try_moves(nextq);

      for (bfs_vec_t::iterator i=nextq.begin();
	   i != nextq.end();
	   i++) {
	if (i->completed())
	  return i->how;
	if (seen.find(i->board) != seen.end()) 
	  continue;
	q.push(*i);
	seen.insert(i->board);
      }
      
    }
    return "";
  }

  bool operator< (const NineSearchItem &other) const {
    return (fitness == other.fitness) ?
      (how.length() > other.how.length()) : 
      (fitness < other.fitness);
  }

  string how;
  int fitness;

};

int main (int argc, char *argv[]) {
  if (argc<2)
    exit(-1);
  
  NineSearchItem b(argv[1], (int)sqrt(strlen(argv[1])));
  cout << b.search() << endl;
  return 0;
}

Sliding Around

START FROM |1|2|3| |4|5|6| |7|8|-|

Leave a comment on “Sliding Around”