Ponder This Challenge - February 2020 - Snakes and Ladders

In the famous Snakes and Ladders game, there is a board with 100 squares. You start at square 0 (just outside of the board) and then proceed to advance based on your move, which is dictacted by the throw of a fair dice. If your piece lands on a square that is at the very bottom of a ladder, you climb it. If your turn lands you at the head of a snake, you slide down to the bottom of its tail. And if your turn takes you out of the board (a square > 100), you stay in the square where you are at the time the dice was thrown.

Your challenge this month is to design a game with 10 ladders and snakes altogether that will lead to an expected number of moves (rounded to the 6th decimal place) of 66.978705.

Provide your answer as a list of 10 [source,target] pairs.

As an example, the standard game of 19, with 9 ladders and 10 snakes:
[1,38],[4,14],[9,31],[21,42],[28,84],[36,44],[51,67],[71,91],[80,100],[16,6],[47,26],[49,11],[56,53],[62,19],[64,60,],[87,24],[93,73],[95,75],[98,78] has an expected 39.225122 moves (again, rounded to the 6th decimal place).

Bonus '*' for getting to at least 12 digits after the decimal point to 66.978705007555420778.

Solution

• Click here to view the solution

  We received several solutions.

  Harald Bögeholz found a solution with only snakes: [[22, 2], [26, 8], [24, 21], [40, 25], [51, 38], [57, 42], [78, 53], [76, 61], [86, 74], [99, 82]]
  Latchezar Christov also sent us a solution with only three snakes/ladders: [[35,15],[67,61],[99,9]]
  The best solution we received is from Asaf Zimmerman: [[61,56],[60,54],[59,53],[58,54],[57,55],[14,38],[35,13],[92,66],[97,89],[84,64]], which is accurate for 15 digits after the decimal point.

  Peter Huggins has an efficient way to halve the search space:
  "The solution was found by considering the board as a left half and right half. At the end of the left half, we prescribed five consecutive snakes with variable left endpoints, so that the only way to make it to the right half of the board was to land on the square immediate after the "blockade" of five snakes. This allowed computing expected number of moves completely separate for left and right half and then adding the two. A search space of such restricted choices of snakes/ladders in the left half was evaluated, and similarly the right half. Then the sum of left and right expectation that was closest to the target sum was found using the standard double linear scan approach after sorting."

  The solution we intended was [[80, 31], [79, 41], [78, 59], [68, 26], [69, 53], [82, 58], [84, 97], [72, 93], [73, 23], [83, 84]]
  which is the ASCII values of "ponderthis" as the first number and the decimal expansion of Pi as the second.

  This gives an expected time of exactly
  12069717322599589450686796528518338401917187078111730231579496649/180202309394278154198991500658119021487803384043920462457077760, which is approximately 66.978705007555420778...

Solvers

• Guillermo Wildschut (28/01/2020 10:29 AM IDT)
• Anders Kaseorg (28/01/2020 11:31 AM IDT)
• *Bert Dobbelaere (28/01/2020 11:38 PM IDT)
• Alper Halbutogullari (28/01/2020 11:38 PM IDT)
• David Greer (30/01/2020 02:00 AM IDT)
• Daniel Chong Jyh Tar (30/01/2020 11:37 AM IDT)
• Lorenzo Gianferrari Pini (30/01/2020 01:09 PM IDT)
• Pern Jie Quah (31/01/2020 02:16 AM IDT)
• Todd Will (31/01/2020 06:30 PM IDT)
• Lorenz Reichel (31/01/2020 09:31 PM IDT)
• Willem H Hendriks (01/02/2020 12:29 AM IDT)
• Gary M. Gerken (01/02/2020 07:15 AM IDT)
• Harald Bögeholz (02/02/2020 09:00 AM IDT)
• Chris Marks (01/02/2020 09:10 PM IDT)
• Joerg Schepers (03/02/2020 12:28 AM IDT)
• David Friedman (03/02/2020 08:29 PM IDT)
• Dominik Reichl (03/02/2020 09:03 PM IDT)
• Dieter Beckerle (04/02/2020 12:55 AM IDT)
• Sebastian Bohm & Martí Bosch (04/02/2020 03:57 PM IDT)
• Mateus Siqueira (04/02/2020 04:10 PM IDT)
• Leonardo Joau (04/02/2020 04:57 PM IDT)
• Kevin Naslund (04/02/2020 05:35 PM IDT)
• *Asaf Zimmerman (04/02/2020 11:34 PM IDT)
• Ayush Jain (05/02/2020 09:51 AM IDT)
• Kang Jin Cho (05/02/2020 10:22 AM IDT)
• Greg Janée (05/02/2020 02:32 PM IDT)
• Khaled Fayed (05/02/2020 02:41 PM IDT)
• Rob Pratt (08/02/2020 01:09 AM IDT)
• Andrew Mullins (08/02/2020 10:31 PM IDT)
• Shouky Dan & Tamir Ganor (09/02/2020 09:00 AM IDT)
• Andreas Stiller (09/02/2020 06:21 PM IDT)
• David Krief (10/02/2020 03:03 PM IDT)
• Andreas Puccio (10/02/2020 08:31 PM IDT)
• Peter Huggins (10/02/2020 10:21 PM IDT)
• Stephen Barr (11/02/2020 05:51 AM IDT)
• Tyler Mullen (11/02/2020 08:26 AM IDT)
• Arthur Vause (11/02/2020 06:41 PM IDT)
• Vladimir Volevich (14/02/2020 05:18 PM IDT)
• Yusuf AttarBashi (15/02/2020 09:40 PM IDT)
• Jack Kennedy (16/02/2020 04:43 PM IDT)
• Nik Vlachos (19/02/2020 12:40 AM IDT)
• Thomas Huet (19/02/2020 08:31 PM IDT)
• Alexander Strasser (21/02/2020 01:48 PM IDT)
• Dimas Ramos (22/02/2020 06:07 PM IDT)
• Stanislav Grudnitskiy (22/02/2020 08:57 PM IDT)
• Graham Hemsley (23/02/2020 07:24 PM IDT)
• Peter Gerritson (23/02/2020 09:22 PM IDT)
• Dipto Thakurta Dipto Thakurta (24/02/2020 06:39 AM IDT)
• Diana Gornea (24/02/2020 11:23 AM IDT)
• *Latchezar Christov (24/02/2020 03:27 PM IDT)
• JJ Rabeyrin (24/02/2020 11:13 PM IDT)
• Daniel Bitin (25/02/2020 12:15 AM IDT)
• Kai Guttmann (25/02/2020 07:06 PM IDT)
• Nyles Heise (26/02/2020 05:08 AM IDT)
• Jean Bertrand Gauthier (26/02/2020 12:24 PM IDT)
• Hugo Pfoertner (26/02/2020 01:22 PM IDT)
• *Bertram Felgenhauer (27/02/2020 11:21 AM IDT)
• Kottmann Markus (27/02/2020 10:37 PM IDT)
• Robert Lang (28/02/2020 12:02 PM IDT)
• Stéphane Higueret (28/02/2020 01:42 PM IDT)
• Govind Jujare (28/02/2020 07:13 PM IDT)
• Radu-Alexandru Todor (01/03/20 12:57 AM IDT)
• Collin Pearce (01/03/20 08:11 AM IDT)
• Marco Bellocchi (01/03/20 09:02 AM IDT)
• Jonah Mann & Joe Hooker (01/03/20 11:44 AM IDT)
• Muralidhar Seshadri (01/03/2020 06:06 PM IDT)
• Erik Wünstel (01/03/2020 06:35 PM IDT)
• Calvin Pozderac (01/03/2020 07:17 PM IDT)
• Oleg Vlasii (01/03/2020 11:15 PM IDT)
• Eden Saig (02/03/2020 01:41 AM IDT)
• Li Li (02/03/2020 06:38 AM IDT)
• Florian Fischer (03/03/2020 07:52 AM IDT)