Odd arithmetic in Grains

The test for the 64th square expects 9223372036854775807 as the result, which looks suspicious since it is an odd number and the real answer is a power of two, namely 2^63. The test for the Total function expects the sum over all the squares to have the same value! In fact, this is 2^63-1, which is the largest positive integer that can be represented. I notice that most solvers got their answers using float2nr(), which “helpfully” maps any value too large to represent onto 2^63-1. Adopting the convention that 2^63-1 is returned if the actual value falls outside the representable range is defensible, but it ought to be mentioned in the problem description. By the way, the skeleton code shows Total taking an argument but the test code calls it without one.

I noticed that too, but forgot to make a PR about it. Do you feel like submitting one?

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?

This exercise should be deprecated

@kotp @BNAndras

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]

PR welcome @alterpatzer @glennj

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

function! GrainsOnChessboard()
  let total_grains = 0

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

  return total_grains

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

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.

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.

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

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.

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.

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 +

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.

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

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:

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.

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.

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

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…)