ASAC

About ASAC

Program synthesis typically takes either natural language or formal specifications as input. While large language models generate substantial code from natural language descriptions, the inherent ambiguity in natural language makes it challenging to guarantee the correctness of generated programs. On the other hand, using formal specifications offers the potential for precise semantics and provable program correctness. However, traditional specification-based approaches often fall short as they tend to produce code snippets too small for practical use.

Some researchers focus on synthesizing algorithms from specification which is both meaningful and feasible. To motivate research on synthesizing algorithms, we present the first benchmark for this problem: ASAC. ASAC consists of 136 tasks collected from a competitive programming contest and covers a wide range of algorithmic paradigms and various difficulty levels. Each task in ASAC includes a formal specification and an efficiency requirement, and the program synthesizer is expected to produce a program that satisfies the formal specification and meets the efficiency requirement.

Get the whole Benchmark

GitHub Repository

Tasks	Tags	Difficulty
2k System of Numeration	System , High Precision , Math	0.66
Abacus Mental Arithmetic Test	Enumerate , Simulation	0.71
Across the river	Search , DP	0.75
Angry Birds	Bitmask , Search	0.7
Arrange Seats	Greedy , Sort	0.65
Borrow Classrooms	Bipartite , Prefix Sum , Difference	0.7
Building Block Competition	Greedy , Recursion , Simulation	0.42
Buying Pencils	Simulation	0.58
Calculate the coefficients	Math	0.65
Campfire Party	Simulation	0.62
Cell Division	Sieve Theory , Prime , Math	0.73
Change Classrooms	Expectation , DP	0.75
Checkerboard	Shortest Path , DFS , BFS , Pruning	0.75
Children’s Numbers	High Precision , Recursion , DP	0.84
Chorus Formation	Monotonic Queue , DP	0.58
Circle	String , Recursion , High Precision , Simulation	0.7
Combinatorial Number Problem	Combinatorics , Math	0.73
Congruence Equation	Extended Euclid , Extended Euclidean , Math	0.45
Counting Numbers	Sort , Simulation	0.59
Cultural Journey	Shortest Path , Search , Graph Theory , Pruning	0.77
Currency System	Greedy , Bagging , DP , Math	0.65
Defend the Kingdom	Heavy-Light Decomposition , Multiply , DP	0.85
Delimit the Minimum Passing Score	Sort , Simulation	0.6
Digit Reversal	String , Simulation	0.56
Divert water into the city	BFS , Search , DP	0.76
Division	Greedy , Monotonic Queue	0.91
Doudizhu	DFS , Greedy , Search	0.76
Earthworms	Heap , Queue	0.8
Energy Necklace	Interval DP , Enumerate , Recursion , DP	0.46
Epidemic Control	Greedy , Tree Structure , Multiply , Sort , Bipartite	0.71
FBI Tree	Tree Structure , String , Search , Recursion , Construct	0.41
Find the Way	Search , Graph Theory	0.7
Flappy Bird	Bagging , Enumerate , DP	0.8
Florist	DP	0.62
Fruit Pile	Heap , Greedy , Priority Queue	0.62
Gathering herbs	Bagging , DP	0.54
Gold Coins	Math , Simulation	0.43
Gray Code	Recursion , Math	0.75
Hankson’s Interesting Question	GCD , Enumerate , Math	0.66
Hanoi Twin Towers	Recursion , High Precision , Math	0.65
Harbor	Simulation	0.71
Helix Matrix	Math , Simulation	0.7
Hopscotch	Bipartite , Queue , Monotonic Queue , DP	0.82
Huarong Road	Search , Graph Theory	0.79
ISBN Number	String , Simulation	0.75
Jam’s Counting Method	Simulation	0.41
Jinjin’s Savings Plan	Enumerate , Simulation	0.59
Jinming’s Budget Plan	Bagging , DP	0.65
Job Scheduling Plan	Simulation	0.64
Joint Weights	LCA , DP	0.73
Jump Rocks	Bipartite , Greedy	0.65
Kat's doubts	Construct , Diophantine Equation , CRT , Math	0.54
King Game	Greedy , Sort , High Precision	0.78
Lay the carpet	Enumerate , Simulation	0.66
Love Running Every Day	LCA , Segment Tree , Link-Cut , Heavy-Light Decomposition , Difference , LCT , Tree	0.77
Machine Translation	Queue , Simulation	0.58
Machining Parts	Shortest Path	0.8
Magic Circle		0.78
Magic Square	Enumerate , Simulation	0.39
Martian	Tree Structure , Recursion , Construct	0.47
Matchstick Equation	Search	0.53
Matrix Number Game	High Precision , System , DP	0.7
Message Passing	Graph Theory , UFDS	0.65
Mine Sweeper	String , Search	0.52
Mingming’s Random Number	Sort , Simulation	0.54
Missile Interception	Sort , Enumerate , Simulation	0.67
Number-Filling Game	DP , Math	0.89
Numbers on the Tree	Tree Structure	0.89
Numeration Problem	String , Simulation	0.5
Palindrome Dates	Enumerate	0.7
Parentheses Tree	Tree Structure , Tree Theory	0.81
Passing Notes	Minimum Cost Flow , DP	0.55
Pave the Road	Greedy , Binary Indexed Tree	0.51
Peanut Picking	Search , Simulation	0.61
Placing Flowers	DP , Simulation	0.59
Polynomial Output	String , Math , Simulation	0.72
Prime Factorization	Sieve Theory , Prime , Math	0.62
Prisoners	UFDS , Greedy , Sort , Graph Theory , Bipartite Graph	0.61
Public Transport Transfer	Simulation	0.77
Queuing Matches	Sort , Binary Indexed Tree	0.6
Receiving Water	Greedy , Search , Simulation	0.55
Road Game	DP	0.64
Scholarship	Sort , Math , Simulation	0.53
Score		0.32
Select Inns	Recursion	0.63
Sequence	System , Math	0.49
Shipping Plan	Heavy-Light Decomposition , LCA , Graph Theory	0.75
Shuffle	Convex Hull Trick , DFS , Enumerate , DP	0.82
Sightseeing bus	Greedy , Recursion	0.67
Simplifying Proportion	GCD , Math	0.56
Solve the Equation	Prime , Sieve Theory , Math , Enumerate , High Precision	0.76
Souvenir Grouping	Greedy , Sort	0.54
Souvenir	Bagging , DP	0.69
Spinning Game	Math , Simulation	0.62
Statistics	Simulation	0.44
String Expansion	String , Simulation	0.73
Stupid Little Monkey	Sort , Prime , Sieve Theory	0.69
Submatrix	Pruning , Search , Enumerate , DP	0.65
Sum	Prefix Sum , Sort , Linear Structure	0.76
Swiss System	Sort , Recursion , Simulation	0.78
Symmetric Binary Tree	Tree Structure , HSASH , Hash	0.73
Taotao Picking Apple	Simulation	0.43
Target-shaped Sudoku	Search , Pruning , Bit Operations	0.75
The Battle Between Dragon and Tiger	Enumerate , Simulation	0.8
The Big Bang Theory edition Rock-Paper-Scissors Game	Simulation	0.44
The Center of Gravity of the Tree	Tree Dp	0.83
The Core of the Tree Network	Simulation , Tree Structure , DP , Shortest Path , Enumerate	0.53
The Escape of the Watchman	Greedy , DP	0.6
The Game of Ball Passing	Recursion , DP , Simulation	0.52
The Happy Jinming	Bagging , DP	0.46
The Librarian	Sort , String	0.59
The Lurker	String , Simulation	0.67
The Number Game	String	0.78
The Optimal Trade	SCC , DP , Shrink Point , Search , Graph Theory , Shortest Path	0.63
The Salesman	Greedy , Binary Indexed Tree , Segment Tree	0.56
The Station Classification	Greedy , Sort , Graph Theory , Topological Sort	0.69
The Three Kingdom Game	Greedy , Game Theory	0.49
The Trees Outside the Campus	Simulation	0.59
The Unhappy Jinjin	Enumerate	0.52
The Value of Expression	String , DP	0.7
The Vigenère Code	String , Simulation	0.48
The Worm-eaten Formula Puzzle	Search , Math	0.77
The location of The Wireless Network Transmitter	Enumerate , Simulation	0.61
The smart quality supervisor	Bipartite , Prefix Sum , Math	0.74
Title Statistics	String , Simulation	0.57
Today’s Meal at Emiya’s House	Inclusion-Exclusion , DP , Math	0.8
Tortoise Chess	Enumerate , Recursion , DP	0.43
Toy Puzzle	Simulation	0.63
Track Construction	Bipartite , Greedy , LCA	0.84
Travel By Car	Multiply	0.68
Travel	DFS , Greedy , Search , Cable Protection	0.82
Treasure Hunt	Probability Theory , Simulation	0.73
Trucking	LCA , UFDS , Greedy , Multiply , Spanning Tree , Graph Theory	0.7
Two Stack Sort	Bipartite Graph , Graph Theory	0.66
Who got the most scholarships	Sort , String	0.53
Word Count	String , Simulation	0.78

---