hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Brute Force Solution
Goto page 1, 2  Next
 
Reply to topic    hacker.org Forum Index » Modulo Puzzle View previous topic
View next topic
Brute Force Solution
Author Message
bok
Site Admin


Joined: 30 Jan 2007
Posts: 24

Post Brute Force Solution Reply with quote
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:

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 ????????");
        }
    }
}

Thu Apr 26, 2007 9:05 pm View user's profile Send private message Send e-mail
k17



Joined: 10 Aug 2007
Posts: 1

Post Re: Brute Force Solution Reply with quote
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:

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 ????????");
        }
    }
}
Cool

_________________
K17
Fri Aug 10, 2007 10:16 am View user's profile Send private message MSN Messenger
jamjardavies



Joined: 18 Jun 2008
Posts: 3

Post Code Reply with quote
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:

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;
            }
        }
    }
}

Wed Jun 18, 2008 4:18 pm View user's profile Send private message
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
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.
Wed Jun 18, 2008 5:49 pm View user's profile Send private message
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
You have the Form1 class set as partial, and only one of the parts is included. Is there something missing?
Wed Jun 18, 2008 7:05 pm View user's profile Send private message
jamjardavies



Joined: 18 Jun 2008
Posts: 3

Post Reply with quote
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.
Thu Jun 19, 2008 3:42 pm View user's profile Send private message
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
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
Thu Jun 19, 2008 7:21 pm View user's profile Send private message
jamjardavies



Joined: 18 Jun 2008
Posts: 3

Post Reply with quote
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.
Fri Jun 20, 2008 8:20 am View user's profile Send private message
Allosentient



Joined: 10 Apr 2008
Posts: 273

Post Reply with quote
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
Fri Jun 20, 2008 6:46 pm View user's profile Send private message
antirem



Joined: 29 Dec 2008
Posts: 10

Post Reply with quote
whats the advantage or writing code in something other than perl?

_________________
please dont use DD-WRT
Hacker - One who is proficient at using or programming a computer; a computer buff
Mon Dec 29, 2008 6:16 am View user's profile Send private message
therethinker



Joined: 28 Mar 2008
Posts: 144
Location: #hacker.org on Freenode

Post Reply with quote
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.
Wed Dec 31, 2008 6:58 pm View user's profile Send private message AIM Address
daMage



Joined: 08 Jul 2008
Posts: 2

Post Reply with quote
antirem wrote:
whats the advantage or writing code in something other than perl?

you can use Python Cool
Fri Feb 20, 2009 2:51 pm View user's profile Send private message
tro95



Joined: 12 Jan 2010
Posts: 3

Post Reply with quote
daMage wrote:
antirem wrote:
whats the advantage or writing code in something other than perl?

you can use Python Cool


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.
Thu Jan 14, 2010 1:52 pm View user's profile Send private message
laz0r



Joined: 04 Feb 2010
Posts: 290
Location: Within the depths of Unix

Post Reply with quote
tro95 wrote:
daMage wrote:
antirem wrote:
whats the advantage or writing code in something other than perl?

you can use Python Cool


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

_________________
There is no spoon.
Thu Feb 11, 2010 5:24 pm View user's profile Send private message
stabat



Joined: 10 Oct 2009
Posts: 5
Location: Denmark

Post Reply with quote
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"?
Wed Oct 20, 2010 12:36 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Modulo Puzzle All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.