Lecture Programming in haskell - Chapter 9: The countdown problem

The "Countdown Problem," originating from a popular British television quiz programme based on the French "Des Chiffres et Des Lettres," presents a compelling challenge in computational problem-solving. This task involves using a given set of numbers and standard arithmetic operators to construct an expression that evaluates to a specific target number. Its significance lies in its utility as a pedagogical tool for demonstrating advanced programming concepts, particularly within functional programming paradigms. This document aims to formalize the rules and computational logic required to systematically approach and solve the Countdown Problem using Haskell, emphasizing the evaluation of expressions and adherence to specific arithmetic constraints.

Sinh viên khoa học máy tính, lập trình viên quan tâm đến lập trình hàm (đặc biệt là Haskell), thiết kế thuật toán, giải quyết vấn đề tổ hợp và đánh giá biểu thức.

This document systematically addresses the "Countdown Problem," a number-based puzzle originating from a well-known television quiz show. The core challenge is to construct an arithmetic expression using a given set of source numbers and basic operators (+, -, *, /) to precisely achieve a predefined target value. The methodology presented leverages Haskell's functional programming capabilities to formalize the problem. It begins by defining algebraic data types for operators (Op) and expressions (Expr), allowing for a structured representation of arithmetic operations. Key functions include apply for executing operations, valid for enforcing rules such as requiring positive natural numbers for intermediate results and unique usage of source numbers, and eval for evaluating an expression to produce its final value. The paper outlines the process of generating potential expressions and validating them against the problem's constraints. This involves a combinatorial approach where choices generates all valid selections of numbers from the input set, and the solution function ties everything together. The solution function verifies that the numbers used in an expression are drawn from the initial set according to the rules and that the expression correctly evaluates to the target number. This approach not only provides a robust solution to the Countdown Problem but also serves as an excellent illustration of how functional programming principles can be applied to solve complex combinatorial search and constraint satisfaction problems, showcasing the elegance and power of Haskell's type system and compositional nature in algorithm design.