Created 1st May, 2005 09:33 (UTC), last edited 17th February, 2006 04:57 (UTC)

Forums

Before posting make sure that you have read the site's copyright policy. Specifically understand that you agree to license all posts under the same license as stated at the bottom of this page.

*The latest post is at the top*

- Io solution Rob 27th October, 2009 10:15 (UTC)
- Mike's did as well, I think. I believe this is the doing more less the same steps that Mike's is going through. Though Python has some features that allow it to be more compact.

- Io solution Kirit Sælensminde 27th October, 2009 10:07 (UTC)
R := File standardInput readLines map(split map(asNumber)); C := list; for(i,0,9,C append(R map(at(i)))); list(R,C) map(map(sum)) flatten max println

I think yours might be the first that actually reads from stdin though.

- Io solution Rob 27th October, 2009 10:00 (UTC)
Not quite as short as the others. It's on one line on account of the wiki.

muriel:Desktop rburns$ ls -l golf.io -rw-r—r—@ 1 rburns staff 147 Oct 27 16:28 golf.io

R := File standardInput readLines map(split map(asNumber)); C := list; for(i,0,9,C append(R map(at(i)))); list(R,C) map(map(sum)) flatten max println

- R=[map(int,raw_input().split()) for i in ' '*10];print max(map(sum,R+map((lambda *r:r),*R))) Mike 22nd October, 2009 11:47 (UTC)
Map input lines into a lists of lists of ints. Append transposed version. Print the greatest row sum.

93 bytes

- R=[map(int,raw_input().split()) for i in range(10)];print max(map(sum,R+map(lambda *r:list(r),*R))) Mike 22nd October, 2009 11:37 (UTC)
Can't be bothered to deal with this wiki… here it is on dpaste.com

Version above is 100 bytes long.

- Matlab 'solution' Kirit Sælensminde 22nd October, 2009 10:26 (UTC)
The square brackets thing is really a pain for programming languages isn't it. That's the mediawiki markup — I'd love to lose it really now and switch to something like tinymce. Wonder when I'll have time?

To be honest I find the criteria a little vague.

Yeah, a certain amount of that is on purpose :) Even as a software practitioner I'm not sure that it is possible to define a specification so tightly that nobody will have any questions about it.

What language should we use? How much of the standard libraries can we use? If you're not too hung up on the solution being a stand-alone program that understands your calling syntax, I have a pretty short Matlab solution. It consists of two parts: loading the file and computing the maximum:

I know ktui also has a solution that doesn't read from stdin. I'll try to get him to post his. I think he used awk (eek)

- Matlab 'solution' JordiB 22nd October, 2009 09:36 (UTC)
Crap, the site ate the square brackets (and some more again). Here's a repost using <> instead of square brackets. Feel free to delete the previous post.

To be honest I find the criteria a little vague. What language should we use? How much of the standard libraries can we use? If you're not too hung up on the solution being a stand-alone program that understands your calling syntax, I have a pretty short Matlab solution. It consists of two parts: loading the file and computing the maximum:

n=load('numbers.txt'); % loading: 22 characters max(<sum(n),sum(n')>) % computing + printing back to console: 21 characters

That's 43 characters if I omit excess whitespace. If you would allow me to rename the file to something like 'n.txt', I could do this:

load n.txt; % 11 characters

Allowing me to rename it to 'n.mat' would allow me to omit 4 more characters:

load n; % 7 characters

If I'm allowed to assume that the number of columns is always equal to the number of rows, the second part can also be shortened:

max(sum(<n n'>)) % 16 characters

So depending on the rules, I either have no valid solution, or a solution of between 43 and 23 characters. Here is the whole shortest solution:

load n;max(sum(<n n'>))

- Answers JordiB 9th October, 2009 10:00 (UTC)
I think for shuffle2 you are decrementing n in the wrong place, but I haven't worked yours out. This is what I did with a pen and paper yesterday. For both I'm going to consider a list of length 2.

For shuffle 1

- At the loop set up we get
*n*= 2 to start with. - We enter the loop (
*n*> 1) and get a random number in the range 0..<2 (i.e. 0 or 1 after the floor op) and*n*becomes 1 - We swap the element at 1 with either the element at 0 or 1.
- The termination condition on the loop fails as
*n*is 1

We have gone through the array and either left the last element where it was or swapped it with the first item. There's a 50% chance of either outcome so it's unbiased.

For shuffle 2

- At the loop set up we get
*n*= 2 to start with. - We enter the loop (
*n*> 1) and get a random number in the range 0..<n+1 which is 0..<3 (uh oh) - We swap the element at 2 with either the element at 0, 1 or 2 (double uh oh — my earlier analysis was wrong as you will always get an array de-index which is out of bounds)
- We decrement
*n*to give us*n*= 1, this time we don't re-enter the loop as*n*> 1 is not met (I got that wrong before, I thought it went around again)

The analysis I did yesterday was slightly off — I thought that shuffle2 would go once more around the loop and I didn't spot the out of bounds de-index on the swap target, but I think what I have written here is right.

The difference is in where

*n*decremented, either at the top of the loop or at the bottom of the loop. I think shuffle2 can be fixed starting*n*off at the length - 1 and then changing the condition to*n*>= 1, but I haven't checked that through either. It was something close to shuffle2 that I wrote initially and I only noticed because I happened to be looking for bias in the output (Flash doesn't give an error when you do anything out of bounds on an array, more's the pity). And why was I getting a bias? I think it's because of the order of the assignments that do the swap. This g'tees that for an array of length 2 the array is always left unchanged — thankfully a very obvious bias to spot.Oh my god, I can't believe I made such a dumb error. You are right, of course `n` is not decremented at the top… In this case I think you are always going out of bounds. The random number might be 2, but `n` always starts out at 2 (out of bounds).

- At the loop set up we get

- Answers Kirit Sælensminde 9th October, 2009 09:29 (UTC)
I think for shuffle2 you are decrementing n in the wrong place, but I haven't worked yours out. This is what I did with a pen and paper yesterday. For both I'm going to consider a list of length 2.

For shuffle 1

- At the loop set up we get
*n*= 2 to start with. - We enter the loop (
*n*> 1) and get a random number in the range 0..<2 (i.e. 0 or 1 after the floor op) and*n*becomes 1 - We swap the element at 1 with either the element at 0 or 1.
- The termination condition on the loop fails as
*n*is 1

We have gone through the array and either left the last element where it was or swapped it with the first item. There's a 50% chance of either outcome so it's unbiased.

For shuffle 2

- At the loop set up we get
*n*= 2 to start with. - We enter the loop (
*n*> 1) and get a random number in the range 0..<n+1 which is 0..<3 (uh oh) - We swap the element at 2 with either the element at 0, 1 or 2 (double uh oh — my earlier analysis was wrong as you will always get an array de-index which is out of bounds)
- We decrement
*n*to give us*n*= 1, this time we don't re-enter the loop as*n*> 1 is not met (I got that wrong before, I thought it went around again)

The analysis I did yesterday was slightly off — I thought that shuffle2 would go once more around the loop and I didn't spot the out of bounds de-index on the swap target, but I think what I have written here is right.

The difference is in where

*n*decremented, either at the top of the loop or at the bottom of the loop. I think shuffle2 can be fixed starting*n*off at the length - 1 and then changing the condition to*n*>= 1, but I haven't checked that through either.It was something close to shuffle2 that I wrote initially and I only noticed because I happened to be looking for bias in the output (Flash doesn't give an error when you do anything out of bounds on an array, more's the pity). And why was I getting a bias? I think it's because of the order of the assignments that do the swap. This g'tees that for an array of length 2 the array is always left unchanged — thankfully a very obvious bias to spot.

- At the loop set up we get

- Answers JordiB 9th October, 2009 09:09 (UTC)
What I meant is that they will produce identical outcomes.

I don't think that they do. I think one of them is a correct implementation of Fisher/Yates, the other has a subtle bug which leads to two problems: It does an extra loop which will introduce a subtle bias in the output, and even worse it will occasionally produce an array subscript which is out of bounds.

I'll refactor both methods a little bit so that they still have the same behavior (I think), but we can analyze the differences more easily (I replaced the square brackets with angle brackets, because otherwise everything would be formatted on one line):

1. Array.prototype.shuffle1 = function() { 2. for ( var n = this.length; n > 1; ) { 3. var old_n = n; 4. var k = Math.floor(Math.random()*old_n); 5. n—; 6. var t = this<k>; 7. this<k> = this<n>; 8. this<n> = t; 9. } 10. return this; 11. }

1. Array.prototype.shuffle2 = function() { 2. for ( var n = this.length; n > 1; ) { 3. n—; 4. var old_n = n+1; 5. var k = Math.floor(Math.random()*old_n); 6. var t = this<k>; 7. this<k> = this<n>; 8. this<n> = t; 9. } 10. return this; 11. }

Lines 1 and 2 are now the same. In shuffle2, we now decrement `n` and then make `old_n` by adding one to `n` again. In both versions `old_n` should have the same value. Agreed? Now, we take the random number `k`, which should now also be the same (because both versions use `old_n`). At this point `n` is still one smaller in the second version, but this is now fixed in line 5 of shuffle1. After line 5 all variables should have the same values and since line 6-11 are also the same in both versions, the behavior should be the same. Where am I going wrong?

Site: About this site

© 2002-2019 Kirit & Tai Sælensminde. All forum posts are copyright their respective authors.

Licensed under a Creative Commons License. Non-commercial use is fine so long as you provide attribution.

kirit.com