package main
import "fmt"
var FREE, TAKEN byte
type Position struct {
X int // This is the width position
Y int // This is the heigth position
}
// TODO: Make an enhacement to implement memoization on this problem. Too many recursion calls
func canBeQueen2(matrix [][]byte, currentPosition Position, prevPosition Position, end int) bool {
// Validate the currentPosition, 0 or > len(matrix) must return false
if currentPosition.Y < 0 || currentPosition.Y >= len(matrix) {
fmt.Printf("On Y failed %v\n", currentPosition)
return false
}
if currentPosition.X < 0 || currentPosition.X >= len(matrix[currentPosition.Y]) {
fmt.Printf("On X failed %v\n", currentPosition)
return false
}
// Validate current position, with an obstacle
if matrix[currentPosition.Y][currentPosition.X] == TAKEN && currentPosition.X != prevPosition.X {
fmt.Printf("Obstacle val A: \n current: %v, prev: %v\n", currentPosition, prevPosition)
return false
}
// Validate if you came from Up and the current position is Free
if matrix[currentPosition.Y][currentPosition.X] == FREE && currentPosition.X == prevPosition.X {
if currentPosition.Y != prevPosition.Y { // Validate first position
return false
}
}
// return true if you did hit the last row in a safe place
if currentPosition.Y == end {
return true
}
// Go to the rigth
if canBeQueen2(matrix, Position{X: currentPosition.X + 1, Y: currentPosition.Y + 1}, currentPosition, end) {
return true
}
// Go to the left
if canBeQueen2(matrix, Position{X: currentPosition.X - 1, Y: currentPosition.Y + 1}, currentPosition, end) {
return true
}
// Go down
if canBeQueen2(matrix, Position{X: currentPosition.X, Y: currentPosition.Y + 1}, currentPosition, end) {
return true
}
// Didn't became Queen
fmt.Printf("On last validation failed %v\n", currentPosition)
return false
}
/**
* The rules are simple: make a function that return true or false
* if a element startinng at position x, y can convert into a Queen.
* The goal to convert into a Queen is to reach from position {start}
* to the last position (the last row in the table).
*
* Allowed moves:
* 1. Move in diagonal down level
* 2. Eat the obstacles down level
*
* Not allowed moves:
* 1. You cannot go up level
* 2. You cannot move in diagonal if there is an obstacle
*
* NOTE: Free spaces are denoted by: 0, and obstacles are denoted by: 1
*/
func canBeQueen(matrix [][]byte, start Position) bool {
return canBeQueen2(matrix, start, start, len(matrix)-1)
}
func main() {
FREE, TAKEN = 0, 1
table := [][]byte{
{FREE, FREE, FREE, FREE, FREE, TAKEN, FREE},
{FREE, FREE, FREE, TAKEN, FREE, FREE, FREE},
{FREE, FREE, TAKEN, TAKEN, FREE, FREE, FREE},
{TAKEN, FREE, FREE, FREE, FREE, TAKEN, FREE},
{FREE, FREE, FREE, TAKEN, FREE, FREE, FREE},
{TAKEN, FREE, TAKEN, FREE, FREE, FREE, TAKEN}}
begin := Position{
X: 0,
Y: 0}
fmt.Printf("The Pawn starting at the position:\n%+v\n"+
"Using the following table:\n%+v\nCan become a Queen? %v",
begin, table, canBeQueen(table, begin))
}
cGFja2FnZSBtYWluCgppbXBvcnQgImZtdCIKCnZhciBGUkVFLCBUQUtFTiBieXRlCgp0eXBlIFBvc2l0aW9uIHN0cnVjdCB7CglYIGludCAvLyBUaGlzIGlzIHRoZSB3aWR0aCBwb3NpdGlvbgoJWSBpbnQgLy8gVGhpcyBpcyB0aGUgaGVpZ3RoIHBvc2l0aW9uCn0KCi8vIFRPRE86IE1ha2UgYW4gZW5oYWNlbWVudCB0byBpbXBsZW1lbnQgbWVtb2l6YXRpb24gb24gdGhpcyBwcm9ibGVtLiBUb28gbWFueSByZWN1cnNpb24gY2FsbHMKZnVuYyBjYW5CZVF1ZWVuMihtYXRyaXggW11bXWJ5dGUsIGN1cnJlbnRQb3NpdGlvbiBQb3NpdGlvbiwgcHJldlBvc2l0aW9uIFBvc2l0aW9uLCBlbmQgaW50KSBib29sIHsKCgkvLyBWYWxpZGF0ZSB0aGUgY3VycmVudFBvc2l0aW9uLCAwIG9yID4gbGVuKG1hdHJpeCkgbXVzdCByZXR1cm4gZmFsc2UKCWlmIGN1cnJlbnRQb3NpdGlvbi5ZIDwgMCB8fCBjdXJyZW50UG9zaXRpb24uWSA+PSBsZW4obWF0cml4KSB7CgkJZm10LlByaW50ZigiT24gWSBmYWlsZWQgJXZcbiIsIGN1cnJlbnRQb3NpdGlvbikKCQlyZXR1cm4gZmFsc2UKCX0KCWlmIGN1cnJlbnRQb3NpdGlvbi5YIDwgMCB8fCBjdXJyZW50UG9zaXRpb24uWCA+PSBsZW4obWF0cml4W2N1cnJlbnRQb3NpdGlvbi5ZXSkgewoJCWZtdC5QcmludGYoIk9uIFggZmFpbGVkICV2XG4iLCBjdXJyZW50UG9zaXRpb24pCgkJcmV0dXJuIGZhbHNlCgl9CgoJLy8gVmFsaWRhdGUgY3VycmVudCBwb3NpdGlvbiwgd2l0aCBhbiBvYnN0YWNsZQoJaWYgbWF0cml4W2N1cnJlbnRQb3NpdGlvbi5ZXVtjdXJyZW50UG9zaXRpb24uWF0gPT0gVEFLRU4gJiYgY3VycmVudFBvc2l0aW9uLlggIT0gcHJldlBvc2l0aW9uLlggewoJCWZtdC5QcmludGYoIk9ic3RhY2xlIHZhbCBBOiBcbiBjdXJyZW50OiAldiwgcHJldjogJXZcbiIsIGN1cnJlbnRQb3NpdGlvbiwgcHJldlBvc2l0aW9uKQoJCXJldHVybiBmYWxzZQoJfQoJLy8gVmFsaWRhdGUgaWYgeW91IGNhbWUgZnJvbSBVcCBhbmQgdGhlIGN1cnJlbnQgcG9zaXRpb24gaXMgRnJlZQoJaWYgbWF0cml4W2N1cnJlbnRQb3NpdGlvbi5ZXVtjdXJyZW50UG9zaXRpb24uWF0gPT0gRlJFRSAmJiBjdXJyZW50UG9zaXRpb24uWCA9PSBwcmV2UG9zaXRpb24uWCB7CgkJaWYgY3VycmVudFBvc2l0aW9uLlkgIT0gcHJldlBvc2l0aW9uLlkgeyAvLyBWYWxpZGF0ZSBmaXJzdCBwb3NpdGlvbgoJCQlyZXR1cm4gZmFsc2UKCQl9Cgl9CgoJLy8gcmV0dXJuIHRydWUgaWYgeW91IGRpZCBoaXQgdGhlIGxhc3Qgcm93IGluIGEgc2FmZSBwbGFjZQoJaWYgY3VycmVudFBvc2l0aW9uLlkgPT0gZW5kIHsKCQlyZXR1cm4gdHJ1ZQoJfQoKCS8vIEdvIHRvIHRoZSByaWd0aAoJaWYgY2FuQmVRdWVlbjIobWF0cml4LCBQb3NpdGlvbntYOiBjdXJyZW50UG9zaXRpb24uWCArIDEsIFk6IGN1cnJlbnRQb3NpdGlvbi5ZICsgMX0sIGN1cnJlbnRQb3NpdGlvbiwgZW5kKSB7CgkJcmV0dXJuIHRydWUKCX0KCS8vIEdvIHRvIHRoZSBsZWZ0CglpZiBjYW5CZVF1ZWVuMihtYXRyaXgsIFBvc2l0aW9ue1g6IGN1cnJlbnRQb3NpdGlvbi5YIC0gMSwgWTogY3VycmVudFBvc2l0aW9uLlkgKyAxfSwgY3VycmVudFBvc2l0aW9uLCBlbmQpIHsKCQlyZXR1cm4gdHJ1ZQoJfQoJLy8gR28gZG93bgoJaWYgY2FuQmVRdWVlbjIobWF0cml4LCBQb3NpdGlvbntYOiBjdXJyZW50UG9zaXRpb24uWCwgWTogY3VycmVudFBvc2l0aW9uLlkgKyAxfSwgY3VycmVudFBvc2l0aW9uLCBlbmQpIHsKCQlyZXR1cm4gdHJ1ZQoJfQoKCS8vIERpZG4ndCBiZWNhbWUgUXVlZW4KCWZtdC5QcmludGYoIk9uIGxhc3QgdmFsaWRhdGlvbiBmYWlsZWQgJXZcbiIsIGN1cnJlbnRQb3NpdGlvbikKCXJldHVybiBmYWxzZQp9CgovKioKICogVGhlIHJ1bGVzIGFyZSBzaW1wbGU6IG1ha2UgYSBmdW5jdGlvbiB0aGF0IHJldHVybiB0cnVlIG9yIGZhbHNlCiAqIGlmIGEgZWxlbWVudCBzdGFydGlubmcgYXQgcG9zaXRpb24geCwgeSBjYW4gY29udmVydCBpbnRvIGEgUXVlZW4uCiAqIFRoZSBnb2FsIHRvIGNvbnZlcnQgaW50byBhIFF1ZWVuIGlzIHRvIHJlYWNoIGZyb20gcG9zaXRpb24ge3N0YXJ0fQogKiB0byB0aGUgbGFzdCBwb3NpdGlvbiAodGhlIGxhc3Qgcm93IGluIHRoZSB0YWJsZSkuCiAqCiAqIEFsbG93ZWQgbW92ZXM6CiAqIAkJMS4gTW92ZSBpbiBkaWFnb25hbCBkb3duIGxldmVsCiAqICAgICAgMi4gRWF0IHRoZSBvYnN0YWNsZXMgZG93biBsZXZlbAogKgogKiBOb3QgYWxsb3dlZCBtb3ZlczoKICoJCTEuIFlvdSBjYW5ub3QgZ28gdXAgbGV2ZWwKICogICAgICAyLiBZb3UgY2Fubm90IG1vdmUgaW4gZGlhZ29uYWwgaWYgdGhlcmUgaXMgYW4gb2JzdGFjbGUKICoKICogTk9URTogRnJlZSBzcGFjZXMgYXJlIGRlbm90ZWQgYnk6IDAsIGFuZCBvYnN0YWNsZXMgYXJlIGRlbm90ZWQgYnk6IDEKICovCmZ1bmMgY2FuQmVRdWVlbihtYXRyaXggW11bXWJ5dGUsIHN0YXJ0IFBvc2l0aW9uKSBib29sIHsKCXJldHVybiBjYW5CZVF1ZWVuMihtYXRyaXgsIHN0YXJ0LCBzdGFydCwgbGVuKG1hdHJpeCktMSkKfQoKZnVuYyBtYWluKCkgewoKCUZSRUUsIFRBS0VOID0gMCwgMQoKCXRhYmxlIDo9IFtdW11ieXRlewoJCXtGUkVFLCBGUkVFLCBGUkVFLCBGUkVFLCBGUkVFLCBUQUtFTiwgRlJFRX0sCgkJe0ZSRUUsIEZSRUUsIEZSRUUsIFRBS0VOLCBGUkVFLCBGUkVFLCBGUkVFfSwKCQl7RlJFRSwgRlJFRSwgVEFLRU4sIFRBS0VOLCBGUkVFLCBGUkVFLCBGUkVFfSwKCQl7VEFLRU4sIEZSRUUsIEZSRUUsIEZSRUUsIEZSRUUsIFRBS0VOLCBGUkVFfSwKCQl7RlJFRSwgRlJFRSwgRlJFRSwgVEFLRU4sIEZSRUUsIEZSRUUsIEZSRUV9LAoJCXtUQUtFTiwgRlJFRSwgVEFLRU4sIEZSRUUsIEZSRUUsIEZSRUUsIFRBS0VOfX0KCgliZWdpbiA6PSBQb3NpdGlvbnsKCQlYOiAwLAoJCVk6IDB9CgoJZm10LlByaW50ZigiVGhlIFBhd24gc3RhcnRpbmcgYXQgdGhlIHBvc2l0aW9uOlxuJSt2XG4iKwoJCSJVc2luZyB0aGUgZm9sbG93aW5nIHRhYmxlOlxuJSt2XG5DYW4gYmVjb21lIGEgUXVlZW4/ICV2IiwKCQliZWdpbiwgdGFibGUsIGNhbkJlUXVlZW4odGFibGUsIGJlZ2luKSkKCn0K