Bulgarian solitaire def bulgarian_solitaire(piles, k): You are given a row of piles of pebbles, all identical, and a positive integer k so that the total number of pebbles in these piles equals k*(k+1)//2, the arithmetic sum formula that equals the sum of positive integers from 1 to k. Almost as if intended as a metaphor for the bleak daily life behind the Iron Curtain, all pebbles are identical and you don't have any choice in your moves. Each move picks up one pebble from each pile (even if doing so makes that pile vanish), and creates a new pile from the resulting handful. For example, starting with[7, 4, 2, 1, 1], the first move turns this into [6, 3, 1, 5]. The next move turns that into [5, 2, 4, 4], which then turns into the five-pile configuration [4, 1, 3, 3, 4], and so on. This function should count how many moves are needed to convert the given initial piles into the goal state where each number from 1 to k appears as the size of exactly one pile, and return that count. These numbers from 1 to k may appear in any order inside the list, not necessarily in sorted order. Applying the basic move to this goal state simply leads right back in that same goal state. (In mathematical lingo, the goal state is a fixed point of the transformation function between these configurations of pebbles, so this process gets stuck in that state forever once it falls into it.)   This problem is from the Martin Gardner column “Bulgarian Solitaire and Other Seemingly Endless Tasks”. It was used there as an example of a while-loop where it is not immediately obvious that this loop will always eventually reach its goal and terminate, analogous to the behaviour of the Collatz 3x+1 problem back in mathproblems.py. However, unlike in that still annoyingly open problem, a combinatorial proof shows that Bulgarian solitaire can never get stuck, but must terminate from any starting configuration of pyramidal numbers after at most k(k-1)/2 steps.

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

Bulgarian solitaire
def bulgarian_solitaire(piles, k):


You are given a row of piles of pebbles, all identical, and a positive integer k so that the total number of pebbles in these piles equals k*(k+1)//2, the arithmetic sum formula that equals the sum of positive integers from 1 to k. Almost as if intended as a metaphor for the bleak daily life
behind the Iron Curtain, all pebbles are identical and you don't have any choice in your moves. Each move picks up one pebble from each pile (even if doing so makes that pile vanish), and creates a new pile from the resulting handful. For example, starting with[7, 4, 2, 1, 1], the first move
turns this into [6, 3, 1, 5]. The next move turns that into [5, 2, 4, 4], which then turns into the five-pile configuration [4, 1, 3, 3, 4], and so on.


This function should count how many moves are needed to convert the given initial piles into the goal state where each number from 1 to k appears as the size of exactly one pile, and return that count. These numbers from 1 to k may appear in any order inside the list, not necessarily in sorted order. Applying the basic move to this goal state simply leads right back in that same goal state. (In mathematical lingo, the goal state is a fixed point of the transformation function between these
configurations of pebbles, so this process gets stuck in that state forever once it falls into it.)

 

This problem is from the Martin Gardner column “Bulgarian Solitaire and Other Seemingly Endless Tasks”. It was used there as an example of a while-loop where it is not immediately obvious that this loop will always eventually reach its goal and terminate, analogous to the behaviour of the Collatz 3x+1 problem back in mathproblems.py. However, unlike in that still annoyingly open problem, a combinatorial proof shows that Bulgarian solitaire can never get stuck, but must terminate from any starting configuration of pyramidal numbers after at most k(k-1)/2 steps.

piles
k
Expected result
[1, 4, 3, 2]
4
[8, 3, 3, 1]
5
9.
[10, 10, 10, 10, 10, 5]
10
74
[3000, 2050]
100
7325
[2*i-1 for i in range(171, 0, -2)]
171
28418
Transcribed Image Text:piles k Expected result [1, 4, 3, 2] 4 [8, 3, 3, 1] 5 9. [10, 10, 10, 10, 10, 5] 10 74 [3000, 2050] 100 7325 [2*i-1 for i in range(171, 0, -2)] 171 28418
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 3 images

Blurred answer
Knowledge Booster
Function Arguments
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education