Displaying the Calculation Process of the Ackermann Function (Part 1) / Solving the DDR Footwork Optimization Problem
Overview
We published a technical book titled "Displaying the Calculation Process of the Ackermann Function (Part 1) / Solving the DDR Footwork Optimization Problem" at Tech Fest 7.
This book deals with the Ackermann function, fighting against large data and recursive functions, and how to proceed with a Rust project. The result is a massive calculation process that can be mesmerizing to behold.
Additionally, using DDR as a theme, we solve the combination optimization problem of finding the optimal footwork using dynamic programming.
The book is divided into two parts, with the first part written by esplo and the second part by maton.
Cover
The cover was illustrated by Mr. Kobayashi Dokuga, who is known for his work on "Sushi: Void Edition" and "Let's Eat!" (Twitter:@doom_k, Pixiv Fanbox). This book was created with inspiration from "Sushi: Void Edition".
Wonderful Cover
Details
The first part of this book focuses on the calculation process of the Ackermann function, covering how to proceed with a Rust project, fighting against recursive functions, and handling large data.
The second part tackles the combination optimization problem of finding the optimal footwork for Dance Dance Revolution, which is a sequence optimization problem (energy minimization problem).
Both parts address how to efficiently solve problems that would otherwise be too large to fit in memory or take too long to calculate.
Recommended for
This book is recommended for those who love large data, want to learn Rust, are interested in large numbers, competitive programmers, and DDR players.
Table of Contents
Part I: Displaying the Calculation Process of the Ackermann Function (Part 1)
- Chapter 1: Introduction
- 1.1 What you can gain from this book
- 1.2 Prerequisites
- 1.3 Desired properties
- 1.4 References for the entire code
- Chapter 2: What is the Ackermann Function?
- 2.1 Overview of the Ackermann function
- 2.2 The world of A(4,2)
- 2.3 What is it, anyway?
- 2.4 Learning more
- Chapter 3: Calculating the Ackermann Function
- 3.1 Implementing the Ackermann function as a program
- 3.2 Calculating the world of A(4,n)
- 3.3 Calculating A(4,2)
- 3.4 Summary so far
- Chapter 4: Displaying the Calculation Process
- 4.1 Results of this book
- 4.2 Naive implementation
- 4.3 Speeding up with memoization
- 4.4 Implementation with a carefully designed data structure
- 4.5 Summary
- Chapter 5: Next Episode
- 5.1 Predicting necessary resources
- 5.2 Analyzing bottlenecks
- 5.3 Ideas for displaying larger calculation processes
- Chapter 6: Afterword
Part II: Solving the DDR Footwork Optimization Problem
- Chapter 7: Introduction
- Chapter 8: Preparation: Terms used in this book
- Chapter 9: Formulation
- 9.1 Introducing costs
- 9.2 Defining the cost function
- 9.3 Formulating the problem as a search problem
- Chapter 10: Solution
- 10.1 Building the calculation array
- 10.2 Searching for the minimum cost element
- 10.3 Extracting the minimum cost footwork
- Chapter 11: Discussion
- 11.1 Concepts we've been ignoring
- 11.2 Challenges in formulation
- Chapter 12: Conclusion
Purchase
The book is available on Booth. Please see the details here. We've also posted a preview of several pages, so please take a look.
