TADM2E 8.17 - Revision history

Matt: Undo revision 1088 by FuckMatt (talk)

2020-08-01T00:49:04Z

Undo revision 1088 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:14:07Z

Redirected page to UNTV

Matt: Undo revision 800 by EthanGamer (talk)

2020-07-23T13:34:25Z

Undo revision 800 by EthanGamer (talk)

EthanGamer: Blanked the page

2020-07-14T02:00:46Z

Blanked the page

Tcaner: Removed wrong solution in the wrong place

2019-12-25T01:47:54Z

Removed wrong solution in the wrong place

Tcaner: Added the solution in Java, with different implementation details.

2019-12-25T01:46:57Z

Added the solution in Java, with different implementation details.

Azazel: Created page with "Consider the following example: {|border="1" |G||G||G||G |- |G||B||G||G |- |G||G||G||G |} There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RR..."

2016-12-22T18:39:49Z

Created page with "Consider the following example: {|border="1" |G||G||G||G |- |G||B||G||G |- |G||G||G||G |} There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RR..."

New page

Consider the following example:

{|border="1"
|G||G||G||G
|-
|G||B||G||G
|-
|G||G||G||G
|}

There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD. We can start at the top-left and fill each square with the possible number of routes that lead to it:

{|border="1"
|1||?||?||?
|-
|?||B||?||?
|-
|?||?||?||?
|}

{|border="1"
|1||1||?||?
|-
|1||B||?||?
|-
|?||?||?||?
|}

{|border="1"
|1||1||1||?
|-
|1||B||?||?
|-
|1||?||?||?
|}

{|border="1"
|1||1||1||1
|-
|1||B||1||?
|-
|1||1||?||?
|}

{|border="1"
|1||1||1||1
|-
|1||B||1||2
|-
|1||1||2||?
|}

{|border="1"
|1||1||1||1
|-
|1||B||1||2
|-
|1||1||2||4
|}

Implementation in Perl:

#!/usr/bin/perl

use warnings;
use strict;

sub count_paths
{
my @bad = @_;

my $nr = @bad;
my $nc = @{$bad[0]};

my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;

for my $r (0 .. $nr - 1)
{
for my $c (0 .. $nc - 1)
{
next if $bad[$r][$c];

my $np = $r == 0 && $c == 0 ? 1 : 0;

$np += $paths[$r - 1][$c] if $r > 0 && !$bad[$r - 1][$c];
$np += $paths[$r] [$c - 1] if $c > 0 && !$bad[$r] [$c - 1];

$paths[$r][$c] = $np;
}
}

return $paths[$nr - 1][$nc - 1];
}

my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);

my $np = count_paths @bad;

print $np, "\n";

← Older revision		Revision as of 10:14, 31 July 2020
Line 1:		Line 1:
−	~~Consider the following example:~~	+	#REDIRECT [[UNTV]]
−
−	~~{\|border="1"~~
−	~~\|G\|\|G\|\|G\|\|G~~
−	\|-
−	~~\|G\|\|B\|\|G\|\|G~~
−	\|-
−	~~\|G\|\|G\|\|G\|\|G~~
−	\|}
−
−	There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD. We can start at the top-left and fill each square with the possible number of routes that lead to it:
−
−	~~{\|border="1"~~
−	~~\|1\|\|?\|\|?\|\|?~~
−	\|-
−	~~\|?\|\|B\|\|?\|\|?~~
−	\|-
−	~~\|?\|\|?\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|?\|\|?~~
−	\|-
−	~~\|1\|\|B\|\|?\|\|?~~
−	\|-
−	~~\|?\|\|?\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|?~~
−	\|-
−	~~\|1\|\|B\|\|?\|\|?~~
−	\|-
−	~~\|1\|\|?\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|1~~
−	\|-
−	~~\|1\|\|B\|\|1\|\|?~~
−	\|-
−	~~\|1\|\|1\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|1~~
−	\|-
−	~~\|1\|\|B\|\|1\|\|2~~
−	\|-
−	~~\|1\|\|1\|\|2\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|1~~
−	\|-
−	~~\|1\|\|B\|\|1\|\|2~~
−	\|-
−	~~\|1\|\|1\|\|2\|\|4~~
−	\|}
−
−	~~Implementation in Perl:~~
−
−	#~~!/usr/bin/perl~~
−
−	~~use warnings;~~
−	~~use strict;~~
−
−	~~sub count_paths~~
−	{
−	~~my @bad = @_;~~
−
−	~~my $nr = @bad;~~
−	~~my $nc = @{$bad~~[~~0]};~~
−
−	~~my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;~~
−
−	~~for my $r (0 .. $nr - 1)~~
−	{
−	~~for my $c (0 .. $nc - 1)~~
−	{
−	~~next if $bad[$r][$c];~~
−
−	~~my $np = $r == 0 && $c == 0 ? 1 : 0;~~
−
−	~~$np += $paths[$r - 1][$c] if $r > 0 && !$bad[$r - 1][$c];~~
−	~~$np += $paths[$r] [$c - 1] if $c > 0 && !$bad[$r] [$c - 1];~~
−
−	~~$paths[$r][$c] = $np;~~
−	}
−	}
−
−	~~return $paths~~[~~$nr - 1~~]~~[$nc - 1];~~
−	}
−
−	~~my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0~~]);
−
−	~~my $np = count_paths @bad;~~
−
−	~~print $np, "\n";~~

← Older revision		Revision as of 02:00, 14 July 2020
Line 1:		Line 1:
−	~~Consider the following example:~~

−	~~{\|border="1"~~
−	~~\|G\|\|G\|\|G\|\|G~~
−	\|-
−	~~\|G\|\|B\|\|G\|\|G~~
−	\|-
−	~~\|G\|\|G\|\|G\|\|G~~
−	\|}
−
−	There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD. We can start at the top-left and fill each square with the possible number of routes that lead to it:
−
−	~~{\|border="1"~~
−	~~\|1\|\|?\|\|?\|\|?~~
−	\|-
−	~~\|?\|\|B\|\|?\|\|?~~
−	\|-
−	~~\|?\|\|?\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|?\|\|?~~
−	\|-
−	~~\|1\|\|B\|\|?\|\|?~~
−	\|-
−	~~\|?\|\|?\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|?~~
−	\|-
−	~~\|1\|\|B\|\|?\|\|?~~
−	\|-
−	~~\|1\|\|?\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|1~~
−	\|-
−	~~\|1\|\|B\|\|1\|\|?~~
−	\|-
−	~~\|1\|\|1\|\|?\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|1~~
−	\|-
−	~~\|1\|\|B\|\|1\|\|2~~
−	\|-
−	~~\|1\|\|1\|\|2\|\|?~~
−	\|}
−
−
−	~~{\|border="1"~~
−	~~\|1\|\|1\|\|1\|\|1~~
−	\|-
−	~~\|1\|\|B\|\|1\|\|2~~
−	\|-
−	~~\|1\|\|1\|\|2\|\|4~~
−	\|}
−
−	~~Implementation in Perl:~~
−
−	~~#!/usr/bin/perl~~
−
−	~~use warnings;~~
−	~~use strict;~~
−
−	~~sub count_paths~~
−	{
−	~~my @bad = @_;~~
−
−	~~my $nr = @bad;~~
−	~~my $nc = @{$bad[0]};~~
−
−	~~my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;~~
−
−	~~for my $r (0 .. $nr - 1)~~
−	{
−	~~for my $c (0 .. $nc - 1)~~
−	{
−	~~next if $bad[$r][$c];~~
−
−	~~my $np = $r == 0 && $c == 0 ? 1 : 0;~~
−
−	~~$np += $paths[$r - 1][$c] if $r > 0 && !$bad[$r - 1][$c];~~
−	~~$np += $paths[$r] [$c - 1] if $c > 0 && !$bad[$r] [$c - 1];~~
−
−	~~$paths[$r][$c] = $np;~~
−	}
−	}
−
−	~~return $paths[$nr - 1][$nc - 1];~~
−	}
−
−	~~my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);~~
−
−	~~my $np = count_paths @bad;~~
−
−	~~print $np, "\n";~~

← Older revision		Revision as of 01:47, 25 December 2019
Line 103:		Line 103:

	print $np, "\n";		print $np, "\n";
−
−
−	~~The solution in Java, different example:~~
−
−	~~public static void main(String[] args) {~~
−	~~boolean[][] bad = {~~
−	~~{false,true,false,false,false,true},~~
−	~~{false,true,false,true,false,true},~~
−	~~{false,true,false,true,false,true},~~
−	~~{false,true,false,true,false,true},~~
−	~~{false,true,false,true,false,true},~~
−	~~{false,false,false,true,false,false},~~
−	};
−	~~boolean[][] visited = new boolean[bad.length][bad.length];~~
−	~~int[][] cost = new int[bad.length][bad.length];~~
−	~~for (int i = 0; i < cost.length; i++) {~~
−	~~for (int j = 0; j < cost.length; j++) {~~
−	~~cost[i][j] = Integer.MAX_VALUE;~~
−	}
−	}
−	~~int result = shortestPath(bad,visited,cost);~~
−	~~System.out.println(result);~~
−	}
−
−	~~private static class Point {~~
−	~~int x, y;~~
−	~~public Point(int x, int y) {~~
−	~~this.x = x;~~
−	~~this.y = y;~~
−	}
−
−	~~public Point toRight() {~~
−	~~return new Point(x+1,y);~~
−	}
−
−	~~public Point toDown() {~~
−	~~return new Point(x, y+1);~~
−	}
−
−	~~public Point toLeft() {~~
−	~~return new Point(x-1,y);~~
−	}
−
−	~~public Point toUp() {~~
−	~~return new Point(x,y-1);~~
−	}
−	}
−
−	~~public static int shortestPath(boolean[][] bad, boolean[][] visited, int[][] cost) {~~
−	~~int length = bad.length;~~
−	~~if (bad[0][0] \|\| bad[length-1][length-1]) {~~
−	~~return -1; // can't be solution~~
−	}
−	~~ArrayList<Point> queue = new ArrayList<>();~~
−	~~queue.add(new Point(0,0));~~
−	~~cost[0][0] = 0;~~
−	~~Point next = null;~~
−	~~while (!queue.isEmpty()) {~~
−	~~next = queue.remove(0);~~
−	~~if (next.x == length-1 && next.y == length-1) {~~
−	~~return cost[next.x][next.y];~~
−	}
−	~~visited[next.x][next.y] = true;~~
−	~~Point nextRight = next.toRight();~~
−	~~if (canMoveRightFrom(next, length, bad)) {~~
−	~~if (!visited(visited,nextRight,length)) {~~
−	~~queue.add(nextRight);~~
−	}
−	~~if (cost[nextRight.x][nextRight.y] > cost[next.x][next.y] + 1) {~~
−	~~cost[nextRight.x][nextRight.y] = cost[next.x][next.y] + 1;~~
−	}
−	}
−	~~Point nextDown = next.toDown();~~
−	~~if (canMoveDownFrom(next, length, bad)) {~~
−	~~if (!visited(visited,nextDown,length)) {~~
−	~~queue.add(nextDown);~~
−	}
−	~~if (cost[nextDown.x][nextDown.y] > cost[next.x][next.y] + 1) {~~
−	~~cost[nextDown.x][nextDown.y] = cost[next.x][next.y] + 1;~~
−	}
−	}
−	~~Point nextUp = next.toUp();~~
−	~~if (canMoveUpFrom(next, length, bad)) {~~
−	~~if (!visited(visited,nextUp,length)) {~~
−	~~queue.add(nextUp);~~
−	}
−	~~if (cost[nextUp.x][nextUp.y] > cost[next.x][next.y] + 1) {~~
−	~~cost[nextUp.x][nextUp.y] = cost[next.x][next.y] + 1;~~
−	}
−	}
−	~~Point nextLeft = next.toLeft();~~
−	~~if (canMoveLeftFrom(next, length, bad)) {~~
−	~~if (!visited(visited,nextLeft,length)) {~~
−	~~queue.add(nextLeft);~~
−	}
−	~~if (cost[nextLeft.x][nextLeft.y] > cost[next.x][next.y] + 1) {~~
−	~~cost[nextLeft.x][nextLeft.y] = cost[next.x][next.y] + 1;~~
−	}
−	}
−	}
−	~~return -2; // wrong solution~~
−	}

← Older revision		Revision as of 01:46, 25 December 2019
Line 103:		Line 103:

	print $np, "\n";		print $np, "\n";
		+
		+
		+	The solution in Java, different example:
		+
		+	public static void main(String[] args) {
		+	boolean[][] bad = {
		+	{false,true,false,false,false,true},
		+	{false,true,false,true,false,true},
		+	{false,true,false,true,false,true},
		+	{false,true,false,true,false,true},
		+	{false,true,false,true,false,true},
		+	{false,false,false,true,false,false},
		+	};
		+	boolean[][] visited = new boolean[bad.length][bad.length];
		+	int[][] cost = new int[bad.length][bad.length];
		+	for (int i = 0; i < cost.length; i++) {
		+	for (int j = 0; j < cost.length; j++) {
		+	cost[i][j] = Integer.MAX_VALUE;
		+	}
		+	}
		+	int result = shortestPath(bad,visited,cost);
		+	System.out.println(result);
		+	}
		+
		+	private static class Point {
		+	int x, y;
		+	public Point(int x, int y) {
		+	this.x = x;
		+	this.y = y;
		+	}
		+
		+	public Point toRight() {
		+	return new Point(x+1,y);
		+	}
		+
		+	public Point toDown() {
		+	return new Point(x, y+1);
		+	}
		+
		+	public Point toLeft() {
		+	return new Point(x-1,y);
		+	}
		+
		+	public Point toUp() {
		+	return new Point(x,y-1);
		+	}
		+	}
		+
		+	public static int shortestPath(boolean[][] bad, boolean[][] visited, int[][] cost) {
		+	int length = bad.length;
		+	if (bad[0][0] \|\| bad[length-1][length-1]) {
		+	return -1; // can't be solution
		+	}
		+	ArrayList<Point> queue = new ArrayList<>();
		+	queue.add(new Point(0,0));
		+	cost[0][0] = 0;
		+	Point next = null;
		+	while (!queue.isEmpty()) {
		+	next = queue.remove(0);
		+	if (next.x == length-1 && next.y == length-1) {
		+	return cost[next.x][next.y];
		+	}
		+	visited[next.x][next.y] = true;
		+	Point nextRight = next.toRight();
		+	if (canMoveRightFrom(next, length, bad)) {
		+	if (!visited(visited,nextRight,length)) {
		+	queue.add(nextRight);
		+	}
		+	if (cost[nextRight.x][nextRight.y] > cost[next.x][next.y] + 1) {
		+	cost[nextRight.x][nextRight.y] = cost[next.x][next.y] + 1;
		+	}
		+	}
		+	Point nextDown = next.toDown();
		+	if (canMoveDownFrom(next, length, bad)) {
		+	if (!visited(visited,nextDown,length)) {
		+	queue.add(nextDown);
		+	}
		+	if (cost[nextDown.x][nextDown.y] > cost[next.x][next.y] + 1) {
		+	cost[nextDown.x][nextDown.y] = cost[next.x][next.y] + 1;
		+	}
		+	}
		+	Point nextUp = next.toUp();
		+	if (canMoveUpFrom(next, length, bad)) {
		+	if (!visited(visited,nextUp,length)) {
		+	queue.add(nextUp);
		+	}
		+	if (cost[nextUp.x][nextUp.y] > cost[next.x][next.y] + 1) {
		+	cost[nextUp.x][nextUp.y] = cost[next.x][next.y] + 1;
		+	}
		+	}
		+	Point nextLeft = next.toLeft();
		+	if (canMoveLeftFrom(next, length, bad)) {
		+	if (!visited(visited,nextLeft,length)) {
		+	queue.add(nextLeft);
		+	}
		+	if (cost[nextLeft.x][nextLeft.y] > cost[next.x][next.y] + 1) {
		+	cost[nextLeft.x][nextLeft.y] = cost[next.x][next.y] + 1;
		+	}
		+	}
		+	}
		+	return -2; // wrong solution
		+	}

← Older revision		Revision as of 00:49, 1 August 2020
Line 1:		Line 1:
−	#~~REDIRECT~~ [[~~UNTV~~]]	+	Consider the following example:
		+
		+	{\|border="1"
		+	\|G\|\|G\|\|G\|\|G
		+	\|-
		+	\|G\|\|B\|\|G\|\|G
		+	\|-
		+	\|G\|\|G\|\|G\|\|G
		+	\|}
		+
		+	There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD. We can start at the top-left and fill each square with the possible number of routes that lead to it:
		+
		+	{\|border="1"
		+	\|1\|\|?\|\|?\|\|?
		+	\|-
		+	\|?\|\|B\|\|?\|\|?
		+	\|-
		+	\|?\|\|?\|\|?\|\|?
		+	\|}
		+
		+
		+	{\|border="1"
		+	\|1\|\|1\|\|?\|\|?
		+	\|-
		+	\|1\|\|B\|\|?\|\|?
		+	\|-
		+	\|?\|\|?\|\|?\|\|?
		+	\|}
		+
		+
		+	{\|border="1"
		+	\|1\|\|1\|\|1\|\|?
		+	\|-
		+	\|1\|\|B\|\|?\|\|?
		+	\|-
		+	\|1\|\|?\|\|?\|\|?
		+	\|}
		+
		+
		+	{\|border="1"
		+	\|1\|\|1\|\|1\|\|1
		+	\|-
		+	\|1\|\|B\|\|1\|\|?
		+	\|-
		+	\|1\|\|1\|\|?\|\|?
		+	\|}
		+
		+
		+	{\|border="1"
		+	\|1\|\|1\|\|1\|\|1
		+	\|-
		+	\|1\|\|B\|\|1\|\|2
		+	\|-
		+	\|1\|\|1\|\|2\|\|?
		+	\|}
		+
		+
		+	{\|border="1"
		+	\|1\|\|1\|\|1\|\|1
		+	\|-
		+	\|1\|\|B\|\|1\|\|2
		+	\|-
		+	\|1\|\|1\|\|2\|\|4
		+	\|}
		+
		+	Implementation in Perl:
		+
		+	#!/usr/bin/perl
		+
		+	use warnings;
		+	use strict;
		+
		+	sub count_paths
		+	{
		+	my @bad = @_;
		+
		+	my $nr = @bad;
		+	my $nc = @{$bad[0]};
		+
		+	my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;
		+
		+	for my $r (0 .. $nr - 1)
		+	{
		+	for my $c (0 .. $nc - 1)
		+	{
		+	next if $bad[$r][$c];
		+
		+	my $np = $r == 0 && $c == 0 ? 1 : 0;
		+
		+	$np += $paths[$r - 1][$c] if $r > 0 && !$bad[$r - 1][$c];
		+	$np += $paths[$r] [$c - 1] if $c > 0 && !$bad[$r] [$c - 1];
		+
		+	$paths[$r][$c] = $np;
		+	}
		+	}
		+
		+	return $paths[$nr - 1][$nc - 1];
		+	}
		+
		+	my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);
		+
		+	my $np = count_paths @bad;
		+
		+	print $np, "\n";

← Older revision	Revision as of 13:34, 23 July 2020
Line 1:	Line 1:
	+	Consider the following example:

	+	{\|border="1"
	+	\|G\|\|G\|\|G\|\|G
	+	\|-
	+	\|G\|\|B\|\|G\|\|G
	+	\|-
	+	\|G\|\|G\|\|G\|\|G
	+	\|}
	+
	+	There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD. We can start at the top-left and fill each square with the possible number of routes that lead to it:
	+
	+	{\|border="1"
	+	\|1\|\|?\|\|?\|\|?
	+	\|-
	+	\|?\|\|B\|\|?\|\|?
	+	\|-
	+	\|?\|\|?\|\|?\|\|?
	+	\|}
	+
	+
	+	{\|border="1"
	+	\|1\|\|1\|\|?\|\|?
	+	\|-
	+	\|1\|\|B\|\|?\|\|?
	+	\|-
	+	\|?\|\|?\|\|?\|\|?
	+	\|}
	+
	+
	+	{\|border="1"
	+	\|1\|\|1\|\|1\|\|?
	+	\|-
	+	\|1\|\|B\|\|?\|\|?
	+	\|-
	+	\|1\|\|?\|\|?\|\|?
	+	\|}
	+
	+
	+	{\|border="1"
	+	\|1\|\|1\|\|1\|\|1
	+	\|-
	+	\|1\|\|B\|\|1\|\|?
	+	\|-
	+	\|1\|\|1\|\|?\|\|?
	+	\|}
	+
	+
	+	{\|border="1"
	+	\|1\|\|1\|\|1\|\|1
	+	\|-
	+	\|1\|\|B\|\|1\|\|2
	+	\|-
	+	\|1\|\|1\|\|2\|\|?
	+	\|}
	+
	+
	+	{\|border="1"
	+	\|1\|\|1\|\|1\|\|1
	+	\|-
	+	\|1\|\|B\|\|1\|\|2
	+	\|-
	+	\|1\|\|1\|\|2\|\|4
	+	\|}
	+
	+	Implementation in Perl:
	+
	+	#!/usr/bin/perl
	+
	+	use warnings;
	+	use strict;
	+
	+	sub count_paths
	+	{
	+	my @bad = @_;
	+
	+	my $nr = @bad;
	+	my $nc = @{$bad[0]};
	+
	+	my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;
	+
	+	for my $r (0 .. $nr - 1)
	+	{
	+	for my $c (0 .. $nc - 1)
	+	{
	+	next if $bad[$r][$c];
	+
	+	my $np = $r == 0 && $c == 0 ? 1 : 0;
	+
	+	$np += $paths[$r - 1][$c] if $r > 0 && !$bad[$r - 1][$c];
	+	$np += $paths[$r] [$c - 1] if $c > 0 && !$bad[$r] [$c - 1];
	+
	+	$paths[$r][$c] = $np;
	+	}
	+	}
	+
	+	return $paths[$nr - 1][$nc - 1];
	+	}
	+
	+	my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);
	+
	+	my $np = count_paths @bad;
	+
	+	print $np, "\n";