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
$113.99
Apple Inc.
+1.98
MSFT
$47.88
Microsoft Corpora
-0.26
GOOG
$534.03
Google Inc.
+5.26

MacTech Search:
Community Search:

Software Updates via MacUpdate

Google Drive 1.18.7821.2489 - File backu...
Google Drive is a place where you can create, share, collaborate, and keep all of your stuff. Whether you're working with a friend on a joint research project, planning a wedding with your fiancé, or... Read more
Eye Candy 7.1.0.1203 - 30 professional P...
Eye Candy renders realistic effects that are difficult or impossible to achieve in Photoshop alone, such as Fire, Chrome, and the new Lightning. Effects like Animal Fur, Smoke, and Reptile Skin are... Read more
MegaSeg 5.9.4 - Professional MP3 DJ appl...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
Parallels Desktop 10.1.2 - Run Windows a...
Parallels Desktop is simply the world's bestselling, top-rated, and most trusted solution for running Windows applications on your Mac. With Parallels Desktop for Mac, you can seamlessly run both... Read more
GarageSale 6.9.1 - Create outstanding eB...
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
Quicksilver 1.2.2 - Application launcher...
Quicksilver is a light, fast and free Mac application that gives you the power to control your Mac with keystrokes alone. Quicksilver allows you to find what you need quickly and easily, then act... Read more
Mac DVDRipper Pro 5.0.1 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
ClamXav 2.7 - Free virus checker, based...
ClamXav is a free virus checker for OS X. It uses the tried, tested, and very popular ClamAV open source antivirus engine as a back end. I hope you like and use ClamXav a lot and that it helps keep... Read more
FoldersSynchronizer 4.2 - Synchronize or...
FoldersSynchronizer is a popular and useful utility that synchronizes and backs-up files, folders, disks and boot disks. On each session you can apply special options like Timers, Multiple Folders,... Read more
Waltr 1.0.6 - Drag-and-drop any media fi...
WALTR is designed to make it easy to upload and convert any music or video file to an iPad or iPhone format for native playback. It supports a huge variety of media file types, including MP3, MP4,... Read more

Latest Forum Discussions

See All

Forget the Gloves – It’s a Cage Match in...
Forget the Gloves – It’s a Cage Match in Real Boxing’s Underground Update Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] | Read more »
Who Wore it Best? Best of 2014
It’s the end of the year, so it’s time for some arbitrary internet awards! In this wrap-up episode of Who Wore it Best? we present our winners for the best, worst, and flat-out weirdest cloned games that graced the App Store in 2014. [ Who... | Read more »
Now You Can Explore Mayan Temples in Ass...
Now You Can Explore Mayan Temples in Assassin’s Creed Pirates’ Newest Update Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] | Read more »
Soft Design aims to do free-to-play righ...
They say a team is only as big as its fans and that’s also certainly the case with video games, judging from the sales certain AAA ‘heavyweights’ get year-after-year. Soft Design took that principle as a core design philosophy and worked closely... | Read more »
Bogga Christmas Tree
Bogga Christmas Tree By Amy Solomon on December 23rd, 2014 Our Rating: Universal App - Designed for iPhone and iPad Bogga Christmas Tree allows young children to trim a tree, any time or place.   | Read more »
Opera Coast 4.0 Launches on iOS with 4 N...
Opera Coast 4.0 Launches on iOS with 4 New Features Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Cricket Kids: Christmas Presents
Cricket Kids: Christmas Presents By Amy Solomon on December 23rd, 2014 Our Rating: Universal App - Designed for iPhone and iPad Cricket Kids: Christmas Presents allows children to play with digital toys opened for the Christmas... | Read more »
Lara Croft & Tomb Raider Mobile Bund...
Lara Croft & Tomb Raider Mobile Bundle – Only $4.99 Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] Lara Croft is coming to you in | Read more »
SimCity BuildIt Review
SimCity BuildIt Review By Nadia Oxford on December 23rd, 2014 Our Rating: :: BUILDING AN OK TOMORROWUniversal App - Designed for iPhone and iPad SimCity BuildIt is a competent city-building game, but its free-to-play trappings are... | Read more »
SimCity Buildit – Tips, Tricks, and Stra...
Hello, Budding Mayors Want to know what we made of all this upgrading and inevitable waiting? Check out our SimCity BuildIt review! SimCity BuildIt is a city-building game from EA. Your job as mayor is to build houses for people to live in, industry... | Read more »

Price Scanner via MacPrices.net

Sony Fixing To Launch Large-Screen Android Ta...
Digitimes’ Aaron Lee and Joseph Tsai report that Sony, which last February exited the laptop computer market with the sale of its VIAO PC-making unit to a group of JApanese investors, is now expected... Read more
After Christmas sale: 13-inch Retina MacBook...
B&H Photo has new 13″ MacBook Pros on sale for up to $150 off MSRP as part of their Holiday pricing. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.5GHz MacBook Pro: $1043 save... Read more
After Christmas sale: 15-inch Retina MacBook...
Adorama has 15″ Retina MacBook Pros on sale for up to $150 off MSRP. Shipping is free, and Adorama charges NY & NJ sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1899 save $100 - 15″ 2.5GHz... Read more
After Christmas sale: MacBook Airs for up to...
B&H Photo has 2014 MacBook Airs on sale for up to $120 off MSRP, for a limited time, for the Thanksgiving/Christmas Holiday shopping season. Shipping is free, and B&H charges NY sales tax... Read more
Apple now offering Certified Refurbished Mac...
The Apple Store is now offering Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.... Read more
Will Apple Build An A-series ARM Processor Po...
In computer terms, it’s been a very long time since the MacBook Air had a major redesign. More than four years have elapsed since Apple recast what had originally been more a pricy boutique device... Read more
iPhone 6s mini With Four-Inch Screen Rumored...
The Times of India’s Komal Mohan, citing a story in The Electronic Times of Taiwan, says that unnamed upstream supply chain sources report that Apple is gearing up to launch a new 4-inch screen... Read more
What’s The Current Value Of Your iOS Apps?
Basel, Switzerland based ConIT AG has announced AppZapp Notify and its free PC and Mac tool available for download. What is the present value of all my downloaded Apps? With AppZapp Notify, for the... Read more
PhatWare Releases WritePad Pro Advanced iOS W...
PhatWare Corporation has announced immediate availability of WritePad Pro 2.0, its advanced word processing, note-taking, and document management app which also takes full advantage of PhatWare’s... Read more
Last minute gift idea: Send an Apple Store Gi...
Send an Apple Store Gift Card by email this season, perhaps as a last minute Christmas gift. According to Apple, “Apple Store Gift Cards can be used to purchase Apple hardware and accessories at any... Read more

Jobs Board

Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** Being a Business Manager at an Apple Store means you're the catalyst for businesses to discover and leverage the power, ease, and flexibility of Apple Read more
*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
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Store Leader Program (US) - Apple, I...
…Summary Learn and grow as you explore the art of leadership at the Apple Store. You'll master our retail business inside and out through training, hands-on experience, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.