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


 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Cyberduck 4.7.1 - FTP and SFTP browser....
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
PDFpen 7.2 - Edit and annotate PDFs with...
We're also offering PDFpenPro for 30% off! PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even... Read more
Skype 7.9.746 - Voice-over-internet phon...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
Apple GarageBand 10.1 - Complete recordi...
The new GarageBand is a whole music creation studio right inside your Mac -- complete with keyboard, synths, orchestral and percussion instruments, presets for guitar and voice, an entirely... Read more
Duplicate Annihilator 5.7.7 - Find and d...
Duplicate Annihilator takes on the time-consuming task of comparing the images in your iPhoto library using effective algorithms to make sure that no duplicate escapes. Duplicate Annihilator... Read more
OS X Server 4.1.3 - For OS X 10.10 Yosem...
Designed for OS X and iOS devices, OS X Server makes it easy to share files, schedule meetings, synchronize contacts, develop software, host your own website, publish wikis, configure Mac, iPhone,... Read more
Firefox 39.0 - Fast, safe Web browser. (...
Firefox offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and casual... Read more
pwSafe 4.1 - Secure password management...
pwSafe provides simple and secure password management across devices and computers. pwSafe uses iCloud to keep your password databases backed-up and synced between Macs and iOS devices. It is... Read more
Kodi 15.0.rc1 - Powerful media center to...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
Coda 2.5.11 - One-window Web development...
Coda is a powerful Web editor that puts everything in one place. An editor. Terminal. CSS. Files. With Coda 2, we went beyond expectations. With loads of new, much-requested features, a few surprises... Read more

This Week at 148Apps: June 29-July 3, 20...
Into July With 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above the... | Read more »
Sonic Runners Guide
Despite its flaws, Sonic Runners' platforming action is actually quite fun. Though it can be a little more complicated than old-school Sonic games. Here's how to make sure you're up to speed when jumping in. [Read more] | Read more »
Rage of Bahamut is Giving Almost All of...
The App Store isn't what it used to be back in 2012, so it's not unexpected to see some games changing their structures with the times. Now we can add Rage of Bahamut to that list with the recent announcement that the game is severely cutting back... | Read more »
Adventures of Pip (Games)
Adventures of Pip 1.0 Device: iOS iPhone Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ** ONE WEEK ONLY — 66% OFF! *** “Adventures of Pip is a delightful little platformer full of charm, challenge and impeccable... | Read more »
Divide By Sheep - Tips, Tricks, and Stre...
Who would have thought splitting up sheep could be so involved? Anyone who’s played Divide by Sheep, that’s who! While we’re not about to give you complete solutions to everything (because that’s just cheating), we will happily give you some... | Read more »
NaturalMotion and Zynga Have Started Tea...
An official sequel to 2012's CSR Racing is officially on the way, with Zynga and NaturalMotion releasing a short teaser trailer to get everyone excited. Well, as excited as one can get from a trailer with no gameplay footage, anyway. [Read more] | Read more »
Grab a Friend and Pick up Overkill 3, Be...
Overkill 3 is a pretty enjoyable third-person shooter that was sort of begging for some online multiplayer. Fortunately the begging can stop, because its newest update has added an online co-op mode. [Read more] | Read more »
Scanner Pro's Newest Update Adds Au...
Scanner Pro is one of the most popular document scanning apps on iOS, thanks in no small part to its near-constant updates, I'm sure. Now we're up to update number six, and it adds some pretty handy new features. [Read more] | Read more »
Heroki (Games)
Heroki 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: CLEAR THE SKIES FOR A NEW HERO!The peaceful sky village of Levantia is in danger! The dastardly Dr. N. Forchin and his accomplice,... | Read more »
Wars of the Roses (Games)
Wars of the Roses 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

Apple refurbished Mac minis available startin...
The Apple Store has Apple Certified Refurbished 2014 Mac minis available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $80 off... Read more
College Student Deals: Additional $100 off Ma...
Take an additional $100 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through August 8, 2015. Anyone with a valid .EDU email address can take... Read more
Sky Atlas Star Walk 2 App For iPhone And iPa...
Vito Technology, developer of educational apps for Android and iOS, is for a limited time offering free of charge their Star Walk 2, the next generation of the company’s best-selling stargazing guide... Read more
13-inch 1.6GHz MacBook Air on sale for $849,...
Amazon has the 2015 13″ 1.6GHz/128GB MacBook Air on sale for $849.99 including free shipping. Their price is $150 off MSRP, and it’s the lowest price available for this model. Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
Adorama has the 13-inch 2.5GHz MacBook Pro on sale for $999 including free shipping plus NY & NJ sales tax only. Their price is $100 off MSRP. Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
15-inch Retina MacBook Pros on sale for up to...
B&H Photo has new 2015 15″ Retina MacBook Pros on sale for up to $225 off MSRP including free shipping plus NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1819 $180 off - 15″ 2.5GHz Retina... Read more
RamDisk4Mac App Helps Run Your Mac Faster And...
Ever use a RAM disk? If you’ve come to the Mac in the OS X era, likely not. The Classic Mac OS had a RAM disk function built-in, but that was dropped in the conversion to OS X. What is a RAM disk?... Read more
13-inch 1.6GHz MacBook Air on sale for $849,...
Best Buy has the 2015 13″ 1.6GHz/128GB MacBook Air on sale for $849.99 on their online store this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders... Read more
Apple Refurbished iMacs available for up to $...
The Apple Store has Apple Certified Refurbished iMacs available for up to $380 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $1949 $... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Senior Payments Security Manager - *Apple*...
**Job Summary** Apple , Inc. is looking for a highly motivated, innovative and hands-on senior payments security manager to join the Apple Pay security team. You will Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Sr. Payment Program Manager, *Apple* Pay -...
**Job Summary** Apple Pay is an exciting environment and a…devices in a simple, private and secure way. The Apple Pay Team is looking for an experienced Senior Read more
Project Manager - *Apple* Pay Security - Ap...
**Job Summary** The Apple Pay Security team is seeking a highly organized, results-driven Project Manager to drive the development of Apple Pay Security. If you are Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.