Jump to content

  • Log In with Google      Sign In   
  • Create Account


#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