give high scoring cpp sol Overview Hex tiles are ...

Question

give high scoring cpp sol

Overview
Hex tiles are hexagonal tiles with edges connected by 3 segments. These tiles are arranged in a hexagonal grid with N tiles on each border. Segments connected between adjacent tiles form paths that run across the grid. Paths enter and exit the grid via tile edges that are on the border of the grid. The grid has B bonus tiles, which give you bonus points when a path crosses them. Each turn you can rotate a single tile clockwise or anti-clockwise. Given a list of exit pairs, your task is to create paths between them.

A path that connects a given pair of exits is called a matched path. The score of a matched path is its length (number of segments) multiplied by (b+1), where b is the number of bonus tiles that it crosses. The total path score t is the sum of all matched path scores. Your final score is the number of matched paths multiplied by (t - m*M), where m is the number of moves taken and M is the provided move penalty. If the final score is negative then it will be set to 0.

Here is a possible solution for seed=1. The coloured paths are the matched paths, while the gray paths are the unmatched paths. Loops are shown in black. The highest scoring path is shown with a thick line. The bonus tile is coloured in cyan. The last rotated tile is highlighted with a thick border. The numbers in the center of each tile (using the -showCoords option) show the coordinate of each tile in the "(row, column)" format. The numbers around the border tiles represent the target exit pairs in the format "p - q", where exit p must match exit q (0-based). Exits are numbered in a clockwise fashion starting from 0 in the top-left tile.

seed1.png

Hexagonal Grid Representation
The hexagonal grid of size N is represented as a square grid of size W*W, where W = 2N-1. Note that some of the corner cells in the square grid are unused (null). The following diagram shows the correspondence where the coordinates are in the "(row, column)" format.

coordinates.png

Tile Format
Each tile contains 3 segments joining its edges. The location of these segments depends on the tile's orientation - a number between 0 and 5, inclusive. The following diagram shows a tile in every possible orientation.

tiles.png

Input and Output
Your code will receive the following input values, each on a separate line:

N, the grid size.
M, the move penalty.
B, the number of bonus tiles.
P, the number of matching exit pairs.
P lines describing the matching exit pairs, formatted as "p q", where p and q are 0-based exit ids.
W*W lines describing the grid in row-major order, where each tile's orientation is represented as a number between 0 and 5, inclusive. Unused tiles are -1.
B lines describing the location of the bonus tiles, formatted as "row column" (0-based).
Your solution must output the following:

m, the number of moves.
m lines representing your moves, formatted as "r c dir". This will rotate a tile at location (r, c), both 0-based. The rotation will be clockwise when dir is +1 and anti-clockwise when it is -1.
Scoring
Your raw score is the final score obtained by your solution. If your return is invalid, your raw score for that test case is -1. Possible reasons include:

Using an invalid move format.
Using more than 24NN moves.
Trying to rotate tiles that are out of bounds or using an invalid rotation direction.
Exceeding the time limit.
If your raw score for a test case is negative, then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is YOUR/MAX, where YOUR is your raw score and MAX is the largest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalized to 100.

Test Case Generation
Please look at the generate() method in the visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

N, the grid size is between 3 and 20, inclusive.
M, the move penalty is between 1 and 5, inclusive.
B, the number of bonus tiles is between 1 and 10, inclusive.
The target grid is created by generating each tile's rotation at random between 0 and 5, inclusive. The paths formed in the target grid are used to determine the target exit pairs.
The provided grid is created by generating each tile's rotation at random between 0 and 5, inclusive.
B distinct bonus tiles inside the grid are chosen at random.
All values are chosen uniformly at random.
Notes
The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
The compilation time limit is 30 seconds.
There are 10 example test cases and 100 provisional test cases. There will be 5000 test cases in the final testing.
The match is rated.
Languages Supported
C#, Java, C++, Python, Rust and Kotlin.

Submission Format
Your submission must be a single ZIP file not larger than 500 MB, with your source code only.
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.

Make sure you name your Source Code file as HexTiles.<appropriate extension>

Sample Submissions
Here are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions:

Java Source Code - HexTiles.java.zip
C++ Source Code - HexTiles.cpp.zip
Python Source Code - HexTiles.py.zip
C# Source Code - HexTiles.cs.zip
Rust Source Code - HexTiles.rs.zip
Kotlin Source Code - HexTiles.kt.zip
Tools
An offline tester is available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.

Downloads
Visualizer Source - HexTilesTester.zip
Visualizer Binary - tester.jar.zip
Offline Tester / Visualizer
Your solution should interact with the tester/visualizer by reading data from standard input and writing data to standard output.

To run the tester with your solution, you should run:

java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation.
If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\HexTiles.exe" or "~/topcoder/HexTiles".
In case your compiled solution is to be run with the help of an interpreter, for example, if your program is in Java, the command will be something like "java -cp C:\TopCoder HexTiles ".

Additionally, you can use the following options:

-seed <seed>. Sets the seed used for test case generation. Seed 0 generates random grids. Seed 1 uses the lowest values of the parameters. Seed 2 uses the highest values of the parameters. The default seed value is 1.
-debug. Print debug information.
-noanimate Do not display the animations and only show the final state.
-novis. Turns off visualisation.
-manual. Play the puzzle manually. Use the left click to rotate tiles anti-clockwise and the right click to rotate tiles clockwise.
-pause. Starts the visualizer in paused mode. See more information below.
-delay <delay>. Sets the delay (in milliseconds) between visualizing consecutive simulation steps, default is 100.
-showCoords. Show tile coordinates.
-showOriginal. Show the target grid by setting it as the provided grid.
-N <N>. Sets a custom grid size.
-M <M>. Sets a custom move penalty.
-B <B>. Sets a custom number of bonus tiles.
The visualizer works in two modes. In regular mode, steps are visualized one after another with a delay specified with the -delay parameter. In paused mode, the next move will be visualized only when you press any key. The space key can be used to switch between regular and paused modes. The default starting mode is regular. You can use the -pause parameter to start in paused mode.

Marathon local testers have many useful options, including running a range of seeds with a single command, running more than one seed at time (multiple threads), controlling time limit, saving input/output/error and loading solution from a file. The usage of these options are described here.

Answer 1

I built a stronger C++17 marathon solver using the exact tile/path rules from your tester.

Files

[HexTiles.cpp]
Ready-to-submit ZIP — contains only HexTiles.cpp

The main improvement over a basic local search is the objective. Comparing only the number of matched paths gives almost no gradient. Instead, the solver takes the current boundary pairing and the target pairing and overlays them. Their union consists of alternating cycles. If there are P cycles, the boundary pairing is exactly the target pairing. So the search uses the number of alternating cycles as a strong continuous-ish signal:

text
target:
0---5    1---7    ...

current:
0---7    1---5    ...

union => alternating cycles

more cycles  => current pairing is closer to target
P cycles     => every exit pair matches

The solver then uses three stages:

Topology simulated annealing
- rewards alternating-cycle count heavily;
- also rewards exact matches and matched-path length;
- accounts for the final rotation penalty;
- uses random kicks when trapped.
Coordinate improvement
- checks all six orientations of individual tiles;
- strongly prefers increasing/preserving the boundary topology;
- breaks ties using actual score.
Final score annealing
- switches focus to the real objective matches * (pathScore - M * moves);
- this matters because forcing all pairs to match is not always optimal when rotations are expensive.

The evaluator only traces paths starting at boundary exits. Internal loops don't affect the score, so an evaluation is roughly O(N²) rather than doing unnecessary work. Bonus tiles are counted once per path, matching the tester implementation.

Another important detail is that search moves and submitted moves are separated. The search directly considers final orientations. At the end, each tile is rotated to that orientation using the minimum of clockwise/anticlockwise distance, so every tile costs at most three submitted moves.

On some local runs against your uploaded tester I got approximately:

text
seed 1:       520
seed 2:   780,200
seed 3:   569,268
seed 4:    65,736
seed 5:   403,680

The solver is stochastic/time-based, so exact results can vary slightly by machine/run.

Compile with:

bash
g++ -O3 -std=c++17 HexTiles.cpp -o HexTiles

and test with:

bash
java -jar tester.jar -exec "./HexTiles" -seed 1 -novis -noanimate

The source uses about 8.7 seconds internally, leaving some safety margin below the 10-second limit.

give high scoring cpp sol Overview Hex tiles are ...

Pregunta

Pensamiento

Respuesta

Compartir este Q&A