Help Sally Crash Into Her Father

Computer Science Level 5

Sally is a very bad skater, so she can only skate in one direction! But Sally still wants to find her dad in the least amount of moves possible so that she can get off the ice. Sally's only way of stopping is (crashing into) walls or the edge of the ice rink.

We describe the ice rink using the following notation:

(#) -- Wall
(.) -- Free space
(S) -- Sally's starting position
(D) -- Dad's position.

For example, in the ice rink at right, the shortest path is 18 steps.

Here is a text file of 5 ice rinks of size 20 × 20 20 \times 20 . The rinks are separated by hyphens.

Find the sum of the shortest paths of these five 20 × 20 20 \times 20 ice rinks.

Note: Sally has to stop at her father's position. She will slide past him if there are no walls.

Image credit: Flickr Saad Akhtar


The answer is 232.

View wiki
Daniel Gabrić by Daniel Gabrić , 25, Canada

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Thaddeus Abiy
May 23, 2014

Sally's Journey can be modeled as a weighted directed graph,where the walls and the edges of the rink are nodes of the graph and the edges are the distances between two nodes.Basically a weighted graph is a graph that associates a label (weight) with every edge in the graph. For example the graph of the given example above(the 10 × 10 10 \times 10 grid in the problem description) is the following graph graph graph .

Finding the shortest possible path in a weighted graph can be done with Dijkstra's algorithm (a more generalized version of A* search). It picks the unvisited node with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors. Dijkstra's algorithm Dijkstra's algorithm

Thank's to Chandler's solution here . I learned about an awesome tool named networkx for managing graphs in python.

Here is the code in python: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
from itertools import *
import networkx as nx
from networkx import shortest_path,dijkstra_path


New='''S.........#.....#...
................#...
....................
....................
....................
....................
....................
....................
.........#.........#
....................
..........#.........
#...................
....................
....................
....................
..#.................
....................
..........#.........
........#..........#
.........#.#......D.
--------------------
......#.........#...
.........#......#...
....................
....................
....................
#........S..........
#........D#.........
#......##.##.......#
....................
....................
....................
.........#..........
....................
....................
....................
....................
.....#...........#..
..............#.....
....................
....................
--------------------
......#.........#...
......#............#
............#..#....
....................
....................
#....S....#........D
#......#..#........#
#......##.##.......#
...........#........
....................
..#.................
.........#..........
....................
....................
.#..................
..........#.........
.....#...........#..
.........#....#.....
#...................
................#..#
--------------------
S...........#......#
....................
....................
....................
#...................
....................
....................
...................#
.......#............
....................
#...................
....................
....................
...................#
.......#............
#...................
....................
................#..#
....................
#...............###D
--------------------
........#...........
............#.......
.................S..
.........#...#......
........#D.........#
....................
....................
....................
....................
........#...........
...................#
....................
....................
....................
..........#.........
#..........#........
....................
....................
...#................
....#......#.#......'''
def Parse(Grid):
     matrix = [[i for i in j] for j in Grid.split('\n')]
     return matrix
def Get_Neighb(Matrix,P):
     Vectors = [(1,0),(0,1),(-1,0),(0,-1)]
     Vectors = {i:True for i in Vectors}
     Size = len(Matrix[0])
     Neighbors = []
     for i in range(1,Size+1):
          for v in Vectors:
               if not Vectors[v]:
                    continue
               x,y = P[0]+(v[0]*i),P[1]+(v[1]*i)
               Pos = x+(v[0]*-1),y+(v[1]*-1)
               if x==-1 or y==-1 or x==Size or y==Size:
                    Vectors[v] = False
                    if Pos != P:
                         Neighbors.append(Pos)
                    continue               
               if Matrix[x][y] in ['#']:                    
                    Vectors[v] = False
                    if Pos != P:
                         if Matrix[x][y]=='D':
                              Neighbors.append((x,y))
                         else:
                              Neighbors.append(Pos)

     return Neighbors
def Length(a,b):
     return abs(a[1]-b[1])+abs(a[0]-b[0])
def Make_Graph(Matrix,Size):
     Main = {}
     Graph = {}
     while [] in Matrix:
          Matrix.remove([])
     for x,y in product(range(Size),repeat=2):
          Cell,Value = (x,y),Matrix[x][y]          
          if Value in ['S','D']:Main[Value]=Cell
          if Value == '#':
               continue
          Graph[Cell] = Get_Neighb(Matrix,Cell)
     return Graph,Main['S'],Main['D']

def Convert(Graph):
     New = nx.DiGraph()
     for node in Graph[0]:
          for neib in Graph[0][node]:
               #print node,neib
               New.add_node(node)
               New.add_edge(node,neib,weight=Length(node,neib))
     return New,Graph[1],Graph[2]

def Sum(l):
     return sum([Length(l[i],l[i+1]) for i in range(len(l)-1)])

def Shortest(g,Size):
     A=Make_Graph(Parse(g),Size)
     B=Convert(A)
     S,D=B[0],B[1]
     return Sum(dijkstra_path(B[0],B[1],B[2]))

Answer=0
for i in New.split('--------------------'):
     print i
     A=Shortest(i,20)
     print 'Shortest path:',A
     Answer+=A
print '\n Final Answer is :',Answer

7 Helpful 0 Interesting 0 Brilliant 2 Confused

This problem can be solved using dijkstra algorithm and my solution implements algorithm from this book and this code is written in C++: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
#include<bits/stdc++.h>

using namespace std;

#define X_SIZE 20
#define Y_SIZE 20
#define INF 9999
 //one test case only, I manually check the number of solution of each test case

typedef tuple<int,int,int,int,int> node;
typedef pair<int,int> ii;

//from N->E->S->W
int direction_x[] = {-1,0,1,0};
int direction_y[] = {0,1,0,-1};

char daddy = 'D';
char sally = 'S';
char obstacle = '#';

ii posDaddy;
ii posSally;

priority_queue<node,vector<node>,greater<node>> pq;
vector<vector<int>> nodeweight;
vector<vector<ii>> nodeParent;
vector<ii> visitedNode;

char maps[X_SIZE+5][Y_SIZE+5];
bool found = false;
bool x_isnotOutofBond(int pos){

  if(pos<X_SIZE && pos>=0) return true;

  return false;

}

bool y_isnotOutofBond(int pos){

  if(pos<Y_SIZE && pos>=0) return true;

  return false;

}

int main(){

  nodeweight.resize(X_SIZE);
  for(int i=0; i<X_SIZE; i++)
  nodeweight[i].resize(X_SIZE);

  nodeParent.resize(X_SIZE);
  for(int i=0; i<X_SIZE; i++)
  nodeParent[i].resize(X_SIZE);

  cout<<"Please Insert the Map:"<<endl;

  for(int i=0; i<X_SIZE; i++){
    for(int j=0; j<Y_SIZE; j++){
      cin>>maps[i][j];
      nodeweight[i][j] = INF;
      if(maps[i][j] == daddy)
      posDaddy = make_pair(i,j);
      else if(maps[i][j] == sally)
      posSally = make_pair(i,j);
    }
  }

  pq.push(make_tuple(0,posSally.first,posSally.second,posSally.first,posSally.second));

  while(!pq.empty()){
    node NodeInfo = pq.top();
    pq.pop();
    ii posNode = make_pair(abs(get<1>(NodeInfo)),abs(get<2>(NodeInfo)));
    int weight = get<0>(NodeInfo);
    nodeweight[posNode.first][posNode.second];
    ii posParent = make_pair(abs(get<3>(NodeInfo)),abs(get<4>(NodeInfo)));

    found = find(visitedNode.begin(),visitedNode.end(),posNode) != visitedNode.end();

    if(found) continue;
    visitedNode.push_back(posNode);
    nodeParent[posNode.first][posNode.second] = posParent;

    if(posNode == posDaddy) break;    

    if(weight > nodeweight[posNode.first][posNode.second]) continue; //close the node   

    for(int i=0; i<(sizeof(direction_x)/sizeof(direction_x[0])); i++){

      ii posNode_temp = posNode;
      int weight_temp = weight;
      if(x_isnotOutofBond(posNode_temp.first+direction_x[i]) && y_isnotOutofBond(posNode_temp.second+direction_y[i])){
      while(maps[posNode_temp.first+direction_x[i]][posNode_temp.second+direction_y[i]] != obstacle
        && x_isnotOutofBond(posNode_temp.first+direction_x[i]) && y_isnotOutofBond(posNode_temp.second+direction_y[i])){

        if(x_isnotOutofBond(posNode_temp.first+direction_x[i]) && y_isnotOutofBond(posNode_temp.second+direction_y[i])){
        posNode_temp = make_pair(posNode_temp.first+direction_x[i],posNode_temp.second+direction_y[i]);
    weight_temp++;
        }
        else break;
      }

      found = find(visitedNode.begin(),visitedNode.end(),posNode_temp) != visitedNode.end();
      if(x_isnotOutofBond(posNode_temp.first) && y_isnotOutofBond(posNode_temp.second) && posNode_temp != posNode
          && found == false){
       if(weight_temp<=nodeweight[posNode_temp.first][posNode_temp.second] && posNode_temp != posNode){

    pq.push(make_tuple(weight_temp,posNode_temp.first,posNode_temp.second,posNode.first,posNode.second));   

        nodeweight[posNode.first][posNode.second] = weight_temp;
      }

    }

  }

}
}

int pathcount = 0;
ii posPath = posDaddy;

while(posPath != posSally){

  ii posPath_temp = posPath;
  int x_temp = nodeParent[posPath_temp.first][posPath_temp.second].first - posPath_temp.first;
  int y_temp = nodeParent[posPath_temp.first][posPath_temp.second].second - posPath_temp.second;

  if(x_temp>0) x_temp = 1;
  else if(x_temp<0) x_temp = -1;
  else if(x_temp==0) x_temp = 0;

  if(y_temp>0) y_temp = 1;
  else if(y_temp<0) y_temp = -1;
  else if(y_temp==0) y_temp = 0;

  while(posPath_temp != nodeParent[posPath.first][posPath.second]){
    if(make_pair(posPath_temp.first + x_temp,posPath_temp.second + y_temp) != posSally 
       && make_pair(posPath_temp.first + x_temp,posPath_temp.second + y_temp)!= posDaddy

      ){ 
      maps[posPath_temp.first + x_temp][posPath_temp.second + y_temp] = 'x';
      pathcount++;
     }
    posPath_temp.first += x_temp;
    posPath_temp.second += y_temp;
  }
  posPath = posPath_temp;
}


cout<<"SOLUTION:"<<endl;
for(int i=0; i<X_SIZE; i++){
  for(int j=0; j<Y_SIZE; j++){
    cout<<maps[i][j];
  }
  cout<<endl;
}

pathcount++; //include Daddy
cout<<"[TOTAL PATH] "<<pathcount<<endl;

}

The output would be: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
'''
S.........#.....#...
................#...
....................
....................
....................
....................
....................
....................
.........#.........#
....................
..........#.........
#...................
....................
....................
....................
..#.................
....................
..........#.........
........#..........#
.........#.#......D.

SOLUTION:
S.........#.....#...
x...............#...
x...................
x...................
x...................
x...................
x...................
x...................
x........#.........#
x...................
xxxxxxxxxx#.........
#........x..........
.........x..........
.........x..........
.........x..........
..#......x..........
.........x..........
.........x#.........
........#xxxxxxxxxx#
.........#.#......D.
[TOTAL PATH] 37


--------------------

......#.........#...
.........#......#...
....................
....................
....................
#........S..........
#........D#.........
#......##.##.......#
....................
....................
....................
.........#..........
....................
....................
....................
....................
.....#...........#..
..............#.....
....................
....................

SOLUTION:
......#xxxxx....#...
.......x.#.x....#...
.......x...x........
.......x...x........
.......x...x........
#......x.Sxxxxxxxxxx
#......xxD#xxxxxxxxx
#......##.##.......#
....................
....................
....................
.........#..........
....................
....................
....................
....................
.....#...........#..
..............#.....
....................
....................
[TOTAL PATH] 37

--------------------

......#.........#...
......#............#
............#..#....
....................
....................
#....S....#........D
#......#..#........#
#......##.##.......#
...........#........
....................
..#.................
.........#..........
....................
....................
.#..................
..........#.........
.....#...........#..
.........#....#.....
#...................
................#..#

SOLUTION:
xx....#.........#...
xx....#............#
xx..........#..#....
xx..................
xxxxxxxxxxxxxxxxxxxx
#xxxxS....#........D
#......#..#........#
#......##.##.......#
...........#........
....................
..#.................
.........#..........
....................
....................
.#..................
..........#.........
.....#...........#..
.........#....#.....
#...................
................#..#
[TOTAL PATH] 34


--------------------

S...........#......#
....................
....................
....................
#...................
....................
....................
...................#
.......#............
....................
#...................
....................
....................
...................#
.......#............
#...................
....................
................#..#
....................
#...............###D

SOLUTION:
Sxxxxxxxxxxx#..xxxx#
...........x...x..x.
...........x...x..x.
...........x...x..x.
#..........x...x..x.
...........x...x..x.
...........x...x..x.
...........x...x..x#
.......#...x...x..x.
...........x...x..x.
#..........x...x..x.
...........x...x..x.
...........x...x..x.
...........x...x..x#
.......#...x...x..x.
#..........x...x..x.
...........x...x..x.
...........x...x#.x#
...........x...x..xx
#..........xxxxx###D
[TOTAL PATH] 76

--------------------

........#...........
............#.......
.................S..
.........#...#......
........#D.........#
....................
....................
....................
....................
........#...........
...................#
....................
....................
....................
..........#.........
#..........#........
....................
....................
...#................
....#......#.#......

SOLUTION:
........#...........
............#.......
xxxxxxxxxxxxxxxxxS..
x........#...#......
x.......#D.........#
x........x..........
x........x..........
x........x..........
x........x..........
x.......#x..........
x........x.........#
x........x..........
x........x..........
x........x..........
xxxxxxxxxx#.........
#..........#........
....................
....................
...#................
....#......#.#......
[TOTAL PATH] 48

--------------------
'''

Total = 232 \boxed{232}

6 Helpful 0 Interesting 0 Brilliant 0 Confused

Thanks Resha. Some comments regarding to your code in C++:

  • Line 51 and 55 you should be using Y SIZE instead of X SIZE (luckily, these have the same value now).
  • In your *_isnotOutofBond functions you can return the condition directly (eg: return pos<X_SIZE && pos>=0 )
  • What does line 77 do?

Juan Eugenio Abadie - 1 year, 7 months ago

Thank you for the feedback

  1. Yes, I deliberately assume that the YSIZE and the XSIZE are the same then it's kinda trivial to concern which variable we should use because they are the same.
  2. Yes of course you can do that, it's crappy designed C++ code which I created back then.
  3. It does nothing I forgot to remove it after debugging .

Resha Dwika Hefni Al-Fahsi - 1 year ago 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
int dx[] = { 1, 0, -1,  0 };
int dy[] = { 0, 1,  0, -1 };

int sum = 0;
for (int rink = 0; rink < 5; rink++) {
    int spath[][] = new int[22][22];
    boolean isnew[][] = new boolean[22][22];

    int sx = 0, sy = 0; 

    for (int x = 0; x < 22; x++) for (int y = 0; y < 22; y++) {
            spath[x][y] = -2; // wall
            isnew[x][y] = false;
    }

    for (int x = 1; x <= 20; x++) for (int y = 1; y <= 20; y++) {
        char c = rinks[rink][y-1].charAt(x-1);

        if (c == '.' || c == 'D') spath[x][y] = -1;
        if (c == 'S') { spath[x][y] = 0; isnew[x][y] = true; }
        if (c == 'D') { sx = x; sy = y; }               
    }

    // every turn, use isnew[][] to see where to extend the search

    boolean changed = true;
    while (changed) {
        changed = false;

        for (int x = 1; x <= 20; x++) for (int y = 1; y <= 20; y++) 
            if (isnew[x][y]) {
                isnew[x][y] = false;

                for (int d = 0; d < 4; d++) {
                    int xx = x, yy = y;

                    int l = 0;         // l = path length
                    while (spath[xx][yy] > -2) {
                        xx += dx[d]; yy += dy[d]; l++;
                    }
                    xx -= dx[d]; yy -= dy[d]; l--;
                    if (x != xx || y != yy) {
                        if (spath[xx][yy] == -1 ||
                            spath[x][y]+l < spath[xx][yy]) {
                                isnew[xx][yy] = true;
                                spath[xx][yy] = spath[x][y] + l;
                                changed = true;
                        }
                    }
                }
            }
    }
    sum += spath[sx][sy];
}

out.println(sum);

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Yes, this method implements Dijkstra's shortest path algorithm, for this particular context. I do not store a graph with explicit path lengths; doing so would increase performance slightly, but would also require more overhead and more code.

Arjen Vreugdenhil - 5 years, 8 months ago
Abdelhamid Saadi
Oct 30, 2015

Here is solution in python 3: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
from time import time
class Rink:
    def __init__(self, plan, taille):
        self.grid = {}
        self.taille = taille
        self.minimum = taille*taille*taille
        self.reached = False
        strs = plan.split('\n')
        for i in range(self.taille+2):
            for j in range(self.taille+2):
                self.grid[(i,j)] = '#'

        for i in range(self.taille):
            for j in range(self.taille):
                self.grid[(i+1,j+1)] = strs[i][j]

        self.daddy = [g for g in self.grid if self.grid[g] == 'D'][0]
        self.sally = [g for g in self.grid if self.grid[g] == 'S'][0]

    def posdir(self, p, d):
        (x, y), (k,h) = p, d
        m = 0
        while self.grid[(x + k*(m+1), y + h*(m+1))] != '#':
            m += 1
        return (d,m)

    def possibles(self,p):
        alls = [self.posdir(p,d) for d in [(0,1),(0,-1), (1,0),( -1,0)]]
        return([q for q in alls if q[1] != 0])      

    def godeep(self, p, level, depth, sofar):
        if sofar >= self.minimum: 
            return
        if level == depth:
            self.reached = True
            return

        self.grid[p] = '*'
        for pos in self.possibles(p):
            (x, y), (d,delta) = p, pos
            (k,h) = d
            q = (x + delta*k, y + delta*h)
            if self.grid[q] != '*':
                if q == self.daddy :
                    if self.minimum > delta +sofar:
                        self.minimum = delta +sofar
                    return
                else:
                    self.godeep(q, level + 1, depth, delta +sofar)
        self.grid[p] = '.'

    def optimal(self):
        depth = 1
        self.reached = True
        sofar = 0
        while  self.reached:
            self.reached = False
            self.godeep(self.sally, 0, depth, sofar)
            depth += 1
        return self.minimum


def solve(n):
    "Help Sally Crash Into Her Father"
    res = 0
    f = open("icerink.txt")
    data = f.read()
    f.close
    for plan in data.split('-'*n + '\n'):
        rink = Rink(plan, n)
        opt = rink.optimal()
        res += opt
    return res

start = time()
print("result : ", solve(20))
print("execution time: ",time() - start)

Result: 

1
2
 
result :  232
execution time:  0.10600590705871582

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...