fork download
copy 
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. var FREE, TAKEN byte
  6.  
  7. type Position struct {
  8. 	X int // This is the width position
  9. 	Y int // This is the heigth position
  10. }
  11.  
  12. // TODO: Make an enhacement to implement memoization on this problem. Too many recursion calls
  13. func canBeQueen2(matrix [][]byte, currentPosition Position, prevPosition Position, end int) bool {
  14.  
  15. 	// Validate the currentPosition, 0 or > len(matrix) must return false
  16. 	if currentPosition.Y < 0 || currentPosition.Y >= len(matrix) {
  17. 		fmt.Printf("On Y failed %v\n", currentPosition)
  18. 		return false
  19. 	}
  20. 	if currentPosition.X < 0 || currentPosition.X >= len(matrix[currentPosition.Y]) {
  21. 		fmt.Printf("On X failed %v\n", currentPosition)
  22. 		return false
  23. 	}
  24.  
  25. 	// Validate current position, with an obstacle
  26. 	if matrix[currentPosition.Y][currentPosition.X] == TAKEN && currentPosition.X != prevPosition.X {
  27. 		fmt.Printf("Obstacle val A: \n current: %v, prev: %v\n", currentPosition, prevPosition)
  28. 		return false
  29. 	}
  30. 	// Validate if you came from Up and the current position is Free
  31. 	if matrix[currentPosition.Y][currentPosition.X] == FREE && currentPosition.X == prevPosition.X {
  32. 		if currentPosition.Y != prevPosition.Y { // Validate first position
  33. 			return false
  34. 		}
  35. 	}
  36.  
  37. 	// return true if you did hit the last row in a safe place
  38. 	if currentPosition.Y == end {
  39. 		return true
  40. 	}
  41.  
  42. 	// Go to the rigth
  43. 	if canBeQueen2(matrix, Position{X: currentPosition.X + 1, Y: currentPosition.Y + 1}, currentPosition, end) {
  44. 		return true
  45. 	}
  46. 	// Go to the left
  47. 	if canBeQueen2(matrix, Position{X: currentPosition.X - 1, Y: currentPosition.Y + 1}, currentPosition, end) {
  48. 		return true
  49. 	}
  50. 	// Go down
  51. 	if canBeQueen2(matrix, Position{X: currentPosition.X, Y: currentPosition.Y + 1}, currentPosition, end) {
  52. 		return true
  53. 	}
  54.  
  55. 	// Didn't became Queen
  56. 	fmt.Printf("On last validation failed %v\n", currentPosition)
  57. 	return false
  58. }
  59.  
  60. /**
  61.  * The rules are simple: make a function that return true or false
  62.  * if a element startinng at position x, y can convert into a Queen.
  63.  * The goal to convert into a Queen is to reach from position {start}
  64.  * to the last position (the last row in the table).
  65.  *
  66.  * Allowed moves:
  67.  * 		1. Move in diagonal down level
  68.  *      2. Eat the obstacles down level
  69.  *
  70.  * Not allowed moves:
  71.  *		1. You cannot go up level
  72.  *      2. You cannot move in diagonal if there is an obstacle
  73.  *
  74.  * NOTE: Free spaces are denoted by: 0, and obstacles are denoted by: 1
  75.  */
  76. func canBeQueen(matrix [][]byte, start Position) bool {
  77. 	return canBeQueen2(matrix, start, start, len(matrix)-1)
  78. }
  79.  
  80. func main() {
  81.  
  82. 	FREE, TAKEN = 0, 1
  83.  
  84. 	table := [][]byte{
  85. 		{FREE, FREE, FREE, FREE, FREE, TAKEN, FREE},
  86. 		{FREE, FREE, FREE, TAKEN, FREE, FREE, FREE},
  87. 		{FREE, FREE, TAKEN, TAKEN, FREE, FREE, FREE},
  88. 		{TAKEN, FREE, FREE, FREE, FREE, TAKEN, FREE},
  89. 		{FREE, FREE, FREE, TAKEN, FREE, FREE, FREE},
  90. 		{TAKEN, FREE, TAKEN, FREE, FREE, FREE, TAKEN}}
  91.  
  92. 	begin := Position{
  93. 		X: 0,
  94. 		Y: 0}
  95.  
  96. 	fmt.Printf("The Pawn starting at the position:\n%+v\n"+
  97. 		"Using the following table:\n%+v\nCan become a Queen? %v",
  98. 		begin, table, canBeQueen(table, begin))
  99.  
  100. }
  101.  
Success #stdin #stdout 0s 4288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Obstacle val A: 
 current: {2 2}, prev: {1 1}
The Pawn starting at the position:
{X:0 Y:0}
Using the following table:
[[0 0 0 0 0 1 0] [0 0 0 1 0 0 0] [0 0 1 1 0 0 0] [1 0 0 0 0 1 0] [0 0 0 1 0 0 0] [1 0 1 0 0 0 1]]
Can become a Queen? true
https://ideone.com/GQrpFY
language:
Go (go 1.12.1)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!