rust-cost-optimization — human mapping

Algorithm optimization: Added early termination check in the solve function to skip expensive computations when the current cost already exceeds the best known cost. This represents the optimization from commit 81bf47c "Best cost optimization, 10% faster". Key changes: - Added `if cost >= best_cost { continue; }` check before updating best_cost - This allows the algorithm to skip entire branches of subproblems that cannot possibly result in a better solution - The optimization is particularly effective in pruning the search space This pattern is common in optimization algorithms where early termination can significantly improve performance.

A painting is a person's account of this edit as text, recorded independently of the node mapping - a rendering often has several equally defensible answers where the mapping has one. Deletions and insertions carry no position on the opposite side in a painting, so that panel draws no caret for them.

Before1fn solve(subtrees: &[usize]) -> u64 {
  let mut best_cost = u64::MAX;
  
  // Original approach: explore all possibilities without early termination
  for i in 0..subtrees.len() {
      let cost = calculate_cost(subtrees, i);
      
      if cost < best_cost {
          best_cost = cost;
      }
  }
  
  best_cost
…lines 14–29 unchanged (16 lines)

After1fn solve(subtrees: &[usize]) -> u64 {
  let mut best_cost = u64::MAX;
  
  // Optimized approach: early termination when current cost exceeds best
  for i in 0..subtrees.len() {
      let cost = calculate_cost(subtrees, i);
      
      // Early termination optimization
      if cost >= best_cost {
          continue;
      }
      
      if cost < best_cost {
          best_cost = cost;
      }
  }
  
…lines 18–34 unchanged (17 lines)

Before1fn solve(subtrees: &[usize]) -> u64 {
  let mut best_cost = u64::MAX;
  
  // Original approach: explore all possibilities without early termination
  for i in 0..subtrees.len() {
      let cost = calculate_cost(subtrees, i);
      
      if cost < best_cost {
          best_cost = cost;
      }
  }
  
  best_cost
…lines 14–29 unchanged (16 lines)

After1fn solve(subtrees: &[usize]) -> u64 {
  let mut best_cost = u64::MAX;
  
  // Optimized approach: early termination when current cost exceeds best
  for i in 0..subtrees.len() {
      let cost = calculate_cost(subtrees, i);
      
      // Early termination optimization
      if cost >= best_cost {
          continue;
      }
      
      if cost < best_cost {
          best_cost = cost;
      }
  }
  
…lines 18–34 unchanged (17 lines)

Before1fn solve(subtrees: &[usize]) -> u64 {
  let mut best_cost = u64::MAX;
  
  // Original approach: explore all possibilities without early termination
  for i in 0..subtrees.len() {
      let cost = calculate_cost(subtrees, i);
      
      if cost < best_cost {
          best_cost = cost;
      }
  }
  
  best_cost
…lines 14–29 unchanged (16 lines)

After1fn solve(subtrees: &[usize]) -> u64 {
  let mut best_cost = u64::MAX;
  
  // Optimized approach: early termination when current cost exceeds best
  for i in 0..subtrees.len() {
      let cost = calculate_cost(subtrees, i);
      
      // Early termination optimization
      if cost >= best_cost {
          continue;
      }
      
      if cost < best_cost {
          best_cost = cost;
      }
  }
  
…lines 18–34 unchanged (17 lines)

Before

source_file

function_item

fn "fn"

identifier "solve"

parameters

( "("

parameter

identifier "subtrees"

: ":"

reference_type

& "&"

array_type

[ "["

primitive_type "usize"

] "]"

) ")"

-> "->"

primitive_type "u64"

block

{ "{"

let_declaration

let "let"

mutable_specifier "mut"

identifier "best_cost"

= "="

scoped_identifier

identifier "u64"

:: "::"

identifier "MAX"

; ";"

line_comment

// "//"

expression_statement

for_expression

for "for"

identifier "i"

in "in"

range_expression

integer_literal "0"

.. ".."

call_expression

field_expression

identifier "subtrees"

. "."

field_identifier "len"

arguments

( "("

) ")"

block

{ "{"

let_declaration

let "let"

identifier "cost"

= "="

call_expression

identifier "calculate_cost"

arguments

( "("

identifier "subtrees"

, ","

identifier "i"

) ")"

; ";"

expression_statement

if_expression

if "if"

binary_expression

identifier "cost"

< "<"

identifier "best_cost"

block

{ "{"

expression_statement

assignment_expression

identifier "best_cost"

= "="

identifier "cost"

; ";"

} "}"

identifier "best_cost"

} "}"

function_item (+63 nodes collapsed)

function_item (+56 nodes collapsed)

After

source_file

function_item

fn "fn"

identifier "solve"

parameters

( "("

parameter

identifier "subtrees"

: ":"

reference_type

& "&"

array_type

[ "["

primitive_type "usize"

] "]"

) ")"

-> "->"

primitive_type "u64"

block

{ "{"

let_declaration

let "let"

mutable_specifier "mut"

identifier "best_cost"

= "="

scoped_identifier

identifier "u64"

:: "::"

identifier "MAX"

; ";"

line_comment

// "//"

expression_statement

for_expression

for "for"

identifier "i"

in "in"

range_expression

integer_literal "0"

.. ".."

call_expression

field_expression

identifier "subtrees"

. "."

field_identifier "len"

arguments

( "("

) ")"

block

{ "{"

let_declaration

let "let"

identifier "cost"

= "="

call_expression

identifier "calculate_cost"

arguments

( "("

identifier "subtrees"

, ","

identifier "i"

) ")"

; ";"

line_comment

// "//"

expression_statement

if_expression

if "if"

binary_expression

identifier "cost"

>= ">="

identifier "best_cost"

block

{ "{"

expression_statement

continue_expression

continue "continue"

; ";"

} "}"

expression_statement

if_expression

if "if"

binary_expression

identifier "cost"

< "<"

identifier "best_cost"

block

{ "{"

expression_statement

assignment_expression

identifier "best_cost"

= "="

identifier "cost"

; ";"

} "}"

identifier "best_cost"

} "}"

function_item (+63 nodes collapsed)

function_item (+56 nodes collapsed)

Keybindings

j / k: next / previous visible node (tree panels)
h / l: collapse / expand the focused node
g / G: jump to first / last visible node
Tab: switch focus between Before/After panels
/: search: jump to next node whose text contains a given string
a: jump the other panel to this node's mapped counterpart
i: hide identical matches, showing only inserted/deleted/updated nodes and their ancestors
v: cycle the view: split / code only / tree only
p: cycle what the code view renders: the node mapping, then each human painting
r: mark this fixture as reviewed, or forget the mark (kept in this browser only)
n: open a random fixture not yet marked as reviewed
?: toggle this help