Home Page > > Details

COMP9012 Flow Puzzle

Deliverables

You are given a base code. You can compile the code and execute the solver by typing ./flow

You are given the structure of a node in node.*files, and also a priority queue queues.* implementation. Look into the engine.* and utils.* files to know about the functions you can call to perform the search.

In your final submission, you are free to change any file, but make sure the command line options remain the same.

Input

In order to execute your solver use the following command:

./flow [options]

for example:

./flow puzzles/regular_5x5_01.txt

Will run the solver for the regular 5 by 5 puzzle, and report if the search was successful, the number of nodes generated and the time taken. if you use flag -q (quiet) it will report the solutions more concisely. This option can be useful if you want to run several puzzles at once and study their performance.

If you append the option -A it will animate the solution found. If you append the option -d it will use the dead-end detection mechanism that you implemented. Feel free to explore the impact of the other options, specifically the ordering in which the colors are explored.

By default, the color that has fewer free neighbors (most constrained), is the one that is going to be considered first.

All the options can be found if you use option -h:

$./flow -h

usage: flow_solver [ OPTIONS ] BOARD1.txt

BOARD2.txt [ ... ] ]

Display options:

-q, --quiet Reduce output

-d, --diagnostics Print diagnostics when search unsuccessful

-A, --animation Animate solution

-F, --fast Speed up animation 4x

-C, --color Force use of ANSI color

-S, --svg Output final state to SVG

Node evaluation options:

-d, --deadends dead-end checking

Color ordering options:

-r, --randomize Shuffle order of colors before solving

-c, --constrained Disable order by most constrained

Search options:

-n, --max-nodes N Restrict storage to N nodes

-m, --max-storage N Restrict storage to N MB (default 1024)

Help:

-h, --help See this help text

Output

Your solver will print the following information if option -q is used:

Puzzle Name

SearchFlag (see utils.c, line 65-68 to understand the flags)

Total Search Time, in seconds

Number of generated nodes

A final Summary

For example, the output of your solver ./flow -q ../puzzles/regular_* could be:

../puzzles/regular_5x5_01.txt s 0.000 18

../puzzles/regular_6x6_01.txt s 0.000 283

../puzzles/regular_7x7_01.txt s 0.002 3,317

../puzzles/regular_8x8_01.txt s 0.284 409,726

../puzzles/regular_9x9_01.txt s 0.417 587,332

5 total s 0.704 1,000,676

These numbers depend on your implementation of the search, the ordering you use, and whether you prune dead-ends. If we use dead-end pruning ./flow -q -d ../puzzles/regular_* we get the following results

../puzzles/regular_5x5_01.txt s 0.000 17

../puzzles/regular_6x6_01.txt s 0.000 254

../puzzles/regular_7x7_01.txt s 0.001 2,198

../puzzles/regular_8x8_01.txt s 0.137 182,136

../puzzles/regular_9x9_01.txt s 0.210 279,287

5 total s 0.349 463,892

Remember that in order to get full marks, your solver has to solve at least the regular puzzles.

Deliverables

Deliverable 1 - Dijkstra Solver source code

You are expected to hand in the source code for your solver, written in C. Obviously, your source code is expected to compile and execute flawlessly using the following makefile command:

make

generating an executable called

flow

Remember to compile using the optimization flag gcc -O3 for doing your experiments, it will run twice as quickly as compiling with the debugging flag gcc -g (see Makefile). The provided Makefile compiles with the optimization flag by default, and with the debugging flag if you type make debug=1. For the submission, please do not remove the -g option from your Makefile, as our scripts need this flag for testing. Your program must not be compiled under any flags that prevent it from working under gdb or valgrind.

Your implementation should be able to solve the regular puzzles provided. To solve the extreme puzzles, you’ll need further enhancements that go beyond the time for this assignment, but feel free to challenge yourself if you finish early and explore how you would solve the extreme puzzles.

Deliverable 2 - Experimentation

Besides handing in the solver source code, you’re required to provide a table reporting at least the execution time and number of generated nodes with and without dead-end detection. Include in the table only the puzzles that your solver finds a solution to.

Plot figures, where the x-axis can be the number of free cells at the start, or the size of the grid, and the y-axis is either the number of generated states or solution time.

Explain your results using your figures and tables. Which complexity growth does your data show? What’s the computational benefit of the dead-end detection, does it decrease the growth rate? Answer concisely.

If you decide to implement any further optimization beyond the instructions of the assignment, or change the default arguments such as allowed memory or color ordering, please discuss their impact on the experimentation section as well.

Please include your Username, Student ID and Full Name in your Document.

My recommendation is that you generate the plots using any standard Python visualization library. See for example Seaborn or Matplotlib. Otherwise, there’s always the old-school excel/open-office/google-sheets method.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Tele9754help With ,Help With Python，C... 2023-11-23
- Comp2005jhelp With ,Help With Python，... 2023-11-23
- Help With Comp228,Help With Python，Ja... 2023-11-23
- Help With Com661,Help With Java,Python... 2023-11-23
- Help With Program,Help With Java Progr... 2023-10-10
- Help With Math36031,Help With Matlab P... 2023-10-10
- Help With Data Programming,Help With P... 2023-10-10
- Isye 6767Help With ,C/C++，Python Prog... 2023-10-10
- Comp 10183Help With ,Help With Java Pr... 2023-10-10
- Help With Program,Java Programminghelp... 2023-10-10
- Help With Elec2103,Matlab Programmingh... 2023-10-10
- Help With Prolog|Help With R Programmi... 2023-10-10
- Help With Comp3670,Python Programmingh... 2023-10-10
- Help With Python Programming|Help With... 2023-10-09
- Csc3150help With ,Help With C/C++ Prog... 2023-10-09
- Comp10002help With ,Help With C/C++ Pr... 2023-10-09
- Help With Cisc 360,Python，C/C++ Progr... 2023-10-08
- Help With Info1113,Java Programminghel... 2023-10-08
- Cmpe 330Help With ,Java，C/C++ Program... 2023-10-08
- Comp2400help With ,R Programminghelp W... 2023-10-08

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！