Edit: Updated file with levels 1-20 - http://dehacked.2y.net/microstorage.php/info/718847732/Polarium%20-%20WIP%202.dsm As you can see there's some room to play after the actual puzzle has been solved but this test run doesn't make much use of that yet. All constructive criticism appreciated.
Hmm, now I almost want to write a script for solving Polarium puzzles optimally. It's just that I have so much else to do…
I'm not convinced that Puzzle mode is the best for a TAS; it's just a sequence of entering the fastest solution to each level, one after the next, and unless there's some sort of crazy glitch it's simply going to be reasonably unimpressive as a TAS. Challenge mode would seem to give more scope for interesting play, especially given that you can accelerate the drops of puzzle sections by swiping down on the cancel button.
EDIT: After looking at it, downswiping is going to be much faster because the main thing that slows down Challenge mode is the cutscene in which lines are eliminated. So you want to be able to remove as many lines as you can per stroke in order to get the top speed. This means waiting for the screen to fill, downswiping does that faster. (In case you don't know the trick, you put the stylus near the top of the cancel buttons and drag it downwards; it's mentioned in the manual, IIRC.)
(more) Optimal route I used (131 frames):
I have contacted the creator of the solver to see if they can provide me the source code/help me with making my own solver so will hopefully get a reply, but if not I'll probably need help making my own solver since I'm not the best programmer and I'm not really sure where to start.
stage 10:
stage 14:
stage 18: http://www.mediafire.com/?5rsb2dp0ala8875
I hope this gives you enough ideas for good solutions.
I think that using the current solver is just a way to prove if there actually is some solution at all, nothing more.
The problem "Does there exist a solution?" is in NP, but asking for the fastest solution is most likely something like O(3^n) where n is the amount of steps for the shortest solution (choose one new direction from "up", "down", "left", "right", but don't go back to the place you just came from). So... solving the easiest of all of them -- stage 14 -- would have taken about 3*5*4*3^8 = 393.660 attemps at worst. Well, most of these attempts would be cancelled rather quickly because the solution would become invalid. Brute-forcing the fastest solution might be possible (and it would even prove that the chosen solution is optimal), but this becomes a lot worse for bigger puzzles...
The main idea is to avoid using the outer fields as much as possible. If you can avoid using the outer fields by walking through more fields in the middle this is always a good idea.
The next idea: Try to avoid placing the two ends of the paths too close to each other.More games should be beatable by automated solvers freely available on the internet.
For anyone interested in the mechanics: - It takes 3 frames to tap a square of input - To move to an adjacent square (up/down/left/right) it takes an additional 3 frames of input - To move to a non adjacent square (up/down/left/right) any distance away takes an additional 4 frames of input
Could you explain your maths from the previous post a bit more? I don't really see where your numbers come from
At the end, you get this result:Language: luafunction deepcopy(orig) local orig_type = type(orig) local copy if orig_type == 'table' then copy = {} for orig_key, orig_value in pairs(orig) do copy[orig_key] = deepcopy(orig_value) end else -- number, string, boolean, etc copy = orig end return copy end puzzlestring = { ".***.", "**.**", ".***." } puzzle = {} for y,str in ipairs(puzzlestring) do puzzle[y] = {} s = puzzlestring[y] for x = 1, string.len(s) do puzzle[y][x] = (string.sub(s, x, x) == ".") end puzzle[y][0] = "*" puzzle[y][string.len(s) + 1] = "*" end height = #puzzle width = #puzzle[1] - 1 for y = 0, height + 1, height + 1 do puzzle[y] = {} for x = 0, width + 1 do puzzle[y][x] = "*" end end function printpuzzle(p) local s = "" local puz = p.puzzle for y = 0, #puz do for x = 0, #puz[y] do local c = puz[y][x] if p.solutionrequired[y] == nil or p.solutionrequired[y] == "*" then if c == true then s = s .. " #" elseif c == false then s = s .. " ." elseif type(c) == "number" then s = s .. string.format("%3u", c) else s = s .. " " .. c end elseif p.solutionrequired[y] == true then if c == true then s = s .. " +" elseif c == false then s = s .. " -" elseif type(c) == "number" then s = s .. string.format("%3u", c) else s = s .. " " .. c end elseif p.solutionrequired[y] == false then if c == false then s = s .. " +" elseif c == true then s = s .. " -" elseif type(c) == "number" then s = s .. string.format("%3u", c) else s = s .. " " .. c end else s = s .. "!failure " .. y .. ";" .. x .. ";" .. tostring(c) .. ";" .. tostring(p.solutionrequired[y]) .. "!" end end s = s .. "\n\n" end print(s) end fifo = {} elementcount = 0 maxelements = 0 -- start an attempt for every starting point for y = 1, #puzzlestring do for x = 1, #puzzlestring[y] do current = { puzzle = deepcopy(puzzle), x = x, y = y, step = 1, solutionrequired = {} } current.solutionrequired[y] = puzzle[y][x] current.puzzle[y][x] = 1 --printpuzzle(current) table.insert(fifo, current) elementcount = elementcount + 1 maxelements = math.max(maxelements, elementcount) end end counter = 1 current = table.remove(fifo, 1) while(current) do print("counter: ".. counter .. "; elements: " .. elementcount .. "; max: " .. maxelements) printpuzzle(current) --check if this one solves the maze validvalues = 0 for y = 1, #puzzlestring do for x = 1, #puzzlestring[y] do if type(current.puzzle[y][x]) == "number" or ( current.solutionrequired[y] ~= nil and current.puzzle[y][x] ~= current.solutionrequired[y] ) then validvalues = validvalues + 1 end end end if validvalues == #puzzlestring * #puzzlestring[1] then print("!! best solution found !!") break end --check if it is possible to go one step up if --field limit hasn't been reached (current.y >= 1) and --we didn't already visit this place (type(current.puzzle[current.y-1][current.x]) ~= "number") and --visiting this place is allowed ( --place can be visited if it is on the outside (current.x == 0 or current.x == #puzzlestring[1] + 1 or current.y == 1) --we didn't visit any field on this row or (current.solutionrequired[current.y - 1] == nil) --we visit a field of the same colour or (current.solutionrequired[current.y - 1] == current.puzzle[current.y-1][current.x]) ) then newpuzzle = deepcopy(current) newpuzzle.step = newpuzzle.step + 1 newpuzzle.y = newpuzzle.y - 1 if newpuzzle.y >= 1 then if newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] ~= "*" then newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] end end newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step table.insert(fifo, newpuzzle) elementcount = elementcount + 1 maxelements = math.max(maxelements, elementcount) end -- check if it is possible to go one step down if --field limit hasn't been reached (current.y <= #puzzlestring) and --we didn't already visit this place (type(current.puzzle[current.y+1][current.x]) ~= "number") and --visiting this place is allowed ( --place can be visited if it is on the outside (current.x == 0 or current.x == #puzzlestring[1] + 1 or current.y == #puzzlestring) --we didn't visit any field on this row or (current.solutionrequired[current.y + 1] == nil) --we visit a field of the same colour or (current.solutionrequired[current.y + 1] == current.puzzle[current.y+1][current.x]) ) then newpuzzle = deepcopy(current) newpuzzle.step = newpuzzle.step + 1 newpuzzle.y = newpuzzle.y + 1 if newpuzzle.y <= #puzzlestring then if newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] ~= "*" then newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] end end newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step table.insert(fifo, newpuzzle) elementcount = elementcount + 1 maxelements = math.max(maxelements, elementcount) end --check if it is possible to go one step left if --field limit hasn't been reached (current.x >= 1) and --we didn't already visit this place (type(current.puzzle[current.y][current.x - 1]) ~= "number") and --visiting this place is allowed ( -- place can be visited if it is on the outside (current.y == 0 or current.y == #puzzlestring[1] + 1 or current.x == 1) -- or if we visit a field of the same colour or (current.solutionrequired[current.y] == current.puzzle[current.y][current.x - 1]) ) then newpuzzle = deepcopy(current) newpuzzle.step = newpuzzle.step + 1 newpuzzle.x = newpuzzle.x - 1 newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step table.insert(fifo, newpuzzle) elementcount = elementcount + 1 maxelements = math.max(maxelements, elementcount) end --check if it is possible to go one step right if --field limit hasn't been reached (current.x <= #puzzlestring[1]) and --we didn't already visit this place (type(current.puzzle[current.y][current.x + 1]) ~= "number") and --visiting this place is allowed ( -- place can be visited if it is on the outside (current.y == 0 or current.y == #puzzlestring[1] + 1 or current.x == #puzzlestring[1]) -- or if we visit a field of the same colour or (current.solutionrequired[current.y] == current.puzzle[current.y][current.x + 1]) ) then newpuzzle = deepcopy(current) newpuzzle.step = newpuzzle.step + 1 newpuzzle.x = newpuzzle.x + 1 newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step table.insert(fifo, newpuzzle) elementcount = elementcount + 1 maxelements = math.max(maxelements, elementcount) end current = table.remove(fifo, 1) elementcount = elementcount - 1 maxelements = math.max(maxelements, elementcount) counter = counter + 1 end
counter: 1532; elements: 519; max: 521
* * * * * * *
* 1 - - - 9 *
* 2 3 - 7 8 *
* - 4 5 6 - *
* * * * * * *
!! best solution found !!counter: 1088987; elements: 18104; max: 46989; unsolvables removed: 396759
* * 5 6 7 8 9 * * *
* - 4 3 2 - 10 11 12 *
* - - - 1 - - - 13 *
* - 48 47 46 - 18 17 14 *
* - - - 45 - 19 16 15 *
* 41 42 43 44 21 20 - - *
* 40 39 38 - 22 25 26 - *
* - - 37 - 23 24 27 - *
* - - 36 35 34 - 28 29 *
* * * * * 33 32 31 30 *
!! best solution found !!44 solutions found.
Total solutions found: 52
Fastest solution (22 frames):
* * *-*-* * *
| |
* . + . + . *
| |
* . + . + . *
| |
* . + . + . *
| |
* . + . $ . *
|
* . + . $ . *
| |
* * *-*-* * *
Shortest solution (16 tiles):
* * *-*-* * *
| |
* . + . + . *
| |
* . + . + . *
| |
* . + . + . *
| |
* . + . $ . *
|
* . + . $ . *
| |
* * *-*-* * *
script finished running
script stopped.Best attempt before brute-forcing:
*?*?A?*?A?*?*
? ? ? ?
* . A . A . *
? ? ? ?
* . A . A . *
? ? ? ?
* . A?A?A . *
? ? ?
* . . A . . *
? ? ?
* . . A . . *
? ? ?
* . . A . . *
? ? ?
* . . A . . *
? ? ?
*?*?*?A?*?*?*
0 solutions found.
Total solutions found: 5962
Fastest solution (47 frames):
* * *-*-* * *
| |
* . + . + . *
| |
* . + . + . *
| |
* . + $-+ . *
|
*-+ + . +-+ *
| | | | |
* + + . + + *
| | | | |
* + + . + + *
| | | | |
* +-+ . + $ *
| |
+-*-*-*-* * +
Shortest solution (29 tiles):
* * *-*-* * *
| |
* . + . + . *
| |
* . + . + . *
| |
* . + $-+ . *
|
* +-+ . +-+ *
| | |
* +-+ . + + *
| | |
* +-+ . + + *
| | |
* +-+ . + $ *
| |
+ * *-*-* * +
script finished running
script stopped.
* * * * * * * 14 13 12
* 21 20 19 18 17 16 15 - 11
23 22 - - - - - - - 10
24 - - - - - - - 8 9
25 - 1 2 3 4 5 6 7 -
26 - - - - - - - 44 43
27 - 51 50 49 48 47 46 45 42
28 - - - - - - - 40 41
29 - 33 34 35 36 37 38 39 *
30 31 32 * * * * * * *Best attempt before brute-forcing:
*-*-*-*-*-*-*-*-* +
| |
* . . . . . . . +-*
| |
*-+ . . . . . . . *
| |
*-+ A?A?A?A?A?A . *
| ? ? ? ? ? ? |
* . A?A?A?A?A?A-+-*
| ? ? ? ? ? ?
*-+-A?A?A?A?A?A . *
? ? ? ? ? ?
* . A?A?A?A?A?A-+-*
? ? ? ? ? ? |
*-+ A?A?A?A?A?A . *
| ? ? ? ? ? ? |
* . A?A?A?A?A?A-+-*
| | | |
*-*-* * *-*-* * * +
Found connections at region edges:
+++++++.
+.......
.......+
+.......
.......+
.aaaaa?+
+!aaaaa.
.??????+
Best attempt before brute-forcing:
A?A?A?A?A?A?A?*?*?*
? ? ? ? ? ? ? | ?
A?A?A?A?A?A?A-+ . *
? | ?
*-+ . . . . . . . *
? ?
* . . . . . . . +-*
? ?
*-+ . . . . . . . *
? ?
* . . . . . . . +-*
? | ?
* . +-B?B?B?B?B?B?B
? | ? ? ? ? ? ?
*-+-+ B?B?B?B?B . *
? ? ? ? ? ? ?
* . +-B?B?B?B?B?B?B
? | ? ? ? ? ? ?
*?*?*?B?B?B?B?B?B BTrying row combination:
1111112.
2.......
.......4
4.......
.......2
.2111111
2111111.
.1111111
0 endpoints available.MEM_COLS = 0x020E3F64
MEM_ROWS = 0x020E3FA8
MEM_CELL_ROW1_COL1 = 0x020E03C4
MEM_rowoffset = 0x0140
MEM_coloffset = 0x14
MEM_valoffset = 0x1
function readpuzzle()
local puzzle = {}
local rows = memory.readbyte(MEM_ROWS)
local cols = memory.readbyte(MEM_COLS)
for r = 1, rows do
puzzle[r] = {}
for c = 1, cols do
puzzle[r][c] =
memory.readbyte(
MEM_CELL_ROW1_COL1
+ MEM_rowoffset * (r - 1)
+ MEM_coloffset * (c - 1)
) - MEM_valoffset
end
end
return puzzle
endThis should be detected as unsolvable. The reason is easy: Take one starting point. Now solve the top part. If you now continue, then you come across the other endpoint and didn't solve the lower part. Now take a starting point, and assume you could solve the lower part. You can't get to the top part afterwards without coming across the other endpoint.Found connections at region edges: +++++++. +....... .......+ +....... .......+ .aaaaa?+ +!aaaaa. .??????+ Best attempt before brute-forcing: A?A?A?A?A?A?A?*?*?* ? ? ? ? ? ? ? | ? A?A?A?A?A?A?A-+ . * ? | ? *-+ . . . . . . . * ? ? * . . . . . . . +-* ? ? *-+ . . . . . . . * ? ? * . . . . . . . +-* ? | ? * . +-B?B?B?B?B?B?B ? | ? ? ? ? ? ? *-+-+ B?B?B?B?B . * ? ? ? ? ? ? ? * . +-B?B?B?B?B?B?B ? | ? ? ? ? ? ? *?*?*?B?B?B?B?B?B B
another edit:MEM_COLS = 0x020E3F64 MEM_ROWS = 0x020E3FA8 MEM_CELL_ROW1_COL1 = 0x020E03C4 MEM_rowoffset = 0x0140 MEM_coloffset = 0x14 MEM_valoffset = 0x1 function readpuzzle() local puzzle = {} local rows = memory.readbyte(MEM_ROWS) local cols = memory.readbyte(MEM_COLS) for r = 1, rows do puzzle[r] = {} for c = 1, cols do puzzle[r][c] = memory.readbyte( MEM_CELL_ROW1_COL1 + MEM_rowoffset * (r - 1) + MEM_coloffset * (c - 1) ) - MEM_valoffset end end return puzzle end
|0|.............244 136 1|
|0|.............244 138 1|
|0|.............243 143 1|
|0|.............241 149 1|
|0|.............243 153 1|
|0|.............245 161 1|
|0|.............246 168 1|
|0|.............245 175 1|