notes

ws ws://maze.server.host/game-pipes/

┓┻┣┣┫┛╹┏
╹┃╺┃╺╸╹┻
╻┛╹━╺╻┓┃
┗━━┻┏┳┣┓
┗━┃┣┃┻╻╺
━╻┛┳┃┳╺━
┃┳┫┳╺┣┛━
┗┓╸╻╺┛┛┏

━┃┏┓┗┛┣┫┳┻╋╸╹╺╻

1,    ╹
12,   ┗
123,  ┣
1234, ╋
124,  ┻
13,   ┃
134,  ┫
14,   ┛
2,    ╺
23,   ┏
234,  ┳
24,   ━
3,    ╻
34,   ┓
4,    ╸

I: ━, ┃
L: ┏, ┛, ┓, ┗
T: ┣, ┫, ┳, ┻
X: ╋
i: ╸, ╹, ╺, ╻

--

1. mums nevajag immutable, mums vajag mutable
1.1. mutable ja tikai viens

2. mums vajag a*?
2.1. store order in btree (has min/max keys?)

3. jāsāk ar malām. vai mums vajag checkerboardā likt klucīšus lai būtu labāki minējumi immediately?

4. iespējams, ka var optimizēt sākot rēķināt no singletoniem

5. varbūt, ka lētāk ir storēt directionus vai nu vektorā vai optimizēt ar lookup table
5.2. special character for wall/uncertain
5.3. optimizēt best ar hashmap O(1), kas ir valīds visiem boardiem

6. simetrijām var nečekot rotācijas (krustam/taisnēm)

7. strongly connected
7.1. ja šis ir solved un ir T vai I, tad var solvēt dažus no apkārtējiem zariem (ja nekonnektējas) – they're forced
7.2. ja šis apmeklēts, tad solved set
7.3. ja rotation is pixValid, tad continue list = (new branches + forced + continue) filter solved. start with first from continue
7.4. ja continue ir empty & size == boardsize, tad valid

8. rotations = filter pixvalid rotations
8.1. if rotations == 1, tad var lietot mutable implement uz boarda

--

2020-12-26-18:55:23
✔ 1. Sides first in backtracking
✔ 2. Solve edge first, sort by solvability
✔ 3. Force unpointed
✔. Check stranded islands (jo dziļāk, jo dziļāk vērts rekursēt)
✔. Store origin in cursors
✔. Render cursor with list of sets per color
7. Subsolve regions around edges that don't touch each other, then combine partially solved solutions
7.1. index partial sets by origin cursor

2020-12-27-13:34:54
✔ 1. solve sides faster than just unambiguous (nextFast) by pop(1) initial only
2. lifecycle is decreasing, returns solve_ returns Either PartialSolution Maze
3. with PartialSolutions, you can share unaffected regions
4. maybe optimize board by using canoical rotation
5. 4*4 precomputed partial solutions

2020-12-27-20:02:40
1. lifecycle decreasing resulting in partial solutions list and solve'
2. calculate unambiguous pieces
3. share solutions
4. maze'
5. solve indirect ambiguous for failure
6. solve'' :: -> Either [PartialSolution] Maze
7. sortContinues with 2nd priority as in diagonals to current
8. unambiguous in Cursor
9. continue as list, initial as unambiguous Cursors (rotations = 1 then next unambiguous if unambiguous)
10. a single hashtable

2020-12-30-13:24:35
1. maybe join solutions by (intersection solved empty), copy solveds, uniq continues
2. hashtable record with functions (= 10. from previous)
3. (not a worthwhile idea) join all continue with choice = 1 solutions
4. nextSolution filter choice = 0

2021-01-10-15:25:31
1. websocket client
2. make maze Vector Vector for more memory sharing
3. optimize by profiler

2021-01-13-13:28:53
1. Make Maze a record with
1.1. board :: Data.Vector.Unboxed.Mutable.MVector Cursor (Char, PartId, solved :: Bool)
1.2. continue :: [Continue]
1.3. solves :: Data.Vector.Unboxed.Mutable.MVector as stack + stack size Int
1.4. bang patterns for all records
2. with mutable maze, when backtracking, set solved = false the cursor from solved stack
3. chocie! in solve' you can explore the rotations with connecting to most solveds first
4. choice! there's the option to abandon solutions with unfavorable characteristics (unconnected component with long, narrow path)
4.1. narrow: compute another score for narrowness, return the maze

2021-01-17-23:33:23
1. mutable vector rewrite
2. audit mazeReads to spot any redundancy
3. cursorDeltasWithWalls
4. strict data everywhere
5. suspendable progress with data about the remaning search space [[Rotation]] or, essentially, [[Continue]]
6. backtracking with fairness and thus parallel
(7. explore if it's worth to keep a pure, unsafe frozen version of MVector)

2021-01-18-23:37:26
1. mvector refactor last bug: unwind should also unwind partEquiv modifications and maybe partEquiv should be Maybe
2. export mutations to top, so it's easier write the unwind procedure

2021-01-26-22:51:04
✗ try sorting by connectivity in pixValidRotations (it had zero impact)
✔ continues as set + deleteMin to remove continue sort bottleneck (prev lvl3 ratio: (6131,2499))
✔ make maze pieces from chars to ints and do bit matching for validation
✔ if any new continues have zero choices, break early (already happening)

• see if we can directly remove solved continues, without occasional filtering
• see if pieceDead really has to iterate over every solved
✔ see if we can cut down on data in Continue (direct, choices are not necessary, char → int)
(•) see if lookup maps are ever reevaluated due to GC

p. try out parallel solving
p.1. by storing a list of Progresses (split space) (can be expensive, because of maze copies)
p.2. store only best solve of each pixValidRotations (run on new core for limited depth)
p.3. heuristics: pick only the luckiest (depth vs iteration) OR narrowest (fewest disconnected components)
p.4. print how many choices do we usually have per-square – is it ever four? (we'd need to combine choices to utilize more cores)

2021-02-01-23:30:06
• write another lookup for Continues with equated PartIds
  we wouldn't then have to partEquate each time – only when updating the map
  components :: Map PartId Int
• reduce all unnecessary thunking

2021-01-31-20:02:24
Choice count for maze 4-1 in solve' with "print (length rotations)"
% ghc solve && ./solve samples/4-1 2>&1 | sort | uniq -c | grep -E ' [0123]$'
    277 0
  25006 1
    508 2

2021-02-08-11:26:40
• cache deltas(with wall :: Boolean) in Vectors (thus avoid mazeBounded)
• priority: Set Continue ordered by score and iter, thus making them a total order (they're not now!)
• continues: Set Continue ordred by cursor
• components: Map PartId Int
-- thus making continues searchable by cursor and partId

• update with better scores through continues, join origins
• bring back Continue{created}, because we don't need guessable scores if we have `continues'

2021-03-18-18:09:33
data Continue = Continue { .. + islandWeight :: Int = 0, island :: Boolean = False }
data Piece = Piece { .. + island :: Boolean = Continue.island }

2021-03-13-13:35:17 - 2021-04-18-19:59:38
• main algo updates:
  ✔ solve whole islands (Continue.islandWeight) on 6 and continue with continuations of islands
  ✔ make components available as Map PartId (Set Cursor)
  ✗ fillNextSolved with mutable sets (no such thing)
• simple fixes
  ✔ fix recursion guard
  ✔ lvl in MMaze
• simple optimizations for later:
  ✔ priority :: Data.IntMap.Strict
  ✔ prioritize all choices = 0 from the top
  ✔ add all init continues with choices = 0 (crosses and edge pieces)
  ✔ continues :: Data.IntMap.Strict Int Continue, problems: deltas must be precomputed (Wall, Cursor)^4) or just bit-packed directions
  ✔ cache next (bit-packed directions, .&. when reprioritizing)
    ✔ make choices :: Int, bit-packed as choices + enabled + set
    ✔ update in continues, make priority :: Map PartId Cursor
    ✗ see if manual check+update is better than alterF
  ✔ continues: use choice count for space
  • unboxed/storable vectors
• visuals
  ✔ 3x3 border for image for easier edge viewing
  ✔ create a hackage page
  ✔ new tracing mode after islandize
  ✗ B&W with continues only (just higher intensity/saturation is fine :)
  • pick colors from pallette
  • create animation with ffmpeg (use threads for actual drawing, but don't forget to wait for them to finish)

-- 2021-05-23-09:19:42
inon() { sed -i '/--.....INLINE/s/-- //' Pipemaze.hs }
inoff() { sed -i '/INLINE/s/{-# INLINE/-- {-# INLINE/' Pipemaze.hs }

2021-05-04-11:36:03
• main algo updates:
  ✔ backtracking with maybe
  ✔ add data Constraints = ConstrNone | ConstrIsland | ConstrIsland1
  ✔ recursion guard before, not after solveContinue step (and works with constraints)
  ✔ compute all solutions of an island with iterateMaybeM (throw out last solution, to retrigger backtracking, add min depth constraint or cut space)
  ✗ recheck island size scoring with image outputs
  ✔ solving by islands
    ✔ compute all islands solutions
    ✔ equate them by their effect on components
    ✔ compute lists of networks joined (each list is a graph node) for each island
    ✔ combine their solutions (an island)
    ✔ fix deterministic constraint (cDeterministic now only stops after first choice)
    • compute all graphs, find first connected graph brute-force
      (no idea whether cutting subtrees of a partial solution is possible, i.e. backtracking)
  • keep multiple progresses ordered by breadth count (split :: Int + 1), have more breadth
• simple optimizations
  ✗ no space/unwinds, if deterministic (area = 1 is deterministic, which it shouldn't)
  ✔ check dump simple (no bueno)
  ✔ rewrite prioritizeContinues
  ✔ use choices in pieceDead
  ✗ rewrite all Continue origins after equating, remove partEquate
  • parallel deterministic solve (are they deterministic in sense that the begining doesn't matter?)
  • parallel island computations
  • inlinable for solveContinue/backtrack
  • unboxed/storable vectors
• visuals
  • pick colors from pallette
  • create animation with ffmpeg (use threads for actual drawing, but don't forget to wait for them to finish)
• prikolīgi
  • Data.Aeson Progress instances, just to see how it looks after a few iterations (maybe make ProgressFrozen)

2021-05-23-22:18:57
• main algo updates:
  ✗ breadth solving (hard and speed-up linear to N of processors)
  ✔ make choice counts strict (leak)
  ✔ reuse flooder
  ✔ parallel deterministic solve (are they deterministic in sense that the begining doesn't matter?, A: yes)
  ✔ parallel island computations
  ✔ group island solutions by graph connectivity partition refinement
  • combine solutions through component history
  • recompute only necessary (by touched components)
  • solve islands directly
• simple optimizations
  ✗ use trivial islands only for level 6 (no difference in bench)
  ✗ see if component writing ops can be removed if id is in components (probably not worth it)
  ✔ inlinable for solveContinue/backtrack
  ✔ only one progressClone in islandChoices
  ✔ unboxed/storable vectors
  ✔ unify space with unwinds
  ✔ deterministic modes
  ✔ aggressive inlining flags
  ✗ UNPACK 'data's (probably unpacked by haskell already or just not important)
  ✔ remove unused choices fields
  ✔ asciinema
• nice-ities
  ✔ monad reader env for config
  ✔ benchmarking mode with no images or maze verification
  ✔ fix parallelism
  ✔ dynamic server URL (git-filter-branch), levels= env var
  ✔ image directories
  ✗ rename area, make sure Piece/Continue names make sense, remove wasIsland(✔)
• prepublish
  ✔ fix warnings
  ✔ fix nix/cabl files, check for unnecessary deps
  ✔ throw out all unnecessary code, update docs, get reviewed
  ✗ better maze downloading?
  ✔ readme -fexternal-interpreter
  ✔ sort functions by toposort call graph as much as possible
  ✔ check important trash files into repo
  ✔ regenerate videos with longer endings
• just ideas
  ¬ I could also track old component IDs, so mazeEquate wouldn't be necessary sometimes

-      let satu = if solved then 0.15 else (if isJust cont then 1 else 0)
-      let inte = if solved then 0.5 else (if isJust cont then 1 else 0.3)
+      let satu = if solved then 1.0 else (if isJust cont then 0.5 else 0)
+      let inte = if solved then 0.25 else (if isJust cont then 1 else 0.0)

--

9f9a4fe
runhaskell solve.hs 2>&1 < samples/2  15.52s user 2.79s system 59% cpu 30.526 total

9f9a4fe + usePixValidPrecomputed
runhaskell solve.hs 2>&1 < samples/2  74.92s user 3.69s system 84% cpu 1:33.56 total
(actual solving timed with phone: 30s... same as with usePixValidPrecomputed = False)

./solve < samples/2-2  4.36s user 0.02s system 99% cpu 4.380 total

./solve < ./samples/3  1.73s user 0.03s system 99% cpu 1.772 total

% ghc solve && for i in {1..4}; do time ./solve < samples/4 2>&1 | grep total; done
./solve < samples/4 2>&1  4.87s user 0.03s system 99% cpu 4.900 total
grep --colour total  0.00s user 0.00s system 0% cpu 4.899 total
./solve < samples/4 2>&1  4.86s user 0.03s system 99% cpu 4.895 total
grep --colour total  0.00s user 0.00s system 0% cpu 4.895 total
./solve < samples/4 2>&1  4.86s user 0.03s system 99% cpu 4.891 total
grep --colour total  0.00s user 0.00s system 0% cpu 4.890 total

on fa170bd at 2021-01-31-21:00:28
% time ./solve samples/4-*
  22060/20000, ratio: 1.103
  24641/20000, ratio: 1.23205
  31466/20000, ratio: 1.5733
  21563/20000, ratio: 1.07815
  22755/20000, ratio: 1.13775
  21087/20000, ratio: 1.05435
  ./solve samples/4-*  6.42s user 0.06s system 99% cpu 6.482 total

on e2b3057 at 2021-02-04-20:27:22
% ghc solve -O && time ./solve samples/4-*
  22060/20000, ratio: 1.103
  24641/20000, ratio: 1.23205
  31466/20000, ratio: 1.5733
  21563/20000, ratio: 1.07815
  22755/20000, ratio: 1.13775
  21087/20000, ratio: 1.05435
  ./solve samples/4-*  1.27s user 0.04s system 99% cpu 1.310 total
% ghc solve -O && time ./solve samples/5-2
  [1 of 1] Compiling Main             ( solve.hs, solve.o )
  Linking solve ...
  7223527/120000, ratio: 60.19606
  ./solve samples/5-2  107.86s user 0.39s system 99% cpu 1:48.26 total

on 3f2f712 at 2021-02-07-23:22:30
% ghc solve -O && time ./solve samples/5-*
  443251/120000, ratio: 3.69376
  185532/120000, ratio: 1.54610
  370056/120000, ratio: 3.08380
  1458363/120000, ratio: 12.15302
  195839/120000, ratio: 1.63199
  654929/120000, ratio: 5.45774
  ./solve samples/5-*  66.74s user 0.60s system 99% cpu 1:07.34 total

on 2d74be3 at 2021-02-20-14:32:31
count of priority queue sizes: (removed solved pieces)
14 130 => 30 27
14 131 => 44 25
14 165 => 44 26
14 177 => 48 29
16 179 => 54 28
20 180 => 55 30
./solve samples/2  0.00s user 0.00s system 92% cpu 0.007 total

on Sun 28 Mar 2021 07:10:32 PM EEST
data Components =
  Components (Map PartId Int)
  ./solve trash/samples/5-{01..10}  19.28s user 0.56s system 99% cpu 19.838 total
  Components' (Map PartId (Set Cursor))
  ./solve trash/samples/5-{01..10}  19.62s user 0.58s system 99% cpu 20.200 total

% c <<< "on $(gsha) at $(date +%F-%T) // $(gmsg)"

on 6330a9a at 2021-04-05-14:23:10:
% ghc -O solve.hs && time ./solve trash/samples/5-{01..20} trash/samples/3-{01..20}
./solve trash/samples/5-{01..20} trash/samples/3-{01..20}  36.78s user 1.06s system 99% cpu 37.851 total

on 9029160 at 2021-04-05-14:42:22 // Priority :: Map Int Cursor
% ghc -O solve.hs && time ./solve trash/samples/5-{01..20} trash/samples/3-{01..20}
./solve trash/samples/5-{01..20} trash/samples/3-{01..20}  36.34s user 1.02s system 99% cpu 37.373 total

on 4bd0ab1 at 2021-04-05-14:47:44 // Data.Map.Strict → Data.Map.IntMap
% ghc -O solve.hs && time ./solve trash/samples/5-{01..20} trash/samples/3-{01..20}
./solve trash/samples/5-{01..20} trash/samples/3-{01..20}  34.87s user 0.95s system 99% cpu 35.834 total

# these times have too much noise, they're not reliable...

on ca8baa2 at 2021-04-08-00:41:14 // seed continues with trivial-choice pieces only
% ghc -O solve.hs && time ./solve trash/samples/5-{01..20} trash/samples/3-{01..20}
./solve trash/samples/5-{01..20} trash/samples/3-{01..20}  32.24s user 0.97s system 99% cpu 33.327 total

on at 2021-05-02-13:05:53 // flat cursors
% ghc Main.hs -o solve && time ./solve trash/samples/5-{01..20} trash/samples/3-{01..20}
./solve trash/samples/5-{01..20} trash/samples/3-{01..20}  25.15s user 0.97s system 99% cpu 26.140 total

on 029ff2c (now 7355ae6) at 2021-05-03-15:30:03 // Components IntMap IntSet
ghc Main.hs -o solve && time ./solve trash/samples/5-{01..20} trash/samples/3-{01..20}
./solve trash/samples/5-{01..20} trash/samples/3-{01..20}  24.55s user 0.94s system 99% cpu 25.498 total

time ./solve trash/samples/{5,3}-{01..20}
9179cfd [39s] fix recursion guard
23ffb80 [31s] bit-packed Choices with saved "next"
c55febf [25s] Use IntMap/Fursor for Continues
f3f02b2 [25s] prioritizeContinues: expose modify
1b72166 [25s] more readable rescoreContinue
514146e [25s] data Island
7355ae6 [25s] IntMap Set -> IntMap IntSet
d28ee3d [25s] make graph validation possible upon backtracking
5c19196 [25s] show graph articulation points
8af8dca [25s] backtracking with Maybe (for splitting stack)
ab65f11 [25s] Clean up solve', clean up pieceDead, remove useless computation
c45a1d9 [25s] update notes
eb8686e [25s] enable computing all solutions
4705e4a [25s] constraints data type
49687c3 [27s] Compute island choices, use for Continue.area
f53e788 [27s] fix deterministic recursion guard
3b8f70c [37s] compute island graph nodes
acbdfde [54s] the big solve (first lvl6 solve)
dd7471e [52s] optimize deterministic solve (small, but noticable gains)
93f6c25 [53s] simpler prioritizeContinues

git log --format=oneline -1 --no-decorate --abbrev-commit

time bench=True ./solve trash/samples/{6..1}-01
21ff6bb [2¾s] solve levels 4/5 in parallel as well
db350d1 [3₀s] update docs, document parallel benchmark times
daee4b8 [5½s] fix all hlint warnings
2bf61ed [5½s] remove needless copying
e82739a [6¾s] simplify Unwind, use space hints without removing UnEquate
6d08269 [7s ] solveIslandStatic
947cfd5 [7s ] unwind "before/after" field order, add more hints
af516fa [6¾s] fix bench bool check, don't verify if bench=True
486871f [9s ] don't save space when solving determinstically (gc gains)
d0192e4 [17s] unify space/unwinds
9745182 [17s] Use Data.Vector.Storable.Mutable (AoS)
15a8329 [20s] island connected component partition refinement (bug fix)
290ed73 [21s] maze copypasting for islandChoices (completely breaks parallelism)
c98633d [30s] Configuration with MonadReader, remove compile conf flags
5561c16 [32s] parallel deterministic solves + parallel island recomputes
ff70695 [32s] reuse flooder for islands
a9c6fd6 [38s] store less data for islands
9d4eea2 [50s] notes

% time bench=True ./solve samples/6-*
bench=True ./solve samples/6-*  113.72s user 2.90s system 99% cpu 1:57.11 total
bench=True ./solve samples/6-*  109.02s user 2.97s system 99% cpu 1:52.16 total
bench=True ./solve samples/6-*  88.12s user 2.96s system 99% cpu 1:31.09 total
bench=True ./solve samples/6-*  128.55s user 32.91s system 333% cpu 48.354 total # parallel -N4