Odd arithmetic in Grains

[alterpatzer]

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.

[kotp]

@alterpatzer

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

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.

[glennj]

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.

[kotp]

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:

Odd arithmetic in Grains

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?

[BNAndras]

@alterpatzer

By the way, the skeleton code shows Total taking an argument but the test code calls it without one.

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.

[alterpatzer]

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.

[kotp]

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

[filbo]

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

[BNAndras]

@glennj

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.

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.

[alterpatzer]

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

[BNAndras]

I talked to @kotp, and we’d like to test the stringified grain count from total. That’ll let the students see some of the limitations of Vim script while playing to its strengths with text editing. Reducing the number of squares might otherwise obscure what’s happening.

[glennj]

@BNAndras

we’d like to test the stringified grain count from total.

I don’t know what that means. Can you expand?

@BNAndras

Reducing the number of squares might otherwise obscure what’s happening.

I went ahead and submitted a PR without re-reading this thread to the end. The PR does just reduce the number of squares.

[BNAndras]

@glennj

I went ahead and submitted a PR without re-reading this thread to the end. The PR does just reduce the number of squares.

The instructions append address how and why we had to change the canonical tests so that addresses my own earlier concerns. I think KOTP’s concern was in part that students wouldn’t be engaging with and working around the limitations of Vim script. Cairo doesn’t support floating-point math so it seemed Space Age wasn’t doable at first without losing precision. However, the maintainer used multiplication to represent the expected floating-point values as integers like 3169 instead of 31.69. That obviously raises the complexity of the exercise, but it’s something a Cairo student will most likely encounter outside of Exercism.

[glennj]

I once implemented addition in bash like this – are you suggesting something similar for this vimscript exercise?

So, we might have the “grains on square 64” and “total for 64 squares” tests (with the expected values as strings) commented out, with appended instructions to uncomment them if the student feels up to the challenge?

[kotp]

Yes, though external tools would not be necessary.

  for i in range(0, len -1)
    let digit = str2nr(num_reversed[i])
    let product = digit * 2 + carry
    let carry = product / 10
    let digit_result = product % 10
    let result .= string(digit_result)
  endfor

Something like that, since we do this as children, we take the digits and work with them as a column and carry the remainder.

[glennj]

Fixed in https://github.com/exercism/vimscript/pull/326

[kotp]

Awesome solution you found to get around language limitations of integers!

[glennj]

I appreciate the help getting it over the finish line.

[glennj]

And, taking it to, well, _an_ extreme:

my solution

const s:SIZE = 64

execute 'source' expand('<sfile>:p:h') .. '/string_arithmetic.vim'

function! Square(number) abort
    if a:number < 1 || a:number > s:SIZE
        throw 'square must be between 1 and ' .. s:SIZE
    endif
    return StringPow('2', a:number - 1)
endfunction

function! Total() abort
    return StringPow('2', s:SIZE)->StringSubtract('1')
endfunction

[kotp]

I can now use it for any number of games, like Sorry! (I ran out of rice) Chutes and Ladders (Ever try to climb that large of a rice mountain) or Life (Ain’t no one got that amount of rice), without worrying about it.