TweetFollow Us on Twitter

Apr 02 Challenge

Volume Number: 18 (2002)
Issue Number: 04
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

Disk Defragmentation

Occasionally people write me to say that the Challenges in this column are too difficult, that there just isn't enough time to solve the problems in the two plus weeks before the solutions are due. And in looking back, I have to confess that the problems have gotten more difficult over time. I rediscover this trend from time to time, and I've made several attempts to reverse it, only to have the problem difficulty creep up again after a while. Or, as others have written, I take a reasonable problem and put some evil twist into the problem statement, making it impossible. In part, the increased difficulty is because all of the easy problems have already been solved. Like all of the inventions worth inventing have been invented, and discoveries worth discovering have been discovered, and doctoral theses worth writing have been written. Probably not true, it just takes creativity. So this month we'll make another attempt at a simpler problem. In the future, of course, you readers can help by sending in your suggestions, which not only gives you the satisfaction of suggesting a Challenge that can actually be solved in the time available, you earn two invaluable Programmer's Challenge points if we use your suggestion.

This month's Challenge? Defragment a simulated disk drive. For each test case, you are given a disk drive with up to 32767 (2^15-1) blocks. On that drive are a number of files, some allocated contiguously, some allocated in a number of noncontiguous fragments. Your job is to move blocks of data so that the storage for each file is contiguous. It doesn't matter where on the disk the files are located; the free storage remaining on the disk does not need to be contiguous. There is one constraint - the amount of available auxiliary storage is limited, so you cannot remove multiple blocks of data from the disk to make room for others. You can move a contiguous sequence of disk blocks from one location to another in a single operation, as long as they don't overlap.

The file defrag.in contains a single line with the number of test cases your program needs to process. The input for each test case is provided in file defragNN.in, where NN ranges from 1 to the number of test cases. The first line of this input file contains the number of blocks in the simulated disk to be defragmented. The next line contains the number of data files on that disk. The remainder of the input file is a sequence of lines for each data file. The first line for each data file is the number of fragments in the allocation of the data file on the disk. This is followed by a line for each fragment, containing the disk block where the fragment starts, and then the number of blocks in that fragment. So an input file might look like the following:

   32767         - number of blocks in the simulated disk
   10            - number of files in this test case
   1            - number of fragments for the first file
   11234,100      - fragment starts at block 11234, uses 100 blocks
   3            - number of fragments for the second file
   11334,10      - fragment starts at block 11334, uses 10 blocks
   11134,100      - fragment starts at block 11134, uses 100 blocks
   11344,50      - fragment starts at block 11344, uses 50 blocks
   ...            - continue for 8 more files

Your program should process each input file and output a sequence of block moves to the file defragNN.out. Each block move should produce one line of output with 3 numbers:

            firstBlockToMove,newBlockLocation,numberOfBlockstoMove

Finally, your program should produce a challenge.log file, with one line per test case containing the integer number of microseconds used by your application to solve that test case, including the time to read the input, find the solution, and produce the output file. The method used to measure execution time may vary based on the development environment you use for your solution, but you should measure time with microsecond precision if possible.

You can improve your chances of winning by incorporating optional features into your solution. For this disk defragmentation problem, you might want to optionally display your solution's progress in defragmenting the disk.

Scoring will be based on minimizing the number of move sequences required to defragment the disk, on minimizing execution time, on a subjective evaluation of additional features, and on the elegance of your code, including the commentary that describes your solution. Your base score will be 100 penalty points for each defragment move sequence. You incur the same number of penalty points for a move of one block as you incur for a single move of multiple contiguous blocks. For each test case, your penalty points are increased by 1% per millisecond of execution time. Your penalty points will be decreased by up to 25% based on any optional features you might incorporate into your solution, and by another 25% based on a subjective evaluation of the elegance of your solution. Since one of the reasons people read the Challenge column is to learn techniques from our Challenge masters, it is important that your code be well documented. Code clarity and commentary will be considered in the evaluation of elegance.

This will be a native PowerPC Challenge, using the development environment of your choice, provided I have or can obtain a copy — email progchallenge@mactech.com to check before you start. You can develop for Mac OS 9 or Mac OS X. Your solution should be a complete Macintosh application, and your submission should provide everything needed to build your application.

A question for you readers, especially those of you that have entered or plan to enter the Challenge: how many of you use Mac OS X regularly? As I write this, Mac OS X has been around for a year or so, and for perhaps half that time in a useable form. I'll confess, I've stuck with Mac OS 9.x until recently, but I've left my most recent machine in its default configuration, booting into Mac OS X 10.1. Although it still annoys the heck out of me on occasion, it is beginning to grow on me. Are we ready to move the Challenge to OS X exclusively? Let me know what you think.

Winner of the January, 2002 Challenge

The January Challenge required contestants to write a player for TriMineSweeper, a variant on the traditional MineSweeper game. Like the classic MineSweeper, this game requires one to map out an arrangement of cells, discovering which cells are safe and which contain bombs. Moves are made by querying one cell at a time, designating whether that cell is believed to be empty (safe) or to contain a bomb (unsafe). Unlike the classic game, cells in TriMineSweeper are triangular in shape, and each cell has twelve neighbors instead of eight.

Congratulations to Xan Gregg for winning the TriMineSweeper Challenge. Xan was significantly more successful than other contestants in solving the TriMineSweeper boards, succeeding in solving eight of the ten test cases I used in the final evaluation. His solution also used less execution time than either of the other top two contestants. His strategy was to make all obviously safe moves, then to evaluate the collective information about the remaining cells to deduce and make other safe moves, and then to "pray" and guess a cell, favoring those cells that have a lower chance of containing a bomb based on what is known from neighboring cells. I suspect the reason Xan's solution was so successful has to do with the way he managed "sets", or collections of unknown cells surrounding a given cell. By combining information from overlapping sets, and by doing so during a "clean up" pass rather than after each move, Xan identified new safe moves and did so efficiently.

The second-place solution by Ernst Munter also used the concept of sets of cells surrounding a given cell, but apparently derived less information from overlapping sets, causing it to have to guess more frequently. Ernst's solution was designed in such a way that it could be adapted relatively easily to other board topologies.

The boards in the evaluation test cases ranged in size from 20x20 to 100x100, with the percentage of cells occupied by bombs ranging from 2.5% to 10%. Half of the test cases had 10% of the cells occupied by bombs, and half had fewer.

The table below lists, for each of the solutions submitted, the total execution time in milliseconds, the number of points earned, equal to the sum of the number of board cells in each game successfully solved, minus one point for each millisecond of execution time. It also lists the code side, data size, and programming language used for each entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

One last note. I received an entry coded in BASIC, but was unfortunately unable to evaluate it because this Challenge required an interface to a test driver written in C. BASIC fans, and users of other development environments, are encouraged to enter this month's Challenge, where solutions are stand-alone applications.

Name Time Points Code Data Language
(msec) Size Size
Xan Gregg(120) 307.8 46691 8076 4284 C
Ernst Munter(882) 1423.9 19677 4440 314 C++
Tom Saxton(203) 345.3 19154 5716 270 C++
Alan Hart(35) 218.5 16781 3040 134 C
Allen Stenger(82) 273.4 4226 4284 648 C++
Peter Heerboth 10.4 1590 5356 306 C
Douglas O'Brien Metal BASIC

Top Contestants ...

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points Wins Total
(24 mo) (24 mo) Points
1. Munter, Ernst 275 10 832
2. Rieken, Willeke 66 3 134
3. Saxton, Tom 52 1 210
4. Wihlborg, Claes 49 2 49
5. Taylor, Jonathan 39 1 63
8. Gregg, Xan 20 1 140
9. Mallett, Jeff 20 1 114
10. Cooper, Tony 20 1 20
11. Truskier, Peter 20 1 20

... and the Top Contestants Looking for a Recent Win

In order to give some recognition to other participants in the Challenge, we also list the high scores for contestants who have accumulated points without taking first place in a Challenge during the past two years. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

Rank Name Points Total
(24 mo) Points
6. Boring, Randy 28 144
7. Sadetsky, Gregory 22 24
12. Stenger, Allen 19 84
13. Shearer, Rob 19 62
14. Schotsman, Jan 16 16
15. Hart, Alan 14 39
16. Maurer, Sebastian 11 108
17. Nepsund, Ronald 10 57
18. Day, Mark 10 30
19. Desch, Noah 10 10
20. Fazekas, Miklos 10 10
21. Flowers, Sue 10 10
22. Leshner, Will 7 7
23. Miller, Mike 7 7

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Xan's winning TriMineSweeper solution:

Jan02 Solution.c
Copyright © 2002
Xan Gregg

/* Solution to TrimineSweeper Programmer's Challenge.
 Solves triangular mine sweeper puzzles.
 Keeps a list of sets of cells.  Each set corresponds to the unknown cells surrounding a 
 given cell; there is a maximum of 12 cells per set.  Each set also knows its total bomb 
 count.
 
 Each cell in the set is represented by its board index, that is, row * boardSize + col.  
 Member cells are stored in numerical order to speed searches for cells and set 
 comparison.
 
 When a non-bomb cell is revealed, a set is added with the learned information.
 
 The play mostly consists of repeatedly making safe moves until there are none.  
 "Safe" moves are revealing cells in sets where the bomb count is zero or the bomb 
 count is the same as the member count.
 
 When no safe moves are obvious, the sets are processed to remove known cells and 
 eliminate subsets.  Removing the known cells as they are discovered turns out to be 
 quite a bit slower than doing it in the clean-up pass. For subset elimination, sets that 
 are subsets of other sets are reduced so that

   4cells  2bombs (11,12) (11,13) (11,14) (11,15)
   3cells  1bombs (11,12) (11,13) (11,14)

 gets reduced to
   1cells  1bombs (11,15)
   3cells  1bombs (11,12) (11,13) (11,14)

 which produces a safe move for the next move pass.  When that fails, the program 
will look for certain intersecting sets, such as 

   6cells  4bombs (10,12) (11,12) (11,13) (11,14) (11,15) (11,16)
   4cells  1bombs ( 9,12) (11,12) (11,13) (11,14)

 which will produce

   3cells  3bombs (10,12) (11,15) (11,16)
   1cells  0bombs ( 9,12)
   3cells  1bombs (11,12) (11,13) (11,14)

 when the common subset is factored out.  Seems to come up in about 1 in 1000
 games, so the value here is debatable.

 When no safe moves or set reductions are possible then the only option is to "pray" 
 and reveal a random square. Of course, prayer is required at least for the first few 
 moves. Before guessing, sets are compared to determined the safest guess based on 
 bombs per member.
*/
#include "Triminesweeper.h"

#include <stdio.h>
#include <stdlib.h>
#include <MacMemory.h>

static const char *gBoard;
static int gBoardSize;
static int gBombsRemaining;
static int gUnknownRemaining;
static MinesweeperMoveProc gMakeMove;
static int gMaxCell;
static Boolean gGameOver;

// arguments for MakeMove function
#define kCheck false
#define kMarkBomb true
 
// the main data structure: a set of cells
#define kMaxNeighbors 12
typedef struct Set {
    int memberCount;
    int bombCount;
    int members[kMaxNeighbors];
} Set;

// the list of sets, allocated size grows as needed
static int gSetCount;
static int gSetAlloc;
static Handle gSetHandle;
static Set *gSets;

// list of sets that have been touched,
// and thus may need cleaning.
// Fixed size is OK because it's ok if everything can't be recorded
#define kStackSize 1000
static int gTouchedStack[kStackSize];
static int gTouchedCount;

// utilities
#define AsSetIndex(row, col)    (((row) * gBoardSize) + (col))
#define SetMemberRow(member)    ((member) / gBoardSize)
#define SetMemberCol(member)    ((member) % gBoardSize)
#define CellValue(row,col) (gBoard[(row)*(gBoardSize) + (col)])

InitSets
// alloc set list
static void InitSets() {
    gSetAlloc = 1000;    // will grow as needed
    gSetHandle = NewHandle(sizeof(Set) * gSetAlloc);
    HLock(gSetHandle);
    gSets = (Set *) *gSetHandle;
    gSetCount = 0;
    
    gTouchedCount = 0;
}

DisposeSets
static void DisposeSets() {
    DisposeHandle(gSetHandle);
}

NoteSetAdded
// set has been added, so it needs to be checked for simplication
static void NoteSetAdded(int s) {
    if (gTouchedCount < kStackSize)
        gTouchedStack[gTouchedCount++] = s;
}

NoteSetReduced
// set has been reduced, so it needs to be checked for simplication
static void NoteSetReduced(int s) {
    int i;
    for (i = 0; i < gTouchedCount; i++) {
        if (gTouchedStack[i] == s)
            return;    // already there, so don't add
    }
    if (gTouchedCount < kStackSize)
        gTouchedStack[gTouchedCount++] = s;
}

PopTouched
// remove a set to be checked
static int PopTouched() {
    if (gTouchedCount > 0)
        return gTouchedStack[—gTouchedCount];
    return 0;
}

NoteSetReplaced
// set has been replaced by another, so any occurrence
// of ‘from' set need to be changed.
static void NoteSetReplaced(int from, int to) {
    int i;
    for (i = 0; i < gTouchedCount; i++) {
        if (gTouchedStack[i] == to) {
            gTouchedStack[i] = gTouchedStack[gTouchedCount - 1];
            gTouchedCount -= 1;
            i -= 1;
        }
        else if (gTouchedStack[i] == from)
            gTouchedStack[i] = to;
    }
}

#define kEqual 0
#define kSubset 1
#define kSuperset 2
#define kDisjoint 3

CompareSets
// compare sets; return equal, subset, superset, or disjoint
static int CompareSets(Set * a, Set * b) {
    int * ap = a->members;
    int * bp = b->members;
    int * aend = ap + a->memberCount;
    int * bend = bp + b->memberCount;
    int am, bm;
    if (a->memberCount == b->memberCount && 
               a->bombCount == b->bombCount) {
                 // may be equal
        while (ap != aend && bp != bend) {
            am = *ap++;
            bm = *bp++;
            if (am != bm)
                return kDisjoint;
        }
        if (ap != aend || bp != bend)
            return kDisjoint;
        return kEqual;
    }
    else if (a->memberCount > b->memberCount && 
                        a->bombCount >= b->bombCount) {
                    // may be superset
        while (ap != aend && bp != bend) {
            am = *ap++;
            bm = *bp++;
            while (am < bm && ap != aend)
                am = *ap++;
            if (am != bm)
                return kDisjoint;
        }
        if (bp != bend)
            return kDisjoint;
        return kSuperset;
    }
    else if (a->memberCount < b->memberCount && 
                           a->bombCount <= b->bombCount) {
                    // may be subset
        while (ap != aend && bp != bend) {
            am = *ap++;
            bm = *bp++;
            while (am > bm && bp != bend)
                bm = *bp++;
            if (am != bm)
                return kDisjoint;
        }
        if (ap != aend)
            return kDisjoint;
        return kSubset;
    }
    else
        return kDisjoint;
}

SubtractSet
// a = a - b; b must be a proper subset of a
static void SubtractSet(Set * a, Set * b) {
    int * ap1 = a->members;
    int * ap2 = a->members;
    int * bp = b->members;
    int * aend = ap1 + a->memberCount;
    int * bend = bp + b->memberCount;
    int am, bm;
    while (bp != bend) {
        am = *ap2++;
        bm = *bp++;
        while (am < bm && ap2 != aend) {
            *ap1++ = am;
            am = *ap2++;
        }
    }
    while (ap2 != aend) {
        *ap1++ = *ap2++;
    }
    a->memberCount -= b->memberCount;
    a->bombCount -= b->bombCount;
}

SimplifySubsets
// Check the modified set against all others.
// Remove if it is equal to one.
// If it has a subset or superset,
// replace the superset with the difference between the sets.
static void SimplifySubsets(Set * modifiedSet) {
    int s;
    Set * set = gSets;
    int answer;
    for (s = 0; s < gSetCount; s++, set ++) {
        if (set == modifiedSet)
            continue;
        answer = CompareSets(set, modifiedSet);
        if (answer == kEqual) {
            gSetCount -= 1;
            *set = gSets[gSetCount];
            NoteSetReplaced(gSetCount, s);
            break;
        }
        else if (answer == kSubset) {
            SubtractSet(modifiedSet, set);
            NoteSetReduced(modifiedSet - gSets);
        }
        else if (answer == kSuperset) {
            SubtractSet(set, modifiedSet);
            NoteSetReduced(set - gSets);
        }
    }
}

SimplifySets
// simplify all sets that have been touched
static Boolean SimplifySets() {
    if (gTouchedCount != 0) {
        while (gTouchedCount != 0)
            SimplifySubsets(&gSets[PopTouched()]);
        return true;
    }
    return false;
}

FindSetMember
// find the given cell in the given set;
// return -1 if not found, otherwise return index
static int FindSetMember(Set * set, int member) {
    int cellCount = set->memberCount;
    int * cells = set->members;
       //fixme — use binary search for larger sets
    int m = 0;
    if (member >= cells[cellCount/2]) {
        m = cellCount/2;
        cells += m;
    }
    for (; m < cellCount; m++, cells++) {
        if (member == *cells)
            return m;
        if (member < *cells)
            break;
    }
    return -1;    // not found
}

AllocSet
// make sure there is space for another set
static Set * AllocSet() {
    if (gSetCount >= gSetAlloc) {
        // need to allocate more sets
        gSetAlloc = gSetCount * 3 / 2;
        HUnlock(gSetHandle);
        SetHandleSize(gSetHandle, sizeof(Set) * gSetAlloc);
        if (MemError() != noErr) {
            printf("\n\nTROUBLE MISTER - OUT OF MEMORY\n\n");
            gGameOver = true;
            gSetCount /= 2;
        }
        HLock(gSetHandle);
        gSets = (Set *) *gSetHandle;
    }
    gSetCount += 1;
    return &gSets[gSetCount - 1];
}

AddNewSet
// add a set for the newly revealed cell, being sure
// to add neighbor cells in order of index value
static Set * AddNewSet(int row, int col, int bombCount) {
    Set * set = AllocSet();
       // whether this triangle is up or down pointing:
    int down = ((row+col) & 1);
    int up = 1 - down;
    int r;
    int c;
    int clo, chi;
    int *memp = set->members;
    int index;
       // row above triangle
    if (row != 0) {
        r = row - 1;
        clo = col - 1 - down;
        if (clo < 0)
            clo = 0;
        chi = col + 1 + down;
        if (chi >= gBoardSize)
            chi = gBoardSize - 1;
        index = AsSetIndex(r, clo);
        for (c = clo; c <= chi; c++, index++) {
            int value = gBoard[index];
            if (value == kUnknown)
                *memp++ = index;
            else if (value == kBomb)
                bombCount -= 1;
        }
    }
    
       // row of this cell
    r = row;
    clo = col - 2;
    if (clo < 0)
        clo = 0;
    chi = col + 2;
    if (chi >= gBoardSize)
        chi = gBoardSize - 1;
    index = AsSetIndex(r, clo);
    for (c = clo; c <= chi; c++, index++) {
        int value = gBoard[index];
        if (value == kUnknown)
            *memp++ = index;
        else if (value == kBomb)
            bombCount -= 1;
    }

       // row below
    if (row != gBoardSize - 1) {
        r = row + 1;
        clo = col - 1 - up;
        if (clo < 0)
            clo = 0;
        chi = col + 1 + up;
        if (chi >= gBoardSize)
            chi = gBoardSize - 1;
        index = AsSetIndex(r, clo);
        for (c = clo; c <= chi; c++, index++) {
            int value = gBoard[index];
            if (value == kUnknown)
                *memp++ = index;
            else if (value == kBomb)
                bombCount -= 1;
        }
    }
    set->memberCount = memp - set->members;
    set->bombCount = bombCount;
    if (set->memberCount == 0) {
              // cancel the add
        gSetCount -= 1;
        set = 0;
    }
    return set;
}

CleanSets
// remove already revealed cells from all sets;
// helps here that set uses same index that board does,
// so it's efficient to look up cell in board.
static Boolean CleanSets() {
    Boolean cleaned = false;
    int s;
    Set * set = gSets;
    for (s = 0; s < gSetCount; s++, set ++) {
        int * p1 = set->members;
        int * p2 = set->members;
        int * end = p1 + set->memberCount;
        int member;
        int value = kUnknown;
                 // move through members until a revealed one is found
        while (p2 != end) {
            member = *p2++;
            value = gBoard[member];
            if (value == kUnknown)
                p1 += 1;
            else {
                set->memberCount -= 1;
                cleaned = true;
                if (value == kBomb)
                    set->bombCount -= 1;
                break;
            }
        }
        // copy members after any revealed members
        while (p2 != end) {
            member = *p2++;
            value = gBoard[member];
            if (value == kUnknown)
                *p1++ = member;
            else {
                set->memberCount -= 1;
                cleaned = true;
                if (value == kBomb)
                    set->bombCount -= 1;
            }
        }
    }
    return cleaned;
}

UpdateSets
// add set for new cell
static void UpdateSets(int row, int col) {
    char value = CellValue(row, col);
    if (value != kBomb) {    // value == n
        // add a new set for this info
        Set * set = AddNewSet(row, col, value);
        if (set != 0)
            NoteSetAdded(set - gSets);
    }
}

MoveAndUpdate
// makes a move via callback and adds set if necessary
static void MoveAndUpdate(int row, int col, Boolean checkOrMark) {
    Boolean youLose = false;
    Boolean youWin = false;
    if (gGameOver)
        return;    // game already over
    gMakeMove(row, col, &gBombsRemaining, checkOrMark, &youLose, 
                                       &youWin);
    gUnknownRemaining -= 1;
    if (youLose || youWin)
        gGameOver = true;    // to escape main loop
    else
        UpdateSets(row, col);
}

ExploreSafely
// make safe moves.  That is, known bombs and known non-bombs.
static Boolean ExploreSafely() {
    Boolean explored = false;
    int s;
    Set * set = gSets;

    for (s = 0; s < gSetCount;) {
        // safe to explore if either no bombs or all bombs
        if (set->bombCount == 0 || 
                        set->bombCount == set->memberCount) {
            int m;
            Boolean checkOrMark = set->bombCount != 0;    
                                    // false means check
            explored = true;
            for (m = 0; m < set->memberCount; m++) {
                int member = set->members[m];
                MoveAndUpdate(SetMemberRow(member),
                        SetMemberCol(member), checkOrMark);
            }
                           // remove this set
            gSetCount -= 1;
            *set = gSets[gSetCount];
            NoteSetReplaced(gSetCount, s);
        }
        else {
            s += 1;
            set += 1;
        }
    }
    return explored;
}

FindInOtherSet
// Look for the given member in all sets except
// for the given one.
static int FindInOtherSet(int knownMember, Set * knownSet) {
    int s;
    Set * set = gSets;
    for (s = 0; s < gSetCount; s++, set ++) {
        int m = FindSetMember(set, knownMember);
        if (m >= 0 && set != knownSet)
            return m;
    }
    return -1;
}

PrayInSet
// Pick a random cell from the given set and reveal it.
// set == 0 means pick from enire board of unknowns.
static void PrayInSet(Set * set, Boolean checkOrMark) {
    int row;
    int col;
    if (set == 0) {
        if (gUnknownRemaining < gMaxCell / 8) {
                        // pick first unknown
            int i;
            for (i = 0; i < gMaxCell; i++) {
                if (gBoard[i] == kUnknown) {
                                            // found an unknown cell, so test it
                    row = i / gBoardSize;
                    col = i % gBoardSize;
                    break;
                }
            }
        }
        else {
                        // pick one at random until an unknown is found
            while (true) {
                int cell = rand() % gMaxCell;
                if (gBoard[cell] == kUnknown) {
                                      // found an unknown cell, so test it
                    row = cell / gBoardSize;
                    col = cell % gBoardSize;
                    break;
                }
            }
        }
    }
    else {
                    // prefer last member — quickest to remove
        int m = set->memberCount - 1;
                    // also prefer cell that is not within another set,
                    // this that set likely has worse odds.
                    // this is costly, but it does make it more likely
                    // of finding a correct solution.
        while (m > 0 && FindInOtherSet(set->members[m],set)>=0)
            m -= 1;
        
        row = SetMemberRow(set->members[m]);
        col = SetMemberCol(set->members[m]);
    }
    MoveAndUpdate(row, col, checkOrMark);
}

Pray
#define kOddsScale 4096

// Find the set with the best oods for guessing and make the guess.
static void Pray() {
    Set * praySet = 0;
    int prayOdds = kOddsScale * 
                           (gUnknownRemaining - gBombsRemaining)
                         / gUnknownRemaining;
    Boolean prayCheckOrMark = kCheck;
    int s;
    if (prayOdds < 0.5) {
        prayOdds = kOddsScale * gBombsRemaining / 
                                       gUnknownRemaining;
        prayCheckOrMark = kMarkBomb;
    }
    if (gUnknownRemaining * 2 < gMaxCell)
        prayOdds = 0;    // too few unknown to be accurate
    for (s = 0; s < gSetCount; s++) {
        Set * set = &gSets[s];
        int cells = set->memberCount;
        int bombs = set->bombCount;
        int odds = kOddsScale * (cells - bombs) / cells;
        Boolean checkOrMark = kCheck;
        if (odds < 0.5) {
            odds = kOddsScale * bombs / cells;
            checkOrMark = kMarkBomb;
        }
        if (odds >= prayOdds) {
            praySet = set;
            prayOdds = odds;
            prayCheckOrMark = checkOrMark;
        }
    }
    PrayInSet(praySet, prayCheckOrMark);
}

IntersetSets
// returns number of common members
// assumes each set has at least two members
static int IntersetSets(Set * a, Set * b, Set * common) {
    int * ap = a->members;
    int * bp = b->members;
    int * cp = common->members;
    int * aend = ap + a->memberCount;
    int * bend = bp + b->memberCount;
    int am, bm;
    int n = -1;
    if (*ap > *(bend-1) || *bp > *(aend-1))
        return 0;
    am = 0;
    bm = 0;
    while (true) {
        if (am == bm) {
            if (n >= 0)
                *cp++ = am;
            n += 1;
            if (ap == aend)
                break;
            am = *ap++;
            if (bp == bend)
                break;
            bm = *bp++;
        }
        else if (am < bm) {
            if (ap == aend)
                break;
            am = *ap++;
        }
        else if (am > bm) {
            if (bp == bend)
                break;
            bm = *bp++;
        }
    }
    common->memberCount = n;
    common->bombCount = 1;
    return n;
}

RemoveIntersection
// Remove the common subset from A and B, add it as a new set
static void RemoveIntersection(Set *a, Set *b, Set * common) {
    Set * set = AllocSet();
    *set = *common;
    NoteSetAdded(set - gSets);
    SubtractSet(a, common);
    NoteSetReduced(a - gSets);
    SubtractSet(b, common);
    NoteSetReduced(b - gSets);
}

EliminateIntersections
// eliminate intersections that fit a specific pattern
// consisting one dense set and one sparse set
static Boolean EliminateIntersections() {
    int s;
    Set * set = gSets;
    Set common;
    if (gUnknownRemaining > gMaxCell - 10)
        return false;    // don't bother early on in game
    for (s = 0; s < gSetCount; s++, set ++) {
        if (set->bombCount >= 3
                && set->memberCount - set->bombCount <= 2) {
                       // found a crowded set (eg, 4 bombs out of 6)
                         // now look for an overlapping sparse one
            int needed = set->memberCount - set->bombCount + 1;
            int sb;
            Set * setb = gSets;
            for (sb = 0; sb < gSetCount; sb++, setb ++) {
                if (setb->bombCount == 1
                        && setb->memberCount > needed) {
                    int actual = IntersetSets(set,setb,&common);
                    if (actual >= needed) {
                                                   // we don't have to pray after all
                RemoveIntersection(set, setb, &common);
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

PlayMinesweeper
// explore, clean, simplify, pray
void PlayMinesweeper (
    int boardSize,
    /* number of rows/columns in board */
    int numberOfBombs,
    /* number of bombs in board */
    const char *board,
    /* board[row*boardSize + col] is board element (row,col) */
    MinesweeperMoveProc MakeMove
    /* procedure for reporting moves */
    /* MakeMove updates elements of board */
) {
    gBoardSize = boardSize;
    gBoard = board;
    gBombsRemaining = numberOfBombs;
    gUnknownRemaining = boardSize * boardSize;
    gMakeMove = MakeMove;
    gMaxCell = boardSize * boardSize;
    gGameOver = false;
    InitSets();
    
    while (!gGameOver) {
        if (!ExploreSafely()
                && !CleanSets()
                && !SimplifySets()
                && !EliminateIntersections()
                ) {
            Pray();
        }
    }
    DisposeSets();
}


 
AAPL
$102.22
Apple Inc.
+1.16
MSFT
$46.89
Microsoft Corpora
-0.18
GOOG
$582.60
Google Inc.
-4.78

MacTech Search:
Community Search:

Software Updates via MacUpdate

GarageSale 6.8 - Create outstanding eBay...
GarageSale is a slick, full-featured client application for the eBay online auction system. Create and manage your auctions with ease. With GarageSale, you can create, edit, track, and manage... Read more
ScreenFlow 4.5.3 - Create screen recordi...
Save 5% with the MacUpdate coupon code: 68031AE15F -- Buy now! ScreenFlow is powerful, easy-to-use screencasting software for the Mac. With ScreenFlow you can record the contents of your entire... Read more
NeoOffice 2014.3 - Mac-tailored, OpenOff...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
Typinator 6.2 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
PopChar X 6.7 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more
Evernote 5.6.0 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
Monosnap 2.2.2 - Versatile screenshot ut...
Monosnap allows you to save screenshots easily, conveniently, and quickly, sharing them with friends and colleagues at once. It's the ideal choice for anyone who is looking for a smart and fast... Read more
Tunnelblick 3.4beta36 - GUI for OpenVPN...
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
SoftRAID 5.0.4 - High-quality RAID manag...
SoftRAID allows you to create and manage disk arrays to increase performance and reliability. SoftRAID's intuitive interface and powerful feature set makes this utility a must have for any Mac OS X... Read more
Audio Hijack Pro 2.11.3 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more

Latest Forum Discussions

See All

PlayHaus Review
PlayHaus Review By Amy Solomon on September 23rd, 2014 Our Rating: iPad Only App - Designed for the iPad PlayHaus is a interesting, stylish app for young children, full of cause-and-effect interactions.   | Read more »
Astropolo Review
Astropolo Review By Amy Solomon on September 23rd, 2014 Our Rating: Universal App - Designed for iPhone and iPad Astropolo is a space-themed children’s app with a great sense of style.   | Read more »
New E*TRADE Update Includes Touch ID and...
New E*TRADE Update Includes Touch ID and Home Screen Widget for iOS 8 Posted by Jessica Fisher on September 23rd, 2014 [ permalink ] | Read more »
Cupcake Carnival Review
Cupcake Carnival Review By Jennifer Allen on September 23rd, 2014 Our Rating: :: SAME OLDUniversal App - Designed for iPhone and iPad Cupcake Carnival does all the right match-3 things but it’s a format we’ve seen a little too... | Read more »
This Week at 148Apps: September 15-19, 2...
Expert App Reviewers   So little time and so very many apps. What’s a poor iPhone/iPad lover to do? Fortunately, 148Apps is here to give you the rundown on the latest and greatest releases. And we even have a tremendous back catalog of reviews; just... | Read more »
Kitty Powers’ Matchmaker – Tips, Tricks,...
Hey There, Kittens: | Read more »
Goblin Sword Review
Goblin Sword Review By Andrew Fisher on September 22nd, 2014 Our Rating: :: RETRO GOODNESSUniversal App - Designed for iPhone and iPad Fun visuals, good music, engaging level design, and lots of content make Goblin Sword an... | Read more »
Major New Update for CSR Racing Adds Fer...
Major New Update for CSR Racing Adds Ferrari and Multiplaye​r Posted by Jessica Fisher on September 22nd, 2014 [ permalink ] | Read more »
Veditor Review
Veditor Review By Jennifer Allen on September 22nd, 2014 Our Rating: :: PIMP YOUR VIDEOUniversal App - Designed for iPhone and iPad Want to add stickers and music to your videos? Veditor can do that easily.   | Read more »
1849′s Nevada Silver DLC is Still Search...
A few months ago, I took a look at 1849 from SomaSim. This Gold Rush-themed city builder for iPad had a fair bit going for it, but lacked in a few crucial areas to make it a true stand-out on the App Store. SomaSim has since added in a sandbox mode... | Read more »

Price Scanner via MacPrices.net

Check Apple prices on your device with iTracx
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
Refurbished 2013 MacBook Pros available for u...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available starting at $929. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook Pros (4GB RAM/... Read more
New iPhones Score Big in SquareTrade Breakabi...
SquareTrade has announced the iPhone 6 and its larger sibling, iPhone 6 Plus, performed impressively in Breakability testing, and each carries the top Breakability Score in their respective category... Read more
10 Million + First Weekend Sales Set New iPho...
Apple has announced it sold over 10 million new iPhone 6 and iPhone 6 Plus models, a new record, just three days after the launch on September 19. iPhone 6 and iPhone 6 Plus are now available in the... Read more
Betty Crocker Launches New Cookbook for iOS
Betty Crocker, a General Mills brand, an established food industry leader, has announced its free digital cookbook app has been refreshed to make cooking with iPhone, iPad and iPod touch even easier... Read more
Apple restocks some refurbished 2014 MacBook...
The Apple Store has restocked some Apple Certified Refurbished 2014 MacBook Airs, with prices starting at $769. An Apple one-year warranty is included with each MacBook, and shipping is free. These... Read more
13-inch 128GB MacBook Air on sale for $949, s...
B&H Photo has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $949.99 including free shipping plus NY tax only. Their price is $50 off MSRP. B&H will also include free copies of... Read more
Apple offering free $25 iTunes Gift Card with...
The Apple Store is offering a free $25 iTunes Gift Card with the purchase of a $99 Apple TV for a limited time. Shipping is free. Read more
Apple refurbished iPod touch available for up...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Most colors are... Read more
iFixIt Tears Down iPhone 6; Awards Respectabl...
iFixit notes that even the smaller 4.7″ iPhone 6 is a giant among iPhones; so big that Apple couldn’t fit it into the familiar iPhone form factor. In a welcome reversal of a recent trend to more or... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.