Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


#ActualÁlvaro

Posted 17 April 2013 - 11:44 AM

If you have a time, please try to make graphics explanation of your algorithm.

I am not going to post graphics, but I can show you some crude code:
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
/*
  Convention:
  -3 : outside
  -2 : flag
  -1 : unknown
  >=0 : That many neighbors are bombs
*/

char knowns[12][12] = {
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3},
  {-3,  0,  1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  1,  3, -2, -1,  4, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1,  1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3}
};

int bombs_unaccounted_for = 19;

int main() {
  bool bomb_locations[12][12]={{0}};
  int danger[12][12]={{0}};
  
  std::vector<int> unknowns;
  for (int i=0; i<12; ++i) {
    for (int j=0; j<12; ++j) {
      if (knowns[i][j] == -1)
        unknowns.push_back(i*12+j);
      bomb_locations[i][j] = (knowns[i][j] == -2);
    }
  }
  for (int count=0; count < 10000; ) {
    // Generate bomb distribution
    bool bl_copy[12][12];
    std::memcpy(bl_copy, bomb_locations, sizeof(bl_copy));
    for (int i=0; i<bombs_unaccounted_for; ++i) {
      int j = i + (std::rand() % (unknowns.size()-i));
      std::swap(unknowns[i], unknowns[j]);
      int b = unknowns[i];
      bl_copy[b/12][b] = true;
    }      
    
    // Verify consistency
    for (int i=1; i<11; ++i) {
      for (int j=1; j<11; ++j) {
        if (knowns[i][j] >= 0) {
          int c = 0;
          for (int di=-1; di<=1; di++)
            for (int dj=-1; dj<=1; dj++)
              c += bl_copy[i+di][j+dj];
          if (knowns[i][j] != c)
            goto NOT_CONSISTENT;
        }
      }
    }
    
    std::cout << "count=" << ++count << '\n';
    // Accumulate danger values
    for (int i=0; i<12; ++i) {
      for (int j=0; j<12; ++j) {
        danger[i][j] += bl_copy[i][j];
        std::cout << (knowns[i][j]==-1 ? danger[i][j] : -1) << ' ';
      }
      std::cout << '\n';
    }
  NOT_CONSISTENT:;
  }
}
After running it for a while, it produces this:
count=10000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 1718 1682 1692 1649 1713 1728 1746 1709 -1 
-1 -1 -1 8282 4904 5001 4985 1708 1708 1736 1718 -1 
-1 -1 -1 -1 5059 -1 5072 1702 1724 1721 1712 -1 
-1 5023 4977 1718 4949 5068 4962 1707 1641 1652 1751 -1 
-1 1640 1207 1246 1283 1669 1701 1662 1689 1693 1758 -1 
-1 1671 1264 -1 1188 1714 1657 1663 1722 1672 1678 -1 
-1 1661 1222 1333 1257 1659 1689 1658 1687 1697 1730 -1 
-1 1615 1652 1803 1785 1762 1770 1590 1643 1628 1649 -1 
-1 1716 1675 1669 1634 1556 1706 1655 1621 1694 1701 -1 
-1 1711 1719 1671 1746 1617 1728 1659 1675 1738 1725 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
There is one spot marked "1188". That is the unknown spot that seems to have the lowest chance of being a bomb, so that's what I would open next.

EDIT: If there were any spots marked "10000", it's a pretty sure bet that there is a bomb there, so you can just mark it.

#4Álvaro

Posted 17 April 2013 - 11:44 AM

If you have a time, please try to make graphics explanation of your algorithm.

I am not going to post graphics, but I can explain show you some crude code:
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
/*
  Convention:
  -3 : outside
  -2 : flag
  -1 : unknown
  >=0 : That many neighbors are bombs
*/

char knowns[12][12] = {
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3},
  {-3,  0,  1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  1,  3, -2, -1,  4, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1,  1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3}
};

int bombs_unaccounted_for = 19;

int main() {
  bool bomb_locations[12][12]={{0}};
  int danger[12][12]={{0}};
  
  std::vector<int> unknowns;
  for (int i=0; i<12; ++i) {
    for (int j=0; j<12; ++j) {
      if (knowns[i][j] == -1)
        unknowns.push_back(i*12+j);
      bomb_locations[i][j] = (knowns[i][j] == -2);
    }
  }
  for (int count=0; count < 10000; ) {
    // Generate bomb distribution
    bool bl_copy[12][12];
    std::memcpy(bl_copy, bomb_locations, sizeof(bl_copy));
    for (int i=0; i<bombs_unaccounted_for; ++i) {
      int j = i + (std::rand() % (unknowns.size()-i));
      std::swap(unknowns[i], unknowns[j]);
      int b = unknowns[i];
      bl_copy[b/12][b] = true;
    }      
    
    // Verify consistency
    for (int i=1; i<11; ++i) {
      for (int j=1; j<11; ++j) {
        if (knowns[i][j] >= 0) {
          int c = 0;
          for (int di=-1; di<=1; di++)
            for (int dj=-1; dj<=1; dj++)
              c += bl_copy[i+di][j+dj];
          if (knowns[i][j] != c)
            goto NOT_CONSISTENT;
        }
      }
    }
    
    std::cout << "count=" << ++count << '\n';
    // Accumulate danger values
    for (int i=0; i<12; ++i) {
      for (int j=0; j<12; ++j) {
        danger[i][j] += bl_copy[i][j];
        std::cout << (knowns[i][j]==-1 ? danger[i][j] : -1) << ' ';
      }
      std::cout << '\n';
    }
  NOT_CONSISTENT:;
  }
}
After running it for a while, it produces this:
count=10000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 1718 1682 1692 1649 1713 1728 1746 1709 -1 
-1 -1 -1 8282 4904 5001 4985 1708 1708 1736 1718 -1 
-1 -1 -1 -1 5059 -1 5072 1702 1724 1721 1712 -1 
-1 5023 4977 1718 4949 5068 4962 1707 1641 1652 1751 -1 
-1 1640 1207 1246 1283 1669 1701 1662 1689 1693 1758 -1 
-1 1671 1264 -1 1188 1714 1657 1663 1722 1672 1678 -1 
-1 1661 1222 1333 1257 1659 1689 1658 1687 1697 1730 -1 
-1 1615 1652 1803 1785 1762 1770 1590 1643 1628 1649 -1 
-1 1716 1675 1669 1634 1556 1706 1655 1621 1694 1701 -1 
-1 1711 1719 1671 1746 1617 1728 1659 1675 1738 1725 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
There is one spot marked "1188". That is the unknown spot that seems to have the lowest chance of being a bomb, so that's what I would open next.

EDIT: If there were any spots marked "10000", it's a pretty sure bet that there is a bomb there, so you can just mark it.

#3Álvaro

Posted 17 April 2013 - 11:43 AM

If you have a time, please try to make graphics explanation of your algorithm.

I am not going to post graphics, but I can explain show you some crude code:
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
/*
  Convention:
  -3 : outside
  -2 : flag
  -1 : unknown
  >=0 : That many neighbors are bombs
*/

char knowns[12][12] = {
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3},
  {-3,  0,  1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  1,  3, -2, -1,  4, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1,  1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3}
};

int bombs_unaccounted_for = 19;

int main() {
  bool bomb_locations[12][12]={{0}};
  int danger[12][12]={{0}};
  
  std::vector<int> unknowns;
  for (int i=0; i<12; ++i) {
    for (int j=0; j<12; ++j) {
      if (knowns[i][j] == -1)
        unknowns.push_back(i*12+j);
      bomb_locations[i][j] = (knowns[i][j] == -2);
    }
  }
  for (int count=0; count < 10000; ) {
    // Generate bomb distribution
    bool bl_copy[12][12];
    std::memcpy(bl_copy, bomb_locations, sizeof(bl_copy));
    for (int i=0; i<bombs_unaccounted_for; ++i) {
      int j = i + (std::rand() % (unknowns.size()-i));
      std::swap(unknowns[i], unknowns[j]);
      int b = unknowns[i];
      bl_copy[b/12][b] = true;
    }      
    
    // Verify consistency
    for (int i=1; i<11; ++i) {
      for (int j=1; j<11; ++j) {
        if (knowns[i][j] >= 0) {
          int c = 0;
          for (int di=-1; di<=1; di++)
            for (int dj=-1; dj<=1; dj++)
              c += bl_copy[i+di][j+dj];
          if (knowns[i][j] != c)
            goto NOT_CONSISTENT;
        }
      }
    }
    
    std::cout << "count=" << ++count << '\n';
    // Accumulate danger values
    for (int i=0; i<12; ++i) {
      for (int j=0; j<12; ++j) {
        danger[i][j] += bl_copy[i][j];
        std::cout << (knowns[i][j]==-1 ? danger[i][j] : -1) << ' ';
      }
      std::cout << '\n';
    }
  NOT_CONSISTENT:;
  }
}
After running it for a while, it produces this:
count=10000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 1718 1682 1692 1649 1713 1728 1746 1709 -1 
-1 -1 -1 8282 4904 5001 4985 1708 1708 1736 1718 -1 
-1 -1 -1 -1 5059 -1 5072 1702 1724 1721 1712 -1 
-1 5023 4977 1718 4949 5068 4962 1707 1641 1652 1751 -1 
-1 1640 1207 1246 1283 1669 1701 1662 1689 1693 1758 -1 
-1 1671 1264 -1 1188 1714 1657 1663 1722 1672 1678 -1 
-1 1661 1222 1333 1257 1659 1689 1658 1687 1697 1730 -1 
-1 1615 1652 1803 1785 1762 1770 1590 1643 1628 1649 -1 
-1 1716 1675 1669 1634 1556 1706 1655 1621 1694 1701 -1 
-1 1711 1719 1671 1746 1617 1728 1659 1675 1738 1725 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
There is one spot marked "1188". That is the unknown spot with the lowest chance of being a bomb, and that's what I would open next.

EDIT: If there were any spots marked "10000", it's a pretty sure bet that there is a bomb there, so you can just mark it.

#2Álvaro

Posted 17 April 2013 - 11:43 AM

If you have a time, please try to make graphics explanation of your algorithm.

I am not going to post graphics, but I can explain what it does in one case. Here is some crude code:
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
/*
  Convention:
  -3 : outside
  -2 : flag
  -1 : unknown
  >=0 : That many neighbors are bombs
*/

char knowns[12][12] = {
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3},
  {-3,  0,  1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  1,  3, -2, -1,  4, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1,  1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3}
};

int bombs_unaccounted_for = 19;

int main() {
  bool bomb_locations[12][12]={{0}};
  int danger[12][12]={{0}};
  
  std::vector<int> unknowns;
  for (int i=0; i<12; ++i) {
    for (int j=0; j<12; ++j) {
      if (knowns[i][j] == -1)
        unknowns.push_back(i*12+j);
      bomb_locations[i][j] = (knowns[i][j] == -2);
    }
  }
  for (int count=0; count < 10000; ) {
    // Generate bomb distribution
    bool bl_copy[12][12];
    std::memcpy(bl_copy, bomb_locations, sizeof(bl_copy));
    for (int i=0; i<bombs_unaccounted_for; ++i) {
      int j = i + (std::rand() % (unknowns.size()-i));
      std::swap(unknowns[i], unknowns[j]);
      int b = unknowns[i];
      bl_copy[b/12][b] = true;
    }      
    
    // Verify consistency
    for (int i=1; i<11; ++i) {
      for (int j=1; j<11; ++j) {
        if (knowns[i][j] >= 0) {
          int c = 0;
          for (int di=-1; di<=1; di++)
            for (int dj=-1; dj<=1; dj++)
              c += bl_copy[i+di][j+dj];
          if (knowns[i][j] != c)
            goto NOT_CONSISTENT;
        }
      }
    }
    
    std::cout << "count=" << ++count << '\n';
    // Accumulate danger values
    for (int i=0; i<12; ++i) {
      for (int j=0; j<12; ++j) {
        danger[i][j] += bl_copy[i][j];
        std::cout << (knowns[i][j]==-1 ? danger[i][j] : -1) << ' ';
      }
      std::cout << '\n';
    }
  NOT_CONSISTENT:;
  }
}
After running it for a while, it produces this:
count=10000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 1718 1682 1692 1649 1713 1728 1746 1709 -1 
-1 -1 -1 8282 4904 5001 4985 1708 1708 1736 1718 -1 
-1 -1 -1 -1 5059 -1 5072 1702 1724 1721 1712 -1 
-1 5023 4977 1718 4949 5068 4962 1707 1641 1652 1751 -1 
-1 1640 1207 1246 1283 1669 1701 1662 1689 1693 1758 -1 
-1 1671 1264 -1 1188 1714 1657 1663 1722 1672 1678 -1 
-1 1661 1222 1333 1257 1659 1689 1658 1687 1697 1730 -1 
-1 1615 1652 1803 1785 1762 1770 1590 1643 1628 1649 -1 
-1 1716 1675 1669 1634 1556 1706 1655 1621 1694 1701 -1 
-1 1711 1719 1671 1746 1617 1728 1659 1675 1738 1725 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
There is one spot marked "1188". That is the unknown spot with the lowest chance of being a bomb, and that's what I would open next.

EDIT: If there were any spots marked "10000", it's a pretty sure bet that there is a bomb there, so you can just mark it.

#1Álvaro

Posted 17 April 2013 - 11:41 AM

If you have a time, please try to make graphics explanation of your algorithm.

I am not going to post graphics, but I can explain what it does in one case. Here is some crude code:
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
/*
  Convention:
  -3 : outside
  -2 : flag
  -1 : unknown
  >=0 : That many neighbors are bombs
*/

char knowns[12][12] = {
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3},
  {-3,  0,  1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3,  1,  3, -2, -1,  4, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1,  1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -3},
  {-3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3, -3}
};

int bombs_unaccounted_for = 19;

int main() {
  bool bomb_locations[12][12]={{0}};
  int danger[12][12]={{0}};
  
  std::vector<int> unknowns;
  for (int i=0; i<12; ++i) {
    for (int j=0; j<12; ++j) {
      if (knowns[i][j] == -1)
        unknowns.push_back(i*12+j);
      bomb_locations[i][j] = (knowns[i][j] == -2);
    }
  }
  for (int count=0; count < 10000; ) {
    // Generate bomb distribution
    bool bl_copy[12][12];
    std::memcpy(bl_copy, bomb_locations, sizeof(bl_copy));
    for (int i=0; i<bombs_unaccounted_for; ++i) {
      int j = i + (std::rand() % (unknowns.size()-i));
      std::swap(unknowns[i], unknowns[j]);
      int b = unknowns[i];
      bl_copy[b/12][b] = true;
    }      
    
    // Verify consistency
    for (int i=1; i<11; ++i) {
      for (int j=1; j<11; ++j) {
        if (knowns[i][j] >= 0) {
          int c = 0;
          for (int di=-1; di<=1; di++)
            for (int dj=-1; dj<=1; dj++)
              c += bl_copy[i+di][j+dj];
          if (knowns[i][j] != c)
            goto NOT_CONSISTENT;
        }
      }
    }
    
    std::cout << "count=" << ++count << '\n';
    // Accumulate danger values
    for (int i=0; i<12; ++i) {
      for (int j=0; j<12; ++j) {
        danger[i][j] += bl_copy[i][j];
        std::cout << (knowns[i][j]==-1 ? danger[i][j] : -1) << ' ';
      }
      std::cout << '\n';
    }
  NOT_CONSISTENT:;
  }
}
After running it for a while, it produces this:
count=10000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 1718 1682 1692 1649 1713 1728 1746 1709 -1 
-1 -1 -1 8282 4904 5001 4985 1708 1708 1736 1718 -1 
-1 -1 -1 -1 5059 -1 5072 1702 1724 1721 1712 -1 
-1 5023 4977 1718 4949 5068 4962 1707 1641 1652 1751 -1 
-1 1640 1207 1246 1283 1669 1701 1662 1689 1693 1758 -1 
-1 1671 1264 -1 1188 1714 1657 1663 1722 1672 1678 -1 
-1 1661 1222 1333 1257 1659 1689 1658 1687 1697 1730 -1 
-1 1615 1652 1803 1785 1762 1770 1590 1643 1628 1649 -1 
-1 1716 1675 1669 1634 1556 1706 1655 1621 1694 1701 -1 
-1 1711 1719 1671 1746 1617 1728 1659 1675 1738 1725 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
There is one spot marked "1188". That is the unknown spot with the lowest chance of being a bomb, and that's what I would open next.

PARTNERS