[Community Puzzle] Number Shifting

Puzzles
#1

https://www.codingame.com/multiplayer/optimization/number-shifting

Send your feedback or ask for help here!

Created by @eulerscheZahl,validated by @codingWhale,@Alain-Delpuch and @Illedan.
If you have any issues, feel free to ping them.

#2

@eulerscheZahl the level generation seems to be broken. Every second level is the same as the previous one (with diff level hash) and also the (real) new levels are just a modified version of the previous level with 1 extra move added (so the solutions are the same with 1 extra move added at the beginning of the solution of the previous level).

#3

Hi.
There were some problems. First @dreadylein managed to reverse the random seed. Then I switched to SecureRandom yesterday while being in a hurry - and screwed up by not modifying the seed for each level.

On top of that the leaderboard reset doesn’t seem to work as expected (ping @_CG_jupoulton):
I cleared it by changing the validator. All players disappeared. Then I submitted a solution with a low score and got my old, high score on the leaderboard again:
image
Could you manually reset the leaderboard please?
I’m really sorry for any inconvenience caused to players losing their progress :frowning:

#4

So the leaderboard is cleared, but as soon as a new submission arrives, the best submission from your history is used for your ranking. I’ll get on this problem as soon as I can.

2 Likes
#5

Quick update: I reset the leaderbaord but the bug fix is not yet deployed.

1 Like
#6

Can we shift a number towards a zero? I’m tempted to think the spirit is no, else most of the second paragraph wouldn’t make sense, especially “The number has to be pushed on another number.”

But I can’t find it stated anywhere that 0 isn’t considered a number.

1 Like
#7

I get this error
java.lang.RuntimeException: Total game duration too long (>30000ms)
at com.codingame.gameengine.core.GameManager.addTurnTime(GameManager.java:575)
at com.codingame.gameengine.core.GameManager.execute(GameManager.java:192)
at com.codingame.gameengine.core.GameManager.execute(GameManager.java:226)
at com.codingame.gameengine.core.AbstractPlayer.execute(AbstractPlayer.java:101)
at com.codingame.game.Referee.gameTurn(Referee.java:56)
at com.codingame.gameengine.core.GameManager.start(GameManager.java:122)
at com.codingame.gameengine.core.RefereeMain.start(RefereeMain.java:67)
at com.codingame.gameengine.core.RefereeMain.main(RefereeMain.java:50)

It stops at level 26.
On my machine level 26 is solved in about 0.027s. I use threads.

#8

I’m aware of the issue.
This happens when you solve too many levels in a single run, as the SDK assumes 50ms for each line you print. I can partially solve this issue by reading multiple lines at once, but not solve it completely.

Replace the “first_level” by the last password from the game output to start at higher levels.
At some point you won’t be able to solve a map within 1s anyways, so you are supposed to solve it offline and submit the password along with your hardcoded solution in order to get the next level.

#9

Hi everybody, funny how long it can take to solve a puzzle for such a little grid! The first levels were quite immediate then it took me hours for level 19. I was wondering if my program would ever give a solution or had just died. :cold_sweat:
I surely need to optimize, but apart from ordering the possible moves (I try minus moves toward big numbers first and plus moves towards big numbers last) I dont’t see. Any clue? Early detection of position with no solution?

#10

Can someone also explain me why just copying the list of moves in the PHP IDE works for submitting to the referee.

#11

I suppose it is because if php script does not start with <?php , then the php interpreter simply echoes the source to output. The legacy of being designed as a server-side dynamic HTML page-generation language.

#12

Got it. Thks

#13

Some people had succes doing GA with mutation, or some other approaches that I don’t know (Westicles for example).

Others divided the problem on smaller ones, and treated it as an Exact Cover problem.
Premises:
-A number can only be used once.
-You know that a solution is when all numbers are removed. That is equal to a set of numbers that ends in a zero (you subtract a number X to another X, reaching a zero).

With these two premises you can infer that a solution probably are N sets of numbers, each set reaching a zero. The problem then changed from getting an precise move list for all numbers to find enough zero-sum sets that can be combined to cover all numbers once and only once (exact cover problem).

This approach is good in most levels below 200. Except a few hard levels most of them are solved in minutes, not hours. Above 200 the size increases a lot and the exact cover problem begins to be intractable.

2 Likes
Puzzles solvable by Algorithm X / Dancing Links
#14

Oh I see (or pretend to). If for example I find a set that ends with zero, I now have to solve a smaller equivalent problem. The first simple approach is to privilege moves that end with zero. Let’s see…

#15

No privileges. Basic steps for me are:

1-Do a lot of random moves, until you can’t move anymore. If you ever find a zero-sum set save it if you don’t already have it. Zero-sum set must be the precise list of moves to reach a 0, not all moves you did. You need to track where do you “send” each number.
2- Restart the map to the original state and repeat a lot of times the first step. Well, the basic MonteCarlo.
3-Once you have enough sets, try to find a solution. With all the zero-sum set you have, use some algorithm that solves de exact cover set problem (cover all numbers once, and only once). If you fail to find a solution, return to 1.

Some advices:
It isn’t a simple game at all, to reach higher levels it requires a lot of pieces and some patience. I ended with MonteCarlo, mutators, DLX Solver, load/save states to file, hashing, unordered sets, threads and a miriad of trials and errors. I think that I have more code that in some multiplayer games.
It’s better to hash the sets with only the numbers used, it dosen’t matter the order or the move itself, that speed up the search of a possible solution.
Some maps are noticeably hard, more than others, like 61, 100 or 138.
It’s hard to tell how many sets you need to solve a map, sometimes a couple of seconds of MC is enough to find a solution, other harder maps can take hours between MC and exact cover search.

8 Likes
#16

Here’s what I am doing:

  1. score=sum of all the numbers on the grid
  2. make random moves until you are stuck
  3. mutate by deleting a random move, and anneal
12 Likes
#17

Dumb question - but how do I progress in this?
Using ‘submit’ gets me to level 11, but I see no output or guidance as to what I succeeded or failed at, and I have never done offline submissions (but would be happy to try if it can be automated)
There’s a ‘next step’ button, but that doesn’t do anything useful

#18

Not dumb, this mechanics is rather special. If your solutions are correct, at some point you just fail from running out of time. If you look at the console output when you play a test, you should see a “Code for next level: xxxx”. If you copy paste xxxx and print it in your code (instead of “first_level”), you will play from that next level on.
To automate this or to go to levels where you need more than 1 second, there is the submit.py script in the linked github repository.

1 Like
#19

Thanks - trying the python tool now

#20

I’ve successfully completed up to about level 23 using the offline tool - but the leaderboard still says level 11 - like it’s being overridden by the value from the tests on the site