The Daily WTF: Curious Perversions in Information Technology

2009-08-12 Reply Admin

incassum:
If the example ignores rules it does not like, I shall do the same (Using C64 Basic):
10 ? "I WIN"
20 GOTO 10

Ah, yes, that reminds me. A long, long time ago, when I was just a grasshopper, the Engineers who ran the Honeywell 66/10 I was programming on, showed me a timesharing program that was something like the following:

chess OK, I choose white. Pawn to K4. Your move. Pawn to K4 (nothing for fifteen seconds) I resign.

Of course, all it was was a script that printed out the first line, accepted and discarded any input from the user, waited fifteen seconds and then printed out "I resign".

There were a number of users who struggled with this concept, however, and tried to have a genuine game of chess with it before getting very angry :)

2009-08-12 Reply Admin

curtmack:
It doesn't generate closed tours, although this would be a pretty easy modification. Because of how it prints the solution, the specified starting point is actually the ending point.

But if you stored it in a doubly-linked list, you could just traverse it backwards. You have provided an example of how to use such a data structure, as per the request of one of the other commenters.

2009-08-12 Reply Admin

@AlpineR

Skipping the trivial case (one piece, one color), the smallest, simplest mosaic is a 1x5 set with all different colors.

ABCDE | ECADB

For a square set, you can achieve it with a 3x3 square assuming "touching" does not include corners

ABC | BGF DEF | IEA GHI | DCH

Fewest colors? 4, as in this 1x5 case:

ABCDD | DBDAC

And I believe the above is the smallest pair using the fewest colors (again, skipping the trivial case).

2009-08-12 Reply Admin

Train MIDGET on knights tour
Insert MIDGET into TURK
Run Knights Tour on TURK

Infinitely programmable, within reason...

2009-08-12 Reply Admin

justsomedude:
using twinview with 2 + a third monitor leads to all sorts of crappy behavior

That's what you get for trying to stuff 3 pounds of monitor into a 2 pound bag...

2009-08-12 Reply Admin

Java. It took us about 4 hours to do this...

import java.awt.Point;
import java.util.ArrayList;


public class Board {

	int[][] squares;
	Point start;
	Point current;
	int tries;
	int failed;

	/**Make a new Board
	 * 
	 * @param boardSize the size of the board
	 * @param start The point at which the knight starts out at
	 * @param start_num The number to start counting moves from
	 */
	public Board(int boardSize, Point start, int start_num){
		this.start = start;
		//current = new Point(0,0);
		current = new Point(start);
		
		squares = new int[boardSize][boardSize];
		squares[start.x][start.y] = start_num;
		tries = 0;
		failed = 0;
	}

	/**Gets all the possible moves for a specified point on the current board
	 * Brute force!
	 * 
	 * @param current The point at which we want to get the moves from
	 * @param squares The board of points which has valid and invalid moves
	 * @return an array of Points(which are all valid moves)
	 */
	public Point[] getPossibleMoves(Point current, int[][] squares){
		ArrayList<Point> theReturn = new ArrayList<Point>();
		if(current.x - 2 >= 0){
			if(current.y - 1 >= 0){
				if(squares[current.x-2][current.y-1] == 0){
					theReturn.add(new Point(current.x-2,current.y-1));
				}
			}
			if(current.y + 1 < squares.length){
				if(squares[current.x-2][current.y+1] == 0){
					theReturn.add(new Point(current.x-2,current.y+1));
				}
			}
		}

		if(current.x - 1 >= 0){
			if(current.y - 2 >= 0){
				if(squares[current.x-1][current.y-2] == 0){
					theReturn.add(new Point(current.x-1,current.y-2));
				}
			}
			if(current.y + 2 < squares.length){
				if(squares[current.x-1][current.y+2] == 0){
					theReturn.add(new Point(current.x-1,current.y+2));
				}
			}
		}

		if(current.x + 2 < squares.length){
			if(current.y - 1 >= 0){
				if(squares[current.x+2][current.y-1] == 0){
					theReturn.add(new Point(current.x+2,current.y-1));
				}
			}
			if(current.y + 1 < squares.length){
				if(squares[current.x+2][current.y+1] == 0){
					theReturn.add(new Point(current.x+2,current.y+1));
				}
			}
		}

		if(current.x + 1 < squares.length){
			if(current.y - 2 >= 0){
				if(squares[current.x+1][current.y-2] == 0){
					theReturn.add(new Point(current.x+1,current.y-2));
				}
			}
			if(current.y + 2 < squares.length){
				if(squares[current.x+1][current.y+2] == 0){
					theReturn.add(new Point(current.x+1,current.y+2));
				}
			}
		}


		Point[] ret = new Point[theReturn.size()];
		for( int x = 0; x < theReturn.size(); x++){
			ret[x] = theReturn.get(x);
		}		
		return ret;
	}

	/**A string representation of the board.  All numbers are two digits
	 * to make printing easy.
	 * 
	 */
	public String toString(){
		String str = "";
		for( int x = 0; x < squares.length; x++){
			for( int y = 0; y < squares.length; y++){
				//String output = squares[x][y] ? "O" : "X";
				int val = squares[x][y];
				String out;
				if( val < 10 ){
					out = "0" + val;
				}else{
					out = val+"";
				}
				str = str +" " +out + " ";
			}
			str = str + "\n";
		}
		return str;
	}
	
	@Deprecated
	public void walk(){		
		boolean done = false;
		int ctr = 2;
		while(!done){
			System.out.println("Board : \n" + this);
			
			Point[] moves = getPossibleMoves(new Point(current), squares);
			
			if(moves.length == 0 )
				done = true;
			else{
				squares[moves[ctr%moves.length].x][moves[ctr%moves.length].y] = ctr;
				current = moves[ctr%moves.length];
			}
			ctr++;
		}
		
	}
	
	/**Begin the recursive walk
	 * 
	 */
	public void walkAll(){
		squares = recursiveWalk(squares, current,  squares[start.x][start.y] + 1);
		System.out.println(this);
	}
	
	/**Walk along the path of all possible moves
	 * 
	 * @param tempSquares The temporary board
	 * @param tempCurrent The temporary point
	 * @param ctr What number we are currently on in the numbering scheme
	 * @return null if there is no solution, else the new board with the next 
	 * 			move filled in
	 */
	public int[][] recursiveWalk(int[][] tempSquares, Point tempCurrent, int ctr)
	{
		int[][] ret = null;
		Point[] moves = getPossibleMoves(tempCurrent, tempSquares);
		
		for (int i = 0; i < moves.length; i++){
			//for every possible move, go thru and see if we can reach an
			//ending situation
			Point newTempCurrent = new Point(moves[i]);
			int[][] newTempSquares = new int[squares.length][squares.length];
			for (int j=0; j < squares.length; j++)
			{
				for (int k = 0; k < squares.length; k++)
				{
					newTempSquares[j][k] = tempSquares[j][k];
				}
			}
			newTempSquares[moves[i].x][moves[i].y] = ctr;
			int[][] tempRet = recursiveWalk(newTempSquares, newTempCurrent, ctr+1);
			if (tempRet != null)
			{				
				ret = tempRet;
				break;
			}
			
		}
		
		if (moves.length == 0)
		{
			//if there are no moves left, we want to see if there are any
			//spaces that we have not visited.  if there are, that solution
			//is not good.
			for (int i = 0; i < squares.length; i++)
			{
				for ( int j = 0; j < squares.length; j++)
				{
					if (tempSquares[i][j] == 0)
					{
						if(tries % 1000000 == 0){
							System.out.println("Failed try " + tries);
						}
						tries ++;
						return null;
					}
				}
			}
			
			//check to see if the last move that we made will allow us to
			//go back to our original position
			Point[] endMoves = getPossibleMoves(start,squares);
			boolean successFlag = false;
			for( int r = 0; r < endMoves.length; r++){
				if(endMoves[r].equals(tempCurrent)){
					successFlag = true;
				}
			}
			if(!successFlag){
				if( failed % 100 == 0){
					System.out.println("Failed fail " + failed);
				}
				failed++;
				return null;
			}
			
			ret = tempSquares; 
		}
		return ret;
	}

	/**Run
	 * 
	 * @param args
	 */
	public static void main(String[] args) {		
		Board b = new Board(6, new Point(1,2),1);
		b.walkAll();
		System.out.println("Done");
	}
}

It's rather slow, unfortunately.

2009-08-12 Reply Admin

Python version, I'm only printing the board in its final state. Pretty fast too.

def knight(m, n):
        rep = ''
        for i in range(m+1): rep += '- '
        rep += '-\n'
        for i in range(m):
            rep += '| '
            for j in range(n):
                rep += 'X '
            rep += '|\n'
        for i in range(m+1): rep += '- '
        rep += '-\n'
        print rep
if __name__ == "__main__":
    print "m =",
    m = int(raw_input())
    print "n =",
    n = int(raw_input())
    knight(m, n)

2009-08-12 Reply Admin

I believe you can do it in a 1x4 like so:

ABCD | BDAC

Smash King · 2009-08-12 Reply Admin

Prophet:
@AlpineR
Skipping the trivial case (one piece, one color), the smallest, simplest mosaic is a 1x5 set with all different colors.

ABCDE | ECADB

Prophet, I believe this may qualify as a shorter answer:

ABCD | CADB

But I agree with your other answers.

2009-08-12 Reply Admin

Another Java implementation of Warnsdorff's algorithm:

import java.util.ArrayList;
import java.util.List;

public class ChessBoard {

	private Cell[][] cells;
	private int size;

	public ChessBoard(int size) {
		this.size = size;
		cells = new Cell[size][size];

		char firstLetter = 'a';
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				cells[i][j] = new Cell(String.valueOf((char)(firstLetter + i)) + (j + 1));
			}
		}

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				List<Cell> possibleMoves = getPossibleMovesForCell(i, j);
				cells[i][j].setMoves(possibleMoves);
			}
		}
	}
	
	public static void main(String[] args) {
		ChessBoard board = new ChessBoard(5);
		board.findPath(2, 2);
	}
	
	public void findPath(int startX, int startY) {
		Cell currentCell = cells[startX][startY];
		
		currentCell.visit();
		while (currentCell.canMove()) {
			currentCell = currentCell.getNextMove();
			currentCell.visit();
		}
	}

	private List<Cell> getPossibleMovesForCell(int xPos, int yPos) {

		List<Cell> moves = new ArrayList<Cell>();

		int leftXCoord = xPos - 2;
		if (leftXCoord >= 0) {
			if (yPos - 1 >= 0) {
				moves.add(cells[leftXCoord][yPos - 1]);
			}
			if (yPos + 1 < size) {
				moves.add(cells[leftXCoord][yPos + 1]);
			}
		}

		int rightXCoord = xPos + 2;
		if (rightXCoord < size) {
			if (yPos - 1 >= 0) {
				moves.add(cells[rightXCoord][yPos - 1]);
			}
			if (yPos + 1 < size) {
				moves.add(cells[rightXCoord][yPos + 1]);
			}
		}

		int downYCoord = yPos - 2;
		if (downYCoord >= 0) {
			if (xPos - 1 >= 0) {
				moves.add(cells[xPos - 1][downYCoord]);
			}
			if (xPos + 1 < size) {
				moves.add(cells[xPos + 1][downYCoord]);
			}
		}

		int upYCoord = yPos + 2;
		if (upYCoord < size) {
			if (xPos - 1 >= 0) {
				moves.add(cells[xPos - 1][upYCoord]);
			}
			if (xPos + 1 < size) {
				moves.add(cells[xPos + 1][upYCoord]);
			}
		}

		return moves;
	}

}

import java.util.List;


public class Cell {

	private String name;
	private List<Cell> neighbours;
	private boolean visited;

	public Cell(String name) {
		this.name = name;
		this.visited = false;
	}

	public void setMoves(List<Cell> possibleMoves) {
		this.neighbours = possibleMoves;
	}

	public void visit() {
		this.visited = true;
		System.out.println(name);
	}

	public boolean canMove() {
		return getMovesLeft() > 0;
	}

	public int getMovesLeft() {
		int unvisitedNeighbours = 0;
		for (Cell neighbour : neighbours) {
			if (!neighbour.visited()) {
				unvisitedNeighbours++;
			}
		}
		return unvisitedNeighbours;
	}

	private boolean visited() {
		return visited;
	}

	public Cell getNextMove() {
		Cell nextMove = null;

		for (Cell possibleMove : neighbours) {
			if (!possibleMove.visited()) {
				if (nextMove == null || possibleMove.getMovesLeft() < nextMove.getMovesLeft()) {
					nextMove = possibleMove;
				}
			}
		}

		return nextMove;
	}

}

amischiefr · 2009-08-12 Reply Admin

Alright, let's flood this bitch with Java implementations!!!

Here's mine with GUI goodness, Warnsdorff's algorithm:

import java.awt.Color;
import java.awt.Container;
import java.awt.GridLayout;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.Random;
import java.util.Stack;

import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.JPanel;

class Move {
	private int x;
	private int y;
	private int count;
	public Move(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public int getX() { return this.x; }
	public int getY() { return this.y; }
	public void setCount(int x) { this.count = x; }
	public int getCount() { return this.count; }
}

public class KnightsTour {

	class ChessBoard extends JFrame implements MouseListener
	{
	    JPanel [][] squares;
	    
	    public ChessBoard(int x, int y) 
	    {
	        Container c = getContentPane();
	        c.setLayout(new GridLayout(8,8, 1 , 1)); 
	        squares = new JPanel[8][8];
	        for(int i=0; i<x; i++)
	        {
	            for(int j=0; j<y; j++)
	            {
	                squares[i][j] = new JPanel();
	                if((i+j)%2 == 0)
	                    squares[i][j].setBackground(Color.white);
	                else
	                    squares[i][j].setBackground(Color.black);
	                squares[i][j].addMouseListener(this);
	                c.add(squares[i][j]);
	            }
	        }
	    }
	    
	    public void placeMove(int x, int y) {
	    	squares[x][y].setBackground(Color.orange);
	    }
	    
	    public void mouseClicked(MouseEvent e){ } 
	    public void mouseEntered(MouseEvent e){ } 
	    public void mouseExited(MouseEvent e) { } 
	    public void mousePressed(MouseEvent e) { } 
	    public void mouseReleased(MouseEvent e) { } 
	}
	    
	private ChessBoard chessBoard = null;
	private final Random r = new Random();
	private int board[][] = null;
	private int curX;
	private int curY;
	private int currentMove = 1;
	private int finishedMoves;
	private int tries = 0;
	private Stack<Move> moves = new Stack<Move>();
	private int xStart;
	private int yStart;
	private int[][] mods = { {2,1} , {1,2} , {-1,2} , {-2,1} , {-2,-1} , {-1,-2} , {1,-2} , {2,-1} };
	
	private boolean isValidMove(Move m) {
		try {
			int val = board[m.getX()][m.getY()];
			if(val == 0) return true;
		} catch (ArrayIndexOutOfBoundsException e) {
			return false;
		}
		return false;
	}
	
	private void setUpBoard(int x, int y) {
		board = new int[x][y];
		for(int i = 0; i < board.length;i++) {
			for(int j = 0 ; j < board[0].length ; j++) {
				board[i][j] = 0;
			}
		}		
	}
	
	private void setValidStart(int x, int y) {
		xStart = r.nextInt(board.length);
		yStart = r.nextInt(board[0].length);
//		if(xStart%2 == 0 && yStart%2==0)
//			setValidStart(x,y);
//		if((yStart==4 || yStart==6 || yStart==8) && xStart==3)
//			setValidStart(x,y);
	}
	
	private void start(int x, int y) {
		chessBoard = new ChessBoard(x,y);
        chessBoard.setSize(300,300);
        chessBoard.setResizable(false);
        chessBoard.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        chessBoard.setVisible(true);
		
		currentMove = 1;
		setUpBoard(x,y);
		finishedMoves = x*y;
		
		setValidStart(x,y);
		
		curX = xStart;
		curY = yStart;
		board[xStart][yStart] = currentMove++;
		chessBoard.placeMove(xStart, yStart);
		
		runSimulation();
		if(this.currentMove==this.finishedMoves)
			printBoard("Success");
		else if(this.tries >= 100)
			printBoard("Failure at 100 tries");
		else
			start(x,y);
	}
	
	private void runSimulation() {
		while(currentMove < finishedMoves) {
			Move m = getMove();

			if(m == null)
				break;
			
			board[m.getX()][m.getY()] = currentMove++;
			curX = m.getX();
			curY = m.getY();
			chessBoard.placeMove(curX, curY);
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		board[this.curX][this.curY] = currentMove;
		chessBoard.placeMove(curX, curY);
		this.tries++;
	}
	
	private Move getMove() {
		Move m = null;
		Move ret = null;
		this.moves = getMoves(this.curX, this.curY);
		Stack<Move> temp = null;
		while(!moves.isEmpty()) {
			m = this.moves.pop();
			temp = getMoves(m.getX(),m.getY());
			if(ret == null) {
				ret = m;
				ret.setCount(temp.size());
			}
			else {
				if(ret.getCount() > temp.size()) {
					ret = m;
					ret.setCount(temp.size());
				}
			}
		}
		return ret;
	}
	
	private Stack<Move> getMoves(int x, int y) {
		Stack<Move> temp = new Stack<Move>();
		for(int i = 0; i < mods.length;i++) {
			for(int j = 0 ; j < mods[0].length ; j++) {
				Move m = new Move(mods[i][j++] + x,mods[i][j] + y);
				if(isValidMove(m)) {
					temp.push(m);
				}
			}
		}
		return temp;
	}
	
	private void printBoard(String str) {
		System.out.println("\n**************** Board "+str+" ****************\n");
		for(int i = 0; i < board.length;i++) {
			for(int j = 0 ; j < board[0].length ; j++) {
				if(board[i][j] < 10)
					System.out.print(board[i][j] + "  ");
				else
					System.out.print(board[i][j] + " ");
			}
			System.out.println();
		}	
		System.out.println("\n***************** Moves = " + this.currentMove + ", in " + this.tries + " tries *****************\n");
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		KnightsTour kt = new KnightsTour();
		kt.start(8,8);
		

	}

}

2009-08-12 Reply Admin

razvan:
Python version, I'm only printing the board in its final state. Pretty fast too.

It's certainly fast.

The case where m=1000 and n=1000 is quite amusing.

The case where m=3 and n=2 is also quite amusing.

My favourite is m=1 and n=1, which just about gets it right...

Apart from ignoring the rubric.

Can't we just leave this sort of thing for lab classes in CS201, and get back to something inventive, like Mandatory Fun Day?

2009-08-12 Reply Admin

Why not just start with a full board and connect ALL the tiles together with knight's moves? Then recursively try removing connections until each tile only has two such connections coming out of it; just have an algorithm to detect if all 64 knights are still connected at each removal.

2009-08-12 Reply Admin

Where can we submit our own problems for possible inclusion in Programming Praxis?

2009-08-12 Reply Admin

Buddy:
Where can we submit our own problems for possible inclusion in Programming Praxis?

There's a link at the bottom of the article: "Got a tip for a future Programming Praxis? Please send it on in!"

2009-08-12 Reply Admin

Interesting, but wouldn't it would be too expensive to test for the connectedness?

2009-08-12 Reply Admin

Yet another java implementation of the Warnsdorff's algorithm:

public class Board {

    boolean[][] board;
    int[][] moves;
    static final int[][] possibleMovements={{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};

    public static void main(String[] args){
        new Board().exec(15,15,0,0);
    }

    public void exec(int sizeX, int sizeY, int x, int y){
        board=new boolean[sizeX][sizeY];
        moves=new int[sizeX*sizeY][2];

        board[x][y]=true;
        moves[0][0]=x;
        moves[0][1]=y;
        
        knight(sizeX,sizeY,x,y);
        for(int i=moves.length-1;i>=0;i--){
            System.out.println("("+moves[i][0]+","+moves[i][1]+")");
        }
    }

    public void knight(int sizeX, int sizeY, int x, int y){
        for(int i=1;i<sizeX*sizeY;i++){
            int[] move=getBestMovement(board, x, y);
            moves[i]=move;
            x=move[0];
            y=move[1];
            board[x][y]=true;
        }
    }

    public int[] getBestMovement(boolean[][] board,int x, int y){
        int minimum=10000;
        int retorno=0;
        for(int i=0;i<possibleMovements.length;i++){
            int tx=x+possibleMovements[i][0];
            int ty=y+possibleMovements[i][1];

            if(tx>=0 && tx<board.length && ty>=0 && ty<board[0].length && board[tx][ty]==false){
                int temp=possibleMovements(board,tx,ty);
                if(temp<minimum){
                    minimum=temp;
                    retorno=i;
                }
            }
        }
        return new int[]{x+possibleMovements[retorno][0],y+possibleMovements[retorno][1]};
    }

    public int possibleMovements(boolean[][] board, int x, int y){
        int k=0;
        for(int i=0;i<possibleMovements.length;i++){
            int tx=x+possibleMovements[i][0];
            int ty=y+possibleMovements[i][1];
            if(tx>=0 && tx<board.length && ty>=0 && ty<board[0].length && board[tx][ty]==false)
              k++;
        }
        return k;
    }
}
</pre>

ParkinT · 2009-08-12 Reply Admin

Anonymous:
In pseudocode it would be something like:
-- snipped Knight's tour - In Pseudocode from Wikipedia --

So this Python code should do the trick:

-- snipped Knight's tour - In Python also from Wikipedia --

Unfortunately, this praxis suffers from the same problem as all the rest - these are extremely well known problems that have been solved a thousand times before. Please, make up something unique or modify an existing problem enough to make us break into a sweat.

I prefer The Monty Python Knight's Tour I fart in your general direction. Now go away or I shall taunt you another time!.

2009-08-12 Reply Admin

Probably a hundred people already posted this solution, but here it is in all of its glory!

public class knight
{
	public static void main(String[] args) throws Exception{
		int boardWidth=Integer.parseInt(args[0]);
		int boardHeight=Integer.parseInt(args[1]);
		int startX=Integer.parseInt(args[2]);
		int startY=Integer.parseInt(args[3]);

		int[][] solution=solvePuzzle(boardWidth,boardHeight,startX,startY);

		printBoard(solution);
	}

	public static int[][] solvePuzzle(int boardWidth, int boardHeight, int startX, int startY) throws Exception{
		int[][] board=new int[boardWidth][boardHeight];

		if(move(board,1,startX,startY)){
			return board;
		}else{
			throw new Exception("IMPOSSIBLE!!!");
		}
	}

	public static boolean move(int[][] board, int moveNumber, int x, int y){
		if(x>board.length-1 || x<0 || y>board[0].length-1 || y<0)return false;  // out of bounds

		if(moveNumber==(board.length*board[0].length)+1){
			// last move
			if(board[x][y]==1){
				// back to square 1
				return true;
			}
		}

		if(board[x][y]>0) return false;  // square already visited

		board[x][y]=moveNumber;

		if(	move(board,moveNumber+1,x+1,y+2)
			|| move(board,moveNumber+1,x+1,y-2)
			|| move(board,moveNumber+1,x+2,y+1)
			|| move(board,moveNumber+1,x+2,y-1)
			|| move(board,moveNumber+1,x-1,y+2)
			|| move(board,moveNumber+1,x-1,y-2)
			|| move(board,moveNumber+1,x-2,y+1)
			|| move(board,moveNumber+1,x-2,y-1)){

			return true;
		}else{
			board[x][y]=0;
			return false;
		}
	}

	public static void printBoard(int[][] board){
		String divider="";

		for(int i=0;i<board.length*3+1;i++){
			divider+="-";
		}

		System.out.println(divider);

		for(int i=0;i<board.length;i++){
			System.out.print("|");

			for(int j=0;j<board[i].length;j++){
				System.out.print(board[i][j]);
				if(board[i][j]<10) System.out.print(" ");
				System.out.print("|");
			}

			System.out.println("\n"+divider);
		}
	}
}
</pre>

Smash King · 2009-08-12 Reply Admin

Anonymous:
Unfortunately, this praxis suffers from the same problem as all the rest - these are extremely well known problems that have been solved a thousand times before. Please, make up something unique or modify an existing problem enough to make us break into a sweat.

http://en.wikipedia.org/wiki/Unsolved_problems_in_mathematics

If you want something that hasn't been beaten to exhaustion, feel free to pick any of those.

2009-08-12 Reply Admin

JL:
Buddy:
Where can we submit our own problems for possible inclusion in Programming Praxis?
There's a link at the bottom of the article: "Got a tip for a future Programming Praxis? Please send it on in!"

I feel pretty stupid.

Technical Thug · 2009-08-12 Reply Admin

Alex Papadimoulis:
Or, you could just whine. That's easier than coding, anyway!

I've had some coworkers who took whining as an art and tried to do it as artfully and continuously as possible.

2009-08-12 Reply Admin

Confused:
justsomedude:
using twinview with 2 + a third monitor leads to all sorts of crappy behavior
That's what you get for trying to stuff 3 pounds of monitor into a 2 pound bag...

In all fairness, that is exactly the solution propoted by Nvidia: Twinview up 2 of them, then xinerama up the twins w/ a third. Performs about as good as I'd imagine vista+areo would on a PII. I hear the problem is located in the driver's RandR functions.

xserver-xgl works flawlessly, it's just not available as a deb for ubuntu past hardy. I read it was deprecated because current version X is supposed to support this behavior natively, but in my experience the native X support for multiple monitors goes to crap once you involve more than 1 video card (I loose all hardware acceleration capacity). It may be a configuration issue, but the people on Compiz/beryl, X, and Ubuntu IRC channels have not been able to locate it.

2009-08-12 Reply Admin

No Haskell yet? Well, here goes, bugs and all:

module Main where

import Data.List (delete, intersect)

board w h = [(x, y) | x <- [1..w], y <- [1..h]] movesFrom = zipWith hop [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)] . repeat where (a, b) hop (c, d) = (a+c, b+d) tours' us s = movesFrom s intersect us >>= (\m -> map (m:) $ tours' (delete m us) m) tours w h s = filter ((==) s . last) (tours' (board w h) s) main = print $ head $ tours 6 6 (1, 1)

It worked before I "optimized" it, really!

2009-08-12 Reply Admin

Bim Job:
Ken B:
I have discovered a truly marvelous 1-line APL solution of this, which this comment is too narrow to contain.
WINNER!

Thanks. I aim to please.

But I got a bone to pick with you, matey, so I has. Yer not bustin' yer boots hard enough. Yer needs a new fermat, so yer does ... arrrrr!
And to all those of you who think that well-known problems in simple math are a suitable excuse for an irritating spew-fest of hastily-constructed implementations (forgiving those who post in Haskell, OCamL, Befunge or Whitespace):

Talk to the parrot, 'cause the hook ain't listening.

Aarg! I tried getting my computer to help by typing "fermat c: /y", but it didn't seem to do anything.

Q: How does a pirate pass parameters to a C program? A: With "arrrrgv" and "arrrrgc".

2009-08-12 Reply Admin

I'm doin' it the hard way :p

mythtv@server:~$ ./knight 6 6 0 0
Doing 6x6 board, starting at (0,0)
00 09 26 07 34 15 
25 06 35 16 27 32 
10 01 08 33 14 17 
05 24 03 20 31 28 
02 11 22 29 18 13 
23 04 19 12 21 30

mythtv@server:~$ cat knight.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int* board;
int highest = 0;
int sizex, sizey;
int startx, starty;

void print_board()
{
    int i, j;
    for(i = 0; i < sizex; i++)
    {
        for(j = 0; j < sizey; j++)
        {
            printf("%02u ", board[i*sizex + j]);
        }
        printf("\n");
    }
}

int try_move(int x, int y, int level)
{
    if (level > highest)
    {
        //printf("Filled %d...\n", level);
        highest = level;
    }
    if (level == (sizex * sizey))
    {
        if ((x == startx) && (y == starty))
        {    
            print_board();
            return 1; /* complete! */
        }
        else
        {
            return 0;
        }
    }

    if ((x < sizex) && (y < sizey) && (x >= 0) && (y >= 0))
    {
        if (board[x * sizex + y] == -1)
        {
            board[x * sizex + y] = level;
            if (try_move(x+2, y-1, level+1)) return 1;
            if (try_move(x+2, y+1, level+1)) return 1;
            if (try_move(x-2, y-1, level+1)) return 1;
            if (try_move(x-2, y+1, level+1)) return 1;
            if (try_move(x-1, y-2, level+1)) return 1;
            if (try_move(x-1, y+2, level+1)) return 1;
            if (try_move(x+1, y-2, level+1)) return 1;
            if (try_move(x+1, y+2, level+1)) return 1;
            board[x * sizex + y] = -1;
        }
    }

    return 0;
}

int main(int argc, char** argv)
{    
    if (argc != 5)
    {
        printf("%s x-max y-max x-start y-start\n", argv[0]);
        return 0;
    }

    sizex = atoi(argv[1]);
    sizey = atoi(argv[2]);

    board = malloc(sizeof(int) * sizex * sizey);
    memset(board, -1, sizeof(int) * sizex * sizey);

    startx = atoi(argv[3]);
    starty = atoi(argv[4]);

    printf("Doing %dx%d board, starting at (%d,%d)\n", sizex, sizey, startx, starty);

    try_move(atoi(argv[3]), atoi(argv[4]), 0);

    free(board);
    board = NULL;

    return 1;
}

BradC · 2009-08-12 Reply Admin

Brute force using (everyone's favorite...) Excel VBA!! :)

Just paste the following into a new Excel Module, then call the function from the immediate window (Ctrl-G to show the immediate window) like "KnightTour 6,1,1"

Not recommended for boards larger than 8 :)

Sub KnightTour(BoardSize As Integer, StartRow As Integer, StartCol As Integer)
    SetupBoard BoardSize
    Cells(StartRow, StartCol).Select
    Application.ScreenUpdating = False
    
    'declare array that will hold sequence of steps
    Dim steps() As Range, direction() As Integer
    ReDim steps(BoardSize * BoardSize), direction(BoardSize * BoardSize)
    Set steps(1) = ActiveCell
    ActiveCell.Value = 1
    
    Dim depth As Integer
    depth = 1
    
    Dim NextCell As Range
    Do
        direction(depth) = direction(depth) + 1
        If direction(depth) > 8 Then 'Back up a level
            direction(depth) = 0
            steps(depth).ClearContents
            depth = depth - 1
            If depth = 0 Then Exit Do
        Else 'get next cell
            Set NextCell = GetNextCell(steps(depth), direction(depth), BoardSize)
            If Not NextCell Is Nothing Then 'lock in, go to next level
                depth = depth + 1
                Set steps(depth) = NextCell
                NextCell.Value = depth
            End If
        End If
    Loop Until depth = 0 Or depth = BoardSize * BoardSize
          
    Application.ScreenUpdating = True
    If depth = 0 Then
        MsgBox "No Solution!"
    Else
        MsgBox "Solved!"
    End If
End Sub

Function GetNextCell(CurrentCell As Range, direction As Integer, BoardSize As Integer) As Range
    'Finds and validates next candidate coordinates
    Dim NewRow As Integer, NewCol As Integer
    Select Case direction
    Case 1: NewRow = CurrentCell.Row - 2: NewCol = CurrentCell.Column + 1
    Case 2: NewRow = CurrentCell.Row - 1: NewCol = CurrentCell.Column + 2
    Case 3: NewRow = CurrentCell.Row + 1: NewCol = CurrentCell.Column + 2
    Case 4: NewRow = CurrentCell.Row + 2: NewCol = CurrentCell.Column + 1
    Case 5: NewRow = CurrentCell.Row + 2: NewCol = CurrentCell.Column - 1
    Case 6: NewRow = CurrentCell.Row + 1: NewCol = CurrentCell.Column - 2
    Case 7: NewRow = CurrentCell.Row - 1: NewCol = CurrentCell.Column - 2
    Case 8: NewRow = CurrentCell.Row - 2: NewCol = CurrentCell.Column - 1
    End Select
    
    If NewRow > 0 And NewRow <= BoardSize And NewCol > 0 And NewCol <= BoardSize Then
        Set GetNextCell = Cells(NewRow, NewCol)
        If GetNextCell.Value > 0 Then
            Set GetNextCell = Nothing
        End If
    End If
End Function

Sub SetupBoard(BoardSize As Integer)
    'Clear and reset the board
    Application.ReferenceStyle = xlR1C1
    ActiveSheet.Cells.Clear
    ActiveSheet.Columns.ColumnWidth = 0
    ActiveSheet.Columns.RowHeight = 0
    
    'set it up with the new dimensions
    Dim i As Integer, j As Integer
    For i = 1 To BoardSize
        ActiveSheet.Rows(i).RowHeight = 27
        ActiveSheet.Columns(i).ColumnWidth = 5
        For j = 1 To BoardSize
            If (i + j) / 2 = (i + j) \ 2 Then
                Cells(i, j).Interior.ColorIndex = 36    'yellow
            Else
                Cells(i, j).Interior.ColorIndex = 37    'blue
            End If
        Next j
    Next i
End Sub

2009-08-12 Reply Admin

BradC:
Brute force using (everyone's favorite...) Excel VBA!! :) ...Snip...

fyi - VBA converts all Integers to Longs, might as well just declare them as type Long to save a few milliseconds.

2009-08-12 Reply Admin

curtmack:
.... almost as disappointing as when you get your PB&J sandwich and the peanut butter is on top of the jelly ....

mate, its a sandwich. Both are between the pieces of bread. If the 'jelly' is on top, you have it upside down.

2009-08-12 Reply Admin

Thanks for providing a more interesting praxis.

Here's a Python 3 solution. You can port it to Python 2 by replacing the word "as" with a comma. This handles a 1516 board in a few seconds:

def tour(w,h,closed=True):
assert w >= 4 and h >= 4
assert w % 2 == 0 or h % 2 == 0 or not closed
class S(Exception): pass # thrown if tour found
try:
d = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)] # deltas
a = [[sum(1 for dy, dx in d if 0 <= y+dy < h and 0 <= x+dx < w)
for x in range(w)] for y in range(h)] # accessibility
def r(g, a, x, y, n): # recursive search
g = [row[:] for row in g] # deep-copy grid
a = [row[:] for row in a] # deep-copy access
g[y][x] = n
a[y][x] = 99999
if n == wh and not closed: raise S(g)
ds = []
# for each delta, decrement the accessibility of the target square
# and add the accessibility and coordinates to "ds".
for dy, dx in d:
ny, nx = y+dy, x+dx
if 0 <= ny < h and 0 <= nx < w:
if n == w*h and closed and g[ny][nx] == 1: raise S(g)
if g[ny][nx] == 0:
a[ny][nx] -= 1
ds.append((a[ny][nx], ny, nx))
# for each delta (sorted on accessibility), recurse
for _, ny, nx in sorted(ds): r(g, a, nx, ny, n+1)
r([[0]*w]h, a, w//2, h//2, 1) # start in middle
except S as s:
colw = len(str(wh)) + 1
for row in s.args[0]:
print(('%'+str(colw)+'i')*w%tuple(row))
else:
raise Exception('No tour found.')

AlpineR · 2009-08-12 Reply Admin

Prophet:
@AlpineR
Skipping the trivial case (one piece, one color), the smallest, simplest mosaic is a 1x5 set with all different colors.

ABCDE | ECADB

For a square set, you can achieve it with a 3x3 square assuming "touching" does not include corners

ABC | BGF DEF | IEA GHI | DCH

Fewest colors? 4, as in this 1x5 case:

ABCDD | DBDAC

And I believe the above is the smallest pair using the fewest colors (again, skipping the trivial case).

Thanks for the response. Unfortunately, I forgot one key rule: consider any piece on an outer edge to be in contact with all other pieces on an outer edge at the same time. So if A and B are on outer edges in the first mosaic, neither A nor B can be on an outer edge in the second mosaic nor can they touch each other in the second mosaic.

2009-08-12 Reply Admin

For anyone bitching about this being an already solved problem, I'd hate to know how the hell you got through high school, where most classes involved solving already solved problems.

As for the "re-inventing the wheel" argument, that's bullshit. If it wasn't, we'd have stone wheels on our cars. And if that were the case, you'd be bitching about your fuel consumption.

And if there's any other whiny little bitch out there who wants Alex to come up with "something original", who is still reading this post and whom I haven't offended yet, then go and program something that does the Knight's Tour on a three-dimensional board. Or on a 3D chess set.

lolwtf · 2009-08-12 Reply Admin

Code Dependent:
Anonymous:
Unfortunately, this praxis suffers from the same problem as all the rest - these are extremely well known problems that have been solved a thousand times before. Please, make up something unique or modify an existing problem enough to make us break into a sweat.
Okay, here's your new, unique Praxis:
Make up something unique or modify an existing problem enough to make us break into a sweat.

Find me a girlfriend. Good luck.

Paddles · 2009-08-12 Reply Admin

Anon:
1. Train MIDGET on knights tour 2. Insert MIDGET into TURK 3. Run Knights Tour on TURK
Infinitely programmable, within reason...

As soon as I saw this, I thought of:

Find Turkish chess grandmaster
Find Neural Network implementation in Perl
????
PROFIT!

2009-08-12 Reply Admin

All of those whiners have been rebuked and have left already. Maybe you should try not to whine so much yourself.

I had a go at the 3D tour and it seems about the same as the 2D one. I tried out 1x1x2 jumps at first but couldn't find any tours for any small boards. This code assumes 0x1x2 jumps:

def tour3d(w,h,d,closed=True):
assert w % 2 == 0 or h % 2 == 0 or d % 2 == 0 or not closed
class S(Exception): pass # thrown if tour found
try:
deltas = [(0,1,2),(0,1,-2),(0,-1,2),(0,-1,-2),
(0,2,1),(0,2,-1),(0,-2,1),(0,-2,-1),
(1,0,2),(1,0,-2),(-1,0,2),(-1,0,-2),
(1,2,0),(1,-2,0),(-1,2,0),(-1,-2,0),
(2,0,1),(2,0,-1),(-2,0,1),(-2,0,-1),
(2,1,0),(2,-1,0),(-2,1,0),(-2,-1,0)]
a = [[[sum(1 for dz, dy, dx in deltas
if 0 <= z+dz < d and 0 <= y+dy < h and 0 <= x+dx < w)
for x in range(w)] for y in range(h)] for z in range(d)]
def r(g, a, x, y, z, n): # recursive search
g = [[row[:] for row in board] for board in g] # deep-copy grid
a = [[row[:] for row in board] for board in a] # deep-copy access
g[z][y][x] = n
a[z][y][x] = 99999
if n == whd and not closed: raise S(g)
ds = []
# for each delta, decrement the accessibility of the target cube
# and add the accessibility and coordinates to "ds".
for dz, dy, dx in deltas:
nz, ny, nx = z+dz, y+dy, x+dx
if 0 <= nz < d and 0 <= ny < h and 0 <= nx < w:
if n == whd and closed and g[nz][ny][nx] == 1: raise S(g)
if g[nz][ny][nx] == 0:
a[nz][ny][nx] -= 1
ds.append((a[nz][ny][nx], nz, ny, nx))
# for each delta (sorted on accessibility), recurse
for _, nz, ny, nx in sorted(ds): r(g, a, nx, ny, nz, n+1)
r([[[0]*w]h]d, a, w//2, h//2, d//2, 1) # start in middle
except S as s:
colw = len(str(whd)) + 1
for zindex, board in enumerate(s.args[0]):
print('z-index:', zindex)
for row in board:
print(('%'+str(colw)+'i')*w%tuple(row))
print()
else:
raise Exception('No tour found.')

2009-08-12 Reply Admin

Anonymous:
Unfortunately, this praxis suffers from the same problem as all the rest - these are extremely well known problems that have been solved a thousand times before. Please, make up something unique or modify an existing problem enough to make us break into a sweat.

This website is about WTF. Programming Praxis is supposed to be easy. The real challenge is coming up with a solution that makes everyone else either think:

a) WTF... b) How the hell did you do that?!

For "b" take a look at the Regex expression which solved one of the previous puzzles. A mathematically true solution using no numbers what so ever. Brilliant.

2009-08-12 Reply Admin

Q: How does a pirate pass parameters to a C program? A: With "arrrrgv" and "arrrrgc".

Which inevitably leads to:

Q: Why did the Fortran main routine and subroutine have so many arguments?

A: Because they had nothing in COMMON.

2009-08-12 Reply Admin

Kev B:
Anonymous:
Alex Papadimoulis:
Anonymous:
In pseudocode it would be something like: -- snip wikipedia copy/paste --
Unfortunately, this praxis suffers from the same problem as all the rest - these are extremely well known problems that have been solved a thousand times before. Please, make up something unique or modify an existing problem enough to make us break into a sweat.

I dont't think you can keep spitting out this reinventing the wheel argument. The fact is these a programming challenges, not meant to fit into robust or scalable apis. They are meant to be a bit of fun. And I think they would be fun to anyone who didn't just straight away head to google for the answer. Try figure it out, and remember the solutions to these problems aren't going to make it into any enterprise applications, so you shouldn't worry too much about your programming design principles.

Suggestions are always welcome. But keep in mind... I don't think the goal should be to spend a week solving a crazy-hard puzzle; perhaps a lunch break or a long coffee break... maybe in a language you're not all too familiar with.

In the case of the Knight's Tour... so long as you don't copy/paste the wikipedia solution, it's actually a bit of a challenge.
As per my above post, re-inventing the wheel is not a challenge, it is a waste of time. But also as per my above post, I understand that you can't spend all day working out coding challenges and I'm working on a couple of submissions myself. And for the record, you can't blame me for copying off Wikipedia - after all, where the hell did you get that animated GIF from?!

Reinventing the wheel is NOT a waste of time if you seek to improve it or understand it better. And isn't the point of these coding challenges to understand our craft better through experience?

2009-08-13 Reply Admin

Here is a Knights tour but it doesn't go to the original location.

/******************************************

Program: Knights Tour
Created By: Tyler George
Purpose: To find the knights tour of
a chess board *****************************************/

import java.util.*;

public class KnightTour { private static int iLength = 0; private static int iWidth = 0; private static int iX = 0; private static int iY = 0; //Each knight only has 8 possible moves because of overlap. //Up two over 1 //Down two over 1 //Right two up/down 1 //Left two up/down 1 private static int moves[] = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};

//Main Program
public static void main(String args[]){
	//Get the user input
	Scanner input = new Scanner(System.in);
	System.out.println("Please enter the length.");
	iLength = input.nextInt();
	System.out.println("Please enter the width.");
	iWidth = input.nextInt();
	System.out.println("Please enter the start X");
	iX = input.nextInt()-1;
	System.out.println("Please enter the start Y");
	iY = input.nextInt()-1;
	//Create a temp array
	int temparray[][] = new int[iLength][iWidth];
	System.out.println("Starting Calculations!");
	//Knights tour
	KnightMove(temparray,iX,iY,1);
	//Done
	System.out.println("Done-Not result with current starting point!");
}

public static void KnightMove(int board[][], int currentX, int currentY,int iMoves){
	//Visit spot
	board[currentX][currentY] = iMoves;
	//Print the updated board.
	//printBoard(board);
	//Check to see if this was the last move
	if(iMoves == iLength * iWidth){
		//Tell the user the solution was found
		System.out.println("Solution Found!");
		printBoard(board);
		//Exit
		System.exit(0);
	}
	
	//Step through each possible move of the night
	for(int i = 0; i < moves.length; i++){
		//Get the new x and y Coords
		int tempX = currentX + moves[i][0];
		int tempY = currentY + moves[i][1];
		//System.out.println("Move: " + i );
		//Check if they are valid
		if((tempY > -1 && tempY < iWidth) && (tempX > -1 && tempX < iLength) && (board[tempX][tempY] == 0) ) {
			//Possible Path
			System.out.println("Current X:" + currentX + " Y: " + currentY);
			System.out.println("Possible Path X:" + tempX + " Y: " + tempY);
			//Continue On
			KnightMove(cloneBoard(board),tempX, tempY,iMoves+1);	
		}
		else{
			//System.out.println("Not a path!");
		}
	}
	
	
}
//Method to print the board.
public static void printBoard(int board[][]){
	//Print the board
	for(int i=0; i < iLength; i++){
		for(int j = 0; j < iWidth; j++){
			//Print data
			System.out.print(board[i][j] + " \t");				
		}
		//Create a new line
		System.out.println();
	}
}

//Java is STUPID
public static int[][] cloneBoard(int board[][]){
	int newBoard[][] = new int[iLength][iWidth];
	for(int i = 0; i < iLength; i++){
		for(int j = 0; j < iWidth; j++ ){
			newBoard[i][j] = board[i][j];
		}
	}
	return newBoard;
}

}

lrucker · 2009-08-13 Reply Admin

I wrote this in college in Applesoft Basic. I doubt the disks are still readable, though.

2009-08-13 Reply Admin

skilsmässa:
Visa hänsyn till din partners barn om hon/han har barn sedan tidigare. Finns inget vidrigare en make som behandlar barn illa. http://www.undvika-skilsmassa.se

Hey Alex, this here is spam in poorly written swedish. Granted, its not as bad as the engrish stuff that pops up here. >.<

Anyway, translated into english;

Show respect for your partner's children if she / he already has children. There is nothing more disgusting than a spouse who treats children bad.

Google Translates take: Show respect to your partner's child if she / he has children in the past. No foul a spouse dealing with child maltreatment.

I like the last bit there. :)

2009-08-13 Reply Admin

Ah, well, seeing as no one has done it yet I'll post a shameless copy and paste conversion from the Wikipedia article to C#.

static void Main(string[] args)
        {
            SolveKnightsTour skt = new SolveKnightsTour();
            skt.Solve();
        }

        class SolveKnightsTour
        {
            static int nMoves = 8;
            static int boardSize = 10;
            int[,] moves = new int[8, 2] { {2, 1}, {2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1} };
            int[,] board = new int[boardSize, boardSize];
    
            public void Solve()
            {
                int x = new Random().Next(1, boardSize);
                int y = new Random().Next(1, boardSize);
                int moveNumber = 2;
                board[x, y] = 1;
                int[] move = new int[2];
                for (int i = 2; i < (boardSize * boardSize); i++)
                {
                    move[0] = x;
                    move[1] = y;
                    move = GetNextMoves(move);
                    x = move[0];
                    y = move[1];
                    board[x, y] = moveNumber;
                    moveNumber += 1;
                }
                for (int i = 0; i < boardSize; i++)
    			    for (int j = 0; j < boardSize; j++)
        			    Console.WriteLine(board[i,j]);
            }
            bool InRangeAndEmpty(int x, int y)
            {
                return (x < boardSize && x >= 0 && y < boardSize && y >= 0 && board[x, y] == 0);
            }
            int GetAccessibility(int x, int y)
            {
                int accessibility = 0;
                for (int i = 0; i < nMoves; i++)
                    if (InRangeAndEmpty(x + moves[i, 0], y + moves[i, 1]))
                        accessibility += 1;
                return accessibility;
            }

            int[] GetNextMoves(int[] move)
            {
                int x = move[0];
                int y = move[1];
                int accessibility = nMoves;
                for (int i = 0; i < nMoves; i++)
                {
                    int newX = x + moves[i, 0];
                    int newY = y + moves[i, 1];
                    int newAcc = GetAccessibility(newX, newY);
                    if (InRangeAndEmpty(newX, newY) && newAcc < accessibility)
                    {
                        move[0] = newX;
                        move[1] = newY;
                        accessibility = newAcc;
                    }
                }
                return move;
            }
        }

2009-08-13 Reply Admin

Mr.'; Drop Database --:
I had a go at the 3D tour ... I tried out 1x1x2 jumps at first but couldn't find any tours for any small boards.

I've just realised that 1x1x2 jumps can't ever work because the sum of the knight's coordinates can never change from odd to even or from even to odd. Seems really obvious now ...

Skizz · 2009-08-13 Reply Admin

public void KnightsTour (Piece knight) { InfiniteImprobilityDrive drive = new InfiniteImprobilityDrive ();

// attach the infinite improbabilty drive to the knight knight.AttachDrive (drive);

// As we know, the infinite improbabilty drive, when // activated, visits all points in the universe // simultaneously, thus completing the knights tour. // Additionally, as demonstrated by the semi-evolved // simian known as Dent Arthur Dent, activating the drive // without first programming a destination results in the // drive returning to its original location. drive.Activate (); // Not only does the knight visit all the locations of // the board it's on, it also visits all the locations // of all the boards in the known universe. }

2009-08-13 Reply Admin

This sounds very elegant indeed. How abount using a http://en.wikipedia.org/wiki/Disjoint-set_data_structure ? (it solves the opposite problem, I guess, but that is left as an exercise for the reader.

2009-08-13 Reply Admin

After all those long and neat solutions, here is a compact (and rather obfuscated) one in C++. Not honoring the last point though.

#include <iostream>
#include <map>

int s, x, y;
std::map<int, std::map<int, int> > B;

#define mx(x, i) (x+(1+i%2)*(1-2*(i%4>>1)))
#define my(y, i) (y+(2-i%2)*(1-2*(i>>2)))
#define f(x, y) ((x)*(s-x+1)>0&&(y)*(s-y+1)>0&&!B[x][y])

int a(int x, int y)
{
   int r=0;
   if (f(x, y)) {
      for (int i = 0; i < 8; ++i)
         r += f(mx(x, i), my(y, i));
      return r;
   }
   return 9;
}

int main()
{
   std::cin >> s >> x >> y;
   B[x][y] = 1;
   for (int z = 2; z <= s*s; ++z)
   {
      int j, m = 9;
      for (int i = 0; i < 8; ++i)
         if (a(mx(x, i), my(y, i)) < m)
            j = i, m = a(mx(x, i), my(y, i));
      x=mx(x, j), y=my(y, j), B[x][y] = z;
      std::cout << x << "," << y << std::endl;
   }
   return 0;
}

2009-08-13 Reply Admin

Hahahaha Last week everyone complains things are too easy.

Now everyone complains the puzzle is too common - but few bother to propose a solution?

As Alex said (on the first page of the comments): we could cheat and find the answer, or you could challenge yourself to do it without looking for the answer outright. OR (as I think he also suggested) good opportunity to familiarise yourself with another language...

2009-08-13 Reply Admin

AlpineR:
I have an original programming praxis if you want:
No-Touch Mosaics

Form a rectangular mosaic from square, colored pieces. Any number of pieces and any number of colors are allowed.

Form another rectangular mosaic from the same set of pieces. But this time, don't allow any pieces that touched before to touch again. Pieces of a common color are considered interchangeable, so if a red piece touched a blue piece in the first mosaic then no red pieces can touch any blue pieces in the second mosaic. Furthermore, if two blue pieces touched in the first mosaic then no blue pieces can touch in the second mosaic.

Provide an example of a pair of mosaics satisfying these rules.

What is the smallest pair of mosaics (of any shape) that satisfies the rules?

What is the smallest pair of square mosaics that satisfies the rules.

What is the fewest number of colors necessary to form such a pair?

Provide an example of the smallest pair using the fewest number of colors?

Addendum (2009-08-12 20:37): One more rule I forgot to mention: Consider any piece on an outer edge to be in contact with all other pieces on an outer edge in the same mosaic. So if both a red piece and a blue piece are on the outer edge in the first mosaic, neither a red piece nor a blue piece can be on the outer edge in the second mosaic, nor can they touch each other in the second mosaic.

Surely the minimal solution is just one piece.

2009-08-13 Reply Admin

php

<?php

define ("FREE", 0);
define ("START", 1);
define ("VISITED", 2);

define ("FAIL", 0);
define ("LOOPCLOSED", -1);

define ("MAXKNIGHTMOVES", 8);

function KnightStep ($BoardSize,  &$Board, $NVisited, $Step, &$theWalk) {
  $KnightMoves [0] = array ("row" => -2, "col" => 1);
  $KnightMoves [1] = array ("row" => -2, "col" => -1);
  $KnightMoves [2] = array ("row" => 1, "col" => 2);
  $KnightMoves [3] = array ("row" => -1, "col" => 2);
  $KnightMoves [4] = array ("row" => 2, "col" => 1);
  $KnightMoves [5] = array ("row" => 2, "col" => -1);
  $KnightMoves [6] = array ("row" => 1, "col" => -2);
  $KnightMoves [7] = array ("row" => -1, "col" => -2);

  if ($NVisited == $BoardSize*$BoardSize) {
    if ($Board [$Step["row"]] [$Step["col"]] == START) {
      return LOOPCLOSED;
      $theWalk .= " " . $Step["row"] . "," . $Step["col"];
    } else {
      return FAIL;
    }
  } else {
    if (($Step["row"] < 0) OR ($Step["col"] < 0) OR ($Step["row"] >= $BoardSize) OR ($Step["col"]>= $BoardSize) OR ($Board [$Step["row"]] [$Step["col"]] != FREE)) {
      return FAIL;
    }
      
    if ($Board [$Step["row"]] [$Step["col"]] == FREE) {
      if ($NVisited == 0)
        $Board [$Step["row"]] [$Step["col"]] = START;
      else
        $Board [$Step["row"]] [$Step["col"]] = VISITED;
      $NVisited++;

      $i = 0;
      do {
        $NextStep["row"] = $Step["row"] + $KnightMoves [$i]["row"]; $NextStep["col"] = $Step["col"] + $KnightMoves [$i]["col"];
        $result = KnightStep ($BoardSize,  $Board, $NVisited, $NextStep, $theWalk);
        $i++;
      } while ($result == FAIL AND $i < MAXKNIGHTMOVES);
      
      if ($result == FAIL) {
        $Board [$Step["row"]] [$Step["col"]] = FREE;
      } else {
        $theWalk .= " " . $Step["row"] . "," . $Step["col"];
      }

      return $result;
    }
  }
}

function KnightWalk ($BoardSize, $StartingPosition) {
  // board initialization
  for ($row=0; $row<$BoardSize; $row++)
    for ($column=0; $column<$BoardSize; $column++)
      $Board [$row][$column] = FREE;
  // walk initialization
  $theWalk = "" . $StartingPosition["row"] . "," . $StartingPosition["col"];
  // let's begin
  KnightStep ($BoardSize, $Board, 0, $StartingPosition, $theWalk);
  return $theWalk;
}

$BoardSize = 6;
$StartHere["row"] = 4;
$StartHere["col"] = 4;
echo KnightWalk ($BoardSize, $StartHere);

?>

2009-08-13 Reply Admin

Did anyone say brute force? Using Prolog! (gprolog Syntax)

move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1+2, Y2 is Y1+1,NStep is Step+1. move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1+2, Y2 is Y1-1,NStep is Step+1. move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1-2, Y2 is Y1+1,NStep is Step+1. move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1-2, Y2 is Y1-1,NStep is Step+1. move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1+1, Y2 is Y1+2,NStep is Step+1. move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1+1, Y2 is Y1-2,NStep is Step+1. move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1-1, Y2 is Y1+2,NStep is Step+1. move(f(X1,Y1),f(X2,Y2),Step,NStep):- X2 is X1-1, Y2 is Y1-2,NStep is Step+1.
init(f(X,Y),size(SX,SY)):- Area is SX*SY,run(f(X,Y),SX,SY,Area,1,[],Out),write(Out).

run(,,_,Area,Area,Res,Res). run(F1,SX,SY,Area,Step,Res,Out):- +(member(F1,Res)),move(F1,f(X,Y),Step,NStep), X=<SX,Y=<SY,X>0,Y>0,run(f(X,Y),SX,SY,Area,NStep,[F1|Res],Out).

Automating the Knight’s Tour

Leave a comment on “Automating the Knight’s Tour”