orchard

  1package skills
  2
  3import (
  4	"context"
  5	"fmt"
  6	"math"
  7	"strconv"
  8	"strings"
  9	"time"
 10	"unicode"
 11)
 12
 13// A question like "30*27" should not spend fifteen seconds fetching web pages
 14// to be told what a calculator knows. This is a small recursive descent parser
 15// over the arithmetic a person types into a search box.
 16//
 17// It is deliberately narrow. Anything it does not fully understand it declines,
 18// and the question goes to the web instead, because a calculator that guesses
 19// is worse than no calculator.
 20
 21// Calculation is an arithmetic question answered without leaving the process.
 22type Calculation struct {
 23	Expression string
 24	Result     float64
 25	Pretty     string
 26}
 27
 28// TryCalculate answers a question if, and only if, the whole of it is
 29// arithmetic. The check is strict: "what is 5% of 20" parses, "how much is a
 30// 5% mortgage on 200k" does not, and should not.
 31func TryCalculate(question string) (*Calculation, bool) {
 32	expr := normalizeExpression(question)
 33	if expr == "" {
 34		return nil, false
 35	}
 36	p := &parser{src: []rune(expr)}
 37	v, err := p.parseExpr()
 38	if err != nil {
 39		return nil, false
 40	}
 41	p.skipSpace()
 42	if p.pos != len(p.src) {
 43		return nil, false
 44	}
 45	// A bare number is not a question, and an overflow is not an answer.
 46	if !p.sawOperator || math.IsNaN(v) || math.IsInf(v, 0) {
 47		return nil, false
 48	}
 49	return &Calculation{Expression: expr, Result: v, Pretty: formatNumber(v)}, true
 50}
 51
 52// normalizeExpression strips the words a person wraps an expression in and
 53// rewrites the symbols they type for the ones the parser reads. It returns ""
 54// when anything is left that is not arithmetic, which is what keeps a real
 55// question from being answered by the calculator.
 56func normalizeExpression(q string) string {
 57	s := strings.ToLower(strings.TrimSpace(q))
 58	s = strings.TrimSuffix(s, "?")
 59	s = strings.TrimSuffix(s, "=")
 60
 61	for _, prefix := range []string{
 62		"what is", "whats", "what's", "calculate", "compute", "how much is",
 63		"how many is", "solve", "evaluate", "work out", "what does",
 64	} {
 65		if strings.HasPrefix(s, prefix) {
 66			s = s[len(prefix):]
 67			break
 68		}
 69	}
 70	s = strings.TrimSpace(strings.TrimSuffix(strings.TrimSpace(s), "equal"))
 71	s = strings.TrimSpace(strings.TrimSuffix(strings.TrimSpace(s), "equals"))
 72
 73	// Words people type for operators.
 74	for from, to := range map[string]string{
 75		" plus ": "+", " minus ": "-", " times ": "*",
 76		" multiplied by ": "*", " divided by ": "/", " over ": "/",
 77		" to the power of ": "^", " mod ": "%", " modulo ": "%",
 78		"×": "*", "÷": "/", "−": "-", "•": "*",
 79	} {
 80		s = strings.ReplaceAll(s, from, to)
 81	}
 82	// "5% of 20" is the one percent form worth supporting, and it has to be
 83	// rewritten before % becomes a modulo operator.
 84	s = strings.ReplaceAll(s, "% of ", "%*")
 85	s = strings.ReplaceAll(s, " of ", "*")
 86
 87	// Thousands separators, but only between digits, so 1,234 works and a list
 88	// does not silently become a number.
 89	var b strings.Builder
 90	for i, r := range s {
 91		if r == ',' && i > 0 && i+1 < len(s) &&
 92			unicode.IsDigit(rune(s[i-1])) && unicode.IsDigit(rune(s[i+1])) {
 93			continue
 94		}
 95		b.WriteRune(r)
 96	}
 97	s = b.String()
 98
 99	// Anything left that is not arithmetic disqualifies the whole question.
100	for _, r := range s {
101		if unicode.IsDigit(r) || unicode.IsSpace(r) {
102			continue
103		}
104		if strings.ContainsRune("+-*/^%().", r) {
105			continue
106		}
107		return ""
108	}
109	return strings.TrimSpace(s)
110}
111
112type parser struct {
113	src         []rune
114	pos         int
115	sawOperator bool
116}
117
118func (p *parser) skipSpace() {
119	for p.pos < len(p.src) && unicode.IsSpace(p.src[p.pos]) {
120		p.pos++
121	}
122}
123
124func (p *parser) peek() rune {
125	p.skipSpace()
126	if p.pos >= len(p.src) {
127		return 0
128	}
129	return p.src[p.pos]
130}
131
132// parseExpr handles + and -, the loosest binding.
133func (p *parser) parseExpr() (float64, error) {
134	v, err := p.parseTerm()
135	if err != nil {
136		return 0, err
137	}
138	for {
139		switch p.peek() {
140		case '+':
141			p.pos++
142			p.sawOperator = true
143			r, err := p.parseTerm()
144			if err != nil {
145				return 0, err
146			}
147			v += r
148		case '-':
149			p.pos++
150			p.sawOperator = true
151			r, err := p.parseTerm()
152			if err != nil {
153				return 0, err
154			}
155			v -= r
156		default:
157			return v, nil
158		}
159	}
160}
161
162// parseTerm handles *, / and %.
163func (p *parser) parseTerm() (float64, error) {
164	v, err := p.parsePower()
165	if err != nil {
166		return 0, err
167	}
168	for {
169		switch p.peek() {
170		case '*':
171			p.pos++
172			p.sawOperator = true
173			r, err := p.parsePower()
174			if err != nil {
175				return 0, err
176			}
177			v *= r
178		case '/':
179			p.pos++
180			p.sawOperator = true
181			r, err := p.parsePower()
182			if err != nil {
183				return 0, err
184			}
185			if r == 0 {
186				return 0, fmt.Errorf("divide by zero")
187			}
188			v /= r
189		case '%':
190			p.pos++
191			p.sawOperator = true
192			r, err := p.parsePower()
193			if err != nil {
194				return 0, err
195			}
196			if r == 0 {
197				return 0, fmt.Errorf("modulo zero")
198			}
199			v = math.Mod(v, r)
200		default:
201			return v, nil
202		}
203	}
204}
205
206// parsePower handles ^, which binds tightest and is right associative.
207func (p *parser) parsePower() (float64, error) {
208	base, err := p.parseUnary()
209	if err != nil {
210		return 0, err
211	}
212	if p.peek() == '^' {
213		p.pos++
214		p.sawOperator = true
215		exp, err := p.parsePower()
216		if err != nil {
217			return 0, err
218		}
219		return math.Pow(base, exp), nil
220	}
221	return base, nil
222}
223
224func (p *parser) parseUnary() (float64, error) {
225	switch p.peek() {
226	case '-':
227		p.pos++
228		v, err := p.parseUnary()
229		return -v, err
230	case '+':
231		p.pos++
232		return p.parseUnary()
233	}
234	return p.parseAtom()
235}
236
237func (p *parser) parseAtom() (float64, error) {
238	switch p.peek() {
239	case 0:
240		return 0, fmt.Errorf("expression ends early")
241	case '(':
242		p.pos++
243		v, err := p.parseExpr()
244		if err != nil {
245			return 0, err
246		}
247		if p.peek() != ')' {
248			return 0, fmt.Errorf("unclosed bracket")
249		}
250		p.pos++
251		return v, nil
252	}
253
254	p.skipSpace()
255	start := p.pos
256	for p.pos < len(p.src) && (unicode.IsDigit(p.src[p.pos]) || p.src[p.pos] == '.') {
257		p.pos++
258	}
259	if start == p.pos {
260		return 0, fmt.Errorf("expected a number")
261	}
262	// A trailing % means percent, so 5%*20 reads as five percent of twenty.
263	v, err := strconv.ParseFloat(string(p.src[start:p.pos]), 64)
264	if err != nil {
265		return 0, err
266	}
267	if p.pos < len(p.src) && p.src[p.pos] == '%' && !p.isModulo() {
268		p.pos++
269		v /= 100
270	}
271	return v, nil
272}
273
274// isModulo tells "5 % 3" from "5%*20". Percent is only a unit when an operator
275// or the end of the expression follows it.
276func (p *parser) isModulo() bool {
277	i := p.pos + 1
278	for i < len(p.src) && unicode.IsSpace(p.src[i]) {
279		i++
280	}
281	if i >= len(p.src) {
282		return true
283	}
284	return unicode.IsDigit(p.src[i]) || p.src[i] == '(' || p.src[i] == '.'
285}
286
287// formatNumber prints a result the way a person would write it: no trailing
288// zeroes, thousands separated, and never in scientific notation for anything of
289// a size a person typed.
290func formatNumber(v float64) string {
291	if v == math.Trunc(v) && math.Abs(v) < 1e15 {
292		return group(strconv.FormatFloat(v, 'f', 0, 64))
293	}
294	s := strconv.FormatFloat(v, 'f', -1, 64)
295	if len(s) > 18 {
296		s = strconv.FormatFloat(v, 'f', 10, 64)
297		s = strings.TrimRight(strings.TrimRight(s, "0"), ".")
298	}
299	if i := strings.IndexByte(s, '.'); i >= 0 {
300		return group(s[:i]) + s[i:]
301	}
302	return group(s)
303}
304
305func group(intPart string) string {
306	neg := strings.HasPrefix(intPart, "-")
307	intPart = strings.TrimPrefix(intPart, "-")
308	if len(intPart) <= 3 {
309		if neg {
310			return "-" + intPart
311		}
312		return intPart
313	}
314	var out []byte
315	for i, c := range []byte(intPart) {
316		if i > 0 && (len(intPart)-i)%3 == 0 {
317			out = append(out, ',')
318		}
319		out = append(out, c)
320	}
321	if neg {
322		return "-" + string(out)
323	}
324	return string(out)
325}
326
327// Calculator is the skill wrapper. The parser above is the whole of it, so
328// this never touches the network and never fails slowly.
329type Calculator struct{}
330
331func (Calculator) Card() Card {
332	return Card{
333		Name: "maths",
334		Does: "evaluates an arithmetic expression the user has written out, and returns the number.",
335		Fires: []string{
336			"30 * 27",
337			"what is 15% of 240",
338			"(1200 + 450) / 3",
339			"2^10",
340			"how much is 45.99 times 3",
341		},
342		NotFor: []string{
343			"how does compound interest work",
344			"what is the average house price in london",
345			"how many calories in a banana",
346			"convert 30 celsius to fahrenheit",
347			"what is the square root of the population of france",
348		},
349		Keywords: nil, // the parser is the matcher, and it is exact
350	}
351}
352
353func (Calculator) Run(ctx context.Context, question string, d Deps) (*Result, error) {
354	start := d.now()
355	calc, ok := TryCalculate(question)
356	if !ok {
357		return nil, nil
358	}
359	return &Result{
360		Skill:   "maths",
361		Shape:   "factual",
362		Text:    fmt.Sprintf("**%s**\n\n`%s = %s`", calc.Pretty, calc.Expression, calc.Pretty),
363		Elapsed: d.now().Sub(start).Round(time.Millisecond).String(),
364	}, nil
365}