[GO] I actually expressed the older sister problem in code and calculated it

What's the problem with your sister?

https://www.youtube.com/watch?v=Q4gTV4r0zRs ** "How to count Fukashigi" With your sister! Let's count together! ** **

This is a youtube video. This is a video in which an older sister who wants to convey the explosion of combinations spends her entire life teaching the greatness of combinations.

The issues addressed here are "There are N x N squares, and you can take a detour from the start on the upper left to the goal on the lower right, so how many directions can you take?" That is. Everyone is told to count, so there is no choice but to count.

The only restriction is that you must not follow the same path.

** I'm curious, so I'd like to verify it myself !! **.

This algorithm

~~ Respect your sister ~~ Use a straightforward method. Specifically, in the case of 2x2, the judgment is as follows. Here, for the sake of explanation Start with [0] [0] and finish with [2] [2].

① First, pack [0] [0] on the stack ② Remove [0] [0] from the stack ③ Decide whether to move up. (I can't proceed this time) ④ Decide whether to proceed downward. (Proceed this time) ⑤ Fill the stack with routes that proceeded from [0] [0] → [1] [0]. ⑥ Decide whether to proceed to the right. (Proceed this time) ⑦ Fill the stack with routes that proceeded from [0] [0] → [0] [1]. ⑧ Decide whether to proceed to the left. (I can't proceed this time) ⑨ Return to ②. (At that time, if the stack is empty, the process ends)

It's a very simple algorithm.

Let the route decide

I wanted to practice implementing it in an object-oriented manner, so I considered it based on that policy.

When implemented like a transaction script, "This route has taken this route, so you can go to the right or left." ** Humans ** judge,

"Route-kun, can you go to the right?" "Yes" Let them decide whether the actual route can go to the right or to the left.

In particular

List<Integer> route = routeSet.getLatest();
if (route == (Some condition)){
Recommended to the right
}

not

if (route.canGoLeft())

Let the route decide, and the actual movement

route.goLeft();

I would like to implement it like this.

Source code

I wrote it with the intention of letting the above route make a decision.

I intended to implement it so that the movement can be intuitively understood without actually being aware of the contents of the Route class. I wanted to standardize the processing after moving the route, but I couldn't think of a good name, and it ended up being a mysterious method name such as postMoveProcess ...

import java.util.Scanner;
import java.util.Stack;

public class MazeSolver {

	private static long count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len = sc.nextInt();
		sc.close();

		long start = System.nanoTime();
		Stack<Route> stack = new Stack<>();

		stack.add(new Route(len));

		while (stack.size() > 0) {
			Route route = stack.pop();
			if (route.canGoDown()) {
				Route clone = route.clone();
				clone.goDown();
				postMoveProcess(stack, clone);
			}
			if (route.canGoUp()) {
				Route clone = route.clone();
				clone.goUp();
				postMoveProcess(stack, clone);
			}
			if (route.canGoRight()) {
				Route clone = route.clone();
				clone.goRight();
				postMoveProcess(stack, clone);
			}
			if (route.canGoLeft()) {
				Route clone = route.clone();
				clone.goLeft();
				postMoveProcess(stack, clone);
			}
		}
		System.out.println(count + "Street");
		System.out.println(((System.nanoTime() - start) / 1000000) + "ms");
	}

	private static void postMoveProcess(Stack<Route> stack, Route route) {
		if (route.isGoal()) {
			route.printRoute();
			count++;
			return;
		}
		stack.add(route);
	}
}

Next is the implementation of the Route class. [0] [0] and two-dimensional array seemed to be difficult, so

[0][0] → 0
[0][1] → 1
[0][2] → 2
[1][0] → 3
・ ・ ・
[2][2]→8

It was managed as a one-dimensional array like. (This time, the length of the route was not decided and the output seemed to be difficult, so it is heavy, but I used ArrayList ...)

import java.util.ArrayList;

class Route implements Cloneable {

	private int len;

	private int goal;

	private ArrayList<Integer> route;

	private int location;

	Route(int len) {
		this.len = len + 1;
		this.route = new ArrayList<>();
		route.add(0);
		this.goal = (len + 1) * (len + 1) - 1;
		this.location = 0;
	}

	public boolean contains(int point) {
		return route.contains(point);
	}

	public boolean canGoUp() {
		int newLocation = location - len;
		if (newLocation < 0 || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goUp() {
		int newLocation = location - len;
		if (!canGoUp()) {
			return;
		}
		move(newLocation);
	}

	public boolean canGoDown() {
		int newLocation = location + len;
		if (newLocation > goal || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goDown() {
		int newLocation = location + len;
		if (!canGoDown()) {
			return;
		}
		move(newLocation);
	}

	public boolean canGoRight() {
		int newLocation = location + 1;
		if (newLocation % len == 0 || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goRight() {
		int newLocation = location + 1;
		if (!canGoRight()) {
			return;
		}
		move(newLocation);
	}

	public boolean canGoLeft() {
		int newLocation = location - 1;
		if (location % len == 0 || contains(newLocation)) {
			return false;
		}
		return true;
	}

	public void goLeft() {
		int newLocation = location - 1;
		if (!canGoLeft()) {
			return;
		}
		move(newLocation);
	}

	private void move(int newLocation) {
		location = newLocation;
		route.add(newLocation);
	}

	public boolean isGoal() {
		return location == goal;
	}

	public void printRoute() {
		System.out.println(route.toString());
	}

	@SuppressWarnings("unchecked")
	@Override
	public Route clone() {
		Route clone = null;
		try {
			clone = (Route) super.clone();
			clone.route = (ArrayList<Integer>) this.route.clone();
		} catch (Exception e) {
			e.printStackTrace();
		}
		return clone;
	}
}

I think it's a bit redundant, but I feel that the advantage of being able to understand the caller of Route is greater.

Let's do it!

The 2x2 output looks like this: Whether it was successful to make various judgments on the points, it worked properly from the first shot.

I learned from the realization that the more complicated the logic, the stronger the object orientation.

2
[0, 1, 2, 5, 8]
[0, 1, 2, 5, 4, 3, 6, 7, 8]
[0, 1, 2, 5, 4, 7, 8]
[0, 1, 4, 3, 6, 7, 8]
[0, 1, 4, 5, 8]
[0, 1, 4, 7, 8]
[0, 3, 4, 5, 8]
[0, 3, 4, 1, 2, 5, 8]
[0, 3, 4, 7, 8]
[0, 3, 6, 7, 8]
[0, 3, 6, 7, 4, 5, 8]
[0, 3, 6, 7, 4, 1, 2, 5, 8]
12 ways
1ms

Stop the output for each route (because the IO here seemed to take a lot of time) The result of executing it is as follows. ~~ 7 is being verified. ~~

Impressions

――I was able to feel the effect while practicing object-oriented programming. ――Although it's still new, it's amazing that a computer can calculate nearly 600 million routes in a realistic amount of time. ――I experienced the combinatorial explosion. ――I understand your sister's feelings.