Bulgarian solitaire for creating a pattern

Bulgarian solitaire is a game in which you start with a sequence of numbers that adds to k(k+1)/2 for some k. (This sum is 1 + 2 + … + k.) Think of each number in the sequence as representing a collection of pebbles. (For example, the sequence <6, 9> represents two piles containing 6 and 9 pebbles.) Form a new sequence by taking one pebble from each pile to form a new pebble. Thus for example, the sequence <6, 9> generates the sequence <2, 5, 8>, then <1, 3, 4, 7> etc. The sequence stops with <1, 2, 3, 4, 5> since this sequence remains unchanged after a move.

My question: Given a sequence, I want to write a program that takes such a sequence as input and displays all the sequences generated by moves of Bulgarian solitaire until the sequence <1, 2, …, k> is reached for some k.

Any help is greatly appreciated! Thanks!

[Steven Lord]

This sounds like a homework assignment. If it is, show us the code you've written to try to solve the problem and ask a specific question about where you're having difficulty and we may be able to provide some guidance.

If you aren't sure where to start because you're not familiar with how to write MATLAB code, I suggest you start with the free MATLAB Onramp tutorial (https://www.mathworks.com/support/learn-with-matlab-tutorials.html) to quickly learn the essentials of MATLAB.

[John D'Errico]

If this is homework, then it was assigned to you, not to us. It was given to you to teach you about both MATLAB and the problem solving process. If we give you code to do your task, then you learn nothing except that a good way to deal with the problem solving process is to get someone else to do the thinking for you.

If this is not homework (I would bet it is) then start by understanding how the game works. Do it on paper for various start points. See what the set of sequences will look like. Now, think of a structure in MATLAB that can be used to store that set, and a way to work with the sequences as generated. Don't write code for such a problem until you can visuaize how it will work.

Think about the end conditions in such a problem. Will the code possibly never terminate? Can it cycle for some start sets? How would you stop the code if it is in an infinite cycle? How will you verify the code has reached a validly terminal state? Do you need to test to see if the set given is valid, thus a true triangle number? Can the sequences change in length over time? If so, how will you store them? What tool would work well there?

[CS]

Here is what I have thus far:

% Bulgarian Solitaire
% Generate a random integer array whose elements total less than 46
array = randperm(45,1);
k = sum(array);
i = 2;
while k <= 45
    array(i) = randperm(45,1);
    k = sum(array);
    i = i+1;
end
while k > 46
    array(i) = 0;
    k = sum(array);
    i = i-1;
end
% Remove zeros from the initial array
value = find(array(:) == 0);
array(value) = [];
array = reshape(array, size(array,1), []);
% Sort array from smallest to largest
array = sort(array)
% Find the value of the largest element in the array
maxValue = max(array(:));
% Iterate the solitaire process
% If maxValue > 9, continue interation
count = 0;
if maxValue > 9
    % Subtract one from each element of the array and increment counter    
    for i = 1:length(array)
        array(i) = array(i) - 1;
        count = count + 1;
        i = i + 1;
    end
% Increment array length by 1 and add the count value to the array
array(length(array) + 1) = count;
% Remove zeros from the array
value = find(array(:) == 0);
array(value) = [];
array = reshape(array, size(array,1), []);
% Find the value of the largest element in the array
maxValue = max(array(:));
% Sort array from smallest to largest
array = sort(array)
end

Any help is appreciated! Thanks!

Answer 1

[Steven Lord]

A couple suggestions:

% Bulgarian Solitaire
% Generate a random integer array whose elements total less than 46
array = randperm(45,1);
k = sum(array);
i = 2;
while k <= 45
    array(i) = randperm(45,1);
    k = sum(array);
    i = i+1;
end
while k > 46
    array(i) = 0;
    k = sum(array);
    i = i-1;
end

So you want a vector of integer values between 1 and 45 whose sum is less than 46? A simpler way to do this would be to generate a 45-element vector (a 45-element vector each element of which is 1 is the longest vector you could create that could satisfy your sum requirement.) Use cumsum to add up the first element, the first two elements, the first three elements, etc. Then find the last element in that cumulative sum that's less than 46 and truncate your array at that point, throwing away the later elements.

% Remove zeros from the initial array
value = find(array(:) == 0);
array(value) = [];
array = reshape(array, size(array,1), []);

The nonzeros function will help you here.

% Sort array from smallest to largest
array = sort(array)

array = 30

% Find the value of the largest element in the array
maxValue = max(array(:));

There's no need to call max here. If you have an array that's been sorted from smallest to largest, which element is the largest?

% Iterate the solitaire process
% If maxValue > 9, continue interation
count = 0;
if maxValue > 9
    % Subtract one from each element of the array and increment counter    
    for i = 1:length(array)
        array(i) = array(i) - 1;
        count = count + 1;
        i = i + 1;
    end
% Increment array length by 1 and add the count value to the array
array(length(array) + 1) = count;
% Remove zeros from the array
value = find(array(:) == 0);
array(value) = [];
array = reshape(array, size(array,1), []);
% Find the value of the largest element in the array
maxValue = max(array(:));
% Sort array from smallest to largest
array = sort(array)
end

array = 1×2

1 29

Your code above processes each element of your array one by one. One of the nice features about MATLAB is that you can operate on vectors or arrays in one command (for many operations.) Have a vector of values 1:5 and want to add to 1 each? You could loop through the elements or you could do it in one command, like where I create y below:

x = 1:5

x = 1×5

1 2 3 4 5

y = x + 1

y = 1×5

2 3 4 5 6

The size and length functions may be of use to you in determining how much larger the sum of elements in y is than the sum of elements in x.