Coursera algs4partII-004 - Assignment 4

Algorithms, Part II
by Kevin Wayne, Robert Sedgewick


Programming Assignment 4: Boggle | boggle.zip
Submission time	Fri-02-Jan 18:45:17
Raw Score	81.67 / 100.00
Feedback	See the Assessment Guide for information on how to read this report.
 Assessment Summary
Compilation:  PASSED
Style:        FAILED
Findbugs:     No potential bugs found.
API:          PASSED

Correctness:  13/13 tests passed
Memory:       0/3 tests passed
Timing:       4/6 tests passed

Aggregate score: 81.67% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]
 Assessment Details
The following files were submitted:
----------------------------------
total 28K
-rw-r--r-- 1 2.5K Jan  3 02:47 BoggleSolver.java
-rw-r--r-- 1 4.1K Jan  3 02:47 Dictionnaire.java
-rw-r--r-- 1 4.3K Jan  3 02:47 Exploration.java
-rw-r--r-- 1 4.1K Jan  3 02:47 studentSubmission.zip


******************************************************************************
*  compiling
******************************************************************************


% javac BoggleSolver.java
*-----------------------------------------------------------
================================================================



% checkstyle *.java
*-----------------------------------------------------------
BoggleSolver.java:14:8: Unused import - java.util.List.
BoggleSolver.java:24:1: File contains tab characters (this is the first instance).
================================================================


% findbugs *.class
*-----------------------------------------------------------
================================================================


Testing the APIs of your programs.
*-----------------------------------------------------------
BoggleSolver:

================================================================


******************************************************************************
*  correctness
******************************************************************************

Testing methods in BoggleSolver
*-----------------------------------------------------------
Running 13 total tests.

Test 1: test getAllValidWords() on two fixed 4-by-4 boards given in assignment
  *  dictionary = dictionary-algs4.txt; board = board4x4.txt
  *  dictionary = dictionary-algs4.txt; board = board-q.txt
==> passed

Test 2: test getAllValidWords() on fixed 4-by-4 boards
  *  dictionary = dictionary-yawl.txt; board = board4x4.txt
  *  dictionary = dictionary-yawl.txt; board = board-points1.txt
  *  dictionary = dictionary-yawl.txt; board = board-points2.txt
  *  dictionary = dictionary-yawl.txt; board = board-points3.txt
  *  dictionary = dictionary-yawl.txt; board = board-points4.txt
  *  dictionary = dictionary-yawl.txt; board = board-points5.txt
==> passed

Test 3: test getAllValidWords() on more fixed 4-by-4 boards
  *  dictionary = dictionary-yawl.txt; board = board-points100.txt
  *  dictionary = dictionary-yawl.txt; board = board-points200.txt
  *  dictionary = dictionary-yawl.txt; board = board-points300.txt
  *  dictionary = dictionary-yawl.txt; board = board-points400.txt
  *  dictionary = dictionary-yawl.txt; board = board-points500.txt
  *  dictionary = dictionary-yawl.txt; board = board-points750.txt
  *  dictionary = dictionary-yawl.txt; board = board-points1000.txt
  *  dictionary = dictionary-yawl.txt; board = board-points1250.txt
  *  dictionary = dictionary-yawl.txt; board = board-points1500.txt
  *  dictionary = dictionary-yawl.txt; board = board-points2000.txt
==> passed

Test 4: test getAllValidWords() on random Hasbro boards
  *  dictionary = dictionary-yawl.txt; board = 10 random Hasbro boards
  *  dictionary = dictionary-yawl.txt; board = 50 random Hasbro boards
  *  dictionary = dictionary-yawl.txt; board = 100 random Hasbro boards
==> passed

Test 5: test getAllValidWords() on high-scoring N-by-N boards
  *  dictionary = dictionary-yawl.txt; board = board-points4410.txt
  *  dictionary = dictionary-yawl.txt; board = board-points4527.txt
  *  dictionary = dictionary-yawl.txt; board = board-points13464.txt
  *  dictionary = dictionary-yawl.txt; board = board-points26539.txt
==> passed

Test 6: test getAllValidWords() on exotic boards
  *  dictionary = dictionary-yawl.txt; board = board-dodo.txt
  *  dictionary = dictionary-yawl.txt; board = board-noon.txt
  *  dictionary = dictionary-yawl.txt; board = board-couscous.txt
  *  dictionary = dictionary-yawl.txt; board = board-rotavator.txt
  *  dictionary = dictionary-yawl.txt; board = board-estrangers.txt
  *  dictionary = dictionary-yawl.txt; board = board-antidisestablishmentarianisms.txt
  *  dictionary = dictionary-yawl.txt; board = board-dichlorodiphenyltrichloroethanes.txt
  *  dictionary = dictionary-yawl.txt; board = board-pneumonoultramicroscopicsilicovolcanoconiosis.txt
==> passed

Test 7: test getAllValidWords() on boards with a Q
  *  dictionary = dictionary-yawl.txt; board = board-qwerty.txt
  *  dictionary = dictionary-yawl.txt; board = board-quinquevalencies.txt
  *  dictionary = dictionary-yawl.txt; board = board-inconsequentially.txt
  *  dictionary = dictionary-yawl.txt; board = board-qaimaqam.txt
  *  dictionary = dictionary-yawl.txt; board = board-aqua.txt
  *  dictionary = dictionary-yawl.txt; board = 100 random Hasbro boards
  *  dictionary = dictionary-16q.txt; board = board-9q.txt
  *  dictionary = dictionary-16q.txt; board = board-16q.txt
==> passed

Test 8: test getAllValidWords() on random M-by-N boards
  *  dictionary = dictionary-common.txt; board = 100 random 3-by-3 boards
  *  dictionary = dictionary-common.txt; board = 100 random 4-by-4 boards
  *  dictionary = dictionary-common.txt; board = 100 random 5-by-5 boards
  *  dictionary = dictionary-common.txt; board = 20 random 5-by-10 boards
  *  dictionary = dictionary-common.txt; board = 20 random 10-by-5 boards
==> passed

Test 9: test getAllValidWords() on random M-by-N boards
  *  dictionary = dictionary-common.txt; board = 10 random 2-by-2 boards
  *  dictionary = dictionary-common.txt; board = 10 random 1-by-10 boards
  *  dictionary = dictionary-common.txt; board = 10 random 10-by-1 boards
  *  dictionary = dictionary-common.txt; board = 10 random 1-by-1 boards
  *  dictionary = dictionary-common.txt; board = 10 random 1-by-2 boards
  *  dictionary = dictionary-common.txt; board = 10 random 2-by-1 boards
  *  dictionary = dictionary-common.txt; board = 1 random 0-by-4 boards
  *  dictionary = dictionary-common.txt; board = 1 random 4-by-0 boards
==> passed

Test 10: test getAllValidWords() on boards with no valid words
  *  dictionary = dictionary-nursery.txt; board = board-points0.txt
  *  dictionary = dictionary-2letters.txt; board = board-points4410.txt
==> passed

Test 11: mutating dictionary[] after passing to BoggleSolver constructor
  *  dictionary = dictionary-algs4.txt
  *  dictionary = dictionary-algs4.txt; board = board4x4.txt
  *  dictionary = dictionary-algs4.txt; board = 10 random Hasbro boards
==> passed

Test 12: create more than one BoggleSolver object at a time
         [ BoggleSolver object 1 uses dictionary-algs4.txt   ]
         [ BoggleSolver object 2 uses dictionary-nursery.txt ]
  *  dictionary = dictionary-algs4.txt; board = 10 random Hasbro boards
  *  dictionary = dictionary-nursery.txt; board = 10 random Hasbro boards
  *  dictionary = dictionary-algs4.txt; board = 10 random Hasbro boards
==> passed

Test 13: test scoreOf() on various dictionaries
  *  dictionary = dictionary-algs4.txt
  *  dictionary = dictionary-common.txt
  *  dictionary = dictionary-shakespeare.txt
  *  dictionary = dictionary-nursery.txt
  *  dictionary = dictionary-yawl.txt
==> passed


Total: 13/13 tests passed!

================================================================

******************************************************************************
*  memory
******************************************************************************

Computing memory of BoggleSolver
*-----------------------------------------------------------
Running 3 total tests.

Test 1: memory with dictionary-algs4.txt (must be <= 2x reference solution).
  - memory of dictionary[]           = 494472 bytes
  - memory of student   BoggleSolver = 2904024 bytes
  - memory of reference BoggleSolver = 5135408 bytes
  - student / reference              = 0.57
==> passed

Test 2: memory with dictionary-shakespeare.txt (must be <= 2x reference solution).
  - memory of dictionary[]           = 1925392 bytes
  - memory of student   BoggleSolver = 10208472 bytes
  - memory of reference BoggleSolver = 17479568 bytes
  - student / reference              = 0.58
==> passed


Total: 0/3 tests passed:Test aborted. Ran out of time or crashed before completion.
================================================================



******************************************************************************
*  timing
******************************************************************************

Timing BoggleSolver
*-----------------------------------------------------------
Running 6 total tests.

Test 1: timing constructor (must be <= 5x reference solution).
 *  dictionary-algs4.txt
      - student   solution time (in seconds): 0.13
      - reference solution time (in seconds): 0.02
      - ratio:                                5.68

 *  dictionary-enable2k.txt
      - student   solution time (in seconds): 0.62
      - reference solution time (in seconds): 0.35
      - ratio:                                1.78

 *  dictionary-yawl.txt
      - student   solution time (in seconds): 0.61
      - reference solution time (in seconds): 0.55
      - ratio:                                1.11

 *  dictionary-zingarelli2005.txt
      - student   solution time (in seconds): 2.76
      - reference solution time (in seconds): 0.62
      - ratio:                                4.48

==> FAILED

Test 2: timing findAllWords() for 1.0 seconds (must be <= 25000x reference solution).
      - reference solution calls per second: 4815.18
      - student   solution calls per second: 359.06
      - reference / student ratio:           13.41

==> passed

Test 3: timing findAllWords() for 1.0 seconds (must be <= 25x reference solution).
      - reference solution calls per second: 5014.99
      - student   solution calls per second: 1191.00
      - reference / student ratio:           4.21

==> passed

Test 4: timing findAllWords() for 1.0 seconds (must be <= 10x reference solution).
      - reference solution calls per second: 5084.92
      - student   solution calls per second: 1130.00
      - reference / student ratio:           4.50

==> passed

Test 5: timing findAllWords() for 1.0 seconds (must be <= 5x reference solution).
      - reference solution calls per second: 4515.48
      - student   solution calls per second: 1116.00
      - reference / student ratio:           4.05

==> passed

Test 6: timing findAllWords() for 3.0 seconds (must be <= 2x reference solution).
      - reference solution calls per second: 5020.00
      - student   solution calls per second: 1131.67
      - reference / student ratio:           4.44

==> FAILED


Total: 4/6 tests passed!

================================================================