Advertising (This ad goes away for registered users. You can Login or Register)

Minesweeper Master.

Programming on your favorite platform, for your favorite platform? Post here
Locked
flatline
Posts: 1
Joined: Tue Nov 04, 2014 3:12 am

Minesweeper Master.

Post by flatline »

It's a google code jam challange for those who don't know. Here's a link to it: https://code.google.com/codejam/contest ... board#s=p2.
Anyway the problem I've with my solution is that it will not detect if the Mines just completely encircle an 'empty' square..
My idea to fix this issue was to get the mines that're near a empty space, detect if it is spaced in and if it is declare the table "Impossible". But the empirically this isn't working out well. My code is in Lua. I do not want the code per-se I just want a general idea on how to fix this issue. Also any ideas on making this more efficent than using a gradient-esque system (as used in A*) would be of great help.
Footnote: I could comment the code if that'd help.

Code: Select all

-- mines hidden
local near = function(tab)
 local array = {
    {TabPos = tab.TabPos + 1, StringPos = tab.StringPos};
    {TabPos = tab.TabPos - 1, StringPos = tab.StringPos};
    {TabPos = tab.TabPos, StringPos = tab.StringPos - 1};
    {TabPos = tab.TabPos, StringPos = tab.StringPos + 1}};
      return array;
  end;
            
local findMatch = function(tab, tab2)
  local match = false;
      for _, subtab2 in next, tab2 do
          if tab.TabPos == subtab2.TabPos and tab.StringPos == subtab2.StringPos then
          match = true;
        end;
    end;
  return match;
end;

local checkNear = function(tab, checkTab, total)
    local numMines, exists = 0, 0;
    local mines, empty = {}, {};
    local array = near({TabPos = tab.TabPos, StringPos = tab.StringPos});
    for _, tab2 in next, array do
      if checkTab[tab2.TabPos] then
        exists = exists + 1;
        if checkTab[tab2.TabPos][tab2.StringPos] == "*" then
              numMines = numMines + 1;
              mines[#mines + 1] = {TabPos = tab2.TabPos, StringPos = tab2.StringPos};
        elseif checkTab[tab2.TabPos][tab2.StringPos] == "." then
              empty[#empty + 1] = {TabPos = tab2.TabPos, StringPos = tab2.StringPos};
            end;
        end;
    end;
    -- We need to find where we connect with the other empties.
    -- If we do not connect we will change; numMines = exists
    if not (#checkTab == 1) then
      total = total - #empty;
      -- we need to connect to everything!
      for _, tab in next, empty do
        for _, tab2 in next, mines do
            if tab.TabPos == tab2.TabPos then
                if tab.StringPos < tab2.StringPos then
                    -- We need to find a way around this and if that's impossible then 'brick'.
                    -- An idea 
                    end;
                end;
            end;
        end;
    end;
    return numMines, exists;
end;

local mainFunction = function(inputFile)
    local Variables = {Cases = 0, Lines = 0,  Characters = 0, Mines = 0};
    local VariablesList, currentVariable = {"Cases", "Lines", "Characters", "Mines"}, 0;
    local file = io.open(inputFile)
    local minesPerLine;
    for input in string.gmatch(file:read("*a"), "%d+") do
        currentVariable = currentVariable + 1; 
        Variables[VariablesList[currentVariable]] = tonumber(input);
    end;
  if (Variables.Lines * Variables.Characters) <= Variables.Mines then
    print("Impossible") 
  else
    for case = 1, Variables.Cases do
      local Tab = {}
      for i = 1, Variables.Lines do
        Tab[i] = {}
        for x = 1, Variables.Characters do
            Tab[i][x] = ".";
          end;
      end;
    -- Add Mines
    local perLine = (Variables.Lines * Variables.Characters)/Variables.Mines
    local String = "";
    for _, SubTab in next, Tab do
        local RandomLine = math.random(#SubTab);
        local CenterLine = math.ceil(math.random(#SubTab/2, (#SubTab/1.5)));
        local Horizantal = math.random(1, 2);
        -- Horizatal determins whther to use (1, 0) or (8, 0), per example.
        --[[
          1: Random
          2: Horizantal
          3: Center Line
        ]]
       local choose = math.random(3);
       if choose == 1 then
        for x = 1, perLine do
         repeat RandomLine = math.random(#SubTab) until SubTab[RandomLine] == ".";
         SubTab[RandomLine] = "*";
        end
       elseif choose == 2 then
        for x = 1, perLine do
         if Horizantal == 1 then
            Horizantal = 1;
        elseif Horizantal == 2 then
            Horizantal = #SubTab - 1
            if Horizantal <= 0 then
              Horizantal = 1;
            end;
         end;
          repeat 
          Horizantal = Horizantal + 1 
          if Horizantal > #SubTab then 
          Horizantal = 1;
            end;
          until SubTab[Horizantal] == ".";
          SubTab[Horizantal] = "*";
        end;
       elseif choose == 3 then
        for x = 1, perLine do
          repeat CenterLine = math.ceil(math.random(#SubTab/2, (#SubTab/1.5))); until
          SubTab[CenterLine] == "."; 
          SubTab[CenterLine] = "*";
                  end;
              end;
          end; -- Mine End
          -- Check
            local solutions = {Solute = {}};
            -- We will need to use each one 
            for intPos, SubTab in next, Tab do
              for intPos2, nString in next, SubTab do
                 local Quene = {};
                 local Checked = {};
                 local var = (Variables.Characters * Variables.Lines) - Variables.Mines;
                 if nString == "." then
                   if var - 1 <= 0 then
                        solutions.Solute[#solutions.Solute] = {TabPos = intPos, StringPos = intPos2};
                   else
                  Checked[#Checked + 1] = {TabPos = intPos, StringPos = intPos2};
                  for _, SubTab2 in next, near({TabPos = intPos, StringPos = intPos2}) do
                    local tab = Tab[SubTab2.TabPos];
                    if tab then 
                      if tab[SubTab2.StringPos] then
                         local match = findMatch(SubTab2, Checked);
                         local minesNear, exists = checkNear(SubTab2, Tab,  
                        (Variables.Characters * Variables.Lines) - Variables.Mines);
                         
                         if not (match) and not (mineNear == exists) then
                              if tab[SubTab2.StringPos] == "." then
                                    Quene[#Quene + 1] = {TabPos = SubTab2.TabPos, StringPos = SubTab2.StringPos};
                                    Checked[#Checked + 1] = {TabPos = SubTab2.TabPos, StringPos = SubTab2.SringPos};
                                  end;
                              end;
                          end;
                      end;
                  end;
                  
                  for _, SubTab3 in next, Quene do
                    local tab = Tab[SubTab3.TabPos]
                    var = var - 1;
                    if var <= 0 then break end;
                    local array = near({TabPos = SubTab3.TabPos, StringPos = SubTab3.StringPos});
                    for _, SubTab4 in next, array do
                        local match = findMatch(SubTab4, Checked);
                        local tab = Tab[SubTab4.TabPos];
                        if tab then
                          if tab[SubTab4.StringPos] == "." then
                            local mineNear, exists = checkNear(SubTab4, Tab,  
                            (Variables.Characters * Variables.Lines) - Variables.Mines);
                            if not (mineNear == exists) and not(match) then
                                    Quene[#Quene + 1] = {TabPos = SubTab4.TabPos, StringPos = SubTab4.StringPos};
                                    Checked[#Checked + 1] = {TabPos = SubTab4.TabPos, StringPos = SubTab4.SringPos};
                                end;
                            end;
                        end;
                    end;
                      -- finished
                  end;
                  if var <= 0 then
                    solutions.Solute[#solutions.Solute + 1] = {TabPos = intPos, StringPos = intPos2};
                  end;
                          
                          end;
                      end;
                  end;
              end;
            if #solutions.Solute == 0 then
              print("Impossible")
              else
             local c;
             repeat c = solutions.Solute[math.random(#solutions.Solute)] until
             not(c["TabPos"] == nil)
              Tab[c.TabPos][c.StringPos] = "c";
              for _, SubTab in next, Tab do
                for _, newString in next, SubTab do String = String..newString; end;
                  String = String.."\n";
              end;
                print("Case #"..case.."\n"..String)
            end;
        end; -- Case End 
    end;
end;
  mainFunction("C:/Users/**/Documents/source/input.txt"); 
Advertising
Locked

Return to “Programming”