This topic is for the purpose of discussing #10455: synabler, FractalFusion & NoMercy's GBA Notenogram "all puzzles" in 01:54.035

You can start 1 frame earlier by pressing Start on frame 282, then A on 283. Here is what I got using Thread #27349: Computationally Optimizing Nonogram TASes: (I said in the thread that the optimum for things 1 is 90, but these are the same routes, just using a different timing method)

things 1
89
U L U .U R D R D R U. U L URU R. R D .D. D. D. D. D. D L DL R.R D. D LD L U L D L U L D L. L U .U .U R.R UR L U LD L U .U. U. U. U .U .U R .R. R. R

things 2
118
D L U. U LUL R U R D R. R .R U R DR L DL D RD L .L DR D .D L.L.L U. U LU L DL U L U .U RU L U RU R U RD RU RD R UR DR UR D R DR D L DR D. D L. L DR D. D. D. D L. L .L U LD L. L U LD L .L U .U. U 

things 3
108
L R. R U R U R D. D L ULU L D L U L.L DL U L UR U R U R D R U R D R U R D R U R D R U R D LD R D L D R D L D R D L D R D L D L. L. L URU L DLD L URU L. L D.D L .L. L U. U RU L. L UR U R L.L

things 4
69
R D L D R D LD U L U L D LDL U RU L U R U R D R U R UL U .U R U L U R DR D. D URU R D L D R D .D L D R D L DR D. D L.L.L D

things 5
123
R DR DR UR U L U R U .U L D LD UL U LU RU R DR U R D R U R D. D L D R D L D R D L D R D L.L DR DR D L .L.L ULU LD LD L U L D L U L D L U .U R U L U.U D RDR D R U R D R U R LU L. LU L UL URU R U L UL RU L .L D. D

nature 1
93
L UR UR U R. R U L U L D UL D L D R D L DL D L U L D L D R DL R D R U. U R DR D. D L D R D R U R U L U R U L U RU RD R U L U R. R U R D R D L. L D R D LD L DL D RUR DR D

nature 2
97
U L U R U R D R LD R DR D RU R UR U LU L. L. L U LU L DL D L. L. L DL D RD R. R D RD LD L .L DL D. D R. R. R. RU R D R U R LU L U. U R D RU RD R. R DR D. D L. L. L

nature 3
95
L.L UL UL UL U .U R .R DR DR D. D RD R UR U .U RU RU R. R D. D LD .DL DL DR DL D .D URUR DR D LD LD L .L ULU L DRD L .L. L. L UL UL U RU RU DR D. D

nature 4
106
DR D RD R LDLD L DL U L D L U.U D L D L U RU L U R U L U R UR U L D L U. U. URU L U R .R DR D R.RDR D R U R UR D LU L U LU R DR U R D R U R D .D L D R D LD RD LD LD RDR D .D LU LD

nature 5
108
R LUL .LDL. L.L U RU L U R.R L U L U R .R D R U R .R.R. R D L D R DR U R U L U R .R .R D L DR D. D. D. D LD L RD L D LD L URU L .L. L D RD L D L U LU RU L .L U LUL D R D L D R D L D 

symbol 1
122
L U L.L D L D L U .U .U R U L U RU R D RU R .R DL DL R D R U RD R U R D R U LULU R. R. R.R D.D. D L DLD R D L D.D R D L DRD L. L. L. L URU L U R U.U. U L D L.L D .D. D. D. D L UL U. U LU L D. D R D L D 

symbol 2
didn't finish running, but seems to be 130

symbol 3
80
R U D.D .D. D R UR UR U. ULU RU R LUL U D.D L .L .L. L. L U. U DLD L RDR DR DL D. D L DL R.R D. D. D RURU R D. D R. R .R UR

symbol 4
91
R U R U L U R U. U DRDRD R D L D.D. D LD R DRDR LD L U L U LDLDL U .U R U L UR U L U L D L U. U. U LU R U L U L D L D. D. D. D R DRD R D L D .D L D L U. U

symbol 5
107
RD R D R D L DR D LD L UL URU L UL U RU LU L. L D.D .DRD L DRD L UL D L U. U R U L U R U L U R UL U R D RU R .RUR U R DR D L.L D R D RD UR URU R. R D.D L DL D R.R D.D L D.D R

portrait 1
112
UL U L UL D.D RDR DRD R DL D.D L UL. L D R D L .L. L U R U L U R UL UR UL U RU L U R U L U R. R D RU R. R. R D R U R DR U R D RD L D R D L D R D LULULU L DR D RD R D LD LD L D L RD R. R .R 

portrait 2
114
L R U RU R. R DLD. D .D L UL DLD L UL U R U L RU LU L UL D. D .D. D RD L D RD RD R. R. R D R U R D R U. U R. RD R U LU L UL UR DR UR LUL U R U R U L UR U L D L U L .L. L DL U L D LU L DL U L D

portrait 3
106
D.D L. L DL UL U. U R.R U. U L DL U LU RU RD RU RD RU R.R DL D R D .D RUR U LU R U RUR D. D. D L DR D. D LD L D L D RDRDR L. LU L D L U.U L. L DRD L U L U L D.D L .L .L

portrait 4
106
DRD L DLD L. L U L U L D RD LD R.R D R U R D R. R UR U.URU DRD L D RD RUR U L U R U. U .U. U. U. U. U. U L DLDL D UR ULU L. L DLD ULU DLD R D L DLD UL U L U R U L U R. R

portrait 5
107
D R D L.L U L RURURU R. R DR DR UR U LU R U LU LD LU LD LU L. L DL .LU L D L D. D R.R. R LDL DL D .D RD R LDL D.D R U R UR D R D U.U R D RDR UR U R D R D R U .U LU L RU R U

story
102
.. R U RU DR D R UR URU L DL U L U L U DLDL D L D L. L U RU RU R LU L DL U L D L D R D L D. DR D. DR D RD RD R U R D. D R U R U LU L.L U R U R .R D R UR UR D.D L DL D R DR D

There are still a few things left to resolve:

• Symbol 2 took forever, so I turned it off for now and need to resume tomorrow.
• There was a small bug in my program (I found while making the Dr. Sudoku TAS and fixed) where I apparently got Concorde to confuse and give a slightly worse solution. I don't know if it affected any of the problems for this game, but I would need to rerun some of them. Fortunately those ones don't take too long.
• I didn't consider that the D-pad restriction also applies for transitions between selecting a level and solving it, e.g. since my route for Things 4 start with R, it's not actually optimal if I also select the level with R+A. I would need a different optimal route, or a different order of levels.

Here is an updated TAS with synabler's improvements so far (Symbol 2 not final): https://tasvideos.org/UserFiles/Info/639147416743231721 (will credit synabler when improvements are final) As for puzzle path, maybe the following (depending on the first move for the Symbol 2 puzzle): Things 4 can only go to Things 3 or Things 5 or Nature 4, all of which cost a frame, and it doesn't seem possible to end on Things 4 without delay.

Symbol 2 route, as well as alternative routes in some levels:

things 4
69
L D L U L D L D R DL D RUR U R D R D UR U L U R U L UL U. U R U L U R DR D.D U R U R D. D L DR D L D R D L DR D. D L.L.L D 

nature 1
93
R UL U R U R. R U LU D L U L D L D R LD LD LD U L D L D R DL R D R U. U R U R DR D L D. D L D R D R U R. R U L. L U R U RU R U L U R. R U R D R D L. L D R D LD L DR DR D 

symbol 1
122
R. R D L DRD L D R DLD R. R .R. R U.U L U R ULU R U L URU R U. U.U L.L. L. L DRDR D L U L D L UL D L U L UR U R L.L DL U L DL D R D L D. D. D R U R U R.R D .D. D. D .D. D. D L UL U. U LU L D. D R D L D 

symbol 2
131
L D RD L D R D R U R U L U R U L U L U R U L.L U.U R DR U RDR D R U R D. D L. L D.D R D .D URU R D. D .D. D .D ULUL D L D R D L .L UL. L D L U. U LUL D L D L D R .R U LUL U R U R U LDL U. U R U L U R U L U. U R .R D.D R D L D

symbol 3
80
R U D.D. D. D R UR UR U .ULU. U R.R L ULU D LD L. L. L ULU D LD L R.R D RD LD .D .D L DL R.R D. D. D RURU R D .D R .R. R UR
80
UR D. D .D. D R UR UR U. ULU .U R. R LUL U DLD L. L. L UL U DLDL R .R D RD. DL D LD R D L.L RDR D .D RURU R D. D R .R. R UR

symbol 4
91
L D L U .U. U LU R U L U L D L D. D. D .D R DRD R D L D L.L D. D R U R. R.RDR U. U R U L UR U L U R U R U L U R U .U DRDRD R D L D.D. D. D L D. D R D R UR
91
R U R U L U R U. U DRDRD R D L D.D .D LD R DRDR LD L U L U LDLDL U RU L U R U. U L U L D L U .U. U LU R U L U L D L D. D .D. D R DRD R D L D. D L D L U. U

symbol 5
107
UR U L U R.R U LU L D LDL. L. L. L D R D L D R D L D R D L D. D R U RD R U.U L U.U. U.U R. R DR DL D RD R DLD RD R UR U LU R U L U L UR UR URU R. R D.D L DL D R.R DLD R D.D L
107
LU L. L URU L. L .L D R D L D R D L D R D L D. D R U RD R U.U L U.U R.R D RD R DLD RD R UR U. U L U R UR U LU DL D L UL UR U L U. U .U R DR D R.R. R. R D.D L DRD. DLD R D.D L

portrait 2
114
L R U RU R. R DLD LDL RD R U RD RU DR UR LUL U R U R U L U R U L DL U L. L. L. L D L U L .L .L .L D R DL D R DL D URUR DR DL R D L D L UL D. D RD RD R U.U R D.D R D R U R D R U. U R U R DR D L
114
U RU R. R DLD LDL U L UL UL D.D R D L D RD R .RUR UR D R UR DR UR LUL U R U R U L U R U L. L D LU L .L. L D L U L. L DL U L D .D. D R DL D .D RD L D RD RD R. R. R D R U R D R U. U R U R DR D L

level select (. = levels we don't have to worry about)
..L.R
.ULDR
.L...
..DDD

Thanks, synabler. Now down to 6812 frames (not yet confirmed final) The path I used is the one in the top left of the image shown below. There were two extra lag frames before a couple puzzles. I tried the other two but they also had two lag frames. synabler: Did you confirm that the numbers above are optimal for each puzzle (including 131 for Symbol 2, even though you mentioned "130" earlier)?

Is this program available to use? It would help massively with some picross TASes I'm making.

The code can be found here, but it still needs some more work in order to make it usable in other games:

• The codebase is still undocumented and not actually usable without modification (it will actually optimize Dr. Sudoku; for Notenogram replace the contents of main.rs with notenogram.rs), so I need some cleanup.
• Since different games may have different movement systems, the code to compute the distance matrix would have to be manually implemented. I think this could be made more accessible somehow, but I don't have an idea yet.
• Although Concorde is quite fast, the graphs generated from this game are much larger than Dr. Sudoku (can go up to over 1,000 nodes) and some of them take a long time to solve, longest being Symbol 2 which took a few hours. I imagine most Nonogram games would have hundreds of puzzles that are also larger than 12x12, for which my program wouldn't be scalable yet. I need to investigate how to either make it faster, or to use a good enough heuristic that doesn't guarantee optimum but is much faster.

synabler: Did you confirm that the numbers above are optimal for each puzzle (including 131 for Symbol 2, even though you mentioned "130" earlier)?

Yes, they are optimal to my knowledge (unless there is a bug of course), since Concorde guarantees optimal solutions to TSP. For Symbol 2, from Concorde's intermediate outputs I guessed the answer would be 130, but it was actually 131. EDIT: oh right, I just remembered there used to be a bug I mentioned in my first post. I reran all of them since then to confirm, IIRC. For the 10 levels that don't have alternative routes, I'll modify the program to check whether the first movement direction is really forced, then it'll be finalized for me.

Funnily enough, there are multiple solutions for at least one of the puzzles, although the game doesn't recognize it as a solution (only the one shown in the TAS works):

For the 10 levels that don't have alternative routes, I'll modify the program to check whether the first movement direction is really forced, then it'll be finalized for me.

Before I finalize everything, did you find anything else? (I don't think Things 3, Things 5 or Nature 4 have an alternative first move direction.)

Just confirmed that all except Symbol 2 have no alternatives. Symbol 2... I feel like it shouldn't have one either, but I'll run it tomorrow.

Turns out Symbol 2 did have an alternative:

131
R U L U R U L.L U.U R DR U RDR D R U R D .D L. L DRD L. L D L D R D L D L. L U R U L U .U LUL U R U L U.U L. L D .D R D L D R D L D RD R U LDL D R. R D L .L D. D R U R D RUR D R U R DR. R .R U L U R U. U. U RU R D. D. D. D. D

which finally makes it possible to avoid all transition delays:

. .-L .-R
| | |   |
.-U L-D R
      | |
.-.-.-. .
|       |
.-.-D-D-D

and with that, it's finalized for me.

Thanks, synabler. One more frame saved (still two lag frames) and so the final TAS is 6811 frames long: https://tasvideos.org/UserFiles/Info/639162225258329106 I added you as co-author and finalized the TAS. Judges, please replace the movie file with this one.

This movie has been published. The posts before this message apply to the submission, and posts after this message apply to the published movie. ---- [7215] GBA Notenogram "all puzzles" by synabler, FractalFusion & NoMercy in 01:54.035