มาสร้างเลข 0–100 จากเลขปี 2567 ด้วย TypeScript กัน
ต้อนรับปี 2567 ด้วยการย้อนอดีตกันซักนิด ใครเกิดทันรายการ IQ 180 บ้างไหมครับ? ที่เอาเลขจำนวนหนึ่ง เช่น 2 5 6 7 มาคำนวณยังไงก็ได้ให้เป็นผลลัพธ์ที่ต้องการ เช่น ถ้าจะให้ผลลัพธ์เป็น 0 วิธีการคำนวณที่ทำได้ก็คือ ((5 + 7) / 6) — 2
และเมื่อมีสกิล Programming ก็อดไม่ได้ที่จะจับ 2 โลกนี้มาชนกัน
Challenge คือเราจะสามารถเขียนโปรแกรมเพื่อสร้างวิธีการคำนวณ 0–100 จากเลข 2567 ได้อย่างไร?
ได้เวลาสนุกอีกแล้วสิ เรามาทดลองแก้โจทย์นี้ด้วย TypeScript กันครับ
Step 1: Permutation
จากเซ็ตตัวเลข 2567 เราจะเขียน Function อย่างไรให้มันสามารถหมุนตัวเลขได้ เป็น 2567, 2576, 2657, … ไปเรื่อยๆ จนถึง 7652 เพราะเวลาเรานำไปคำนวณ ตัวเลขมันจะสามารถสลับตำแหน่งได้
Function โดยทั่วไปของ Typescript จะ Return ได้แค่ค่าเดียว แต่ Typescript (และ JavaScript) มี Function อีกแบบที่ไม่ค่อยได้ใช้กัน เรียกว่า Generator Function โดย Generator Function จะใช้ Keyword คำว่า Yield เพื่อ Return ค่าแต่ละตัว
ซึ่งวิธีเขียน Permute Function เราสามารถเขียนได้ตามนี้
function* permute<T>(list: T[]): Generator<T[]> {
if (list.length === 1) {
return yield list
}
for (let i = 0; i < list.length; i++) {
const item = list[i]
const nextList = list.slice(0, i).concat(list.slice(i + 1))
for (const permuted of permute(nextList)) {
yield [item, ...permuted]
}
}
}ถ้าเรา Call Permute([1, 2, 3]) เราจะได้คำตอบเป็น 123, 132, 213, 231, 312, 321
Step 2: Binary Bracketing
ถัดมาคือการใส่วงเล็บ เช่น 5762 เราสามารถแบ่งเป็น (((57)6)2), ((5(76))2), ((57)(62)), (5((76)2)), (5(7(62)))
วิธีเขียนก็สามารถใช้ Generator Function ได้เช่นเดิม เขียนได้ตามนี้
function* binaryBracketing<T>(list: T[], op: (a: T, b: T) => T): Generator<T> {
if (list.length === 1) {
return yield list[0]
}
for (let i = 1; i < list.length; i++) {
for (const left of binaryBracketing(list.slice(0, i), op)) {
for (const right of binaryBracketing(list.slice(i), op)) {
yield op(left, right)
}
}
}
}Step 3: สร้าง data type ของตัวเลข และเครื่องหมาย + - * /
ขั้นตอนนี้จะค่อนข้างซับซ้อน จึงขอแบ่งเป็นสเต็ปย่อยๆ
Step 3.1: สร้าง Expression
สำหรับตัวเลขต่างๆ และเครื่องหมายบวกลบคูณหาร หรือ + - * / เราต้องสร้าง Data Type ให้มัน เพื่อให้สามารถแสดงค่าและคำนวณได้ เราจะเรียกสิ่งนี้ว่า Expression
interface Expression {
toString(): string
valueOf(): number
rank(): number
precedence: number
}toString: เอาไว้ Output ออกมาเป็นสมการ เช่น “((5 + 7) / 6) - 2”
valueOf: เอาไว้ Output มาเป็นผลลัพธ์ เช่น 0
rank: เอาไว้จัดลำดับความสวยของสมการ เช่น เราอยากได้คำตอบที่เป็น + - * / มากกว่าใช้ Factorial
precedence: เอาไว้ตัดวงเล็บตอน toString เช่น (((5 + 7) + 6) + 2) เครื่องหมาย + เหมือนกันหมด เราสามารถลดให้เหลือแค่ 5 + 7 + 6 + 2 (ไม่ต้องมีวงเล็บ)
Step 3.2: Expression สำหรับตัวเลข
เราสามารถเขียน Expression สำหรับตัวเลขได้ดังนี้
class ConstantExpression implements Expression {
constructor(public num: number) { }
toString() {
return this.num.toString()
}
valueOf() {
return this.num
}
rank() {
return 0
}
precedence = 0
}Step 3.3: สร้าง Base Class สำหรับเครื่องหมายต่างๆ
โดยเครื่องหมายการคำนวณสามารถแบ่งได้ 2 แบบ คือ BinaryExpression เครื่องหมายที่ใช้ตัวเลข 2 ตัว เช่น (a + b) และอีกแบบคือ UnaryExpression เครื่องหมายที่ใช้ตัวเลขตัวเดียว เช่น sqrt(a)
abstract class UnaryExpression implements Expression {
constructor(protected node: Expression) {}
abstract toString(): string
abstract valueOf(): number
abstract rankValue: number
precedence= 0
rank() {
return Math.max(this.node.rank(), this.rankValue)
}
}
abstract class BinaryExpression implements Expression {
constructor(protected left: Expression, protected right: Expression) {}
abstract toString(): string
abstract valueOf(): number
abstract rankValue: number
abstract precedence: number
rank() {
return Math.max(this.left.rank(), this.right.rank(), this.rankValue)
}
protected format(node: Expression, minPrecedence: number) {
return node.precedence >= minPrecedence ? `(${node})` : node
}
}Step 3.4: สร้าง UnaryExpression แบบต่างๆ
เราจะทำ UnaryExpression 2 ตัวคือ
- Factorial เช่น 5! (5 * 4 * 3 * 2 * 1)
- Sqrt เช่น Sqrt(9)
class FactorialExpression extends UnaryExpression {
toString(): string {
return this.node.precedence >= 1 ? `(${this.node})!` : `${this.node}!`
}
private fact(n: number): number {
return n <= 1 ? 1 : n * this.fact(n - 1)
}
valueOf(): number {
const val = +this.node
return val < 0 || val >= 10 || ~~val !== val ? NaN : this.fact(val)
}
rankValue = 4
}
class SqrtExpression extends UnaryExpression {
toString(): string {
return `sqrt(${this.node})`
}
valueOf(): number {
return Math.sqrt(+this.node)
}
rankValue = 3
}Step 3.5: สร้าง BinaryExpression แบบต่างๆ
เราจะทำ BinaryExpression ทั้งหมด 6 แบบ คือ
- + - * /
- ยกกำลัง
- นำเลขมาต่อกัน เช่น 2 กับ 5 สามารถเป็นเลข 25 ได้
class AddExpression extends BinaryExpression {
toString(): string {
return `${this.left} + ${this.right}`
}
valueOf(): number {
return +this.left + +this.right
}
rankValue = 1
precedence = 3
}
class SubtractExpression extends BinaryExpression {
toString() {
return `${this.left} - ${this.format(this.right, 3)}`
}
valueOf() {
return +this.left - +this.right
}
rankValue = 1
precedence = 3
}
class MultiplyExpression extends BinaryExpression {
toString(): string {
return `${this.format(this.left, 3)} * ${this.format(this.right, 3)}`
}
valueOf(): number {
return +this.left * +this.right
}
rankValue = 1
precedence = 2
}
class DivideExpression extends BinaryExpression {
toString(): string {
return `${this.format(this.left, 3)} / ${this.format(this.right, 2)}`
}
valueOf(): number {
return +this.left / +this.right
}
rankValue = 1
precedence = 2
}
class PowerExpression extends BinaryExpression {
toString(): string {
return `${this.format(this.left, 2)}^${this.format(this.right, 1)}`
}
valueOf(): number {
return (+this.left) ** +this.right
}
rankValue = 2
precedence = 1
}
class ConcatExpression extends ConstantExpression {
constructor(left: ConstantExpression, right: ConstantExpression) {
super(+`${left.num}${right.num}`)
}
rank(): number {
return 5
}
}Step 4: ใส่เครื่องหมาย + - * /
เช่น (((57)6)2) เราสามารถใส่ (((5 + 7) + 6) + 2) หรือจะเป็น (((5 + 7) / 6) - 2) ก็ได้ผลลัพธ์ก็จะได้ไม่เท่ากัน
Class ที่จะลองใส่เครื่องหมายต่างๆ เราจะใช้ Iterable โดย Iterable จะคล้ายๆ Generator Function ด้านบน แต่ต่างกันแค่ว่า Generator Function เป็น Function ในขณะที่ Iterable เป็น Class
Step 4.1: Iterable ของตัวเลข
class SingletonIterable implements Iterable<Expression> {
constructor(private num: number) { }
*[Symbol.iterator](): Iterator<Expression> {
yield new ConstantExpression(this.num)
}
}ตัวเลขเราจะ Yield แค่ทีเดียว คือตัวเลขนั้นๆ
Step 4.2: Iterable ของ Sqrt และ Factorial
class UnaryIterable implements Iterable<Expression> {
constructor(private iterator: Iterable<Expression>) { }
*[Symbol.iterator](): Iterator<Expression> {
for (const node of this.iterator) {
yield node
yield new SqrtExpression(node)
if (node instanceof ConstantExpression) {
yield new FactorialExpression(node)
}
}
}
}จากโค้ดเราจะ Yield 3 รอบ
- แบบไม่ใส่เครื่องหมาย เช่น 4
- แบบใส่ Sqrt เช่น Sqrt(4)
- แบบใส่ Factorial เช่น 4! (โดยเราจะใส่ Factorial เฉพาะตัวเลข)
Step 4.3: Iterable ของเครื่องหมาย + - * /
class BinaryIterable implements Iterable<Expression> {
constructor(private left: Iterable<Expression>, private right: Iterable<Expression>) { }
*[Symbol.iterator](): Iterator<Expression> {
for (const a of this.left) {
for (const b of this.right) {
yield new AddExpression(a, b)
yield new SubtractExpression(a, b)
yield new MultiplyExpression(a, b)
yield new DivideExpression(a, b)
yield new PowerExpression(a, b)
if (a instanceof ConstantExpression && b instanceof ConstantExpression) {
yield new ConcatExpression(a, b)
}
}
}
}
}จากโค้ดเราจะ Yield 6 รอบ
- + - * /
- ยกกำลัง
- นำเลขมาต่อกัน (ซึ่งจะต่อกันเฉพาะตัวเลข)
Step 5 (สุดท้าย): เขียนตัวคำนวณ
type Answer = {
rank: number
solution: string
}
function newyear(num: number[]) {
const result: Answer[] = []
const numExpr = num.map(it => new UnaryIterable(new SingletonIterable(it)))
for (const nums of permute(numExpr)) {
for (const iter of binaryBracketing(nums, (a, b) => new UnaryIterable(new BinaryIterable(a, b)))) {
for (const expr of iter) {
const ans = +expr
if (ans < 0 || ans > 100 || ~~ans !== ans || !isFinite(ans)) {
continue
}
const old = result[ans]
const rank = expr.rank()
if (old?.rank <= rank) {
continue
}
const solution = expr.toString()
result[ans] = { rank, solution }
}
}
}
return result
}จากโค้ดเราก็ทำตามสเต็ปด้านบน
- Permute
- binaryBracketing
- Loop Iterable เพื่อใส่เครื่องหมายแบบต่างๆ
- ถ้าได้เลข 0–100 ก็นำผลลัพธ์ใส่ Result
มาลองรันกันครับ
const result = newyear([2, 5, 6, 7])
console.table(result)ได้ผลลัพธ์ตามนี้
| (index) │ rank │ solution │
├─────────┼──────┼──────────────────────────┤
│ 0 │ 1 │ '2 - (5 + 7) / 6' │
│ 1 │ 1 │ '2 / ((5 + 7) / 6)' │
│ 2 │ 1 │ '2 * (5 - 7) + 6' │
│ 3 │ 1 │ '(2 - 5) * (6 - 7)' │
│ 4 │ 1 │ '2 + (5 + 7) / 6' │
│ 5 │ 1 │ '2 * (5 - 6) + 7' │
│ 6 │ 1 │ '2 + 5 + 6 - 7' │
│ 7 │ 1 │ '2 - 5 * (6 - 7)' │
│ 8 │ 1 │ '2 * (5 + 6 - 7)' │
│ 9 │ 1 │ '2 - (5 - 6) * 7' │
│ 10 │ 1 │ '2 - (5 - (6 + 7))' │
│ 11 │ 1 │ '2 * 5 - (6 - 7)' │
│ 12 │ 1 │ '2 * (5 - (6 - 7))' │
│ 13 │ 1 │ '2 * 7 + 5 - 6' │
│ 14 │ 1 │ '2 - (5 - 7) * 6' │
│ 15 │ 1 │ '2 * (5 + 6) - 7' │
│ 16 │ 1 │ '2 * (6 - (5 - 7))' │
│ 17 │ 2 │ '6 * 7 - 5^2' │
│ 18 │ 1 │ '2 * (5 + 7) - 6' │
│ 19 │ 1 │ '5 * (7 - 2) - 6' │
│ 20 │ 1 │ '2 + 5 + 6 + 7' │
│ 21 │ 1 │ '(2 - (5 - 6)) * 7' │
│ 22 │ 1 │ '5 / (2 / 6) + 7' │
│ 23 │ 1 │ '2 * 5 + 6 + 7' │
│ 24 │ 1 │ '(2 - (5 - 7)) * 6' │
│ 25 │ 1 │ '2 + 5 * 6 - 7' │
│ 26 │ 1 │ '5 + 6 / (2 / 7)' │
│ 27 │ 1 │ '(5 - 2) * 7 + 6' │
│ 28 │ 1 │ '(2 * 5 - 6) * 7' │
│ 29 │ 1 │ '2 * (5 + 6) + 7' │
│ 30 │ 1 │ '2 * (5 + 7) + 6' │
│ 31 │ 1 │ '2 + 5 * 7 - 6' │
│ 32 │ 1 │ '5 * 7 - 6 / 2' │
│ 33 │ 1 │ '(2 + 6) * 5 - 7' │
│ 34 │ 2 │ '5 + 6^2 - 7' │
│ 35 │ 1 │ '(2 + 5) * 6 - 7' │
│ 36 │ 1 │ '2 * (5 + 6 + 7)' │
│ 37 │ 3 │ 'sqrt(5^2) * 6 + 7' │
│ 38 │ 1 │ '5 * 7 + 6 / 2' │
│ 39 │ 1 │ '2 - (5 - 6 * 7)' │
│ 40 │ 1 │ '(2 * 7 - 6) * 5' │
│ 41 │ 3 │ 'sqrt(5^2) * 7 + 6' │
│ 42 │ 3 │ 'sqrt((2 + 5) * 7) * 6' │
│ 43 │ 1 │ '2 + 5 * 7 + 6' │
│ 44 │ 1 │ '2 * 7 + 5 * 6' │
│ 45 │ 1 │ '5 - (2 - 6 * 7)' │
│ 46 │ 1 │ '2 * (5 * 6 - 7)' │
│ 47 │ 1 │ '2 * 6 + 5 * 7' │
│ 48 │ 1 │ '(5 + 7) * (6 - 2)' │
│ 49 │ 1 │ '2 + 5 + 6 * 7' │
│ 50 │ 1 │ '5 * (6 / 2 + 7)' │
│ 51 │ 1 │ '(2 + 6) * 7 - 5' │
│ 52 │ 1 │ '2 * 5 + 6 * 7' │
│ 53 │ 1 │ '2 * 5 * 6 - 7' │
│ 54 │ 1 │ '(2 * 7 - 5) * 6' │
│ 55 │ 1 │ '(2 + 5) * 7 + 6' │
│ 56 │ 1 │ '(5 + 6 / 2) * 7' │
│ 57 │ 1 │ '(5 / 2 + 7) * 6' │
│ 58 │ 1 │ '2 * (5 * 7 - 6)' │
│ 59 │ 1 │ '(2 + 7) * 6 + 5' │
│ 60 │ 1 │ '(5 - (2 - 7)) * 6' │
│ 61 │ 1 │ '(2 + 6) * 7 + 5' │
│ 62 │ 2 │ '2^6 + 5 - 7' │
│ 63 │ 1 │ '(5 - (2 - 6)) * 7' │
│ 64 │ 1 │ '2 * 5 * 7 - 6' │
│ 65 │ 3 │ 'sqrt(5^2) * (6 + 7)' │
│ 66 │ 2 │ '2 + (5 - 7)^6' │
│ 67 │ 1 │ '2 + 5 * (6 + 7)' │
│ 68 │ 4 │ '2^7 - sqrt(5 * 6!)' │
│ 69 │ 3 │ '(2 + sqrt(7^6)) / 5' │
│ 70 │ 1 │ '(5 + 7) * 6 - 2' │
│ 71 │ 2 │ '5 * 7 + 6^2' │
│ 72 │ 2 │ '2 / 6^(5 - 7)' │
│ 73 │ 4 │ '2 + sqrt(6 - (5 - 7!))' │
│ 74 │ 1 │ '2 * (5 * 6 + 7)' │
│ 75 │ 1 │ '(2 + 6 + 7) * 5' │
│ 76 │ 1 │ '2 * 5 * 7 + 6' │
│ 77 │ 3 │ '(sqrt(5^2) + 6) * 7' │
│ 78 │ 4 │ '2 / (5! / 7!) - 6' │
│ 79 │ 1 │ '2 + (5 + 6) * 7' │
│ 80 │ 4 │ '2 + 5! - 6 * 7' │
│ 81 │ 4 │ '(5! + 6 * 7) / 2' │
│ 82 │ 1 │ '2 * (5 * 7 + 6)' │
│ 83 │ 5 │ '2 + 5 + 76' │
│ 84 │ 1 │ '(2 + 5 + 7) * 6' │
│ 85 │ 4 │ '5 + 6! / (2 + 7)' │
│ 86 │ 4 │ '(2 - (5! - 6!)) / 7' │
│ 87 │ 5 │ '2 * 6 + 75' │
│ 88 │ 5 │ '2 * (5! - 76)' │
│ 89 │ 1 │ '2 * 6 * 7 + 5' │
│ 90 │ 3 │ 'sqrt(2 + 7) * 5 * 6' │
│ 91 │ 1 │ '(2 + 5) * (6 + 7)' │
│ 92 │ 4 │ '(2 - 6) * 7 + 5!' │
│ 93 │ 4 │ '5! - sqrt(2 + 6! + 7)' │
│ 94 │ 1 │ '2 * (5 + 6 * 7)' │
│ 95 │ 1 │ '(2 * 6 + 7) * 5' │
│ 96 │ 1 │ '(2 + 6) * (5 + 7)' │
│ 97 │ 5 │ '5 * 7 + 62' │
│ 98 │ 2 │ '2^7 - 5 * 6' │
│ 99 │ 1 │ '(2 + 7) * (5 + 6)' │
│ 100 │ 1 │ '(2 * 7 + 6) * 5' │เพียงเท่านี้เราก็รู้วิธีการคำนวณให้ได้ผลลัพธ์ 0–100 แล้ว ผมลง Source Code ไว้ที่นี่นะครับ เผื่ออยากนำไปศึกษาต่อ
ถ้าใครอยากดูว่าแต่ละ Function นั้นทำงานอย่างไร ผมมีทำวิดีโอที่อธิบายอย่างละเอียดไว้ที่นี่ครับ ไปศึกษาต่อกันได้ครับ
Happy Coding ครับ
สำหรับใครที่ชื่นชอบบทความนี้ อย่าลืมกดติดตาม Medium: KBTG Life เรามีสาระความรู้และเรื่องราวดีๆ จากชาว KBTG พร้อมเสิร์ฟให้ที่นี่ที่แรก
