Solve System of Linear Addition Equations

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

class Solution {
public:
    map<string, int> solveEquations(string equations) {
        vector<string> lines = split(equations, '\n');
        map<string, vector<pair<string, int>>> deps; // var -> [(var, coeff), (const, value)]
        map<string, int> constants; // var -> constant_sum
        map<string, int> solution;
        
        // Parse equations
        for (string& line : lines) {
            if (!parseEquation(line, deps, constants)) {
                return {};
            }
        }
        
        // Find variables that can be solved directly
        queue<string> ready;
        for (auto& [var, terms] : deps) {
            bool hasOnlyConstants = true;
            for (auto& [term, coeff] : terms) {
                if (isVariable(term)) {
                    hasOnlyConstants = false;
                    break;
                }
            }
            if (hasOnlyConstants) {
                ready.push(var);
            }
        }
        
        // Solve using topological sort approach
        while (!ready.empty()) {
            string var = ready.front();
            ready.pop();
            
            if (solution.count(var)) continue;
            
            // Calculate value for this variable
            int value = constants[var];
            for (auto& [term, coeff] : deps[var]) {
                if (isVariable(term)) {
                    if (!solution.count(term)) {
                        // Still depends on unsolved variable
                        continue;
                    }
                    value += solution[term] * coeff;
                } else {
                    value += stoi(term) * coeff;
                }
            }
            
            solution[var] = value;
            
            // Update dependencies and check for newly solvable variables
            for (auto& [otherVar, terms] : deps) {
                if (solution.count(otherVar)) continue;
                
                bool canSolve = true;
                for (auto& [term, coeff] : terms) {
                    if (isVariable(term) && !solution.count(term)) {
                        canSolve = false;
                        break;
                    }
                }
                if (canSolve) {
                    ready.push(otherVar);
                }
            }
        }
        
        // Check if all variables are solved
        for (auto& [var, terms] : deps) {
            if (!solution.count(var)) {
                return {}; // Unsolvable (circular dependency)
            }
        }
        
        // Verify solution consistency
        if (!verifySolution(lines, solution)) {
            return {};
        }
        
        return solution;
    }
    
private:
    vector<string> split(string str, char delim) {
        vector<string> result;
        stringstream ss(str);
        string item;
        while (getline(ss, item, delim)) {
            result.push_back(item);
        }
        return result;
    }
    
    bool isVariable(const string& term) {
        return !term.empty() && isalpha(term[0]);
    }
    
    bool parseEquation(string line, map<string, vector<pair<string, int>>>& deps, 
                      map<string, int>& constants) {
        // Remove spaces
        line.erase(remove(line.begin(), line.end(), ' '), line.end());
        
        size_t eqPos = line.find('=');
        if (eqPos == string::npos) return false;
        
        string left = line.substr(0, eqPos);
        string right = line.substr(eqPos + 1);
        
        // Parse right side
        vector<pair<string, int>> terms;
        int constantSum = 0;
        
        stringstream ss(right);
        string token;
        int sign = 1;
        
        size_t pos = 0;
        while (pos < right.length()) {
            if (right[pos] == '+') {
                sign = 1;
                pos++;
            } else if (right[pos] == '-') {
                sign = -1;
                pos++;
            }
            
            size_t nextOp = right.find_first_of("+-", pos);
            if (nextOp == string::npos) nextOp = right.length();
            
            string term = right.substr(pos, nextOp - pos);
            if (isVariable(term)) {
                terms.push_back({term, sign});
            } else {
                constantSum += sign * stoi(term);
            }
            
            pos = nextOp;
        }
        
        deps[left] = terms;
        constants[left] = constantSum;
        return true;
    }
    
    bool verifySolution(const vector<string>& lines, const map<string, int>& solution) {
        for (const string& line : lines) {
            string cleanLine = line;
            cleanLine.erase(remove(cleanLine.begin(), cleanLine.end(), ' '), cleanLine.end());
            
            size_t eqPos = cleanLine.find('=');
            string left = cleanLine.substr(0, eqPos);
            string right = cleanLine.substr(eqPos + 1);
            
            int leftVal = solution.count(left) ? solution.at(left) : stoi(left);
            int rightVal = evaluateExpression(right, solution);
            
            if (leftVal != rightVal) return false;
        }
        return true;
    }
    
    int evaluateExpression(const string& expr, const map<string, int>& solution) {
        int result = 0;
        int sign = 1;
        size_t pos = 0;
        
        while (pos < expr.length()) {
            if (expr[pos] == '+') {
                sign = 1;
                pos++;
            } else if (expr[pos] == '-') {
                sign = -1;
                pos++;
            }
            
            size_t nextOp = expr.find_first_of("+-", pos);
            if (nextOp == string::npos) nextOp = expr.length();
            
            string term = expr.substr(pos, nextOp - pos);
            if (isVariable(term)) {
                result += sign * solution.at(term);
            } else {
                result += sign * stoi(term);
            }
            
            pos = nextOp;
        }
        
        return result;
    }
};

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

func SolveEquations(equations string) map[string]int {
    lines := strings.Split(equations, "\n")
    deps := make(map[string][]Term)
    constants := make(map[string]int)
    solution := make(map[string]int)
    
    // Parse equations
    for _, line := range lines {
        if !parseEquation(line, deps, constants) {
            return nil
        }
    }
    
    // Find variables that can be solved directly
    ready := make([]string, 0)
    for variable, terms := range deps {
        hasOnlyConstants := true
        for _, term := range terms {
            if isVariable(term.Name) {
                hasOnlyConstants = false
                break
            }
        }
        if hasOnlyConstants {
            ready = append(ready, variable)
        }
    }
    
    // Solve using topological sort approach
    for len(ready) > 0 {
        variable := ready[0]
        ready = ready[1:]
        
        if _, exists := solution[variable]; exists {
            continue
        }
        
        // Calculate value for this variable
        value := constants[variable]
        canSolve := true
        
        for _, term := range deps[variable] {
            if isVariable(term.Name) {
                if termValue, exists := solution[term.Name]; exists {
                    value += termValue * term.Coefficient
                } else {
                    canSolve = false
                    break
                }
            } else {
                if termValue, err := strconv.Atoi(term.Name); err == nil {
                    value += termValue * term.Coefficient
                }
            }
        }
        
        if !canSolve {
            continue
        }
        
        solution[variable] = value
        
        // Check for newly solvable variables
        for otherVar, terms := range deps {
            if _, exists := solution[otherVar]; exists {
                continue
            }
            
            canSolveOther := true
            for _, term := range terms {
                if isVariable(term.Name) {
                    if _, exists := solution[term.Name]; !exists {
                        canSolveOther = false
                        break
                    }
                }
            }
            if canSolveOther {
                ready = append(ready, otherVar)
            }
        }
    }
    
    // Check if all variables are solved
    for variable := range deps {
        if _, exists := solution[variable]; !exists {
            return nil // Unsolvable
        }
    }
    
    // Verify solution
    if !verifySolution(lines, solution) {
        return nil
    }
    
    return solution
}

type Term struct {
    Name        string
    Coefficient int
}

func isVariable(term string) bool {
    return len(term) > 0 && ((term[0] >= 'a' && term[0] <= 'z') || (term[0] >= 'A' && term[0] <= 'Z'))
}

func parseEquation(line string, deps map[string][]Term, constants map[string]int) bool {
    // Remove spaces
    line = strings.ReplaceAll(line, " ", "")
    
    parts := strings.Split(line, "=")
    if len(parts) != 2 {
        return false
    }
    
    left := parts[0]
    right := parts[1]
    
    // Parse right side
    terms := make([]Term, 0)
    constantSum := 0
    
    // Simple parsing for terms separated by + or -
    pos := 0
    sign := 1
    
    for pos < len(right) {
        if pos < len(right) && right[pos] == '+' {
            sign = 1
            pos++
        } else if pos < len(right) && right[pos] == '-' {
            sign = -1
            pos++
        }
        
        // Find next operator or end
        nextOp := pos
        for nextOp < len(right) && right[nextOp] != '+' && right[nextOp] != '-' {
            nextOp++
        }
        
        if nextOp > pos {
            term := right[pos:nextOp]
            if isVariable(term) {
                terms = append(terms, Term{Name: term, Coefficient: sign})
            } else {
                if value, err := strconv.Atoi(term); err == nil {
                    constantSum += sign * value
                }
            }
        }
        
        pos = nextOp
    }
    
    deps[left] = terms
    constants[left] = constantSum
    return true
}

func verifySolution(lines []string, solution map[string]int) bool {
    for _, line := range lines {
        line = strings.ReplaceAll(line, " ", "")
        parts := strings.Split(line, "=")
        if len(parts) != 2 {
            continue
        }
        
        left := parts[0]
        right := parts[1]
        
        leftVal := 0
        if isVariable(left) {
            if val, exists := solution[left]; exists {
                leftVal = val
            } else {
                return false
            }
        } else {
            if val, err := strconv.Atoi(left); err == nil {
                leftVal = val
            }
        }
        
        rightVal := evaluateExpression(right, solution)
        if leftVal != rightVal {
            return false
        }
    }
    return true
}

func evaluateExpression(expr string, solution map[string]int) int {
    result := 0
    sign := 1
    pos := 0
    
    for pos < len(expr) {
        if pos < len(expr) && expr[pos] == '+' {
            sign = 1
            pos++
        } else if pos < len(expr) && expr[pos] == '-' {
            sign = -1
            pos++
        }
        
        nextOp := pos
        for nextOp < len(expr) && expr[nextOp] != '+' && expr[nextOp] != '-' {
            nextOp++
        }
        
        if nextOp > pos {
            term := expr[pos:nextOp]
            if isVariable(term) {
                if val, exists := solution[term]; exists {
                    result += sign * val
                }
            } else {
                if val, err := strconv.Atoi(term); err == nil {
                    result += sign * val
                }
            }
        }
        
        pos = nextOp
    }
    
    return result
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

class Solution {
    public Map<String, Integer> solveEquations(String equations) {
        String[] lines = equations.split("\n");
        Map<String, List<Term>> deps = new HashMap<>();
        Map<String, Integer> constants = new HashMap<>();
        Map<String, Integer> solution = new HashMap<>();
        
        // Parse equations
        for (String line : lines) {
            if (!parseEquation(line, deps, constants)) {
                return null;
            }
        }
        
        // Find variables that can be solved directly
        Queue<String> ready = new LinkedList<>();
        for (Map.Entry<String, List<Term>> entry : deps.entrySet()) {
            String var = entry.getKey();
            List<Term> terms = entry.getValue();
            
            boolean hasOnlyConstants = true;
            for (Term term : terms) {
                if (isVariable(term.name)) {
                    hasOnlyConstants = false;
                    break;
                }
            }
            if (hasOnlyConstants) {
                ready.offer(var);
            }
        }
        
        // Solve using topological sort approach
        while (!ready.isEmpty()) {
            String var = ready.poll();
            
            if (solution.containsKey(var)) continue;
            
            // Calculate value for this variable
            int value = constants.getOrDefault(var, 0);
            boolean canSolve = true;
            
            for (Term term : deps.get(var)) {
                if (isVariable(term.name)) {
                    if (solution.containsKey(term.name)) {
                        value += solution.get(term.name) * term.coefficient;
                    } else {
                        canSolve = false;
                        break;
                    }
                } else {
                    try {
                        value += Integer.parseInt(term.name) * term.coefficient;
                    } catch (NumberFormatException e) {
                        return null;
                    }
                }
            }
            
            if (!canSolve) continue;
            
            solution.put(var, value);
            
            // Check for newly solvable variables
            for (Map.Entry<String, List<Term>> entry : deps.entrySet()) {
                String otherVar = entry.getKey();
                List<Term> terms = entry.getValue();
                
                if (solution.containsKey(otherVar)) continue;
                
                boolean canSolveOther = true;
                for (Term term : terms) {
                    if (isVariable(term.name) && !solution.containsKey(term.name)) {
                        canSolveOther = false;
                        break;
                    }
                }
                if (canSolveOther) {
                    ready.offer(otherVar);
                }
            }
        }
        
        // Check if all variables are solved
        for (String var : deps.keySet()) {
            if (!solution.containsKey(var)) {
                return null; // Unsolvable
            }
        }
        
        // Verify solution
        if (!verifySolution(lines, solution)) {
            return null;
        }
        
        return solution;
    }
    
    private static class Term {
        String name;
        int coefficient;
        
        Term(String name, int coefficient) {
            this.name = name;
            this.coefficient = coefficient;
        }
    }
    
    private boolean isVariable(String term) {
        return !term.isEmpty() && Character.isLetter(term.charAt(0));
    }
    
    private boolean parseEquation(String line, Map<String, List<Term>> deps, 
                                 Map<String, Integer> constants) {
        line = line.replaceAll("\\s+", "");
        
        String[] parts = line.split("=");
        if (parts.length != 2) return false;
        
        String left = parts[0];
        String right = parts[1];
        
        List<Term> terms = new ArrayList<>();
        int constantSum = 0;
        
        // Parse right side
        int pos = 0;
        int sign = 1;
        
        while (pos < right.length()) {
            if (pos < right.length() && right.charAt(pos) == '+') {
                sign = 1;
                pos++;
            } else if (pos < right.length() && right.charAt(pos) == '-') {
                sign = -1;
                pos++;
            }
            
            int nextOp = pos;
            while (nextOp < right.length() && 
                   right.charAt(nextOp) != '+' && right.charAt(nextOp) != '-') {
                nextOp++;
            }
            
            if (nextOp > pos) {
                String term = right.substring(pos, nextOp);
                if (isVariable(term)) {
                    terms.add(new Term(term, sign));
                } else {
                    try {
                        constantSum += sign * Integer.parseInt(term);
                    } catch (NumberFormatException e) {
                        return false;
                    }
                }
            }
            
            pos = nextOp;
        }
        
        deps.put(left, terms);
        constants.put(left, constantSum);
        return true;
    }
    
    private boolean verifySolution(String[] lines, Map<String, Integer> solution) {
        for (String line : lines) {
            line = line.replaceAll("\\s+", "");
            String[] parts = line.split("=");
            if (parts.length != 2) continue;
            
            String left = parts[0];
            String right = parts[1];
            
            int leftVal = 0;
            if (isVariable(left)) {
                if (!solution.containsKey(left)) return false;
                leftVal = solution.get(left);
            } else {
                try {
                    leftVal = Integer.parseInt(left);
                } catch (NumberFormatException e) {
                    return false;
                }
            }
            
            int rightVal = evaluateExpression(right, solution);
            if (leftVal != rightVal) return false;
        }
        return true;
    }
    
    private int evaluateExpression(String expr, Map<String, Integer> solution) {
        int result = 0;
        int sign = 1;
        int pos = 0;
        
        while (pos < expr.length()) {
            if (pos < expr.length() && expr.charAt(pos) == '+') {
                sign = 1;
                pos++;
            } else if (pos < expr.length() && expr.charAt(pos) == '-') {
                sign = -1;
                pos++;
            }
            
            int nextOp = pos;
            while (nextOp < expr.length() && 
                   expr.charAt(nextOp) != '+' && expr.charAt(nextOp) != '-') {
                nextOp++;
            }
            
            if (nextOp > pos) {
                String term = expr.substring(pos, nextOp);
                if (isVariable(term)) {
                    if (solution.containsKey(term)) {
                        result += sign * solution.get(term);
                    }
                } else {
                    try {
                        result += sign * Integer.parseInt(term);
                    } catch (NumberFormatException e) {
                        // Skip invalid terms
                    }
                }
            }
            
            pos = nextOp;
        }
        
        return result;
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

class Solution:
    def solveEquations(self, equations: str) -> Optional[Dict[str, int]]:
        lines = equations.strip().split('\n')
        deps: Dict[str, List[Tuple[str, int]]] = {}
        constants: Dict[str, int] = {}
        solution: Dict[str, int] = {}
        
        # Parse equations
        for line in lines:
            if not self._parseEquation(line, deps, constants):
                return None
        
        # Find variables that can be solved directly
        ready: List[str] = []
        for var, terms in deps.items():
            hasOnlyConstants = True
            for term, coeff in terms:
                if self._isVariable(term):
                    hasOnlyConstants = False
                    break
            if hasOnlyConstants:
                ready.append(var)
        
        # Solve using topological sort approach
        while ready:
            var = ready.pop(0)
            
            if var in solution:
                continue
            
            # Calculate value for this variable
            value = constants.get(var, 0)
            canSolve = True
            
            for term, coeff in deps[var]:
                if self._isVariable(term):
                    if term in solution:
                        value += solution[term] * coeff
                    else:
                        canSolve = False
                        break
                else:
                    try:
                        value += int(term) * coeff
                    except ValueError:
                        return None
            
            if not canSolve:
                continue
            
            solution[var] = value
            
            # Check for newly solvable variables
            for otherVar, terms in deps.items():
                if otherVar in solution:
                    continue
                
                canSolveOther = True
                for term, coeff in terms:
                    if self._isVariable(term) and term not in solution:
                        canSolveOther = False
                        break
                
                if canSolveOther and otherVar not in ready:
                    ready.append(otherVar)
        
        # Check if all variables are solved
        for var in deps:
            if var not in solution:
                return None  # Unsolvable
        
        # Verify solution
        if not self._verifySolution(lines, solution):
            return None
        
        return solution
    
    def _isVariable(self, term: str) -> bool:
        return len(term) > 0 and term[0].isalpha()
    
    def _parseEquation(self, line: str, deps: Dict[str, List[Tuple[str, int]]], 
                      constants: Dict[str, int]) -> bool:
        # Remove spaces
        line = line.replace(' ', '')
        
        if '=' not in line:
            return False
        
        left, right = line.split('=', 1)
        
        # Parse right side
        terms: List[Tuple[str, int]] = []
        constantSum = 0
        
        # Simple parsing for terms separated by + or -
        pos = 0
        sign = 1
        
        while pos < len(right):
            if pos < len(right) and right[pos] == '+':
                sign = 1
                pos += 1
            elif pos < len(right) and right[pos] == '-':
                sign = -1
                pos += 1
            
            # Find next operator or end
            nextOp = pos
            while nextOp < len(right) and right[nextOp] not in '+-':
                nextOp += 1
            
            if nextOp > pos:
                term = right[pos:nextOp]
                if self._isVariable(term):
                    terms.append((term, sign))
                else:
                    try:
                        constantSum += sign * int(term)
                    except ValueError:
                        return False
            
            pos = nextOp
        
        deps[left] = terms
        constants[left] = constantSum
        return True
    
    def _verifySolution(self, lines: List[str], solution: Dict[str, int]) -> bool:
        for line in lines:
            line = line.replace(' ', '')
            if '=' not in line:
                continue
            
            left, right = line.split('=', 1)
            
            # Evaluate left side
            if self._isVariable(left):
                if left not in solution:
                    return False
                leftVal = solution[left]
            else:
                try:
                    leftVal = int(left)
                except ValueError:
                    return False
            
            # Evaluate right side
            rightVal = self._evaluateExpression(right, solution)
            
            if leftVal != rightVal:
                return False
        
        return True
    
    def _evaluateExpression(self, expr: str, solution: Dict[str, int]) -> int:
        result = 0
        sign = 1
        pos = 0
        
        while pos < len(expr):
            if pos < len(expr) and expr[pos] == '+':
                sign = 1
                pos += 1
            elif pos < len(expr) and expr[pos] == '-':
                sign = -1
                pos += 1
            
            nextOp = pos
            while nextOp < len(expr) and expr[nextOp] not in '+-':
                nextOp += 1
            
            if nextOp > pos:
                term = expr[pos:nextOp]
                if self._isVariable(term):
                    if term in solution:
                        result += sign * solution[term]
                else:
                    try:
                        result += sign * int(term)
                    except ValueError:
                        pass  # Skip invalid terms
            
            pos = nextOp
        
        return result

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

class Solution {
public:
    map<string, int> solveEquationsMatrix(string equations) {
        vector<string> lines = split(equations, '\n');
        set<string> variables;
        
        // First pass: collect all variables
        for (const string& line : lines) {
            collectVariables(line, variables);
        }
        
        vector<string> varList(variables.begin(), variables.end());
        map<string, int> varIndex;
        for (int i = 0; i < varList.size(); i++) {
            varIndex[varList[i]] = i;
        }
        
        int n = varList.size();
        int m = lines.size();
        
        // Create augmented matrix [A|b]
        vector<vector<double>> matrix(m, vector<double>(n + 1, 0));
        
        for (int i = 0; i < m; i++) {
            if (!parseEquationToMatrix(lines[i], matrix[i], varIndex)) {
                return {};
            }
        }
        
        // Gaussian elimination
        int rank = gaussianElimination(matrix, n);
        
        // Check for inconsistency
        for (int i = rank; i < m; i++) {
            if (abs(matrix[i][n]) > 1e-9) {
                return {}; // Inconsistent system
            }
        }
        
        // Check if system is underdetermined
        if (rank < n) {
            return {}; // Infinite solutions or underdetermined
        }
        
        // Back substitution
        vector<double> solution(n);
        for (int i = n - 1; i >= 0; i--) {
            solution[i] = matrix[i][n];
            for (int j = i + 1; j < n; j++) {
                solution[i] -= matrix[i][j] * solution[j];
            }
            solution[i] /= matrix[i][i];
        }
        
        // Convert to integer solution and verify
        map<string, int> result;
        for (int i = 0; i < n; i++) {
            double val = solution[i];
            if (abs(val - round(val)) > 1e-9) {
                return {}; // Non-integer solution
            }
            result[varList[i]] = (int)round(val);
        }
        
        // Verify solution
        if (!verifySolution(lines, result)) {
            return {};
        }
        
        return result;
    }
    
private:
    vector<string> split(string str, char delim) {
        vector<string> result;
        stringstream ss(str);
        string item;
        while (getline(ss, item, delim)) {
            result.push_back(item);
        }
        return result;
    }
    
    void collectVariables(const string& line, set<string>& variables) {
        string cleaned = line;
        cleaned.erase(remove(cleaned.begin(), cleaned.end(), ' '), cleaned.end());
        
        for (int i = 0; i < cleaned.length(); i++) {
            if (isalpha(cleaned[i])) {
                string var = "";
                while (i < cleaned.length() && isalnum(cleaned[i])) {
                    var += cleaned[i++];
                }
                i--; // Adjust for loop increment
                variables.insert(var);
            }
        }
    }
    
    bool parseEquationToMatrix(const string& line, vector<double>& row, 
                              const map<string, int>& varIndex) {
        string cleaned = line;
        cleaned.erase(remove(cleaned.begin(), cleaned.end(), ' '), cleaned.end());
        
        size_t eqPos = cleaned.find('=');
        if (eqPos == string::npos) return false;
        
        string left = cleaned.substr(0, eqPos);
        string right = cleaned.substr(eqPos + 1);
        
        // Parse left side (should be single variable or constant)
        if (isVariable(left)) {
            row[varIndex.at(left)] = 1;
        } else {
            row[row.size() - 1] = stoi(left);
        }
        
        // Parse right side and subtract from left
        parseExpressionToMatrix(right, row, varIndex, -1);
        
        return true;
    }
    
    void parseExpressionToMatrix(const string& expr, vector<double>& row,
                                const map<string, int>& varIndex, int multiplier) {
        int sign = multiplier;
        size_t pos = 0;
        
        while (pos < expr.length()) {
            if (pos < expr.length() && expr[pos] == '+') {
                sign = multiplier;
                pos++;
            } else if (pos < expr.length() && expr[pos] == '-') {
                sign = -multiplier;
                pos++;
            }
            
            size_t nextOp = expr.find_first_of("+-", pos);
            if (nextOp == string::npos) nextOp = expr.length();
            
            string term = expr.substr(pos, nextOp - pos);
            if (isVariable(term)) {
                row[varIndex.at(term)] += sign;
            } else {
                row[row.size() - 1] += sign * stoi(term);
            }
            
            pos = nextOp;
        }
    }
    
    bool isVariable(const string& term) {
        return !term.empty() && isalpha(term[0]);
    }
    
    int gaussianElimination(vector<vector<double>>& matrix, int n) {
        int rank = 0;
        
        for (int col = 0; col < n && rank < matrix.size(); col++) {
            // Find pivot
            int pivot = -1;
            for (int row = rank; row < matrix.size(); row++) {
                if (abs(matrix[row][col]) > 1e-9) {
                    pivot = row;
                    break;
                }
            }
            
            if (pivot == -1) continue; // No pivot in this column
            
            // Swap rows
            if (pivot != rank) {
                swap(matrix[rank], matrix[pivot]);
            }
            
            // Eliminate
            for (int row = 0; row < matrix.size(); row++) {
                if (row != rank && abs(matrix[row][col]) > 1e-9) {
                    double factor = matrix[row][col] / matrix[rank][col];
                    for (int j = 0; j <= n; j++) {
                        matrix[row][j] -= factor * matrix[rank][j];
                    }
                }
            }
            
            rank++;
        }
        
        return rank;
    }
    
    bool verifySolution(const vector<string>& lines, const map<string, int>& solution) {
        // Implementation similar to Method 1
        return true; // Simplified for brevity
    }
};

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

func SolveEquationsMatrix(equations string) map[string]int {
    lines := strings.Split(equations, "\n")
    variables := make(map[string]bool)
    
    // Collect all variables
    for _, line := range lines {
        collectVariables(line, variables)
    }
    
    varList := make([]string, 0, len(variables))
    for variable := range variables {
        varList = append(varList, variable)
    }
    sort.Strings(varList) // For consistent ordering
    
    varIndex := make(map[string]int)
    for i, variable := range varList {
        varIndex[variable] = i
    }
    
    n := len(varList)
    m := len(lines)
    
    // Create augmented matrix
    matrix := make([][]float64, m)
    for i := range matrix {
        matrix[i] = make([]float64, n+1)
    }
    
    for i, line := range lines {
        if !parseEquationToMatrix(line, matrix[i], varIndex) {
            return nil
        }
    }
    
    // Gaussian elimination
    rank := gaussianElimination(matrix, n)
    
    // Check for inconsistency
    for i := rank; i < m; i++ {
        if math.Abs(matrix[i][n]) > 1e-9 {
            return nil // Inconsistent
        }
    }
    
    if rank < n {
        return nil // Underdetermined
    }
    
    // Back substitution
    solution := make([]float64, n)
    for i := n - 1; i >= 0; i-- {
        solution[i] = matrix[i][n]
        for j := i + 1; j < n; j++ {
            solution[i] -= matrix[i][j] * solution[j]
        }
        solution[i] /= matrix[i][i]
    }
    
    // Convert to integer solution
    result := make(map[string]int)
    for i, variable := range varList {
        val := solution[i]
        if math.Abs(val-math.Round(val)) > 1e-9 {
            return nil // Non-integer solution
        }
        result[variable] = int(math.Round(val))
    }
    
    return result
}

func collectVariables(line string, variables map[string]bool) {
    cleaned := strings.ReplaceAll(line, " ", "")
    
    for i := 0; i < len(cleaned); i++ {
        if (cleaned[i] >= 'a' && cleaned[i] <= 'z') || (cleaned[i] >= 'A' && cleaned[i] <= 'Z') {
            variable := ""
            for i < len(cleaned) && ((cleaned[i] >= 'a' && cleaned[i] <= 'z') || 
                                    (cleaned[i] >= 'A' && cleaned[i] <= 'Z') ||
                                    (cleaned[i] >= '0' && cleaned[i] <= '9')) {
                variable += string(cleaned[i])
                i++
            }
            i-- // Adjust for loop increment
            variables[variable] = true
        }
    }
}

func parseEquationToMatrix(line string, row []float64, varIndex map[string]int) bool {
    cleaned := strings.ReplaceAll(line, " ", "")
    
    parts := strings.Split(cleaned, "=")
    if len(parts) != 2 {
        return false
    }
    
    left := parts[0]
    right := parts[1]
    
    // Parse left side
    if isVariableGo(left) {
        row[varIndex[left]] = 1
    } else {
        if val, err := strconv.ParseFloat(left, 64); err == nil {
            row[len(row)-1] = val
        }
    }
    
    // Parse right side and subtract
    parseExpressionToMatrix(right, row, varIndex, -1)
    
    return true
}

func parseExpressionToMatrix(expr string, row []float64, varIndex map[string]int, multiplier float64) {
    sign := multiplier
    pos := 0
    
    for pos < len(expr) {
        if pos < len(expr) && expr[pos] == '+' {
            sign = multiplier
            pos++
        } else if pos < len(expr) && expr[pos] == '-' {
            sign = -multiplier
            pos++
        }
        
        nextOp := pos
        for nextOp < len(expr) && expr[nextOp] != '+' && expr[nextOp] != '-' {
            nextOp++
        }
        
        if nextOp > pos {
            term := expr[pos:nextOp]
            if isVariableGo(term) {
                row[varIndex[term]] += sign
            } else {
                if val, err := strconv.ParseFloat(term, 64); err == nil {
                    row[len(row)-1] += sign * val
                }
            }
        }
        
        pos = nextOp
    }
}

func isVariableGo(term string) bool {
    return len(term) > 0 && ((term[0] >= 'a' && term[0] <= 'z') || (term[0] >= 'A' && term[0] <= 'Z'))
}

func gaussianElimination(matrix [][]float64, n int) int {
    rank := 0
    
    for col := 0; col < n && rank < len(matrix); col++ {
        // Find pivot
        pivot := -1
        for row := rank; row < len(matrix); row++ {
            if math.Abs(matrix[row][col]) > 1e-9 {
                pivot = row
                break
            }
        }
        
        if pivot == -1 {
            continue
        }
        
        // Swap rows
        if pivot != rank {
            matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
        }
        
        // Eliminate
        for row := 0; row < len(matrix); row++ {
            if row != rank && math.Abs(matrix[row][col]) > 1e-9 {
                factor := matrix[row][col] / matrix[rank][col]
                for j := 0; j <= n; j++ {
                    matrix[row][j] -= factor * matrix[rank][j]
                }
            }
        }
        
        rank++
    }
    
    return rank
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

class Solution {
    public Map<String, Integer> solveEquationsMatrix(String equations) {
        String[] lines = equations.split("\n");
        Set<String> variables = new HashSet<>();
        
        // Collect all variables
        for (String line : lines) {
            collectVariables(line, variables);
        }
        
        List<String> varList = new ArrayList<>(variables);
        Collections.sort(varList); // For consistent ordering
        
        Map<String, Integer> varIndex = new HashMap<>();
        for (int i = 0; i < varList.size(); i++) {
            varIndex.put(varList.get(i), i);
        }
        
        int n = varList.size();
        int m = lines.length;
        
        // Create augmented matrix
        double[][] matrix = new double[m][n + 1];
        
        for (int i = 0; i < m; i++) {
            if (!parseEquationToMatrix(lines[i], matrix[i], varIndex)) {
                return null;
            }
        }
        
        // Gaussian elimination
        int rank = gaussianElimination(matrix, n);
        
        // Check for inconsistency
        for (int i = rank; i < m; i++) {
            if (Math.abs(matrix[i][n]) > 1e-9) {
                return null; // Inconsistent
            }
        }
        
        if (rank < n) {
            return null; // Underdetermined
        }
        
        // Back substitution
        double[] solution = new double[n];
        for (int i = n - 1; i >= 0; i--) {
            solution[i] = matrix[i][n];
            for (int j = i + 1; j < n; j++) {
                solution[i] -= matrix[i][j] * solution[j];
            }
            solution[i] /= matrix[i][i];
        }
        
        // Convert to integer solution
        Map<String, Integer> result = new HashMap<>();
        for (int i = 0; i < n; i++) {
            double val = solution[i];
            if (Math.abs(val - Math.round(val)) > 1e-9) {
                return null; // Non-integer solution
            }
            result.put(varList.get(i), (int) Math.round(val));
        }
        
        return result;
    }
    
    private void collectVariables(String line, Set<String> variables) {
        line = line.replaceAll("\\s+", "");
        
        for (int i = 0; i < line.length(); i++) {
            if (Character.isLetter(line.charAt(i))) {
                StringBuilder var = new StringBuilder();
                while (i < line.length() && Character.isLetterOrDigit(line.charAt(i))) {
                    var.append(line.charAt(i++));
                }
                i--; // Adjust for loop increment
                variables.add(var.toString());
            }
        }
    }
    
    private boolean parseEquationToMatrix(String line, double[] row, Map<String, Integer> varIndex) {
        line = line.replaceAll("\\s+", "");
        
        String[] parts = line.split("=");
        if (parts.length != 2) return false;
        
        String left = parts[0];
        String right = parts[1];
        
        // Parse left side
        if (isVariableMatrix(left)) {
            row[varIndex.get(left)] = 1;
        } else {
            try {
                row[row.length - 1] = Double.parseDouble(left);
            } catch (NumberFormatException e) {
                return false;
            }
        }
        
        // Parse right side and subtract
        parseExpressionToMatrix(right, row, varIndex, -1);
        
        return true;
    }
    
    private void parseExpressionToMatrix(String expr, double[] row, 
                                       Map<String, Integer> varIndex, double multiplier) {
        double sign = multiplier;
        int pos = 0;
        
        while (pos < expr.length()) {
            if (pos < expr.length() && expr.charAt(pos) == '+') {
                sign = multiplier;
                pos++;
            } else if (pos < expr.length() && expr.charAt(pos) == '-') {
                sign = -multiplier;
                pos++;
            }
            
            int nextOp = pos;
            while (nextOp < expr.length() && 
                   expr.charAt(nextOp) != '+' && expr.charAt(nextOp) != '-') {
                nextOp++;
            }
            
            if (nextOp > pos) {
                String term = expr.substring(pos, nextOp);
                if (isVariableMatrix(term)) {
                    row[varIndex.get(term)] += sign;
                } else {
                    try {
                        row[row.length - 1] += sign * Double.parseDouble(term);
                    } catch (NumberFormatException e) {
                        // Skip invalid terms
                    }
                }
            }
            
            pos = nextOp;
        }
    }
    
    private boolean isVariableMatrix(String term) {
        return !term.isEmpty() && Character.isLetter(term.charAt(0));
    }
    
    private int gaussianElimination(double[][] matrix, int n) {
        int rank = 0;
        
        for (int col = 0; col < n && rank < matrix.length; col++) {
            // Find pivot
            int pivot = -1;
            for (int row = rank; row < matrix.length; row++) {
                if (Math.abs(matrix[row][col]) > 1e-9) {
                    pivot = row;
                    break;
                }
            }
            
            if (pivot == -1) continue;
            
            // Swap rows
            if (pivot != rank) {
                double[] temp = matrix[rank];
                matrix[rank] = matrix[pivot];
                matrix[pivot] = temp;
            }
            
            // Eliminate
            for (int row = 0; row < matrix.length; row++) {
                if (row != rank && Math.abs(matrix[row][col]) > 1e-9) {
                    double factor = matrix[row][col] / matrix[rank][col];
                    for (int j = 0; j <= n; j++) {
                        matrix[row][j] -= factor * matrix[rank][j];
                    }
                }
            }
            
            rank++;
        }
        
        return rank;
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

class Solution:
    def solveEquationsMatrix(self, equations: str) -> Optional[Dict[str, int]]:
        lines = equations.strip().split('\n')
        variables: Set[str] = set()
        
        # Collect all variables
        for line in lines:
            self._collectVariables(line, variables)
        
        varList = sorted(list(variables))  # For consistent ordering
        varIndex = {var: i for i, var in enumerate(varList)}
        
        n = len(varList)
        m = len(lines)
        
        # Create augmented matrix
        matrix: List[List[float]] = [[0.0] * (n + 1) for _ in range(m)]
        
        for i, line in enumerate(lines):
            if not self._parseEquationToMatrix(line, matrix[i], varIndex):
                return None
        
        # Gaussian elimination
        rank = self._gaussianElimination(matrix, n)
        
        # Check for inconsistency
        for i in range(rank, m):
            if abs(matrix[i][n]) > 1e-9:
                return None  # Inconsistent
        
        if rank < n:
            return None  # Underdetermined
        
        # Back substitution
        solution: List[float] = [0.0] * n
        for i in range(n - 1, -1, -1):
            solution[i] = matrix[i][n]
            for j in range(i + 1, n):
                solution[i] -= matrix[i][j] * solution[j]
            solution[i] /= matrix[i][i]
        
        # Convert to integer solution
        result: Dict[str, int] = {}
        for i, variable in enumerate(varList):
            val = solution[i]
            if abs(val - round(val)) > 1e-9:
                return None  # Non-integer solution
            result[variable] = int(round(val))
        
        return result
    
    def _collectVariables(self, line: str, variables: Set[str]) -> None:
        cleaned = line.replace(' ', '')
        
        i = 0
        while i < len(cleaned):
            if cleaned[i].isalpha():
                variable = ""
                while i < len(cleaned) and cleaned[i].isalnum():
                    variable += cleaned[i]
                    i += 1
                variables.add(variable)
            else:
                i += 1
    
    def _parseEquationToMatrix(self, line: str, row: List[float], 
                              varIndex: Dict[str, int]) -> bool:
        cleaned = line.replace(' ', '')
        
        if '=' not in cleaned:
            return False
        
        left, right = cleaned.split('=', 1)
        
        # Parse left side
        if self._isVariableMatrix(left):
            row[varIndex[left]] = 1
        else:
            try:
                row[len(row) - 1] = float(left)
            except ValueError:
                return False
        
        # Parse right side and subtract
        self._parseExpressionToMatrix(right, row, varIndex, -1)
        
        return True
    
    def _parseExpressionToMatrix(self, expr: str, row: List[float],
                                varIndex: Dict[str, int], multiplier: float) -> None:
        sign = multiplier
        pos = 0
        
        while pos < len(expr):
            if pos < len(expr) and expr[pos] == '+':
                sign = multiplier
                pos += 1
            elif pos < len(expr) and expr[pos] == '-':
                sign = -multiplier
                pos += 1
            
            nextOp = pos
            while nextOp < len(expr) and expr[nextOp] not in '+-':
                nextOp += 1
            
            if nextOp > pos:
                term = expr[pos:nextOp]
                if self._isVariableMatrix(term):
                    row[varIndex[term]] += sign
                else:
                    try:
                        row[len(row) - 1] += sign * float(term)
                    except ValueError:
                        pass  # Skip invalid terms
            
            pos = nextOp
    
    def _isVariableMatrix(self, term: str) -> bool:
        return len(term) > 0 and term[0].isalpha()
    
    def _gaussianElimination(self, matrix: List[List[float]], n: int) -> int:
        rank = 0
        
        for col in range(n):
            if rank >= len(matrix):
                break
                
            # Find pivot
            pivot = -1
            for row in range(rank, len(matrix)):
                if abs(matrix[row][col]) > 1e-9:
                    pivot = row
                    break
            
            if pivot == -1:
                continue
            
            # Swap rows
            if pivot != rank:
                matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
            
            # Eliminate
            for row in range(len(matrix)):
                if row != rank and abs(matrix[row][col]) > 1e-9:
                    factor = matrix[row][col] / matrix[rank][col]
                    for j in range(n + 1):
                        matrix[row][j] -= factor * matrix[rank][j]
            
            rank += 1
        
        return rank