17
\$\begingroup\$

A man lives in the north-west corner (0, 0) of a town with height h and width w . Everyday he walks from his home to the border (?, w) or (h, ?). In the following example, the man goes to (3, 3) today.

(0, 0) +--+ + + . (0, 4) | + +--+--+ . | + + + + . | (3, 0) . . . . . (3, 4)

The man records a bit at each points (+ in example above). Every time he reaches a point, he goes east if the bit is 1 and south otherwise. The bit is flipped after he leaves. For example:

Day 1: 1--0 1 1 Day 2: 0 1 1 1 Day 3: 1--1--1--1-- Day 4: 0 0 0 0 | | | 0 1--0 0 0 0 1 0 1 0 1 0 1--0 1 0 | | | 1 0 1--0 1--0 0 1 0 1 0 1 0 1--0 1 | | | Destination: (3, 3) Destination: (3, 1) Destination: (0, 4) Destination: (3, 2)

Given the size of the town and the man's record, calculate the man's destination after n days.

Input:

In the first line are three integers, h, w and n.

In the following h lines are w integers, denoting the man's record.

h <= 1000, w <= 1000, n <= 1000000000

Output:

Two integers, denoting the man's destination after n days.

Sample Input:

3 4 3 1 0 1 1 0 1 0 0 1 0 1 0

Sample Output:

0 4

Sample Code:

#include <iostream> using namespace std; bool d[1000][1000]; int main(){ int h, w, n; cin >> h >> w >> n; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) cin >> d[i][j]; int i, j; while(n--) for(i = 0, j = 0; i < h && j < w;){ bool &b = d[i][j]; d[i][j] ? j++ : i++; b = !b; } cout << i << " " << j << endl; }

Scoring:

  • Lowest byte count in UTF-8 wins.
  • If the running time of your code is independent of n, reduce your score by 50%.
    • Don't just calculate the results of all 1000000000 days or do anything similarly stupid to get this bonus. Find an efficient algorithm!
Improve this question
\$\endgroup\$
12
  • \$\begingroup\$ 2 things I dont understand. The output, sometimes you use 0 index other times you dont. How does that work? Should it be like border+1? Second thing is the second line with scoring. How do you mean that? \$\endgroup\$ Commented Apr 4, 2014 at 9:58
  • \$\begingroup\$ Day 4 should output 3,2 right? \$\endgroup\$ Commented Apr 4, 2014 at 10:26
  • 2
    \$\begingroup\$ If, no matter what n is, my code calculates the results of all 1000000000 days, then output the result of n, do I still get the -50% bonus? \$\endgroup\$ Commented Apr 4, 2014 at 10:48
  • \$\begingroup\$ @ace now you put it like that, it does make sense doesnt it? Thanks for that :P \$\endgroup\$ Commented Apr 4, 2014 at 10:59
  • \$\begingroup\$ @TeunPronk Yes. It's my fault. \$\endgroup\$ Commented Apr 4, 2014 at 11:14

7 Answers 7

Reset to default
13
\$\begingroup\$

Python 2, 192 bytes * 0.5 bonus = 96

To solve this problem efficiently, the key realization is that we can compute how many times each cell is visited based on the number of times the cells above and to the left are visited, without needing to determine the exact paths taken. Effectively, we simulate n trips at once and keep track of how many times each cell is used.

Substantial improvement due to push-based approach inspired by johnchen902's solution:

r=lambda:map(int,raw_input().split()) h,w,n=r() v=[n]+w*[0] x=y=0 for i in range(h): for j,b in enumerate(r()): if i-x==j-y==0:d=v[j]&1^b;x+=d;y+=1^d f=v[j]+b>>1;v[j]-=f;v[j+1]+=f print x,y

Previous, pull-based implementation:

r=lambda i:map(int,raw_input().split()) h,w,n=r(0) x=range(h) g=map(r,x) v=[w*[0]for i in x] v[0][0]=n-1 for i in x: for j in range(w):v[i][j]+=(i and(v[i-1][j]+(1^g[i-1][j]))/2)+(j and(v[i][j-1]+g[i][j-1])/2) i=j=0 while i<h and j<w:f=g[i][j]^v[i][j]&1;j+=f;i+=1^f print i,j

Original, ungolfed version:

h, w, n = map(int, raw_input().split()) grid = [map(int, raw_input().split()) for i in xrange(h)] # Determine the number of times each cell was visited in the first n-1 trips visits = [[0]*w for i in xrange(h)] visits[0][0] = n-1 for i in xrange(h): for j in xrange(w): if i: # Count visits from above cell visits[i][j] += (visits[i-1][j] + (not grid[i-1][j])) // 2 if j: # Count visits from left cell visits[i][j] += (visits[i][j-1] + grid[i][j-1]) // 2 # Flip the bits corresponding to each cell visited an odd number of times for i in xrange(h): for j in xrange(w): grid[i][j] ^= visits[i][j] & 1 # Figure out where the final trip ends i = j = 0 while i < h and j < w: if grid[i][j]: j += 1 else: i += 1 print i, j
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can shorten the not to 1^ and the long if condition can be written f=g[i][j]^v[i][j]&1 j+=f i+=1^f. \$\endgroup\$ Commented Apr 4, 2014 at 14:09
  • 1
    \$\begingroup\$ If you allow r to take a parameter (r = lambda x: ...), then you can shorten g=[r()for i in x] to g=map(r,x). \$\endgroup\$ Commented Apr 4, 2014 at 20:56
  • \$\begingroup\$ @RobertoBonvallet: Yup. Advice implemented. \$\endgroup\$ Commented Apr 4, 2014 at 23:09
8
\$\begingroup\$

Ruby, 159 143

n,*l=$<.read.split$/ i=->a{a.split.map &:to_i} x=y=l.map!{|k|i[k]} (n=i[n])[-1].times{x=y=0 (x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]} p x,y

The first line uses the * operator to grab the first line of input in one variable, and the rest of the input in another. Then an i function is defined to convert "1 2 3 4" into [1, 2, 3, 4], which is applied to both l and n. (x and y are saved for later.)

n[-1] is the last element of n, so the following block (the simulation) is executed that many times. First, x and y are initialized to zero (they are declared outside the block so that their scope is large enough), and then the simulation line is executed, which is pretty self-explanatory, but here's some commentary anyway:

l[x][y]<1? is it zero (less than one)? x+=l[x][y]=1 if it's zero, set it to one, and (conveniently) we can add that to x :y+=(l[x][y]=0)+1 otherwise, set it to zero, add one, and add that to y while x<n[0]&&y<n[1] keep doing this while we're still inside the array

Edit: new simulation line provided by Howard, thanks! I'm pretty sure I understand how it works but I don't have time to add an explanation, so one will be added later.

Finally, p x,y outputs the numbers, and we are done!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Some basic wins: change the newline to $/ and the while loop can be reduced to (x+=f=l[x][y]^=1;y+=f^1)while x<n[0]&&y<n[1]}. \$\endgroup\$ Commented Apr 4, 2014 at 13:00
7
\$\begingroup\$

GolfScript, 52.5 (105 characters with 50% bonus)

~](;(\((2$(1,*+\@/{]zip 0\{~@@+.2$!+2/\@+.2/\@[\1&]}%zip~@;}%\;[{.0=0=\1${{1>}%}{1>}if.{~}%}do;].1-,n@0-,

The version is very efficient and can be tested online even for large values.

It uses an approach similar to user2357112's solution.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Please don't ask for an explanation ;-) I can't even change it without breaking and debugging this beast is horrible. \$\endgroup\$ Commented Apr 4, 2014 at 14:16
4
\$\begingroup\$

Delphi XE3 (437 bytes|| 897874 without bonus counted)

When thinking about how to solve this with the bonus I thought of the following.
If you walk 4 days cell 0,0 is changed 4 times. The cell on its right is changed twice aswell as the cell beneath it.
If there is an uneven number of days and the number in the cell starts with 1 the cell on the right gets one more than the cell beneath, and the other way around if the cell is 0.

By doing this for every cell you can see if the end value should be changed by: Cell was changed X times. if X mod 2>0 then change the cell.

Results in the following code:
{Whispers at JohnChen902} do I get your upvote now? :P

uses SysUtils,Classes,idglobal;var a:TArray<TArray<byte>>;b:TArray<TArray<int64>>;h,w,x,y,t:int16;n:int64;s:string;r:TStringList;tra:byte;begin r:=TStringList.Create;readln(h,w,n);h:=h-1;w:=w-1;for y:=0to h do begin readln(s);r.Add(StringReplace(s,' ','',[rfReplaceAll]));end;SetLength(a,h);SetLength(b,h);for y:=0to h do begin SetLength(a[y],w);SetLength(b[y],w);for x:=1to Length(r[y])do a[y][x-1]:=Ord(r[y][x])-48;end;b[0][0]:=n-1;for Y:=0to h do for X:=0to w do begin t:=b[y][x];if x<w then b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2);if y<h then b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2);end;for Y:=0to h do for X:=0to w do if b[y][x]mod 2=1then a[y][x]:=iif(a[y][x]=1,0,1);y:=0;x:=0;repeat a[y][x]:=iif(a[y][x]=1,0,1);if a[y][x]=1then inc(y) else inc(x);until(y>h)or(x>w);write(Format('%d %d',[y,x]));end.

Ungolfed

uses SysUtils,Classes,idglobal; var a:TArray<TArray<byte>>; b:TArray<TArray<int64>>; h,w,x,y,t:int16; n:int64; s:string; r:TStringList; tra:byte; begin r:=TStringList.Create; readln(h,w,n); h:=h-1;w:=w-1; for y:=0to h do begin readln(s); r.Add(StringReplace(s,' ','',[rfReplaceAll])); end; SetLength(a,h); SetLength(b,h); for y:=0to h do begin SetLength(a[y],w); SetLength(b[y],w); for x:=1to Length(r[y])do a[y][x-1]:=Ord(r[y][x])-48; end; b[0][0]:=n-1; for Y:=0to h do for X:=0to w do begin t:=b[y][x]; if x<w then b[y][x+1]:=b[y][x+1]+iif((t mod 2=1)and(a[y][x]=1),(t div 2)+1,t div 2); if y<h then b[y+1][x]:=b[y+1][x]+iif((b[y][x]mod 2=1)and(a[y][x]=0),(t div 2)+1,t div 2); end; for Y:=0to h do for X:=0to w do if b[y][x]mod 2=1then a[y][x]:=iif(a[y][x]=1,0,1); y:=0;x:=0; repeat a[y][x]:=iif(a[y][x]=1,0,1); if a[y][x]=1then inc(y) else inc(x); until(y>h)or(x>w); write(Format('%d %d',[y,x])); end.
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You haven't get my vote yet. I was eating dinner. (Upvoted) \$\endgroup\$ Commented Apr 4, 2014 at 13:46
4
\$\begingroup\$

C++ 213 bytes * 0.5 = 106.5

Here is my solution. It's similar to user2357112's solution, but there are several difference:

  • First, I dispatch visiting times to the right and bottom, instead of compute them from the top and left.
  • Second, I do everything (reading input, dispatching, tracking the man's location) simultaneously.
  • Third, I keep only one row of memory.
#include <iostream> int o[1001],h,w,r,c,i,j,t,u;int main(){std::cin>>h>>w>>*o;for(;i<h;i++)for(j=0;j<w;)std::cin>>t,u=o[j],o[j]/=2,u%2&&o[j+t]++,r-i|c-j||((u+t)%2?r:c)++,o[++j]+=u/2;std::cout<<r<<" "<<c<<"\n";}

Here is the ungolfed version:

#include <iostream> using namespace std; int o[1001]; int main(){ int h, w, n; cin >> h >> w >> n; o[0] = n; int r = 0, c = 0; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){ bool t; cin >> t; int u = o[j]; o[j + 1] += u / 2; o[j] = u / 2; if(u % 2) (t ? o[j + 1] : o[j])++; if(r == i && c == j) ((u + t) % 2 ? r : c)++; } cout << r << " " << c << endl; }
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ These three differences make things much terser. We can shorten the indexing and combine several redundant data structures. The logic for pushing visits forward turns out to be much shorter than the logic for pulling visits from previous cells. Horizontal boundary conditions are handled simply by extending the data structure an extra space to the right, and vertical boundary conditions aren't an issue. \$\endgroup\$ Commented Apr 5, 2014 at 5:47
  • \$\begingroup\$ I've upvoted your answer and incorporated the concepts into my own code. So far, they've taken 84 bytes out of my solution, an improvement of 30%. \$\endgroup\$ Commented Apr 5, 2014 at 5:50
  • \$\begingroup\$ I suspect you might be able to save some bytes by not doing --*o;, and instead switching which case you move the guy down and which case you move the guy to the right. \$\endgroup\$ Commented Apr 5, 2014 at 5:59
  • \$\begingroup\$ @user2357112 Implemented, but code length increase due to a previous mistake (It should have been 218 bytes). \$\endgroup\$ Commented Apr 5, 2014 at 8:20
3
\$\begingroup\$

Python, 177 bytes

My first try ever in Code Golfing, so sorry if I got something wrong here! Code used to grab the input based on user2357112's code.

l=lambda:map(int,raw_input().split()) h,w,n=l() m=[l() for i in[1]*h] while n>0: n-=1;x=y=0 while x!=w and y!=h: if m[y][x]>0:m[y][x]=0;x+=1 else:m[y][x]=1;y+=1 print y,x

Input:

3 4 3 1 0 1 1 0 1 0 0 1 0 1 0

Output:

0 4
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

R, 196 bytes * 0.5 = 98

f=function(h,w,n,x){I=J=rep(1,n);for(i in 1:h)for(j in 1:w){M=which(I==i&J==j);N=length(M);if(N){z=seq(1,N,by=2);if(x[i,j])z=-z;f=M[-z];s=M[z];I[f]=i;J[f]=j+1;I[s]=i+1;J[s]=j}};cat(I[n]-1,J[n]-1)}

Ungolfed:

f=function(h,w,n,x) { I = J = rep(1,n) for(i in 1:h) for(j in 1:w) { M = which(I==i&J==j) N = length(M) if (N) { z = seq(1,N,by=2) if (x[i,j]) z = -z f = M[-z] s = M[z] I[f] = i J[f] = j+1 I[s] = i+1 J[s] = j } } cat(I[n]-1, J[n]-1) }

Usage:

f(3,4,4,matrix(c(1,0,1,0,1,0,1,0,1,1,0,0),3)) 3 2
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.