Odd arithmetic in Grains

Programming Vim script
3

Yes, I can submit a PR. Do you think that I should just update the problem description to say to use the largest positive value if the answer is too big to fit in an integer?

4

This exercise should be deprecated

@kotp @BNAndras

5

float2nr(), which “helpfully” maps any value too large to represent onto 2^63-1.

Yes, I see what you mean

:for exp in [62,63,64,65] | echo [exp, float2nr(pow(2,exp))] | endfor
[62, 4611686018427387904]
[63, 9223372036854775807]
[64, 9223372036854775807]
[65, 9223372036854775807]
6

PR welcome @alterpatzer @glennj

7

I’ll also proof the existing Vim script exercise stubs this weekend.

8 
function! GrainsOnChessboard()
  let total_grains = 0

  for square in range(1, 64)
    let grains = pow(2, square - 1)
    let total_grains += grains
  endfor

  return total_grains
endfunction

echo GrainsOnChessboard()
" Gives 1.844674e19 on my system

And it is not uncommon in programming languages to hit numeric boundaries. So I am interested in why it should be deprecated. It is a practice exercise, right?

1 Like
9

vimscript’s maximum Number is 9,223,372,036,854,775,807 – we cannot represent the correct values:

  • the number of grains on square 64 is 9,223,372,036,854,775,808
  • the total number of grains is 18,446,744,073,709,551,615

It should be deprecated because the language cannot calculate the correct answer.

Perhaps instead of deprecating, we could remove the bad tests and add a .docs/instructions.md.append file explaining vimscripts Number boundaries and how it affects the exercise.

10

I like the second option. We could also use only “playable” (for checkers) squares on the board, reducing the problem to 32 squares. But learning the boundaries of the numbers has value.

11

The story conceit is a chessboard with the same number of rows and columns so would 36 squares be a better fit than 32?

12

Well, there are half of the squares that are playable on a board for checkers, so 36 would involve 4 unused areas. If you were to fold the board in half you would only have 32 if you used both colors as you do for chess.

13

I don’t know if anyone still uses 32-bit builds of vim, but if so, even 32 is too large. I see the following options:

  • Return the largest possible value if the real answer can’t be represented, which is what the current tests expect. Amusingly, you can write let infinity = 1/0 and you get this largest value. There is also a builtin v:numbermax that contains it.

  • Throw an exception if the value can’t be represented. Detecting this needs some care, since for instance, pow(2, 63) > v:numbermax returns false.

  • Require the return value to be a list of decimal digits or some other multi-precision format.

Personally, the convention that v:numbermax represents an infinite range of numbers rubs me the wrong way, so I’d be most inclined to throw an exception. This has the pedagogical benefit of making the solver think about numeric limits and how to handle them. In any case, the problem description should give some guidance.

14

It could also be a string of digit characters, we are not really limited to a strict Numeric value. It changes the exercise.

Going from the right hand side of both numbers and adding them, carrying the one, and adding the new digit to the string, until you end up with the answer.

123456
123456 +
======
246912

So it is not that it can not be represented, we only need to figure out if we are limiting ourselves to integer representation. Our choice will affect how it is solved.

15

Or we can change the exercise’s story:

A man does a favour for the king. In return he asks for one grain of rice the next day, and, for the next 30 days, twice the previous day’s amount. How many grains on day N? How many in total?

That keeps everything about the current code except for the upper bound.

1 Like
16

Yeah, keeping it a binary problem keeps the solution in line with other languages, and does not change the nature of the solution.

Though as shown, we do not need to change the upper bound, with this solution, only what we are expecting in the test:

17

I submitted a PR to get this particular change in front of students soon. I looked over the existing stubs and didn’t see any other inconsistent ones.

18

I started working on this and discovered that the problem descriptions and test cases are common across all languages, but you can add language-specific comments at the end by creating a .docs/instructions.append.md file. So my current thought is that the simplest way forward is to add a paragraph saying that the king had to stop on day 30 because he ran out of wheat. This is somewhat realistic: according to the data here, 2 billion grains of wheat is about 65 tons.

19

Not that stacking even a tenth of that is realistic on a chess board’s square. ;)

20

This entire problem works fine in integers, in (64-bit) vim script, up to square 63 (where the overall total reaches exactly v:numbermax).

So I’d say the story could be that the King of the Kingdom of VimScript was a little poorer than some of his neighbor kings, and had to stop one square earlier than his neighbors. (All of whom were apparently rooked into this terrible deal…)

1 Like
21

This works for me as an elegant solution. I still want an instructions append about how Vim’s integer handling affected this exercise. I’m thinking a brief overview (just two or three sentences) and then possibly a link or a reference to the built-in docs for more information.

22

This entire problem works fine in integers, in (64-bit) vim script, up to square 63

This is true if you assume that no one is using a 32-bit build of vim. Most likely that is the case, but I am not sure.

this terrible deal…

According to the data on the wheat-growers’ website, the entire annual output of the United States would be enough to cover 51 squares (which must be very big ones).