Page 1 of 2
Brute Force Solution
Posted: Thu Apr 26, 2007 9:05 pm
by bok
I figured that to get people started, I would post a trivial brute-force puzzle solver, to give others a soup starter. This is really the simplest implementation, with no 'smarts', but it might help as a starting point for smart algorithms.
This is a small java program which takes on the command line the puzzle parameters extracted from the puzzle's HTML page, and when a solution is found it prints out the list of coordinates for the shapes, as well as a formatted string that can be used to post the solution to the server without having the manually click on the page (HINT: you can automate all this solving stuff, and let it run while you sleep).
Code: Select all
import java.util.ArrayList;
final class Shape {
public int[][] cells;
int rows;
int columns;
public Shape(String spec) {
String[] rowSpecs = spec.split("\\,");
rows = rowSpecs.length;
columns = rowSpecs[0].length();
ArrayList coordinates = new ArrayList();
for (int row=0; row<rows; row++) {
for (int column=0; column<columns; column++) {
if (rowSpecs[row].charAt(column) == 'X') coordinates.add(new int[] {column, row});
}
}
cells = new int[coordinates.size()][];
coordinates.toArray(cells);
}
}
final class Board {
public int depth;
public int[] cells;
public int columns;
public int rows;
public Board(String spec, int depth) {
this.depth = depth;
cells = new int[spec.length()];
String[] rowSpecs = spec.split(",");
rows = rowSpecs.length;
columns = rowSpecs[0].length();
for (int row=0; row<rows; row++) {
for (int column=0; column<columns; column++) {
cells[column+row*columns] = (byte)(rowSpecs[row].charAt(column)-'0');
}
}
}
public void apply(Shape shape, int column, int row, int delta) {
for (int i=0; i<shape.cells.length; i++) {
int o = column+shape.cells[i][0]+(row+shape.cells[i][1])*columns;
cells[o] = (cells[o]+delta)%(depth+1);
}
}
}
class Solver {
Board board;
Shape[] shapes;
int[][] positions;
public Solver(Board board, Shape[] shapes) {
this.board = board;
this.shapes = shapes;
positions = new int[shapes.length][2];
}
int[][] solve(int index) {
if (index == shapes.length) {
for (int i=0; i<board.cells.length; i++) {
if (board.cells[i] != 0) return null;
}
return positions;
} else {
Shape shape = shapes[index];
for (int column = 0; column<=board.columns-shape.columns; column++) {
for (int row = 0; row<=board.rows-shape.rows; row++) {
positions[index][0] = column;
positions[index][1] = row;
board.apply(shape, column, row, 1);
int[][] t = solve(index+1);
board.apply(shape, column, row, board.depth);
if (t != null) return t;
}
}
return null;
}
}
}
public class Modulo {
public static void main(String[] args) throws Exception {
// parse command line args: <depth> <pieces> <board>
// where <depth>, <pieces> and <board> parameters are obtained from
// the <applet> tag found in the puzzle HTML page
// NOTE: the <pieces> string contains spaces, so you will need to surround
// the string with quotes on the command line
int depth = Integer.parseInt(args[0])-1;
Board board = new Board(args[1], depth);
String[] shapeSpecs = args[2].split(" ");
Shape[] shapes = new Shape[shapeSpecs.length];
for (int i=0; i<shapeSpecs.length; i++) {
shapes[i] = new Shape(shapeSpecs[i]);
}
// solve the puzzle
Solver solver = new Solver(board, shapes);
int[][] solution = solver.solve(0);
if (solution != null) {
for (int i=0; i<solution.length; i++) {
System.out.println("Shape " + i + " at " + solution[i][0] + "," + solution[i][1]);
}
System.out.println("Formatted solution sequence (for the modulo.php?seq= part of the submit URL:");
for (int i=0; i<solution.length; i++) {
System.out.print(String.format("%02x%02x", solution[i][0], solution[i][1]));
}
System.out.println("");
} else {
System.out.println("????????? no solution found ????????");
}
}
}
Re: Brute Force Solution
Posted: Fri Aug 10, 2007 10:16 am
by k17
bok wrote:I figured that to get people started, I would post a trivial brute-force puzzle solver, to give others a soup starter. This is really the simplest implementation, with no 'smarts', but it might help as a starting point for smart algorithms.
This is a small java program which takes on the command line the puzzle parameters extracted from the puzzle's HTML page, and when a solution is found it prints out the list of coordinates for the shapes, as well as a formatted string that can be used to post the solution to the server without having the manually click on the page (HINT: you can automate all this solving stuff, and let it run while you sleep).
Code: Select all
import java.util.ArrayList;
final class Shape {
public int[][] cells;
int rows;
int columns;
public Shape(String spec) {
String[] rowSpecs = spec.split("\\,");
rows = rowSpecs.length;
columns = rowSpecs[0].length();
K17
ArrayList coordinates = new ArrayList();
for (int row=0; row<rows; row++) {
for (int column=0; column<columns; column++) {
if (rowSpecs[row].charAt(column) == 'X') coordinates.add(new int[] {column, row});
}
}
cells = new int[coordinates.size()][];
coordinates.toArray(cells);
}
}
final class Board {
public int depth;
public int[] cells;
public int columns;
public int rows;
public Board(String spec, int depth) {
this.depth = depth;
cells = new int[spec.length()];
String[] rowSpecs = spec.split(",");
rows = rowSpecs.length;
columns = rowSpecs[0].length();
for (int row=0; row<rows; row++) {
for (int column=0; column<columns; column++) {
cells[column+row*columns] = (byte)(rowSpecs[row].charAt(column)-'0');
}
}
}
public void apply(Shape shape, int column, int row, int delta) {
for (int i=0; i<shape.cells.length; i++) {
int o = column+shape.cells[i][0]+(row+shape.cells[i][1])*columns;
cells[o] = (cells[o]+delta)%(depth+1);
}
}
}
class Solver {
Board board;
Shape[] shapes;
int[][] positions;
public Solver(Board board, Shape[] shapes) {
this.board = board;
this.shapes = shapes;
positions = new int[shapes.length][2];
}
int[][] solve(int index) {
if (index == shapes.length) {
for (int i=0; i<board.cells.length; i++) {
if (board.cells[i] != 0) return null;
}
return positions;
} else {
Shape shape = shapes[index];
for (int column = 0; column<=board.columns-shape.columns; column++) {
for (int row = 0; row<=board.rows-shape.rows; row++) {
positions[index][0] = column;
positions[index][1] = row;
board.apply(shape, column, row, 1);
int[][] t = solve(index+1);
board.apply(shape, column, row, board.depth);
if (t != null) return t;
}
}
return null;
}
}
}
public class Modulo {
public static void main(String[] args) throws Exception {
// parse command line args: <depth> <pieces> <board>
// where <depth>, <pieces> and <board> parameters are obtained from
// the <applet> tag found in the puzzle HTML page
// NOTE: the <pieces> string contains spaces, so you will need to surround
// the string with quotes on the command line
int depth = Integer.parseInt(args[0])-1;
Board board = new Board(args[1], depth);
String[] shapeSpecs = args[2].split(" ");
Shape[] shapes = new Shape[shapeSpecs.length];
for (int i=0; i<shapeSpecs.length; i++) {
shapes[i] = new Shape(shapeSpecs[i]);
}
// solve the puzzle
Solver solver = new Solver(board, shapes);
int[][] solution = solver.solve(0);
if (solution != null) {
for (int i=0; i<solution.length; i++) {
System.out.println("Shape " + i + " at " + solution[i][0] + "," + solution[i][1]);
}
System.out.println("Formatted solution sequence (for the modulo.php?seq= part of the submit URL:");
for (int i=0; i<solution.length; i++) {
System.out.print(String.format("%02x%02x", solution[i][0], solution[i][1]));
}
System.out.println("");
} else {
System.out.println("????????? no solution found ????????");
}
}
}
Code
Posted: Wed Jun 18, 2008 4:18 pm
by jamjardavies
I have converted all this code into c# and it never works it out. Could you please have a look and see if I have done anything wrong please.
Thanks
James
Code: Select all
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Collections;
namespace WindowsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
// parse command line args: <depth> <pieces> <board>
// where <depth>, <pieces> and <board> parameters are obtained from
// the <applet> tag found in the puzzle HTML page
// NOTE: the <pieces> string contains spaces, so you will need to surround
// the string with quotes on the command line
int depth = 2;
Board board = new Board("110,010,110", depth);
String[] shapeSpecs = "X,X X.,XX X,X".Split(' ');
Shape[] shapes = new Shape[shapeSpecs.Length];
for (int i = 0; i < shapeSpecs.Length; i++)
{
shapes[i] = new Shape(shapeSpecs[i]);
}
// solve the puzzle
Solver solver = new Solver(board, shapes);
int[][] solution = solver.solve(0);
if (solution != null)
{
for (int i = 0; i < solution.Length; i++)
{
this.listBox1.Items.Add("Shape " + i + " at " + solution[i][0] + "," + solution[i][1]);
}
this.listBox1.Items.Add("Formatted solution sequence (for the modulo.php?seq= part of the submit URL:");
for (int i = 0; i < solution.Length; i++)
{
this.listBox1.Items.Add(String.Format("%02x%02x", solution[i][0], solution[i][1]));
}
this.listBox1.Items.Add("");
}
else
{
this.listBox1.Items.Add("????????? no solution found ????????");
}
}
}
public class Shape
{
public int[][] cells;
public int rows;
public int columns;
public Shape(String spec)
{
String[] rowSpecs = spec.Split(',');
rows = rowSpecs.Length;
columns = rowSpecs[0].Length;
ArrayList coordinates = new ArrayList();
for (int row = 0; row < rows; row++)
{
for (int column = 0; column < columns; column++)
{
if (rowSpecs[row].Substring(column, 1) == "X") coordinates.Add(new int[] { column, row });
}
}
cells = new int[coordinates.Count][];
for (int x = 0; x < coordinates.Count; x++)
{
cells[x] = (int[])coordinates[x];
}
}
}
public class Board
{
public int depth;
public int[] cells;
public int columns;
public int rows;
public Board(String spec, int depth)
{
this.depth = depth;
cells = new int[spec.Length];
String[] rowSpecs = spec.Split(',');
rows = rowSpecs.Length;
columns = rowSpecs[0].Length;
for (int row = 0; row < rows; row++)
{
for (int column = 0; column < columns; column++)
{
cells[column + row * columns] = (byte)(rowSpecs[row][(column)] - '0');
}
}
}
public void apply(Shape shape, int column, int row, int delta)
{
for (int i = 0; i < shape.cells.Length; i++)
{
int o = column + shape.cells[i][0] + (row + shape.cells[i][1]) * columns;
cells[o] = (cells[o] + delta) % (depth + 1);
}
}
}
public class Solver
{
Board board;
Shape[] shapes;
int[][] positions;
public Solver(Board board, Shape[] shapes)
{
this.board = board;
this.shapes = shapes;
positions = new int[shapes.Length][];
}
public int[][] solve(int index)
{
if (index == shapes.Length)
{
for (int i = 0; i < board.cells.Length; i++)
{
if (board.cells[i] != 0) return null;
}
return positions;
}
else
{
Shape shape = shapes[index];
int[] varName = new int[2];
for (int column = 0; column <= board.columns - shape.columns; column++)
{
for (int row = 0; row <= board.rows - shape.rows; row++)
{
varName[0] = column;
varName[1] = row;
positions[index] = varName;
//positions[index][0] = column;
//positions[index][1] = row;
board.apply(shape, column, row, 1);
int[][] t = solve(index + 1);
board.apply(shape, column, row, board.depth);
if (t != null) return t;
}
}
return null;
}
}
}
}
Posted: Wed Jun 18, 2008 5:49 pm
by Allosentient
Ah, another C# person! Welcome to the site.
I will have a look at this later after I get my car fixed
Try running through debugger in the meantime, and learn the puzzle enough to understand what a solver should do.
Posted: Wed Jun 18, 2008 7:05 pm
by Allosentient
You have the Form1 class set as partial, and only one of the parts is included. Is there something missing?
Posted: Thu Jun 19, 2008 3:42 pm
by jamjardavies
Hi thanks for the VERY quick reply. I use vb.net and c#.net and the Form1 class was made automatically. All I have there is a list box and a button to run the app in.
Posted: Thu Jun 19, 2008 7:21 pm
by Allosentient
If you cannot reproduce the code, could you submit a non-graphical version of this? I wouldn't try to use windows forms yet until you can get the very basics working
Posted: Fri Jun 20, 2008 8:20 am
by jamjardavies
I don't use java sorry, I know c# and I have stepped through the code and it seems to be doing the things correctly, but its just not solving it. It says no solution in like seconds.
Please also note that I am not one of these 15 year olds who go around trying to do things and claim that they know things.
Posted: Fri Jun 20, 2008 6:46 pm
by Allosentient
Did you know that you can write C# without using windows forms? Maybe you need to study C# some more.
Or you can post the .NET assembly (exe file) and all included DLL files from the binary folder and I will take a look at it. Either use rapidshare or send e-mail to
allosentient@gmail.com
I will try to work on making a version of the solver in the meantime and see what happens
Posted: Mon Dec 29, 2008 6:16 am
by antirem
whats the advantage or writing code in something other than perl?
Posted: Wed Dec 31, 2008 6:58 pm
by therethinker
Well, some languages are faster than perl. Others are easier to write & rewrite. Some people don't like perl or they don't know it too well...
Its sort of like asking what are the advantanges to using a keyboard other than using keyboard X. Everything has pros & cons but it comes down to a personal choice.
Posted: Fri Feb 20, 2009 2:51 pm
by daMage
antirem wrote:whats the advantage or writing code in something other than perl?
you can use Python
Posted: Thu Jan 14, 2010 1:52 pm
by tro95
daMage wrote:antirem wrote:whats the advantage or writing code in something other than perl?
you can use Python
Python is great for brute forcing and "cracking" into stuff.
Something like Turbo Delphi (a form of pascal) or Java would be ideal for hacking all of these games as it would be very easy to interact it with the website, very easy to program, and they run very efficiently.
Posted: Thu Feb 11, 2010 5:24 pm
by laz0r
tro95 wrote:daMage wrote:antirem wrote:whats the advantage or writing code in something other than perl?
you can use Python
Python is great for brute forcing and "cracking" into stuff.
Something like Turbo Delphi (a form of pascal) or Java would be ideal for hacking all of these games as it would be very easy to interact it with the website, very easy to program, and they run very efficiently.
Turbo Delphi is good, although try using SCAR instead as it can do much more than delphi is capable of
Posted: Wed Oct 20, 2010 12:36 pm
by stabat
I found this puzzle very interesting, but my solver is just not fast enough to beat big boards with lot of pieces. I don't think the target of the puzzle is to run a brute force algorithm for more than 5-10 mins, so I am trying to optimize my solver, rather let it run for hours, that I guess would provide me with the correct solution.
Should we discuss ways of optimizing our solver, and make it react more "clever"?