https://www.codingame.com/multiplayer/optimization/2048
Send your feedback or ask for help here!
Created by @eulerscheZahl,validated by @wlesavo,@darkhorse64 and @Illedan.
If you have any issues, feel free to ping them.
4 Likes
Thatās a perfect puzzle to study Beam Search Algirothm!
I used this as a tutorial: https://www.codingame.com/playgrounds/11358/breadth-first-search-and-beam-search-comparison
Climbed up to 32/109 without thinking about 2048 strategy.
10 Likes
Hi there. I liked the puzzle but it was a bit of a let down to discover
all test cases pass on submission without changing the code.
Looks like the right answer is always āUā. =/
I tried to submit using C#
Would be nice if you fixed it <3
2 Likes
This is an optimization puzzle, youāre supposed to get the best score possible. If you keep the default code, all testcases will pass, but you wonāt have a very good score.
1 Like
Huhā¦ doh.
My appologizes, I will try to read the full description next time. 
Thank you!
Kind Regards
2 Likes
Same for C++
1 Like
And did you read the reply from hemhel right below?
Print something else than āUā and climb the leaderboard.
I donāt see 100% with the default code as a bug per se, the contribution just wasnāt created with the puzzle of the week achievement of the quest map in mind.
And I wonāt change it now, as it would totally mess up the chances of new players to climb the leaderboard (at least for the lower and medium ranks).
3 Likes
Hello!
Very nice puzzle, it reminds me of my school years!!
However the spawnTile method copy-pasted from the github repo doesnāt seem to work for meā¦ the spawned tile isnāt in the right place (the seed seems well managed however). And the direction values are reversed compared to the github repo (āURDLā on github, āLDRUā) in my code. But I canāt see why as my board seems oriented the same way as on github (rows = rows on the screen, col = columns on the screen).
Any idea why this is happening? @eulerscheZahl
Has anyone else had the same problem?
Thanks a lot if you can help me 
IIRC you have to count free cells column by column, not row by row, to determine which one gets a spawn.
3 Likes
oh thank you so much!!
How does the seed affect the new tiles that are spawned each turn :p?
The github link in the problem text takes you straight to the spawnTile() code.
1 Like
found this on HN today:
The Mathematics of 2048: Optimal Play with Markov Decision Processes (2018) | Hacker News
article:
The Mathematics of 2048: Optimal Play with Markov Decision Processes
2 Likes
Can't figure out how to calculate the position of the spawned number.
Example:
turn=1,seed=48610991
[[0 0 0 0]
[0 2 0 0]
[0 0 0 0]
[0 2 0 0]]
turn=2,seed=35171608
[[0 0 0 0]
[0 0 2 2]
[0 0 0 0]
[0 0 0 2]]
turn2 ist state after move 'RIGHT'.
The spawned number 2 has position (1,2)
This is what I have tried:
If I make move 'RIGHT' form turn 1, the result is:
[[0 0 0 0]
[0 0 0 2]
[0 0 0 0]
[0 0 0 2]]
Then I calculate the freeCells like its done in the Java-Github Code:
freeCells = []
for x in range(4):
for y in range(4):
if grid[x,y]==0:
freeCells.append(x+4*y)
print(freeCells)
>>> [0, 4, 8, 12, 1, 5, 9, 2, 6, 10, 14, 3, 7, 11]
Then I calculate the spawnIndex with the seed from turn1
spawnIndex = freeCells[48610991 % len(freeCells)]
print(spawnIndex)
>>> 10
Then I calculate the position of the new number:
print(spawnIndex % 4,spawnIndex // 4)
>>> 2,2
But the position of the new number is (1,2). What am I missing?
Found the error:
this should be:
for y in range(4):
for x in range(4):
What is the technique over 2,000,000 ? itās my score. And the max command in one time.
2000000, itās copy reverse the grid on diagonal, do a beam search, use the algorithm of the source code to calculate the score on the grid, and spawn a new tile with the same technique on the source code. Repeat the beam search with k=10 and depth=20, and keep path[0:7]. How to improve that ?
I thought Iād share my scores on the individual testcases. The color coding is as follows:
Green: My score is achieved online and is the theoretical maximum. There are 15 such cases.
Yellow: My score is partially hardcoded. I run an online solver, usually to around 1.74M and then it would get stuck online, but the rest of my solution is hardcoded (and heavily compressed). There are 12 cases like this.
Orange: Same as yellow but I was not able to find the theoretical maximum. There are 3 such cases.
By the way, the theoretical maximum is achieved by ignoring all movement restrictions and just letting tiles fall on top of eachother when they need to combine. It is entirely possible my scores are the actual highest possible, even for the orange 3. It is hard to be sure.
5 Likes
Hello everybody and especially MSmits (impressive 1st place),
I spent lot of time working on this puzzle and Iām pretty happy from my score (iām just an amateur) 
Nevertheless, Iām wondering how you can push a command list which size is greater than 2900 character with the limitation of 100 ko for a coding game file (29 x 3 ko is the maximum for all the cases) ?
Indeed, I wrote a C++ simulator in xcode which can double my score (by example : about 710 Ko for the first case seed = 290797) but iām unabled to submit it because the produced string is 16 Ko for one case !!
You explain that you use heavily compressed āstringsā but I studied theory about string compression and I donāt know how is possible to do that and CG dont permit use of zlib library ā¦
Do you have some tips to share please 
?
thanks !
Certainly I can do that. Itās not ācompressionā in the traditional sense. Itās more making use of the maximum capacity you can store in a character. I believe I did the following:
I store 4 moves in a single uint8_t (2 bits each, which means the array below has a capacity of 88k moves). Then I cram as many bytes as possible in as few unicode characters as I can. You can fit around 15 bit in a single unicode character, skipping some problematic characters that might be an issue copy/pasting into the CG IDE (at around unicode 8232 and in the early part of the unicode range)
Forgive the poor variable names in the code below. I did not bother renaming it to something sensible.
The code below is just the encoding. To decode, you need to do something similar. Try it yourself. If you canāt make it work, just reply here in a while and I will share the decoding function as well.
uint8_t outputCompact[22000] = { 0 };
void BytesToString()
{
int bitIndex = 0;
int number = 0;
for (int i = 0; i < 1 + outputIndex / 4; i++)
{
uint8_t byte = outputCompact[i];
number |= byte << bitIndex;
bitIndex += 8;
if (bitIndex >= 15)
{
int charNumber = number & 0x7FFF;
charNumber += 95;
if (charNumber + 97 >= 8232)
charNumber += 2;
wstring b = L"a";
b[0] += charNumber;
outputString += b;
number = number >> 15;
bitIndex -= 15;
}
}
if (bitIndex > 0)
{
int charNumber = number & 0x7FFF;
charNumber += 95;
if (charNumber >= 8232)
charNumber += 2;
wstring b = L"a";
b[0] += charNumber;
outputString += b;
}
const std::locale utf8_locale = std::locale(std::locale(), new std::codecvt_utf8<wchar_t>());
wofstream f(L"sample.txt");
f.imbue(utf8_locale);
f << outputString << endl;
f.close();
}
1 Like
Ouaou !!! 
thank you very much for the explanation !
I thought about ASCII ācompressionā (by example LL, LR, LD, LU = 1 ascii code) but i forgot unicode has many more possibilities !!
Iām not sure to be able to understand your code but Iām happy you shared it.
I will study it and certainly learn something new thanks to you
thank you very much
1 Like