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

Yasu 4.0.0 β - System maintenance app; p...
Yasu was created with System Administrators who service large groups of workstations in mind, Yasu (Yet Another System Utility) was made to do a specific group of maintenance tasks quickly within a... Read more
Skype 7.37.0.178 - Voice-over-internet p...
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
EtreCheck 3.0.5 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
Amadeus Pro 2.3.1 - Multitrack sound rec...
Amadeus Pro lets you use your Mac computer for any audio-related task, such as live audio recording, digitizing tapes and records, converting between a variety of sound formats, etc. Thanks to its... Read more
NeoFinder 6.9.3 - Catalog your external...
NeoFinder (formerly CDFinder) rapidly organizes your data, either on external or internal disks, or any other volumes. It catalogs all your data, so you stay in control of your data archive or disk... Read more
WhatsApp 0.2.1880 - Desktop client for W...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
Hazel 4.0.6 - Create rules for organizin...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a familiar... Read more
Apple iBooks Author 2.5 - Create and pub...
Apple iBooks Author helps you create and publish amazing Multi-Touch books for iPad. Now anyone can create stunning iBooks textbooks, cookbooks, history books, picture books, and more for iPad. All... Read more
MYStuff Pro 2.0.26 - $39.99
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
MarsEdit 3.7.8 - Quick and convenient bl...
MarsEdit is a blog editor for OS X that makes editing your blog like writing email, with spell-checking, drafts, multiple windows, and even AppleScript support. It works with with most blog services... Read more

How to get past Vulture Island's tr...
Vulture Island is a colorful and quirky mish-mash of platforming and puzzles. It’s creative and fresh, but sometimes the game can throw a curveball at you, leaving you stuck as to how you should progress. These tips will help you explore smoothly... | Read more »
The new Clash of Kings is just for Weste...
If you’ve played the original Clash of Kings, you’ll probably recognise the city building, alliance forging and strategic battles in Clash of Kings: The West. What sets this version apart is that it’s tailor made for a Western audience and the... | Read more »
Frost - Survival card game (Games)
Frost - Survival card game 1.12.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.12.1 (iTunes) Description: *Warning: the game will work on iPhone 5C and above and iPad Pro / 4. Other devices are not supported* | Read more »
How to build and care for your team in D...
Before you hit the trail and become a dog sledding legend, there’s actually a fair bit of prep work to be done. In Dog Sled Saga, you’re not only racing, you’re also building and caring for a team of furry friends. There’s a lot to consider—... | Read more »
How to win every race in Dog Sled Saga
If I had to guess, I’d say Dog Sled Saga is the most adorable racing game on the App Store right now. It’s a dog sled racing sim full of adorable, loyal puppies. Just look at those fluffy little tails wagging. Behind that cute, pixelated facade is... | Read more »
Let the war games commence in Gunship Ba...
Buzz Lightyear famously said, “This isn’t flying, this is falling – with style!” In the case of Gunship Battle: Second War, though, this really is flying - with style! The flight simulator app from Joycity puts you in control of 20 faithfully... | Read more »
How to get a high score in Fired Up
Fired Up is Noodlecake Games’ high score chasing, firefighting adventure. You take control of a wayward firefighter who propels himself up the side of a highrise with blasts of water. Sound silly? It is. It’s also pretty difficult. You can’t... | Read more »
NBA 2K17 (Games)
NBA 2K17 1.0 Device: iOS iPhone Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: Following the record-breaking launch of NBA 2K16, the NBA 2K franchise continues to stake its claim as the most authentic sports video... | Read more »
Dog Sled Saga (Games)
Dog Sled Saga 1.0.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.1 (iTunes) Description: A game by Dan + Lisa As a rookie musher, foster a dogsledding team whose skills will grow if they're treated right. Week by... | Read more »
60 Seconds! Atomic Adventure (Games)
60 Seconds! Atomic Adventure 1.2 Device: iOS Universal Category: Games Price: $2.99, Version: 1.2 (iTunes) Description: 60 Seconds! is a dark comedy atomic adventure of scavenge and survival. Collect supplies and rescue your family... | Read more »

Price Scanner via MacPrices.net

21-inch iMacs on sale for up to $120 off MSRP
B&H Photo has 21″ iMacs on sale for up to $120 off MSRP including free shipping plus NY sales tax only: - 21″ 3.1GHz iMac 4K: $1379 $120 off MSRP - 21″ 2.8GHz iMac: $1199.99 $100 off MSRP - 21″ 1... Read more
13-inch 2.7GHz/256GB Retina MacBook Pro on sa...
Amazon.com has the 13″ 2.7GHz/256GB Retina Apple MacBook Pro on sale for $151 off MSRP including free shipping: - 13″ 2.7GHz/256GB Retina MacBook Pro (sku MF840LL/A): $1348 $151 off MSRP Read more
Apple TVs on sale for up to $50 off MSRP
Best Buy has 32GB and 64GB Apple TVs on sale for $40-$50 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store... Read more
Apple refurbished 13-inch Retina MacBook Pros...
Apple has Certified Refurbished 13″ Retina MacBook Pros available for up to $270 off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free: - 13″ 2.7GHz... Read more
Duplicate Sweeper Free On Mac App Store For O...
To celebrate the launch of Apple’s latest macOS Sierra, Stafford, United Kingdom based Wide Angle Software has announced that its duplicate file finder software, Duplicate Sweeper, is now available... Read more
13-inch Retina MacBook Pros on sale for up to...
B&H Photo has 13″ Retina Apple MacBook Pros on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1174.99 $125 off MSRP - 13... Read more
Evidence Surfaces Pointing To New A10X Chip F...
Citing a job description for a Project Lead position at Apple’s Austin, Texas engineering labs, Motley Fool’s Ashraf Eassa deduces that development is progressing well on Apple’s next-generation in-... Read more
Check Print’R for macOS Allows Anyone to Easi...
Delaware-based Match Software has announced the release and immediate availability of Check Print’R 3.21, an important update to their easy-to-use check printing application for macOS. Check Print’R... Read more
Apple refurbished 11-inch MacBook Airs availa...
Apple has Certified Refurbished 11″ MacBook Airs (the latest models), available for up to $170 off the cost of new models. An Apple one-year warranty is included with each MacBook, and shipping is... Read more
Apple refurbished 15-inch Retina MacBook Pros...
Apple has Certified Refurbished 2015 15″ Retina MacBook Pros available for up to $380 off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free: - 15″ 2... Read more

Jobs Board

Sr. *Apple* Mac Engineer - Net2Source Inc....
…staffing, training and technology. We have following position open with our client. Sr. Apple Mac Engineer6+ Months CTH Start date : 19th Sept Travelling Job If Read more
*Apple* Retail - Multiple Positions-Norfolk,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Restaurant Manager (Neighborhood Captain) - A...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
Lead *Apple* Solutions Consultant - Apple (...
# Lead Apple Solutions Consultant Job Number: 51829230 Detroit, Michigan, United States Posted: Sep. 19, 2016 Weekly Hours: 40.00 **Job Summary** The Lead ASC is an Read more
US- *Apple* Store Leader Program - Apple (Un...
…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 Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.