EiffelStudio: an EiffelSoftware project - User contributions [en]

RosettaCode Balanced Brackets

2012-10-03T10:39:57Z

Marco2357:

[[Category:Rosetta Code]]
[[Category:Flash Code]]

'''-> [[RosettaCode]] Overview'''

==Reference==
Statement of the Balanced Brackets problem on RosettaCode: [http://rosettacode.org/wiki/Balanced_brackets here].

==Eiffel code==

Here's a candidate implementation using [[EiffelBase2]]:

<e>
class
BALANCED_BRACKETS

create
make

feature {NONE} -- Initialization

make
-- Generate bracket string.
local
random: V_RANDOM
do
create random
count := 2 * random.bounded_item (0, Max_half_count)
-- count := 50
create brackets.make (1, count)
fill_random
brackets := as_boolean_array ("") ; printout
brackets := as_boolean_array ("[]") ; printout
brackets := as_boolean_array ("[][]") ; printout
brackets := as_boolean_array ("[[][]]") ; printout
brackets := as_boolean_array ("][") ; printout
brackets := as_boolean_array ("][][") ; printout
brackets := as_boolean_array ("[]][[]") ; printout
end

feature -- Access

Max_half_count: INTEGER = 10
-- Maximum possible value for count // 2.

count: INTEGER
-- Number of items in bracket sequence.

brackets: V_ARRAY [BOOLEAN]
-- The string of brackets to be generated and analyzed.
-- True is opening bracket, False is closing.

feature -- Basic operations

is_balanced: BOOLEAN
-- Is bracket string represented by `brackets' bracket-balanced?
local
balance: INTEGER
do
Result := True
across brackets as b until not Result loop
if b.item then
balance := balance + 1
else
if balance = 0 then
Result := False
else
balance := balance - 1
end
end
end
Result := Result and (balance = 0)
end

feature -- Conversion

as_bracket_string (br: V_ARRAY [BOOLEAN]): STRING
-- `br' understood as a string consisting solely of opening and closing brackets.
do
create Result.make (count)

across br as b loop
if b.item then
Result.extend ('[')
else
Result.extend (']')
end
end

end

as_boolean_array (bs: STRING): V_ARRAY [BOOLEAN]
-- `br' turned into boolean array ("[" is True, "]"is False).
require
exists: bs /= Void
only_brackets: bs.occurrences ('[') + bs.occurrences (']') = bs.count
do
create Result.make (1, bs.count)
across bs as b loop
Result [b.target_index] := (b.item = '[')
end

end

feature -- Input and output

printout
-- Output result.
do
print ("Bracket string: ")
print (as_bracket_string (brackets)+ "%T")
if not is_balanced then
print ("NOT ")
end
print ("OK%N")
end

feature {NONE} -- Implementation

fill_random
-- Set `count//2' random `brackets' position to opening.
local
random: V_RANDOM
filled, pos: INTEGER
do
from
create random
invariant
filled <= count // 2
until
filled = count // 2
loop
pos := random.bounded_item (brackets.lower, brackets.upper)
if not brackets [pos] then
brackets [pos] := True
filled := filled + 1
end
random.forth
-- variant
-- Interestingly enough, there is no variant as this
-- loop might in principle not terminate, depending
-- on the properties of the random generator.
end
end

invariant
count_limit: count <= 2 * Max_half_count
array_length_consistent: brackets.count = count

end
</e>

RosettaCode Balanced Brackets

2012-10-03T08:50:35Z

Marco2357:

[[Category:Rosetta Code]]
[[Category:Flash Code]]

'''-> [[RosettaCode]] Overview'''

==Reference==
Statement of the Balanced Brackets problem on RosettaCode: [http://rosettacode.org/wiki/Balanced_brackets here].

==Eiffel code==

Here's a candidate implementation using [[EiffelBase2]]:

<e>
class
APPLICATION

create
make

feature {NONE} -- Initialization

make
-- Generate bracket string.
local
random: V_RANDOM
do
create random
count := 2 * random.bounded_item (0, Max_half_count)
-- count := 50
create brackets.make (1, count)
fill_random
brackets := as_boolean_array ("") ; printout
brackets := as_boolean_array ("[]") ; printout
brackets := as_boolean_array ("[][]") ; printout
brackets := as_boolean_array ("[[][]]") ; printout
brackets := as_boolean_array ("][") ; printout
brackets := as_boolean_array ("][][") ; printout
brackets := as_boolean_array ("[]][[]") ; printout
end

feature -- Access

Max_half_count: INTEGER = 10
-- Maximum possible value for count // 2.

count: INTEGER
-- Number of items in bracket sequence.

brackets: V_ARRAY [BOOLEAN]
-- The string of brackets to be generated and analyzed.
-- True is opening bracket, False is closing.

feature -- Basic operations

is_balanced: BOOLEAN
-- Is bracket string represented by `brackets' bracket-balanced?
local
balance: INTEGER
do
Result := True
across brackets as b until not Result loop
if b.item then
balance := balance + 1
else
if balance = 0 then
Result := False
else
balance := balance - 1
end
end
end
Result := Result and (balance = 0)
end

feature -- Conversion

as_bracket_string (br: V_ARRAY [BOOLEAN]): STRING
-- `br' understood as a string consisting solely of opening and closing brackets.
do
create Result.make (count)

across br as b loop
if b.item then
Result.extend ('[')
else
Result.extend (']')
end
end

end

as_boolean_array (bs: STRING): V_ARRAY [BOOLEAN]
-- `br' turned into boolean array ("[" is True, "]"is False).
require
exists: bs /= Void
only_brackets: bs.occurrences ('[') + bs.occurrences (']') = bs.count
do
create Result.make (1, bs.count)
across bs as b loop
Result [b.target_index] := (b.item = '[')
end

end

feature -- Input and output

printout
-- Output result.
do
print ("Bracket string: ")
print (as_bracket_string (brackets)+ "%T")
if not is_balanced then
print ("NOT ")
end
print ("OK%N")
end

feature {NONE} -- Implementation

fill_random
-- Set `count//2' random `brackets' position to opening.
local
random: V_RANDOM
filled, pos: INTEGER
do
from
create random
invariant
filled <= count // 2
until
filled = count // 2
loop
pos := random.bounded_item (brackets.lower, brackets.upper)
if not brackets [pos] then
brackets [pos] := True
filled := filled + 1
end
random.forth
-- variant
-- Interestingly enough, there is no variant as this
-- loop might in principle not terminate, depending
-- on the properties of the random generator.
end
end

invariant
count_limit: count <= 2 * Max_half_count
array_length_consistent: brackets.count = count

end
</e>

RosettaCode Balanced Brackets

2012-10-03T08:49:35Z

Marco2357:

[[Category:Rosetta Code]]
[[Category:Flash Code]]

'''-> [[RosettaCode]] Overview'''

==Reference==
Statement of the Balanced Brackets problem on RosettaCode: [http://rosettacode.org/wiki/Balanced_brackets here].

==Eiffel code==

Here's a candidate implementation using [[EiffelBase2]]:

<e>
class
APPLICATION

create
make

feature {NONE} -- Initialization

make
-- Generate bracket string.
local
random: V_RANDOM
do
create random
count := 2 * random.bounded_item (0, Max_half_count)
-- count := 50
create brackets.make (1, count)
fill_random
brackets := as_boolean_array ("") ; printout
brackets := as_boolean_array ("[]") ; printout
brackets := as_boolean_array ("[][]") ; printout
brackets := as_boolean_array ("[[][]]") ; printout
brackets := as_boolean_array ("][") ; printout
brackets := as_boolean_array ("][][") ; printout
brackets := as_boolean_array ("[]][[]") ; printout
end

feature -- Access

Max_half_count: INTEGER = 10
-- Maximum possible value for count // 2.

count: INTEGER
-- Number of items in bracket sequence.

brackets: V_ARRAY [BOOLEAN]
-- The string of brackets to be generated and analyzed.
-- True is opening bracket, False is closing.

feature -- Basic operations

is_balanced: BOOLEAN
-- Is bracket string represented by `brackets' bracket-balanced?
local
balance: INTEGER
do
Result := True
across brackets as b until not Result loop
if b.item then
balance := balance + 1
else
if balance = 0 then
Result := False
else
balance := balance - 1
end
end
end
Result := Result and (balance = 0)
end

feature -- Conversion

as_bracket_string (br: V_ARRAY [BOOLEAN]): STRING
-- `br' understood as a string consisting solely of opening and closing brackets.
do
create Result.make (count)

across br as b loop
if b.item then
Result.extend ('[')
else
Result.extend (']')
end
end

end

as_boolean_array (bs: STRING): V_ARRAY [BOOLEAN]
-- `br' turned into boolean array ("[" is True, "]"is False).
require
exists: bs /= Void
only_brackets: bs.occurrences ('[') + bs.occurrences (']') = bs.count
do
create Result.make (1, bs.count)
across bs as b loop
Result [b.target_index] := (b.item = '[')
end

end

feature -- Input and output

printout
-- Output result.
do
print ("Bracket string: ")
print (as_bracket_string (brackets)+ "%T")
if not is_balanced then
print ("NOT ")
end
print ("OK%N")
end

feature {NONE} -- Implementation

fill_random
-- Set `count//2' random `brackets' position to opening.
local
random: V_RANDOM
filled, pos: INTEGER
do
from
create random
invariant
filled <= count // 2
until
filled = count // 2
loop
pos := random.bounded_item (brackets.lower, brackets.upper)
if not brackets [pos] then
brackets [pos] := True
filled := filled + 1
end
random.forth
-- variant
-- Interestingly enough, there is no variant as this
-- loop might in principle not terminate, depending
-- on the properties of the random generator.
end
end

invariant
count_limit: count <= 2 * Max_half_count
array_length_consistent: brackets.count = count

end
</e>

RosettaCode Balanced Brackets

2012-10-03T08:43:32Z

Marco2357: New page: Category:Rosetta Code Category:Flash Code '''-> RosettaCode Overview''' ==Reference== Statement of the Balanced Brackets problem on RosettaCode: [http://rosettacode.org/wiki/...

[[Category:Rosetta Code]]
[[Category:Flash Code]]

'''-> [[RosettaCode]] Overview'''

==Reference==
Statement of the Balanced Brackets problem on RosettaCode: [http://rosettacode.org/wiki/Balanced_brackets here].

==Eiffel code==

Here's a candidate implementation using [[EiffelBase2]]:

<e>
class
APPLICATION

create
make

feature {NONE} -- Initialization

make
-- Generate bracket string.
local
random: V_RANDOM
do
create random
count := 2 * random.bounded_item (0, Max_half_count)
-- count := 50
create brackets.make (1, count)
fill_random
brackets := as_boolean_array ("") ; printout
brackets := as_boolean_array ("[]") ; printout
brackets := as_boolean_array ("[][]") ; printout
brackets := as_boolean_array ("[[][]]") ; printout
brackets := as_boolean_array ("][") ; printout
brackets := as_boolean_array ("][][") ; printout
brackets := as_boolean_array ("[]][[]") ; printout
end

feature -- Access

Max_half_count: INTEGER = 10
-- Maximum possible value for count // 2.

count: INTEGER
-- Number of items in bracket sequence.

brackets: V_ARRAY [BOOLEAN]
-- The string of brackets to be generated and analyzed.
-- True is opening bracket, False is closing.

feature -- Basic operations

is_balanced: BOOLEAN
-- Is bracket string represented by `brackets' bracket-balanced?
local
balance: INTEGER
do
Result := True
across brackets as b until not Result loop
if b.item then
balance := balance + 1
else
if balance = 0 then
Result := False
else
balance := balance - 1
end
end
end
Result := Result and (balance = 0)
end

feature -- Conversion

as_bracket_string (br: V_ARRAY [BOOLEAN]): STRING
-- `br' understood as a string consisting solely of opening and closing brackets.
do
create Result.make (count)

across br as b loop
if b.item then
Result.extend ('[')
else
Result.extend (']')
end
end

end

as_boolean_array (bs: STRING): V_ARRAY [BOOLEAN]
-- `br' turned into boolean array ("[" is True, "]"is False).
require
exists: bs /= Void
only_brackets: bs.occurrences ('[') + bs.occurrences (']') = bs.count
do
create Result.make (1, bs.count)
across bs as b loop
Result [b.target_index] := (b.item = '[')
end

end

feature -- Input and output

printout
-- Output result.
do
print ("Bracket string: ")
print (as_bracket_string (brackets)+ "%T")
if not is_balanced then
print ("NOT ")
end
print ("OK%N")
end

feature {NONE} -- Implementation

fill_random
-- Set `count//2' random `brackets' position to opening.
local
random: V_RANDOM
filled, pos: INTEGER
do
from
create random
invariant
filled <= count // 2
until
filled = count // 2
loop
pos := random.bounded_item (brackets.lower, brackets.upper)
if not brackets [pos] then
brackets [pos] := True
filled := filled + 1
end
random.forth
-- variant
-- Interestingly enough, there is no variant as this
-- loop might in principle not terminate, depending
-- on the properties of the random generator.
end
end

invariant
count_limit: count <= 2 * Max_half_count
array_length_consistent: brackets.count = count

end
</e>

RosettaCode Monty Hall

2012-10-03T08:27:26Z

Marco2357:

[[Category:Rosetta Code]]
[[Category:Flash Code ]]

'''-> [[RosettaCode]] Overview'''

==Reference==
Statement of the Monty Hall problem on RosettaCode: [http://rosettacode.org/wiki/Monty_Hall_problem here].
<br>Deadline for adding to RosettaCode page: 31 Aug 2012; submitter:

==Eiffel code==

Here's a candidate implementation. This compiles and runs, producing output similar to this:

Staying wins 333504 times.

Switching wins 666496 times.

<e>
class
MONTY_HALL

create
make

feature {NONE} -- Initialization

make
local
games_count: INTEGER
do
create random_generator.make
games_count := 1000000

across 1 |..| games_count as game loop
play
end

print ("Staying wins " + staying_wins.out + " times.%N")
print ("Switching wins " + (games_count - staying_wins).out + " times.%N")
end

feature -- Commands

play
local
doors: ARRAYED_LIST [BOOLEAN]
chosen, shown: INTEGER
do
create doors.make_filled (Door_count) -- False is a goat, True is a car
doors [next_random_door] := True -- Put a car behind a random door
chosen := next_random_door -- Pick a door, any door

-- Monty selects a door which is neither the winner nor the choice
from
shown := next_random_door
until
shown /= chosen and not doors [shown]
loop
shown := next_random_door
end

if doors [chosen] then -- If you would have won by staying, count it
staying_wins := staying_wins + 1
end
ensure
staying_wins_valid: staying_wins = old staying_wins or staying_wins = old staying_wins + 1
end

feature {NONE} -- Implementation

Door_count: INTEGER = 3
-- The total number of doors.

staying_wins: INTEGER
-- The number of times that the strategy of staying would win.

random_generator: RANDOM
-- A random number generator for selecting doors.

next_random_door: INTEGER
-- A door chosen at random.
do
random_generator.forth
Result := random_generator.item \\ Door_count + 1
ensure
valid_door: Result >= 1 and Result <= Door_count
end

end

</e>

==Comments==

Note that the implementations in many other languages maintain a separate variable to count the number of switch wins. They calculate whether switching wins at each step via some funky logic that relies on zero-based array indexing, which would be inconvenient in Eiffel. But we don't need to do that at all anyway, because calculating it at each step is completely redundant: we can just do a final subtraction at the end, right?

RosettaCode Monty Hall

2012-10-03T08:27:12Z

Marco2357:

[[Category:Rosetta Code]]
[[Category:Flash Code ]]

'''[[RosettaCode]] Overview'''

==Reference==
Statement of the Monty Hall problem on RosettaCode: [http://rosettacode.org/wiki/Monty_Hall_problem here].
<br>Deadline for adding to RosettaCode page: 31 Aug 2012; submitter:

==Eiffel code==

Here's a candidate implementation. This compiles and runs, producing output similar to this:

Staying wins 333504 times.

Switching wins 666496 times.

<e>
class
MONTY_HALL

create
make

feature {NONE} -- Initialization

make
local
games_count: INTEGER
do
create random_generator.make
games_count := 1000000

across 1 |..| games_count as game loop
play
end

print ("Staying wins " + staying_wins.out + " times.%N")
print ("Switching wins " + (games_count - staying_wins).out + " times.%N")
end

feature -- Commands

play
local
doors: ARRAYED_LIST [BOOLEAN]
chosen, shown: INTEGER
do
create doors.make_filled (Door_count) -- False is a goat, True is a car
doors [next_random_door] := True -- Put a car behind a random door
chosen := next_random_door -- Pick a door, any door

-- Monty selects a door which is neither the winner nor the choice
from
shown := next_random_door
until
shown /= chosen and not doors [shown]
loop
shown := next_random_door
end

if doors [chosen] then -- If you would have won by staying, count it
staying_wins := staying_wins + 1
end
ensure
staying_wins_valid: staying_wins = old staying_wins or staying_wins = old staying_wins + 1
end

feature {NONE} -- Implementation

Door_count: INTEGER = 3
-- The total number of doors.

staying_wins: INTEGER
-- The number of times that the strategy of staying would win.

random_generator: RANDOM
-- A random number generator for selecting doors.

next_random_door: INTEGER
-- A door chosen at random.
do
random_generator.forth
Result := random_generator.item \\ Door_count + 1
ensure
valid_door: Result >= 1 and Result <= Door_count
end

end

</e>

==Comments==

Note that the implementations in many other languages maintain a separate variable to count the number of switch wins. They calculate whether switching wins at each step via some funky logic that relies on zero-based array indexing, which would be inconvenient in Eiffel. But we don't need to do that at all anyway, because calculating it at each step is completely redundant: we can just do a final subtraction at the end, right?

RosettaCode

2012-10-03T08:25:57Z

Marco2357:

[[RosettaCode_Monty_Hall|Monty Hall]]

[[RosettaCode_Balanced_Brackets|Balanced Brackets]]

RosettaCode

2012-10-03T08:24:14Z

Marco2357: New page: Monty Hall Balanced Brackets

[[Monty Hall]]

[[Balanced Brackets]]