day19.tiny

input_contents := read_file("inputs/day19.txt")

func split_by_char(input: str, ch: int): array {
    // Necessary because mutating arguments doesn't work haha
    s := input
    parts := array()

    while true {
        end_of_part_pos := strchr(s, ch)
        part := substr(s, 0, end_of_part_pos)

        array_push(parts, part)

        if end_of_part_pos == -1 {
            break
        }
        
        s = substr(s, end_of_part_pos + 1, -1)
    }

    return parts
}

struct Rule {
    cat: int
    op: int
    value: int
    target: str
}

struct Workflow {
    name: str
    predicate_rules: array
    default_target: str
}

// Example workflow: `px{a<2006:qkq,m>2090:A,rfg}`
func parse_workflow(line: str): Workflow {
    rules_start_pos := strchr(line, '{')
    rules_end_pos := strchr(line, '}')

    name := substr(line, 0, rules_start_pos)
    rules_str := substr(line, rules_start_pos + 1, rules_end_pos)
    
    rules_strs := split_by_char(rules_str, ',')

    predicate_rules := array()
    default_target := ""

    for i := 0; i < array_len(rules_strs); i += 1 {
        rule_str: str = array_get(rules_strs, i)

        // Predicate rules have a colon
        colon_pos := strchr(rule_str, ':')

        if colon_pos == -1 {
            default_target = rule_str
            continue
        }

        rule_parts := split_by_char(rule_str, ':')

        predicate_str: str = array_get(rule_parts, 0) 

        cat := stridx(predicate_str, 0)
        op := stridx(predicate_str, 1)
        value := stoi(substr(predicate_str, 2, -1), 10)
        target: str = array_get(rule_parts, 1)

        array_push(predicate_rules, new Rule{cat, op, value, target})
    }

    return new Workflow{name, predicate_rules, default_target}
}

func print_workflow(workflow: Workflow) {
    printf("%s{", workflow.name)

    for i := 0; i < array_len(workflow.predicate_rules); i += 1 {
        rule: Rule = array_get(workflow.predicate_rules, i)

        printf("%c%c%i:%s", rule.cat, rule.op, rule.value, rule.target)
    }
    
    printf(",%s}\n", workflow.default_target)
}

struct CatValue {
    cat: int
    value: int
}

struct Part {
    cat_values: array
}

// Part example: {x=787,m=2655,a=1222,s=2876}
func parse_part(line: str): Part {
    sub := substr(line, 1, strlen(line) - 1)

    cat_strs := split_by_char(sub, ',')

    cat_values := array()

    for i := 0; i < array_len(cat_strs); i += 1 {
        cat_value_str: str = array_get(cat_strs, i)

        cat := stridx(cat_value_str, 0)
        value := stoi(substr(cat_value_str, 2, -1), 10)

        array_push(cat_values, new CatValue{cat, value})    
    }

    return new Part{cat_values}
}

func value_for_cat(part: Part, cat: int): int {
    len := array_len(part.cat_values)

    for i := 0; i < len; i += 1 {
        cv: CatValue = array_get(part.cat_values, i)

        if cv.cat == cat {
            return cv.value
        }
    }

    return -1
}

func find_workflow_by_name(workflows: array, name: str): Workflow {
    len := array_len(workflows)

    for i := 0; i < len; i += 1 {
        workflow: Workflow = array_get(workflows, i)

        if workflow.name == name {
            return workflow
        }
    }
    
    return null
}

func is_accepted(part: Part, workflows: array): bool {
    cur_workflow := find_workflow_by_name(workflows, "in")

    while true {
        pred_rule_count := array_len(cur_workflow.predicate_rules)

        match_result: str = null

        for i := 0; i < pred_rule_count; i += 1 {
            pred_rule: Rule = array_get(cur_workflow.predicate_rules, i)

            value := value_for_cat(part, pred_rule.cat)
            match := false

            if pred_rule.op == '<' {
                match = value < pred_rule.value 
            } else {
                match = value > pred_rule.value
            }

            if match {
                match_result = pred_rule.target
                break
            }
        }

        if match_result == null {
            match_result = cur_workflow.default_target
        }

        if match_result == "A" {
            return true
        } else if match_result == "R" {
            return false 
        }

        cur_workflow = find_workflow_by_name(workflows, match_result)
    }    

    // Should never get here
    return false
}

func print_part(part: Part) {
    printf("{")
    
    first := true

    for i := 0; i < array_len(part.cat_values); i += 1 {
        if !first {
            printf(",")
        }

        first = false

        cat_value: CatValue = array_get(part.cat_values, i)

        printf("%c=%i", cat_value.cat, cat_value.value)
    }

    printf("}\n")
}

// Cases:
// Let input_bounds be bounds that result in entering the workflow
// input_bounds are {1<=x<=4000, 1<=m<=4000, ...} for `in`
// - Default target is "A" -> restrict input_bounds such that it gets rejected by all rules; if possible,
//   add the perms for these bounds to total combos
// - One of the predicate targets is "A" -> restrict input bounds such that it matches predicate,
//   add the perms for these bounds to total combos
// - Default target is another workflow -> restrict input_bounds such that it gets rejected by all rules,
//   visit this new workflow with these input_bounds in mind
// - One of the predicate targets is a workflow -> restrict input bounds such that it matches the predicate,
//   visit the target workflow

struct CatValueBounds {
    cat: int
    min_value: int
    max_value: int
}

struct PartBounds {
    cvb_array: array
}

func find_cat_value_bounds(pb: PartBounds, cat: int): CatValueBounds {
    len := array_len(pb.cvb_array)

    for i := 0; i < len; i += 1 {
        cvb: CatValueBounds = array_get(pb.cvb_array, i)

        if cvb.cat == cat {
            return cvb
        }
    }
    
    return null
}

func perms_for_part_bounds(pb: PartBounds): i64 { 
    perms := int_to_i64(1)
    len := array_len(pb.cvb_array)

    for i := 0; i < len; i += 1 {
        cvb: CatValueBounds = array_get(pb.cvb_array, i)

        possible_values := (cvb.max_value - cvb.min_value) + 1

        if possible_values <= 0 {
            return 0
        }

        perms = i64_mul_many(perms, int_to_i64(possible_values))
    }

    return perms
}

func start_part_bounds(): PartBounds { 
    cvb_array := array()

    array_push(cvb_array, new CatValueBounds{'x', 1, 4000})
    array_push(cvb_array, new CatValueBounds{'m', 1, 4000})
    array_push(cvb_array, new CatValueBounds{'a', 1, 4000})
    array_push(cvb_array, new CatValueBounds{'s', 1, 4000})

    return new PartBounds{cvb_array}
}

func copy_part_bounds(pb: PartBounds): PartBounds {
    copy_cvb_array := array()
    len := array_len(pb.cvb_array)

    for i := 0; i < len; i += 1 {
        cvb: CatValueBounds = array_get(pb.cvb_array, i)

        array_push(copy_cvb_array, new CatValueBounds{
            cvb.cat,
            cvb.min_value,
            cvb.max_value
        })
    }

    return new PartBounds{copy_cvb_array}
}

func restrict_part_bounds(pb: PartBounds, cat: int, op: int, value: int, invert: bool) {
    cvb := find_cat_value_bounds(pb, cat)    

    if op == '<' {
        if invert {
            if cvb.min_value < value {
                cvb.min_value = value
            }
        } else if cvb.max_value >= value {
            cvb.max_value = value - 1
        }
    } else {
        if invert {
            if cvb.max_value > value {
                cvb.max_value = value
            }
        } else if cvb.min_value <= value {
            cvb.min_value = value + 1
        }
    }
}

struct PartBoundsTarget {
    pb: PartBounds
    target: str
}

func print_part_bounds(pb: PartBounds) {
    printf("{")
    len := array_len(pb.cvb_array)

    for i := 0; i < len; i += 1 {
        cvb: CatValueBounds = array_get(pb.cvb_array, i)

        printf("%i<=%c<=%i, ", cvb.min_value, cvb.cat, cvb.max_value)
    }

    printf("}")
}

func count_accepted_perms(workflows: array): i64 {
    total_perms := int_to_i64(0)

    // Stack of candidates
    pbw_cands := array()

    array_push(pbw_cands, new PartBoundsTarget{
        start_part_bounds(),
        "in"
    })

    while array_len(pbw_cands) > 0 {
        cand: PartBoundsTarget = array_pop(pbw_cands)     
        
        cand_perms := perms_for_part_bounds(cand.pb)
        
        if cand_perms == 0 {
            // Don't bother exploring impossible paths
            continue
        }

        perms_str := i64_to_string(cand_perms)

        //print_part_bounds(cand.pb) 
        //printf("->%s\n", perms_str)

        if cand.target == "A" {
            total_perms = i64_add_many(total_perms, cand_perms)
            continue
        } else if cand.target == "R" {
            continue
        }
        
        workflow := find_workflow_by_name(workflows, cand.target)

        // These are the bounds if we want no match
        no_match_bounds := copy_part_bounds(cand.pb)

        pred_rule_count := array_len(workflow.predicate_rules)

        for i := 0; i < pred_rule_count; i += 1 {
            pred_rule: Rule = array_get(workflow.predicate_rules, i)
        
            // We want to start with the no match bounds since we do not want to match our
            // the previous workflows
            match_bounds := copy_part_bounds(no_match_bounds)
            
            restrict_part_bounds(match_bounds, pred_rule.cat, pred_rule.op, pred_rule.value, false)

            array_push(pbw_cands, new PartBoundsTarget{
                match_bounds,
                pred_rule.target
            })

            // Restrict the no match bounds as we go, using the invert parameter to invert the predicate
            restrict_part_bounds(no_match_bounds, pred_rule.cat, pred_rule.op, pred_rule.value, true) 
        }

        array_push(pbw_cands, new PartBoundsTarget{
            no_match_bounds,
            workflow.default_target   
        })
    }

    return total_perms
}

lines := split_by_char(input_contents, '\n')

parts := array()
workflows := array()

for i := 0; i < array_len(lines); i += 1 {
    line: str = array_get(lines, i)

    if strlen(line) == 0 {
        continue
    }

    if stridx(line, 0) == '{' { 
        part := parse_part(line)
        print_part(part) 

        array_push(parts, part)
    } else {
        workflow := parse_workflow(line)
        print_workflow(workflow)

        array_push(workflows, workflow)
    }
}

perms := count_accepted_perms(workflows)

printf("perms=%s\n", i64_to_string(perms))