Functional coverage tree
Functional coverage is a measure of how much a particular function of a system has been verified as correct. It is used heavily in tracking the completeness of the verification of complex System on Chip (SoC) integrated circuits, where it can also be used to track how well the functional requirements of the system have been verified.
You are encouraged to solve this task according to the task description, using any language you may know.
This task uses a sub-set of the calculations sometimes used in tracking functional coverage but uses a more familiar(?) scenario.
- Task Description
The head of the clean-up crews for "The Men in a very dark shade of grey when viewed at night" has been tasked with managing the cleansing of two properties after an incident involving aliens.
She arranges the task hierarchically with a manager for the crews working on each house who return with a breakdown of how they will report on progress in each house.
The overall hierarchy of (sub)tasks is as follows,
cleaning house1 bedrooms bathrooms bathroom1 bathroom2 outside lavatory attic kitchen living rooms lounge dining room conservatory playroom basement garage garden house2 upstairs bedrooms suite 1 suite 2 bedroom 3 bedroom 4 bathroom toilet attics groundfloor kitchen living rooms lounge dining room conservatory playroom wet room & toilet garage garden hot tub suite basement cellars wine cellar cinema
The head of cleanup knows that her managers will report fractional completion of leaf tasks (tasks with no child tasks of their own), and she knows that she will want to modify the weight of values of completion as she sees fit.
Some time into the cleaning, and some coverage reports have come in and she thinks see needs to weight the big house2 60-40 with respect to coverage from house1 She prefers a tabular view of her data where missing weights are assumed to be 1.0 and missing coverage 0.0.
NAME_HIERARCHY |WEIGHT |COVERAGE | cleaning | | | house1 |40 | | bedrooms | |0.25 | bathrooms | | | bathroom1 | |0.5 | bathroom2 | | | outside_lavatory | |1 | attic | |0.75 | kitchen | |0.1 | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | |1 | basement | | | garage | | | garden | |0.8 | house2 |60 | | upstairs | | | bedrooms | | | suite_1 | | | suite_2 | | | bedroom_3 | | | bedroom_4 | | | bathroom | | | toilet | | | attics | |0.6 | groundfloor | | | kitchen | | | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | | | wet_room_&_toilet | | | garage | | | garden | |0.9 | hot_tub_suite | |1 | basement | | | cellars | |1 | wine_cellar | |1 | cinema | |0.75 |
- Calculation
The coverage of a node in the tree is calculated as the weighted average of the coverage of its children evaluated bottom-upwards in the tree.
The task is to calculate the overall coverage of the cleaning task and display the coverage at all levels of the hierarchy on this page, in a manner that visually shows the hierarchy, weights and coverage of all nodes.
- Extra Credit
After calculating the coverage for all nodes, one can also calculate the additional/delta top level coverage that would occur if any (sub)task were to be fully covered from its current fractional coverage. This is done by multiplying the extra coverage that could be gained for any node, by the product of the `powers` of its parent nodes from the top down to the node.
The power of a direct child of any parent is given by the power of the parent multiplied by the weight of the child divided by the sum of the weights of all the direct children.
The pseudo code would be:
method delta_calculation(this, power): sum_of_weights = sum(node.weight for node in children) this.delta = (1 - this.coverage) * power for node in self.children: node.delta_calculation(power * node.weight / sum_of_weights) return this.delta
Followed by a call to:
top.delta_calculation(power=1)
Note: to aid in getting the data into your program you might want to use an alternative, more functional description of the starting data given on the discussion page.
Go
<lang go>package main
import "fmt"
type FCNode struct {
name string weight int coverage float64 children []*FCNode parent *FCNode
}
func newFCN(name string, weight int, coverage float64) *FCNode {
return &FCNode{name, weight, coverage, nil, nil}
}
func (n *FCNode) addChildren(nodes []*FCNode) {
for _, node := range nodes { node.parent = n n.children = append(n.children, node) } n.updateCoverage()
}
func (n *FCNode) setCoverage(value float64) {
if n.coverage != value { n.coverage = value // update any parent's coverage if n.parent != nil { n.parent.updateCoverage() } }
}
func (n *FCNode) updateCoverage() {
v1 := 0.0 v2 := 0 for _, node := range n.children { v1 += float64(node.weight) * node.coverage v2 += node.weight } n.setCoverage(v1 / float64(v2))
}
func (n *FCNode) show(level int) {
indent := level * 4 nl := len(n.name) + indent fmt.Printf("%*s%*s %3d | %8.6f |\n", nl, n.name, 32-nl, "|", n.weight, n.coverage) if len(n.children) == 0 { return } for _, child := range n.children { child.show(level + 1) }
}
var houses = []*FCNode{
newFCN("house1", 40, 0), newFCN("house2", 60, 0),
}
var house1 = []*FCNode{
newFCN("bedrooms", 1, 0.25), newFCN("bathrooms", 1, 0), newFCN("attic", 1, 0.75), newFCN("kitchen", 1, 0.1), newFCN("living_rooms", 1, 0), newFCN("basement", 1, 0), newFCN("garage", 1, 0), newFCN("garden", 1, 0.8),
}
var house2 = []*FCNode{
newFCN("upstairs", 1, 0), newFCN("groundfloor", 1, 0), newFCN("basement", 1, 0),
}
var h1Bathrooms = []*FCNode{
newFCN("bathroom1", 1, 0.5), newFCN("bathroom2", 1, 0), newFCN("outside_lavatory", 1, 1),
}
var h1LivingRooms = []*FCNode{
newFCN("lounge", 1, 0), newFCN("dining_room", 1, 0), newFCN("conservatory", 1, 0), newFCN("playroom", 1, 1),
}
var h2Upstairs = []*FCNode{
newFCN("bedrooms", 1, 0), newFCN("bathroom", 1, 0), newFCN("toilet", 1, 0), newFCN("attics", 1, 0.6),
}
var h2Groundfloor = []*FCNode{
newFCN("kitchen", 1, 0), newFCN("living_rooms", 1, 0), newFCN("wet_room_&_toilet", 1, 0), newFCN("garage", 1, 0), newFCN("garden", 1, 0.9), newFCN("hot_tub_suite", 1, 1),
}
var h2Basement = []*FCNode{
newFCN("cellars", 1, 1), newFCN("wine_cellar", 1, 1), newFCN("cinema", 1, 0.75),
}
var h2UpstairsBedrooms = []*FCNode{
newFCN("suite_1", 1, 0), newFCN("suite_2", 1, 0), newFCN("bedroom_3", 1, 0), newFCN("bedroom_4", 1, 0),
}
var h2GroundfloorLivingRooms = []*FCNode{
newFCN("lounge", 1, 0), newFCN("dining_room", 1, 0), newFCN("conservatory", 1, 0), newFCN("playroom", 1, 0),
}
func main() {
cleaning := newFCN("cleaning", 1, 0)
house1[1].addChildren(h1Bathrooms) house1[4].addChildren(h1LivingRooms) houses[0].addChildren(house1)
h2Upstairs[0].addChildren(h2UpstairsBedrooms) house2[0].addChildren(h2Upstairs) h2Groundfloor[1].addChildren(h2GroundfloorLivingRooms) house2[1].addChildren(h2Groundfloor) house2[2].addChildren(h2Basement) houses[1].addChildren(house2)
cleaning.addChildren(houses) topCoverage := cleaning.coverage fmt.Printf("TOP COVERAGE = %8.6f\n\n", topCoverage) fmt.Println("NAME HIERARCHY | WEIGHT | COVERAGE |") cleaning.show(0)
h2Basement[2].setCoverage(1) // change Cinema node coverage to 1 diff := cleaning.coverage - topCoverage fmt.Println("\nIf the coverage of the Cinema node were increased from 0.75 to 1") fmt.Print("the top level coverage would increase by ") fmt.Printf("%8.6f to %8.6f\n", diff, topCoverage+diff) h2Basement[2].setCoverage(0.75) // restore to original value if required
}</lang>
- Output:
TOP COVERAGE = 0.409167 NAME HIERARCHY | WEIGHT | COVERAGE | cleaning | 1 | 0.409167 | house1 | 40 | 0.331250 | bedrooms | 1 | 0.250000 | bathrooms | 1 | 0.500000 | bathroom1 | 1 | 0.500000 | bathroom2 | 1 | 0.000000 | outside_lavatory | 1 | 1.000000 | attic | 1 | 0.750000 | kitchen | 1 | 0.100000 | living_rooms | 1 | 0.250000 | lounge | 1 | 0.000000 | dining_room | 1 | 0.000000 | conservatory | 1 | 0.000000 | playroom | 1 | 1.000000 | basement | 1 | 0.000000 | garage | 1 | 0.000000 | garden | 1 | 0.800000 | house2 | 60 | 0.461111 | upstairs | 1 | 0.150000 | bedrooms | 1 | 0.000000 | suite_1 | 1 | 0.000000 | suite_2 | 1 | 0.000000 | bedroom_3 | 1 | 0.000000 | bedroom_4 | 1 | 0.000000 | bathroom | 1 | 0.000000 | toilet | 1 | 0.000000 | attics | 1 | 0.600000 | groundfloor | 1 | 0.316667 | kitchen | 1 | 0.000000 | living_rooms | 1 | 0.000000 | lounge | 1 | 0.000000 | dining_room | 1 | 0.000000 | conservatory | 1 | 0.000000 | playroom | 1 | 0.000000 | wet_room_&_toilet | 1 | 0.000000 | garage | 1 | 0.000000 | garden | 1 | 0.900000 | hot_tub_suite | 1 | 1.000000 | basement | 1 | 0.916667 | cellars | 1 | 1.000000 | wine_cellar | 1 | 1.000000 | cinema | 1 | 0.750000 | If the coverage of the Cinema node were increased from 0.75 to 1 the top level coverage would increase by 0.016667 to 0.425833
J
Implementation (raw data):
<lang J>raw=: 0 :0 NAME_HIERARCHY |WEIGHT |COVERAGE | cleaning | | |
house1 |40 | | bedrooms | |0.25 | bathrooms | | | bathroom1 | |0.5 | bathroom2 | | | outside_lavatory | |1 | attic | |0.75 | kitchen | |0.1 | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | |1 | basement | | | garage | | | garden | |0.8 | house2 |60 | | upstairs | | | bedrooms | | | suite_1 | | | suite_2 | | | bedroom_3 | | | bedroom_4 | | | bathroom | | | toilet | | | attics | |0.6 | groundfloor | | | kitchen | | | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | | | wet_room_&_toilet | | | garage | | | garden | |0.9 | hot_tub_suite | |1 | basement | | | cellars | |1 | wine_cellar | |1 | cinema | |0.75 |
)</lang>
Implementation (unpacking raw data):
<lang J>labels=: {.<;._2;._2 raw 'hier wspec cspec'=:|:}.<;._2;._2 raw level=: (%+./) (0 i.~' '&=)"1 hier weight=: (+ 0=]) ,".wspec coverage=: ,".cspec</lang>
Implementation (translation of leaf coverage to functional coverage):
<lang J>merge=: ;@(({.@[,(+}.)~)&.> [: +/\1,_1}.#@>) unrooted=: ([: merge <@(_1,$:@}.);.1)^:(0<#) parent=: unrooted level parent_cover=: (] (1}.~.parent)}~ 1}. * %&(parent +//. ]) [)^:_</lang>
unrooted
translates indentation information to a parent tree structure. However, the limitations of recursion require we distinguish the parent node from its children, so we use _1 to denote the parent node of the recursive intermediate result unrooted trees. (This works well with using arithmetic to adjust sub-tree indices based on the lengths of preceding sub-trees.) merge
combines a boxed sequence of these subtrees to form a single tree - we also rely on the first node of each tree being both _1 and the root node.
Thus, parent_cover
propagates coverage to parent nodes based on the weighted average of coverage at the children.
Task example (format and show result):
<lang J> 1 1 }._1 }.":labels,each ":each hier;(,.weight);,.weight parent_cover coverage NAME_HIERARCHY │WEIGHT │COVERAGE │ cleaning │ 1 │0.409167 │
house1 │40 │ 0.33125 │ bedrooms │ 1 │ 0.25 │ bathrooms │ 1 │ 0.5 │ bathroom1 │ 1 │ 0.5 │ bathroom2 │ 1 │ 0 │ outside_lavatory │ 1 │ 1 │ attic │ 1 │ 0.75 │ kitchen │ 1 │ 0.1 │ living_rooms │ 1 │ 0.25 │ lounge │ 1 │ 0 │ dining_room │ 1 │ 0 │ conservatory │ 1 │ 0 │ playroom │ 1 │ 1 │ basement │ 1 │ 0 │ garage │ 1 │ 0 │ garden │ 1 │ 0.8 │ house2 │60 │0.461111 │ upstairs │ 1 │ 0.15 │ bedrooms │ 1 │ 0 │ suite_1 │ 1 │ 0 │ suite_2 │ 1 │ 0 │ bedroom_3 │ 1 │ 0 │ bedroom_4 │ 1 │ 0 │ bathroom │ 1 │ 0 │ toilet │ 1 │ 0 │ attics │ 1 │ 0.6 │ groundfloor │ 1 │0.316667 │ kitchen │ 1 │ 0 │ living_rooms │ 1 │ 0 │ lounge │ 1 │ 0 │ dining_room │ 1 │ 0 │ conservatory │ 1 │ 0 │ playroom │ 1 │ 0 │ wet_room_&_toilet │ 1 │ 0 │ garage │ 1 │ 0 │ garden │ 1 │ 0.9 │ hot_tub_suite │ 1 │ 1 │ basement │ 1 │0.916667 │ cellars │ 1 │ 1 │ wine_cellar │ 1 │ 1 │ cinema │ 1 │ 0.75 │</lang>
Extra credit:
<lang J>trace=: (~.@,each (0 >. parent)&{)^:_ i.#parent power=: */@:{&(parent (] % (i.~ ~.)@[ { +//.) weight)@> trace
power*1-weight parent_cover coverage
0.590833 0.2675 0.0375 0.025 0.00833333 0.0166667 0 0.0125 0.045 0.0375 0.0125 0.0125 0.0125 0 0.05 0.05 0.01 0.323333 0.17 0.05 0.0125 0.0125 0.0125 0.0125 0.05 0.05 0.02 0.136667 0.0333333 0.0333333 0.00833333 0.00833333 0.00833333 0.00833333 0.0333333 0.0333333 0.00333333 0 0.0166667 0 0 0.0166667</lang>
Explanation:
trace
is, for each node, the set of nodes (or indices of nodes - since we use indices to identify nodes) leading from that node to its root.
parent (] % (i.~ ~.)@[ { +//.) weight
is the weight of each node divided by the total weight for all nodes with the same parent.
power
is the product of these relative weights for each member of the trace.
And, weight parent_cover coverage
was the functional coverage for each node.
Julia
Most implementations of functional coverage are going to store values in a database. The implementation stores the tree in a CSV file with an index to the parent of each entry to allow reconstitution of the tree. <lang Julia>using CSV, DataFrames
function updatecoverage(dfname, outputname)
df = CSV.read(dfname) dchild = Dict{Int, Vector{Int}}([i => Int[] for i in 0:maximum(df[!, 1])])
for row in eachrow(df) push!(dchild[row[3]], row[1]) end
function coverage(t) return dchild[t] == [] ? df[t, :COVERAGE] * df[t, :WEIGHT] : sum(coverage, dchild[t]) / sum(x -> df[x, :WEIGHT], dchild[t]) * df[t, :WEIGHT] end
df[!, :COVERAGE] .= coverage.(df.NUMBER)
CSV.write(outputname, df)
end
function displaycoveragedb(dfname)
df = CSV.read(dfname) indentlevel(t) = (i = 0; while (j = df[t, 3]) != 0 i += 1; t = j end; i) indent1 = [indentlevel(i) for i in df.NUMBER] maxindent = maximum(indent1) indent2 = maxindent .- indent1 println("INDEX AREA NAME_HIERARCHY WEIGHT COVERAGE") for (i, row) in enumerate(eachrow(df)) println(rpad(row[1], 7), " "^indent1[i], rpad(row[2], 20), " "^indent2[i], rpad(row[4], 8), row[5]) end
end
const dbname = "coverage.csv" const newdbname = "coverageupdated.csv"
println("Input data:") displaycoveragedb(dbname) updatecoverage(dbname, newdbname) println("\nUpdated data:") displaycoveragedb(newdbname)
</lang>
- Output:
Input data: INDEX AREA NAME_HIERARCHY WEIGHT COVERAGE 1 cleaning 1 0.0 2 house1 40 0.0 3 bedrooms 1 0.25 4 bathrooms 1 0.0 5 bathroom1 1 0.5 6 bathroom2 1 0.0 7 outside_lavatory 1 1.0 8 attic 1 0.75 9 kitchen 1 0.1 10 living_rooms 1 0.0 11 lounge 1 0.0 12 dining_room 1 0.0 13 conservatory 1 0.0 14 playroom 1 1.0 15 basement 1 0.0 16 garage 1 0.0 17 garden 1 0.8 18 house2 60 0.0 19 upstairs 1 0.0 20 bedrooms 1 0.0 21 suite_1 1 0.0 22 suite_2 1 0.0 23 bedroom_3 1 0.0 24 bedroom_4 1 0.0 25 bathroom 1 0.0 26 toilet 1 0.0 27 attics 1 0.6 28 groundfloor 1 0.0 29 kitchen 1 0.0 30 living_rooms 1 0.0 31 lounge 1 0.0 32 dining_room 1 0.0 33 conservatory 1 0.0 34 playroom 1 0.0 35 wet_room_&_toilet 1 0.0 36 garage 1 0.0 37 garden 1 0.9 38 hot_tub_suite 1 1.0 39 basement 1 0.0 40 cellars 1 1.0 41 wine_cellar 1 1.0 42 cinema 1 0.75 Updated data: INDEX AREA NAME_HIERARCHY WEIGHT COVERAGE 1 cleaning 1 0.4091666666666666 2 house1 40 13.250000000000002 3 bedrooms 1 0.25 4 bathrooms 1 0.5 5 bathroom1 1 0.5 6 bathroom2 1 0.0 7 outside_lavatory 1 1.0 8 attic 1 0.75 9 kitchen 1 0.1 10 living_rooms 1 0.25 11 lounge 1 0.0 12 dining_room 1 0.0 13 conservatory 1 0.0 14 playroom 1 1.0 15 basement 1 0.0 16 garage 1 0.0 17 garden 1 0.8 18 house2 60 27.666666666666664 19 upstairs 1 0.15 20 bedrooms 1 0.0 21 suite_1 1 0.0 22 suite_2 1 0.0 23 bedroom_3 1 0.0 24 bedroom_4 1 0.0 25 bathroom 1 0.0 26 toilet 1 0.0 27 attics 1 0.6 28 groundfloor 1 0.31666666666666665 29 kitchen 1 0.0 30 living_rooms 1 0.0 31 lounge 1 0.0 32 dining_room 1 0.0 33 conservatory 1 0.0 34 playroom 1 0.0 35 wet_room_&_toilet 1 0.0 36 garage 1 0.0 37 garden 1 0.9 38 hot_tub_suite 1 1.0 39 basement 1 0.9166666666666666 40 cellars 1 1.0 41 wine_cellar 1 1.0 42 cinema 1 0.75
Kotlin
<lang scala>// version 1.2.10
class FCNode(val name: String, val weight: Int = 1, coverage: Double = 0.0) {
var coverage = coverage set(value) { if (field != value) { field = value // update any parent's coverage if (parent != null) parent!!.updateCoverage() } }
val children = mutableListOf<FCNode>() var parent: FCNode? = null
fun addChildren(nodes: List<FCNode>) { children.addAll(nodes) nodes.forEach { it.parent = this } updateCoverage() }
private fun updateCoverage() { val v1 = children.sumByDouble { it.weight * it.coverage } val v2 = children.sumBy { it.weight } coverage = v1 / v2 }
fun show(level: Int = 0) { val indent = level * 4 val nl = name.length + indent print(name.padStart(nl)) print("|".padStart(32 - nl)) print(" %3d |".format(weight)) println(" %8.6f |".format(coverage)) if (children.size == 0) return for (child in children) child.show(level + 1) }
}
val houses = listOf(
FCNode("house1", 40), FCNode("house2", 60)
)
val house1 = listOf(
FCNode("bedrooms", 1, 0.25), FCNode("bathrooms"), FCNode("attic", 1, 0.75), FCNode("kitchen", 1, 0.1), FCNode("living_rooms"), FCNode("basement"), FCNode("garage"), FCNode("garden", 1, 0.8)
)
val house2 = listOf(
FCNode("upstairs"), FCNode("groundfloor"), FCNode("basement")
)
val h1Bathrooms = listOf(
FCNode("bathroom1", 1, 0.5), FCNode("bathroom2"), FCNode("outside_lavatory", 1, 1.0)
)
val h1LivingRooms = listOf(
FCNode("lounge"), FCNode("dining_room"), FCNode("conservatory"), FCNode("playroom", 1, 1.0)
)
val h2Upstairs = listOf(
FCNode("bedrooms"), FCNode("bathroom"), FCNode("toilet"), FCNode("attics", 1, 0.6)
)
val h2Groundfloor = listOf(
FCNode("kitchen"), FCNode("living_rooms"), FCNode("wet_room_&_toilet"), FCNode("garage"), FCNode("garden", 1, 0.9), FCNode("hot_tub_suite", 1, 1.0)
)
val h2Basement = listOf(
FCNode("cellars", 1, 1.0), FCNode("wine_cellar", 1, 1.0), FCNode("cinema", 1, 0.75)
)
val h2UpstairsBedrooms = listOf(
FCNode("suite_1"), FCNode("suite_2"), FCNode("bedroom_3"), FCNode("bedroom_4")
)
val h2GroundfloorLivingRooms = listOf(
FCNode("lounge"), FCNode("dining_room"), FCNode("conservatory"), FCNode("playroom")
)
fun main(args: Array<String>) {
val cleaning = FCNode("cleaning")
house1[1].addChildren(h1Bathrooms) house1[4].addChildren(h1LivingRooms) houses[0].addChildren(house1)
h2Upstairs[0].addChildren(h2UpstairsBedrooms) house2[0].addChildren(h2Upstairs) h2Groundfloor[1].addChildren(h2GroundfloorLivingRooms) house2[1].addChildren(h2Groundfloor) house2[2].addChildren(h2Basement) houses[1].addChildren(house2)
cleaning.addChildren(houses) val topCoverage = cleaning.coverage println("TOP COVERAGE = ${"%8.6f".format(topCoverage)}\n") println("NAME HIERARCHY | WEIGHT | COVERAGE |") cleaning.show()
h2Basement[2].coverage = 1.0 // change Cinema node coverage to 1.0 val diff = cleaning.coverage - topCoverage println("\nIf the coverage of the Cinema node were increased from 0.75 to 1.0") print("the top level coverage would increase by ") println("${"%8.6f".format(diff)} to ${"%8.6f".format(topCoverage + diff)}") h2Basement[2].coverage = 0.75 // restore to original value if required
}</lang>
- Output:
TOP COVERAGE = 0.409167 NAME HIERARCHY | WEIGHT | COVERAGE | cleaning | 1 | 0.409167 | house1 | 40 | 0.331250 | bedrooms | 1 | 0.250000 | bathrooms | 1 | 0.500000 | bathroom1 | 1 | 0.500000 | bathroom2 | 1 | 0.000000 | outside_lavatory | 1 | 1.000000 | attic | 1 | 0.750000 | kitchen | 1 | 0.100000 | living_rooms | 1 | 0.250000 | lounge | 1 | 0.000000 | dining_room | 1 | 0.000000 | conservatory | 1 | 0.000000 | playroom | 1 | 1.000000 | basement | 1 | 0.000000 | garage | 1 | 0.000000 | garden | 1 | 0.800000 | house2 | 60 | 0.461111 | upstairs | 1 | 0.150000 | bedrooms | 1 | 0.000000 | suite_1 | 1 | 0.000000 | suite_2 | 1 | 0.000000 | bedroom_3 | 1 | 0.000000 | bedroom_4 | 1 | 0.000000 | bathroom | 1 | 0.000000 | toilet | 1 | 0.000000 | attics | 1 | 0.600000 | groundfloor | 1 | 0.316667 | kitchen | 1 | 0.000000 | living_rooms | 1 | 0.000000 | lounge | 1 | 0.000000 | dining_room | 1 | 0.000000 | conservatory | 1 | 0.000000 | playroom | 1 | 0.000000 | wet_room_&_toilet | 1 | 0.000000 | garage | 1 | 0.000000 | garden | 1 | 0.900000 | hot_tub_suite | 1 | 1.000000 | basement | 1 | 0.916667 | cellars | 1 | 1.000000 | wine_cellar | 1 | 1.000000 | cinema | 1 | 0.750000 | If the coverage of the Cinema node were increased from 0.75 to 1.0 the top level coverage would increase by 0.016667 to 0.425833
Perl
<lang perl>#!/usr/bin/perl
use strict; use warnings;
print $_->[0] for walktree( do { local $/; } );
sub walktree
{ my @parts; while( $_[0] =~ /(( *)\S.*\n)((?:\2 .*\n)*)/g ) { my ($head, $body, $w, $wsum) = ($1, $3, 0, 0); $head =~ /^.*?\|(\S*) *\|(\S*) *\|/; my $weight = sprintf '%-8s', $1 || 1; my $coverage = sprintf '%-10s', $2 || 0; $w += $_->[1], $wsum += $_->[1] * $_->[2], $head .= $_->[0] for walktree( $body ); $w and $coverage = sprintf '%-10.8g', $wsum / $w; push @parts, [ $head =~ s/\|.*/|$weight|$coverage|/r, $weight, $coverage ]; } return @parts; }
__DATA__ NAME_HIERARCHY |WEIGHT |COVERAGE | cleaning | | |
house1 |40 | | bedrooms | |0.25 | bathrooms | | | bathroom1 | |0.5 | bathroom2 | | | outside_lavatory | |1 | attic | |0.75 | kitchen | |0.1 | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | |1 | basement | | | garage | | | garden | |0.8 | house2 |60 | | upstairs | | | bedrooms | | | suite_1 | | | suite_2 | | | bedroom_3 | | | bedroom_4 | | | bathroom | | | toilet | | | attics | |0.6 | groundfloor | | | kitchen | | | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | | | wet_room_&_toilet | | | garage | | | garden | |0.9 | hot_tub_suite | |1 | basement | | | cellars | |1 | wine_cellar | |1 | cinema | |0.75 |
</lang>
- Output:
NAME_HIERARCHY |WEIGHT |COVERAGE | cleaning |1 |0.40916667| house1 |40 |0.33125 | bedrooms |1 |0.25 | bathrooms |1 |0.5 | bathroom1 |1 |0.5 | bathroom2 |1 |0 | outside_lavatory |1 |1 | attic |1 |0.75 | kitchen |1 |0.1 | living_rooms |1 |0.25 | lounge |1 |0 | dining_room |1 |0 | conservatory |1 |0 | playroom |1 |1 | basement |1 |0 | garage |1 |0 | garden |1 |0.8 | house2 |60 |0.46111111| upstairs |1 |0.15 | bedrooms |1 |0 | suite_1 |1 |0 | suite_2 |1 |0 | bedroom_3 |1 |0 | bedroom_4 |1 |0 | bathroom |1 |0 | toilet |1 |0 | attics |1 |0.6 | groundfloor |1 |0.31666667| kitchen |1 |0 | living_rooms |1 |0 | lounge |1 |0 | dining_room |1 |0 | conservatory |1 |0 | playroom |1 |0 | wet_room_&_toilet |1 |0 | garage |1 |0 | garden |1 |0.9 | hot_tub_suite |1 |1 | basement |1 |0.91666667| cellars |1 |1 | wine_cellar |1 |1 | cinema |1 |0.75 |
Python
Python: Using lists and tuples
It's actually some of the raw code used when researching this task.
<lang python>from itertools import zip_longest
fc2 = \
cleaning,,
house1,40, bedrooms,,.25 bathrooms,, bathroom1,,.5 bathroom2,, outside_lavatory,,1 attic,,.75 kitchen,,.1 living_rooms,, lounge,, dining_room,, conservatory,, playroom,,1 basement,, garage,, garden,,.8 house2,60, upstairs,, bedrooms,, suite_1,, suite_2,, bedroom_3,, bedroom_4,, bathroom,, toilet,, attics,,.6 groundfloor,, kitchen,, living_rooms,, lounge,, dining_room,, conservatory,, playroom,, wet_room_&_toilet,, garage,, garden,,.9 hot_tub_suite,,1 basement,, cellars,,1 wine_cellar,,1 cinema,,.75
NAME, WT, COV = 0, 1, 2
def right_type(txt):
try: return float(txt) except ValueError: return txt
def commas_to_list(the_list, lines, start_indent=0):
Output format is a nest of lists and tuples lists are for coverage leaves without children items in the list are name, weight, coverage tuples are 2-tuples for nodes with children. The first element is a list representing the name, weight, coverage of the node (some to be calculated); the second element is a list of child elements which may be 2-tuples or lists as above. the_list is modified in-place lines must be a generator of successive lines of input like fc2 for n, line in lines: indent = 0 while line.startswith(' ' * (4 * indent)): indent += 1 indent -= 1 fields = [right_type(f) for f in line.strip().split(',')] if indent == start_indent: the_list.append(fields) elif indent > start_indent: lst = [fields] sub = commas_to_list(lst, lines, indent) the_list[-1] = (the_list[-1], lst) if sub not in (None, []) : the_list.append(sub) else: return fields if fields else None return None
def pptreefields(lst, indent=0, widths=['%-32s', '%-8g', '%-10g']):
Pretty prints the format described from function commas_to_list as a table with names in the first column suitably indented and all columns having a fixed minimum column width. lhs = ' ' * (4 * indent) for item in lst: if type(item) != tuple: name, *rest = item print(widths[0] % (lhs + name), end='|') for width, item in zip_longest(widths[1:len(rest)], rest, fillvalue=widths[-1]): if type(item) == str: width = width[:-1] + 's' print(width % item, end='|') print() else: item, children = item name, *rest = item print(widths[0] % (lhs + name), end='|') for width, item in zip_longest(widths[1:len(rest)], rest, fillvalue=widths[-1]): if type(item) == str: width = width[:-1] + 's' print(width % item, end='|') print() pptreefields(children, indent+1)
def default_field(node_list):
node_list[WT] = node_list[WT] if node_list[WT] else 1.0 node_list[COV] = node_list[COV] if node_list[COV] else 0.0
def depth_first(tree, visitor=default_field):
for item in tree: if type(item) == tuple: item, children = item depth_first(children, visitor) visitor(item)
def covercalc(tree):
Depth first weighted average of coverage sum_covwt, sum_wt = 0, 0 for item in tree: if type(item) == tuple: item, children = item item[COV] = covercalc(children) sum_wt += item[WT] sum_covwt += item[COV] * item[WT] cov = sum_covwt / sum_wt return cov
if __name__ == '__main__':
lstc = [] commas_to_list(lstc, ((n, ln) for n, ln in enumerate(fc2.split('\n')))) #pp(lstc, width=1, indent=4, compact=1) #print('\n\nEXPANDED DEFAULTS\n') depth_first(lstc) #pptreefields(['NAME_HIERARCHY WEIGHT COVERAGE'.split()] + lstc) print('\n\nTOP COVERAGE = %f\n' % covercalc(lstc)) depth_first(lstc) pptreefields(['NAME_HIERARCHY WEIGHT COVERAGE'.split()] + lstc)</lang>
- Output:
TOP COVERAGE = 0.409167 NAME_HIERARCHY |WEIGHT |COVERAGE | cleaning |1 |0.409167 | house1 |40 |0.33125 | bedrooms |1 |0.25 | bathrooms |1 |0.5 | bathroom1 |1 |0.5 | bathroom2 |1 |0 | outside_lavatory |1 |1 | attic |1 |0.75 | kitchen |1 |0.1 | living_rooms |1 |0.25 | lounge |1 |0 | dining_room |1 |0 | conservatory |1 |0 | playroom |1 |1 | basement |1 |0 | garage |1 |0 | garden |1 |0.8 | house2 |60 |0.461111 | upstairs |1 |0.15 | bedrooms |1 |0 | suite_1 |1 |0 | suite_2 |1 |0 | bedroom_3 |1 |0 | bedroom_4 |1 |0 | bathroom |1 |0 | toilet |1 |0 | attics |1 |0.6 | groundfloor |1 |0.316667 | kitchen |1 |0 | living_rooms |1 |0 | lounge |1 |0 | dining_room |1 |0 | conservatory |1 |0 | playroom |1 |0 | wet_room_&_toilet |1 |0 | garage |1 |0 | garden |1 |0.9 | hot_tub_suite |1 |1 | basement |1 |0.916667 | cellars |1 |1 | wine_cellar |1 |1 | cinema |1 |0.75 |
Python: Class based and extra credit
A cleaner implementation that uses the class static variable path2node as in the previous example so you don't have to traverse the tree to work out the position to add new nodes. This relies on parent nodes appearing before their children which is the case in the order of the add_node calls.
<lang python># -*- coding: utf-8 -*-
SPACES = 4 class Node:
path2node = {} def add_node(self, pathname, wt, cov): path2node = self.path2node path, name = pathname.strip().rsplit('/', 1) node = Node(name, wt, cov) path2node[pathname] = node path2node[path].child.append(node) # Link the tree
def __init__(self, name="", wt=1, cov=0.0, child=None): if child is None: child = [] self.name, self.wt, self.cov, self.child = name, wt, cov, child self.delta = None self.sum_wt = wt if name == "": # designate the top of the tree self.path2node[name] = self def __repr__(self, indent=0): name, wt, cov, delta, child = (self.name, self.wt, self.cov, self.delta, self.child) lhs = ' ' * (SPACES * indent) + "Node(%r," % name txt = '%-40s wt=%2g, cov=%-8.5g, delta=%-10s, child=[' \ % (lhs, wt, cov, ('n/a' if delta is None else '%-10.7f' % delta)) if not child: txt += (']),\n') else: txt += ('\n') for c in child: txt += c.__repr__(indent + 1) txt += (' ' * (SPACES * indent) + "]),\n") return txt
def covercalc(self): Depth first weighted average of coverage child = self.child if not child: return self.cov sum_covwt, sum_wt = 0, 0 for node in child: nwt = node.wt ncov = node.covercalc() sum_wt += nwt sum_covwt += ncov * nwt cov = sum_covwt / sum_wt self.sum_wt = sum_wt self.cov = cov return cov
def deltacalc(self, power=1.0): Top down distribution of weighted residuals sum_wt = self.sum_wt self.delta = delta = (1 - self.cov) * power for node in self.child: node.deltacalc(power * node.wt / sum_wt) return delta
def isclose(a, b, rel_tol=1e-9, abs_tol=1e-9):
return abs(a-b) <= max( rel_tol * max(abs(a), abs(b)), abs_tol )
if __name__ == '__main__':
top = Node() # Add placeholder for top of tree add_node = top.add_node add_node('/cleaning', 1, 0) add_node('/cleaning/house1', 40, 0) add_node('/cleaning/house1/bedrooms', 1, 0.25) add_node('/cleaning/house1/bathrooms', 1, 0) add_node('/cleaning/house1/bathrooms/bathroom1', 1, 0.5) add_node('/cleaning/house1/bathrooms/bathroom2', 1, 0) add_node('/cleaning/house1/bathrooms/outside_lavatory', 1, 1) add_node('/cleaning/house1/attic', 1, 0.75) add_node('/cleaning/house1/kitchen', 1, 0.1) add_node('/cleaning/house1/living_rooms', 1, 0) add_node('/cleaning/house1/living_rooms/lounge', 1, 0) add_node('/cleaning/house1/living_rooms/dining_room', 1, 0) add_node('/cleaning/house1/living_rooms/conservatory', 1, 0) add_node('/cleaning/house1/living_rooms/playroom', 1, 1) add_node('/cleaning/house1/basement', 1, 0) add_node('/cleaning/house1/garage', 1, 0) add_node('/cleaning/house1/garden', 1, 0.8) add_node('/cleaning/house2', 60, 0) add_node('/cleaning/house2/upstairs', 1, 0) add_node('/cleaning/house2/upstairs/bedrooms', 1, 0) add_node('/cleaning/house2/upstairs/bedrooms/suite_1', 1, 0) add_node('/cleaning/house2/upstairs/bedrooms/suite_2', 1, 0) add_node('/cleaning/house2/upstairs/bedrooms/bedroom_3', 1, 0) add_node('/cleaning/house2/upstairs/bedrooms/bedroom_4', 1, 0) add_node('/cleaning/house2/upstairs/bathroom', 1, 0) add_node('/cleaning/house2/upstairs/toilet', 1, 0) add_node('/cleaning/house2/upstairs/attics', 1, 0.6) add_node('/cleaning/house2/groundfloor', 1, 0) add_node('/cleaning/house2/groundfloor/kitchen', 1, 0) add_node('/cleaning/house2/groundfloor/living_rooms', 1, 0) add_node('/cleaning/house2/groundfloor/living_rooms/lounge', 1, 0) add_node('/cleaning/house2/groundfloor/living_rooms/dining_room', 1, 0) add_node('/cleaning/house2/groundfloor/living_rooms/conservatory', 1, 0) add_node('/cleaning/house2/groundfloor/living_rooms/playroom', 1, 0) add_node('/cleaning/house2/groundfloor/wet_room_&_toilet', 1, 0) add_node('/cleaning/house2/groundfloor/garage', 1, 0) add_node('/cleaning/house2/groundfloor/garden', 1, 0.9) add_node('/cleaning/house2/groundfloor/hot_tub_suite', 1, 1) add_node('/cleaning/house2/basement', 1, 0) add_node('/cleaning/house2/basement/cellars', 1, 1) add_node('/cleaning/house2/basement/wine_cellar', 1, 1) add_node('/cleaning/house2/basement/cinema', 1, 0.75)
top = top.child[0] # Remove artificial top cover = top.covercalc() delta = top.deltacalc() print('TOP COVERAGE = %g\n' % cover) print(top) assert isclose((delta + cover), 1.0), "Top level delta + coverage should " \ "equal 1 instead of (%f + %f)" % (delta, cover)
</lang>
- Output:
The deltas where checked by, for example, changing the coverage of the cinema in house2 to be 1.0 instead of 0.75 and observing an additional 0.0166667 increase in the top level coverage at node 'cleaning'.
TOP COVERAGE = 0.409167 Node('cleaning', wt= 1, cov=0.40917 , delta=0.5908333 , child=[ Node('house1', wt=40, cov=0.33125 , delta=0.2675000 , child=[ Node('bedrooms', wt= 1, cov=0.25 , delta=0.0375000 , child=[]), Node('bathrooms', wt= 1, cov=0.5 , delta=0.0250000 , child=[ Node('bathroom1', wt= 1, cov=0.5 , delta=0.0083333 , child=[]), Node('bathroom2', wt= 1, cov=0 , delta=0.0166667 , child=[]), Node('outside_lavatory', wt= 1, cov=1 , delta=0.0000000 , child=[]), ]), Node('attic', wt= 1, cov=0.75 , delta=0.0125000 , child=[]), Node('kitchen', wt= 1, cov=0.1 , delta=0.0450000 , child=[]), Node('living_rooms', wt= 1, cov=0.25 , delta=0.0375000 , child=[ Node('lounge', wt= 1, cov=0 , delta=0.0125000 , child=[]), Node('dining_room', wt= 1, cov=0 , delta=0.0125000 , child=[]), Node('conservatory', wt= 1, cov=0 , delta=0.0125000 , child=[]), Node('playroom', wt= 1, cov=1 , delta=0.0000000 , child=[]), ]), Node('basement', wt= 1, cov=0 , delta=0.0500000 , child=[]), Node('garage', wt= 1, cov=0 , delta=0.0500000 , child=[]), Node('garden', wt= 1, cov=0.8 , delta=0.0100000 , child=[]), ]), Node('house2', wt=60, cov=0.46111 , delta=0.3233333 , child=[ Node('upstairs', wt= 1, cov=0.15 , delta=0.1700000 , child=[ Node('bedrooms', wt= 1, cov=0 , delta=0.0500000 , child=[ Node('suite_1', wt= 1, cov=0 , delta=0.0125000 , child=[]), Node('suite_2', wt= 1, cov=0 , delta=0.0125000 , child=[]), Node('bedroom_3', wt= 1, cov=0 , delta=0.0125000 , child=[]), Node('bedroom_4', wt= 1, cov=0 , delta=0.0125000 , child=[]), ]), Node('bathroom', wt= 1, cov=0 , delta=0.0500000 , child=[]), Node('toilet', wt= 1, cov=0 , delta=0.0500000 , child=[]), Node('attics', wt= 1, cov=0.6 , delta=0.0200000 , child=[]), ]), Node('groundfloor', wt= 1, cov=0.31667 , delta=0.1366667 , child=[ Node('kitchen', wt= 1, cov=0 , delta=0.0333333 , child=[]), Node('living_rooms', wt= 1, cov=0 , delta=0.0333333 , child=[ Node('lounge', wt= 1, cov=0 , delta=0.0083333 , child=[]), Node('dining_room', wt= 1, cov=0 , delta=0.0083333 , child=[]), Node('conservatory', wt= 1, cov=0 , delta=0.0083333 , child=[]), Node('playroom', wt= 1, cov=0 , delta=0.0083333 , child=[]), ]), Node('wet_room_&_toilet', wt= 1, cov=0 , delta=0.0333333 , child=[]), Node('garage', wt= 1, cov=0 , delta=0.0333333 , child=[]), Node('garden', wt= 1, cov=0.9 , delta=0.0033333 , child=[]), Node('hot_tub_suite', wt= 1, cov=1 , delta=0.0000000 , child=[]), ]), Node('basement', wt= 1, cov=0.91667 , delta=0.0166667 , child=[ Node('cellars', wt= 1, cov=1 , delta=0.0000000 , child=[]), Node('wine_cellar', wt= 1, cov=1 , delta=0.0000000 , child=[]), Node('cinema', wt= 1, cov=0.75 , delta=0.0166667 , child=[]), ]), ]), ]),
Python: Composition of pure functions
Parsing the task statement text directly to a tree of dictionaries, folding a weightedTreeAverage function over that tree, and mainly using pre-existing generic functions, including foldTree, and drawTree:
<lang python>Functional coverage tree
from itertools import chain, repeat, starmap from collections import defaultdict from functools import reduce from operator import add import re
- TEST ----------------------------------------------------
- main :: IO ()
def main():
Summary tree structure from a parse of the table in the task statement. print(drawForest( map( foldTree(weightedTreeAverage), map( fmapTree(recordFromLine), forestFromLineIndents( indentLevelsFromLines( lines(REPORT)[2:] ) ) ) ) ))
- weightedTreeAverage :: Tree Dict -> [Tree Dict] -> Tree Dict
def weightedTreeAverage(x):
The weighted average of a tree node, as a function of the weighted averages of its children. def go(xs): return Node(dict( x, **{ 'coverage': x['coverage'] + ( sum(map( lambda dct: dct['root']['coverage'] * ( dct['root']['weight'] ), xs )) / ( sum(map( lambda dct: dct['root']['weight'], xs )) or 1 ) ) } ))(xs) return lambda xs: go(xs)
- recordFromLine :: String ->
- { name :: String, weight :: Float, completion :: Float }
def recordFromLine(s):
A dictionary of 3 key-value pairs, derived from a '|' delimited string. return dict(map( lambda k, v: ( k, float(v) if v else ( 1.0 if k != 'coverage' else 0.0 ) ) if k != 'name' else (k, v), ['name', 'weight', 'coverage'], map(strip, splitOn('|')(s)) ))
- GENERIC AND REUSABLE FUNCTIONS --------------------------
- Node :: a -> [Tree a] -> Tree a
def Node(v):
Constructor for a Tree node which connects a value of some kind to a list of zero or more child trees. return lambda xs: {'type': 'Tree', 'root': v, 'nest': xs}
- Tuple (,) :: a -> b -> (a, b)
def Tuple(x):
Constructor for a pair of values, possibly of two different types. return lambda y: ( x + (y,) ) if isinstance(x, tuple) else (x, y)
- compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
Composition, from right to left, of a series of functions. return lambda x: reduce( lambda a, f: f(a), fs[::-1], x )
- concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
A concatenated list or string over which a function f has been mapped. The list monad can be derived by using an (a -> [b]) function which wraps its output in a list (using an empty list to represent computational failure). return lambda xs: (.join if isinstance(xs, str) else list)( chain.from_iterable(map(f, xs)) )
- div :: Int -> Int -> Int
def div(x):
Integer division. return lambda y: x // y
- draw :: Tree a -> [String]
def draw(node):
List of the lines of an ASCII diagram of a tree. def shift_(first, other, xs): return list(starmap( add, zip( [first] + list( repeat(other, len(xs) - 1) ), xs ) ))
def drawSubTrees(xs): return ( ( ['|'] + shift_( '├─ ', '│ ', draw(xs[0]) ) + drawSubTrees(xs[1:]) ) if 1 < len(xs) else ['|'] + shift_( '└─ ', ' ', draw(xs[0]) ) ) if xs else []
return (show(root(node))).splitlines() + ( drawSubTrees(nest(node)) )
- drawForest :: [Tree String] -> String
def drawForest(trees):
A simple unicode character representation of a list of trees. return '\n'.join(map(drawTree, trees))
- drawTree :: Tree a -> String
def drawTree(tree):
ASCII diagram of a tree. return '\n'.join(draw(tree))
def firstArrow(f):
A simple function lifted to one which applies to a tuple, transforming only its first item. return lambda xy: Tuple(f(xy[0]))( xy[1] )
- flip :: (a -> b -> c) -> b -> a -> c
def flip(f):
The (curried or uncurried) function f with its arguments reversed. return lambda a: lambda b: f(b)(a)
- fmapTree :: (a -> b) -> Tree a -> Tree b
def fmapTree(f):
A new tree holding the results of applying f to each root in the existing tree. def go(x): return Node(f(x['root']))( [go(v) for v in x['nest']] ) return lambda tree: go(tree)
- foldTree :: (a -> [b] -> b) -> Tree a -> b
def foldTree(f):
The catamorphism on trees. A summary value obtained by a depth-first fold. def go(node): return f(node['root'])([ go(x) for x in node['nest'] ]) return lambda tree: go(tree)
- forestFromLineIndents :: [(Int, String)] -> [Tree String]
def forestFromLineIndents(tuples):
A list of trees derived from a list of lines paired with integers giving their levels of indentation. def go(xs): if xs: (n, s) = xs[0] # Lines indented under this line, # tupled with all the rest. (firstTreeLines, rest) = span( lambda x: n < x[0] )(xs[1:]) # This first tree, and then the rest. return [Node(s)(go(firstTreeLines))] + go(rest) else: return [] return go(tuples)
- indentLevelsFromLines :: [String] -> [(Int, String)]
def indentLevelsFromLines(xs):
Each input line stripped of leading white space, and tupled with a preceding integer giving its level of indentation from 0 upwards. rgxSpace = re.compile(r'\s+') indentTextPairs = list(map( compose(firstArrow(len), span(rgxSpace.match)), xs )) indentUnit = min(concatMap( lambda x: [x[0]] if x[0] else [] )(indentTextPairs)) return list(map( firstArrow(flip(div)(indentUnit)), indentTextPairs ))
- lines :: String -> [String]
def lines(s):
A list of strings, (containing no newline characters) derived from a single new-line delimited string. return s.splitlines()
- nest :: Tree a -> [Tree a]
def nest(t):
Accessor function for children of tree node. return t['nest'] if 'nest' in t else None
- root :: Tree a -> a
def root(t):
Accessor function for data of tree node. return t['root'] if 'root' in t else None
- show :: a -> String
def show(x):
Stringification of a value. def go(v): return defaultdict(lambda: repr, [ ('list', showList), # ('Either', showLR), # ('Maybe', showMaybe), ('Tree', drawTree), # ('NoneType', showNone) ])[typeName(v)](v) return go(x)
- showList :: [a] -> String
def showList(xs):
Stringification of a list. return '[' + ', '.join(show(x) for x in xs) + ']'
- strip :: String -> String
def strip(s):
A copy of s without any leading or trailling white space. return s.strip()
- span :: (a -> Bool) -> [a] -> ([a], [a])
def span(p):
The longest (possibly empty) prefix of xs that contains only elements satisfying p, tupled with the remainder of xs. span p xs is equivalent to (takeWhile p xs, dropWhile p xs). def go(xs): lng = len(xs) return splitAt( until(lambda i: (lng == i) or not p(xs[i]))(succ)(0) )(xs) return lambda xs: go(xs)
- Unimplemented <- splitOn for lists (Eq a => [a] -> [a] -> a)
- splitOn :: String -> String -> [String]
def splitOn(pat):
A list of the strings delimited by instances of a given pattern in s. return lambda xs: ( xs.split(pat) if isinstance(xs, str) else None )
- succ :: Enum a => a -> a
def succ(x):
The successor of a value. For numeric types, (1 +). return 1 + x if isinstance(x, int) else ( chr(1 + ord(x)) )
- splitAt :: Int -> [a] -> ([a], [a])
def splitAt(n):
A tuple pairing the prefix of length n with the rest of xs. return lambda xs: (xs[0:n], xs[n:])
- typeName :: a -> String
def typeName(x):
Name string for a built-in or user-defined type. Selector for type-specific instances of polymorphic functions. if isinstance(x, dict): return x.get('type') if 'type' in x else 'dict' else: return 'iter' if hasattr(x, '__next__') else ( type(x).__name__ )
- until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
The result of repeatedly applying f until p holds. The initial seed value is x. def go(f, x): v = x while not p(v): v = f(v) return v return lambda f: lambda x: go(f, x)
- MAIN ----------------------------------------------------
if __name__ == '__main__':
REPORT = NAME_HIERARCHY |WEIGHT |COVERAGE | cleaning | | | house1 |40 | | bedrooms | |0.25 | bathrooms | | | bathroom1 | |0.5 | bathroom2 | | | outside_lavatory | |1 | attic | |0.75 | kitchen | |0.1 | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | |1 | basement | | | garage | | | garden | |0.8 | house2 |60 | | upstairs | | | bedrooms | | | suite_1 | | | suite_2 | | | bedroom_3 | | | bedroom_4 | | | bathroom | | | toilet | | | attics | |0.6 | groundfloor | | | kitchen | | | living_rooms | | | lounge | | | dining_room | | | conservatory | | | playroom | | | wet_room_&_toilet | | | garage | | | garden | |0.9 | hot_tub_suite | |1 | basement | | | cellars | |1 | wine_cellar | |1 | cinema | |0.75 | main()</lang>
- Output:
{'name': 'cleaning', 'weight': 1.0, 'coverage': 0.4091666666666666} | ├─ {'name': 'house1', 'weight': 40.0, 'coverage': 0.33125000000000004} │ | │ ├─ {'name': 'bedrooms', 'weight': 1.0, 'coverage': 0.25} │ | │ ├─ {'name': 'bathrooms', 'weight': 1.0, 'coverage': 0.5} │ │ | │ │ ├─ {'name': 'bathroom1', 'weight': 1.0, 'coverage': 0.5} │ │ | │ │ ├─ {'name': 'bathroom2', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ └─ {'name': 'outside_lavatory', 'weight': 1.0, 'coverage': 1.0} │ | │ ├─ {'name': 'attic', 'weight': 1.0, 'coverage': 0.75} │ | │ ├─ {'name': 'kitchen', 'weight': 1.0, 'coverage': 0.1} │ | │ ├─ {'name': 'living_rooms', 'weight': 1.0, 'coverage': 0.25} │ │ | │ │ ├─ {'name': 'lounge', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'dining_room', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'conservatory', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ └─ {'name': 'playroom', 'weight': 1.0, 'coverage': 1.0} │ | │ ├─ {'name': 'basement', 'weight': 1.0, 'coverage': 0.0} │ | │ ├─ {'name': 'garage', 'weight': 1.0, 'coverage': 0.0} │ | │ └─ {'name': 'garden', 'weight': 1.0, 'coverage': 0.8} | └─ {'name': 'house2', 'weight': 60.0, 'coverage': 0.4611111111111111} | ├─ {'name': 'upstairs', 'weight': 1.0, 'coverage': 0.15} │ | │ ├─ {'name': 'bedrooms', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'suite_1', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'suite_2', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'bedroom_3', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ └─ {'name': 'bedroom_4', 'weight': 1.0, 'coverage': 0.0} │ | │ ├─ {'name': 'bathroom', 'weight': 1.0, 'coverage': 0.0} │ | │ ├─ {'name': 'toilet', 'weight': 1.0, 'coverage': 0.0} │ | │ └─ {'name': 'attics', 'weight': 1.0, 'coverage': 0.6} | ├─ {'name': 'groundfloor', 'weight': 1.0, 'coverage': 0.31666666666666665} │ | │ ├─ {'name': 'kitchen', 'weight': 1.0, 'coverage': 0.0} │ | │ ├─ {'name': 'living_rooms', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'lounge', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'dining_room', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ ├─ {'name': 'conservatory', 'weight': 1.0, 'coverage': 0.0} │ │ | │ │ └─ {'name': 'playroom', 'weight': 1.0, 'coverage': 0.0} │ | │ ├─ {'name': 'wet_room_&_toilet', 'weight': 1.0, 'coverage': 0.0} │ | │ ├─ {'name': 'garage', 'weight': 1.0, 'coverage': 0.0} │ | │ ├─ {'name': 'garden', 'weight': 1.0, 'coverage': 0.9} │ | │ └─ {'name': 'hot_tub_suite', 'weight': 1.0, 'coverage': 1.0} | └─ {'name': 'basement', 'weight': 1.0, 'coverage': 0.9166666666666666} | ├─ {'name': 'cellars', 'weight': 1.0, 'coverage': 1.0} | ├─ {'name': 'wine_cellar', 'weight': 1.0, 'coverage': 1.0} | └─ {'name': 'cinema', 'weight': 1.0, 'coverage': 0.75}
Racket
To save on paper, the coverage table needs to be saved to a file
(in this case data/functional-coverage.txt
).
<lang racket>#lang racket/base (require racket/list racket/string racket/match racket/format racket/file)
(struct Coverage (name weight coverage weighted-coverage children) #:transparent #:mutable)
- -| read/parse |------------------------------------------------------------------------------------
(define (build-hierarchies parsed-lines)
(define inr (match-lambda ['() (values null null)] [`((,head-indent . ,C) ,tail-lines ...) (define child? (match-lambda [(cons i _) #:when (> i head-indent) #t] [_ #f])) (define-values (chlds rels) (splitf-at tail-lines child?)) (define-values (rels-tree rels-rem) (inr rels)) (values (cons (struct-copy Coverage C (children (build-hierarchies chlds))) rels-tree) rels-rem)])) (define-values (hierarchies remaining-lines) (inr parsed-lines)) hierarchies)
(define report-line->indent.c/e-line
(match-lambda [(regexp #px"^( *)([^ ]*) *\\| *([^ ]*) *\\| *([^ ]*) *\\|$" (list _ (app string-length indent-length) name (or (and (not "") (app string->number wght)) (app (λ (x) 1) wght)) (or (and (not "") (app string->number cvrg)) (app (λ (x) 0) cvrg)))) (cons indent-length (Coverage name wght cvrg 0 #f))]))
(define (report->indent.c/e-list rprt)
(map report-line->indent.c/e-line (drop (string-split rprt "\n") 1)))
- -| evaluate |--------------------------------------------------------------------------------------
(define find-wght-cvrg
(match-lambda [(and e (Coverage _ w c _ '())) (struct-copy Coverage e (weighted-coverage (* w c)))] [(and e (Coverage _ _ _ _ `(,(app find-wght-cvrg (and cdn+ (Coverage _ c-ws _ c-w/cs _))) ...))) (define chld-wghtd-avg (for/sum ((w (in-list c-ws)) (w/c (in-list c-w/cs))) (* w w/c))) (struct-copy Coverage e (weighted-coverage (/ chld-wghtd-avg (apply + c-ws))) (children cdn+))]))
- -| printing |--------------------------------------------------------------------------------------
(define max-description-length
(match-lambda [(Coverage (app string-length name-length) _ _ _ (list (app max-description-length children-lengths) ...)) (apply max name-length (map add1 children-lengths))]))
(define (~a/right w x)
(~a x #:width w #:align 'right))
(define (~a/decimal n dec-dgts)
(~a/right (+ dec-dgts 3) (if (zero? n) "" (real->decimal-string n dec-dgts))))
(define (print-coverage-tree tree)
(define mdl (max-description-length tree)) (printf "| ~a |WEIGT| COVER |WGHTD CVRG|~%" (~a "NAME" #:width mdl #:align 'center)) (let inr ((depth 0) (tree tree)) (unless (null? tree) (match tree [(Coverage name w c w/c chlds) (printf "| ~a | ~a | ~a | ~a |~%" (~a (string-append (make-string depth #\space) name) #:width mdl) (~a/right 3 w) (~a/decimal c 2) (~a/decimal w/c 5)) (for ((c chlds)) (inr (add1 depth) c))]))))
- ---------------------------------------------------------------------------------------------------
(module+ main
- data/functional-coverage.txt contains a verbatim copy of
- the table in the task's description
(for-each
(compose print-coverage-tree find-wght-cvrg) (build-hierarchies (report->indent.c/e-list (file->string "data/functional-coverage.txt")))))</lang>
- Output:
| NAME |WEIGT| COVER |WGHTD CVRG| | cleaning | 1 | | 0.40917 | | house1 | 40 | | 0.33125 | | bedrooms | 1 | 0.25 | 0.25000 | | bathrooms | 1 | | 0.50000 | | bathroom1 | 1 | 0.50 | 0.50000 | | bathroom2 | 1 | | | | outside_lavatory | 1 | 1.00 | 1.00000 | | attic | 1 | 0.75 | 0.75000 | | kitchen | 1 | 0.10 | 0.10000 | | living_rooms | 1 | | 0.25000 | | lounge | 1 | | | | dining_room | 1 | | | | conservatory | 1 | | | | playroom | 1 | 1.00 | 1.00000 | | basement | 1 | | | | garage | 1 | | | | garden | 1 | 0.80 | 0.80000 | | house2 | 60 | | 0.46111 | | upstairs | 1 | | 0.15000 | | bedrooms | 1 | | | | suite_1 | 1 | | | | suite_2 | 1 | | | | bedroom_3 | 1 | | | | bedroom_4 | 1 | | | | bathroom | 1 | | | | toilet | 1 | | | | attics | 1 | 0.60 | 0.60000 | | groundfloor | 1 | | 0.31667 | | kitchen | 1 | | | | living_rooms | 1 | | | | lounge | 1 | | | | dining_room | 1 | | | | conservatory | 1 | | | | playroom | 1 | | | | wet_room_&_toilet | 1 | | | | garage | 1 | | | | garden | 1 | 0.90 | 0.90000 | | hot_tub_suite | 1 | 1.00 | 1.00000 | | basement | 1 | | 0.91667 | | cellars | 1 | 1.00 | 1.00000 | | wine_cellar | 1 | 1.00 | 1.00000 | | cinema | 1 | 0.75 | 0.75000 |