ToddlerToy
SRM 810 · 2021-07-22 · by misof
Problem Statement
In this problem you will meet a Montessori toy for toddlers. It helps the toddlers develop color recognition, hand-eye coordination, fine motor skills, but most importantly, cognitive thinking and problem-solving skills.
Let's see whether you are a match for toddlers :)
The toy is a vertically placed wooden board. A hole with a comb-like shape is cut into the board. Seen from a side, the board looks as shown below: '#' is wood, '.' is a hole.
Note that we can view the board as a collection of cells: some contain wood, others are empty. The letters and numbers around the board are coordinates of those cells.
ABCDEFGHIJK
0 ###########
1 #.........#
2 ##.#.#.#.##
3 ##.#.#.#.##
4 ##.#.#.#.##
5 ##.#.#.#.##
6 ###########
Twelve pegs are placed into the hole. Each peg occupies one of the cells. The pegs are shaped so that they cannot be removed from the board, but they can freely be moved up, down, left and right.
The pegs come in four different colors, and there are three pegs of each color. We will use the digits '0' to '3' to represent the colors.
In the initial configuration, each of the vertical "comb teeth" on the board contains three of the pegs. For example:
###########
#.........#
##.#.#.#.##
##0#1#2#3##
##0#2#1#1##
##0#3#3#2##
###########
You are given the initial configuration in the
The goal of the puzzle is to rearrange the pegs into a possibly different configuration of the same shape.
You are given the goal configuration in the
A valid move consists of taking a single peg and shifting it one cell up, down, left, or right. The new cell must be empty.
For this problem we will add an extra restriction. We don't ever want the pegs to fall, because it damages the paint on them.
Thus, we require that after each move only the peg you most recently moved can be in the air (i.e., have an empty cell immediately below itself). If the most recently moved peg is in the air, you must keep holding it and moving it until it rests on wood or on top of another peg again.
Find any sequence of at most 1000 valid moves that transforms the start configuration into the goal configuration.
The description of a move is a string of length 3 of the form [column_letter][row_number][direction]. The first two characters are the current coordinates of a peg you want to move (see the first figure in the statement), and [direction] is one of "UDLR" for up, down, left, and right.
Return the concatenation of moves you want to perform, in chronological order.
Notes
- Any valid answer will be accepted. You do not have to minimize the number of moves used, you just need to be within the given limit.
Constraints
- start and goal will have the form described in the problem statement (four elements, each of length 3, together containing three copies of each of the digits '0' to '3').
{"000", "123", "213", "312"}
{"000", "123", "213", "312"}
Returns: ""
We start with the configuration in the problem statement and we want to end with the same configuration. We can simply do nothing.
{"000", "123", "213", "312"}
{"000", "123", "313", "212"}
Returns: "G3UG2UG1LI3UI2UI1LH1LG1DG2DF1RG1RH1RI1DI2D"
The returned answer first moves the '2' peg away from the top of the third column: ########### #....2....# ##.#.#.#.## ##0#1#.#3## ##0#2#1#1## ##0#3#3#2## ########### Then it moves the '3' peg from the top of the fourth column to the top of the third column: ########### #....2....# ##.#.#.#.## ##0#1#3#.## ##0#2#1#1## ##0#3#3#2## ########### And finally it moves the peg '2' from its temporary location to where it belongs.
{"000", "123", "213", "312"}
{"210", "003", "213", "312"}
Returns: "C3UC2UC1RD1RE1RF1RG1DC4UC3UC2UC1LE3UE2UE1LD1LC1DC2DC3DE4UE3UE2UE1LD1LC1DC2DB1RC1RD1RE1DE2DE3DG2UG1LF1LE1DE2D"
A slightly more complicated task that involves the movement of (at least) four pegs. Note that our returned solution does not do this in an optimal number of moves. This is to illustrate that minimizing the number of moves is not required. Our solution starts by moving the '0's that are not in their places away from the leftmost column: ########### #.........# ##.#.#0#.## ##.#1#2#3## ##0#2#1#1## ##0#3#3#2## ########### ########### #0........# ##.#.#0#.## ##.#1#2#3## ##.#2#1#1## ##0#3#3#2## ########### Then we move the '1' to its desired location and we follow it by moving the '2' to its desired location: ########### #0........# ##.#.#0#.## ##2#.#2#3## ##1#.#1#1## ##0#3#3#2## ########### And we finish by bringing the '0's to the now-empty locations in the second column.
{"300", "011", "122", "233"}
{"000", "111", "222", "333"}
Returns: "C3UC2UC1RD1RE1RF1RG1RH1RI1RE3UE2UE1LD1LC1DC2DG3UG2UG1LF1LE1DE2DI3UI2UI1LH1LG1DG2DJ1LI1DI2D"
Our returned solution performs a cyclic shift of the four misplaced pegs: first it moves the '3' peg out of the way, then it moves '0', '1', and '2' to their correct columns, and finally it moves the '3' from its current location to the now-empty space in its column.
{"000", "111", "222", "333"}
{"111", "222", "333", "000"}
Returns: "C3UC2UC1LC4UC3UC2UC1RD1RE1RF1RG1RH1RI1RC5UC4UC3UC2UC1RD1RE1RF1RG1DE3UE2UE1LD1LC1DC2DC3DC4DG2UG1LF1LE1LD1LC1DC2DC3DJ1LI1LH1LG1LF1LE1LD1LC1DC2DB1RC1RD1RE1DE2DE3UE2UE1RE4UE3UE2UE1LD1LC1DE5UE4UE3UE2UE1LD1LC1LB1RC1RD1RE1DE2DE3DE4DF1LE1DE2DE3DC2UC1RD1RE1DE2DC3UC2UC1LC4UC3UC2UC1RD1RE1RF1RG1RH1RI1RE3UE2UE1LD1LC1DC2DC3DJ1LI1LH1LG1LF1LE1LD1LC1DC2DB1RC1RD1RE1DE2DE3UE2UE1RE4UE3UE2UE1LD1LC1DE5UE4UE3UE2UE1LD1LC1LF1LE1DE2DE3DE4DC2UC1RD1RE1DE2DE3DB1RC1RD1RE1DE2DC3UC2UC1LE3UE2UE1LD1LC1DC2DB1RC1RD1RE1DE2DE3UE2UE1LD1LC1LE4UE3UE2UE1RF1RG1RH1RI1RE5UE4UE3UE2UE1LD1LC1DG3UG2UG1LF1LE1DE2DE3DE4DC2UC1RD1RE1DE2DE3DJ1LI1LH1LG1LF1LE1DE2DB1RC1RD1RE1RF1RG1DG2DG3UG2UG1RG4UG3UG2UG1LF1LE1DG5UG4UG3UG2UG1LF1LE1LD1RE1RF1RG1DG2DG3DG4DH1LG1DG2DG3DE2UE1RF1RG1DG2DE3UE2UE1LD1LC1LE4UE3UE2UE1RF1RG1RH1RI1RG3UG2UG1LF1LE1DE2DE3DJ1LI1LH1LG1LF1LE1DE2DB1RC1RD1RE1RF1RG1DG2DG3UG2UG1RG4UG3UG2UG1LF1LE1DG5UG4UG3UG2UG1LF1LE1LH1LG1DG2DG3DG4DE2UE1RF1RG1DG2DG3DD1RE1RF1RG1DG2DE3UE2UE1LD1LC1LG3UG2UG1LF1LE1DE2DB1RC1RD1RE1RF1RG1DG2DG3UG2UG1LF1LE1LD1LC1LG4UG3UG2UG1RH1RI1RG5UG4UG3UG2UG1LF1LE1LD1LC1DI3UI2UI1LH1LG1DG2DG3DG4DC2UC1RD1RE1RF1RG1DG2DG3DJ1LI1LH1LG1DG2DB1RC1RD1RE1RF1RG1RH1RI1DI2DI3UI2UI1RI4UI3UI2UI1LH1LG1DI5UI4UI3UI2UI1LH1LG1LF1RG1RH1RI1DI2DI3DI4DJ1LI1DI2DI3DG2UG1RH1RI1DI2DG3UG2UG1LF1LE1LD1LC1LG4UG3UG2UG1RH1RI1RI3UI2UI1LH1LG1DG2DG3DJ1LI1LH1LG1DG2DB1RC1RD1RE1RF1RG1RH1RI1DI2DI3UI2UI1RI4UI3UI2UI1LH1LG1DI5UI4UI3UI2UI1LH1LG1LJ1LI1DI2DI3DI4DG2UG1RH1RI1DI2DI3DF1RG1RH1RI1DI2DG3UG2UG1LF1LE1LD1LC1LI3UI2UI1LH1LG1DG2DB1RC1RD1RE1RF1RG1RH1RI1DI2D"
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ToddlerToy with a public method string solve(vector<string> start, vector<string> goal) · 60 test cases · 2 s / 256 MB per case