12
$\begingroup$

This is an entry to the 12th fortnightly challenge.

This maze is built out of the integers $1,\dots,560$. You may step from $k$ to $2k$, or from $3k+1$ to $5k+1$, or vice versa in each case, provided you don't step outside that range $1,\dots,560$. ($k$ is an integer.)

So here is a small part of the maze: $$ \begin{array}{c} &&&&21& \longleftrightarrow &42& \longleftrightarrow &84&&176& \longleftrightarrow &352\\ && & & \updownarrow&&&&&&\updownarrow \\ 3 & \longleftrightarrow & 6 & & 13 & \longleftrightarrow & 26 & & 53 & \longleftrightarrow & 106& & 213 & \longleftrightarrow & 426 \\ & & \updownarrow & & & & \updownarrow & & & & \updownarrow & & & & \updownarrow \\ 2 & \longleftrightarrow & 4 &\longleftrightarrow& 8 & \longleftrightarrow & 16 & \longleftrightarrow & 32 & \longleftrightarrow & 64 & \longleftrightarrow & 128 & \longleftrightarrow & 256 & \longleftrightarrow & 512 \\ & & & & & & \updownarrow & & & & & & & & \updownarrow \\ & & & & 5 & \longleftrightarrow & 10 & \longleftrightarrow & 20 & \longleftrightarrow & 40 & & 77 & \longleftrightarrow & 154 & \longleftrightarrow & 308 \\ \end{array} $$

Your starting-position is a sexual one for two, and you finish where Bradbury's famous work catches fire.

Further (arithmetical) clues to those positions:

Their product is 31119 and their sum is 520.

Bonus: Why $560$, not $600$, say?

$\endgroup$
  • $\begingroup$ Very interesting idea! But to clarify: as you only show a part of the maze: are we to built the maze as we step along, with the two optional types of steps being horizontal / vertical? $\endgroup$ – BmyGuest Jul 22 '16 at 7:29
  • 1
    $\begingroup$ @RosieF: Sorry about that! Didn't want to post it as an answer since it would be way too short. $\endgroup$ – Deusovi Jul 22 '16 at 7:41
  • 1
    $\begingroup$ @BmyGuest: I think I've figured out both of them: rot13: fvkgl avar gb sbhe uhaqerq svsgl bar $\endgroup$ – Deusovi Jul 22 '16 at 7:43
  • 1
    $\begingroup$ @Rosie: Now we don't even need to figure out the clues! The quadratic formula just tells us the answers. $\endgroup$ – Deusovi Jul 22 '16 at 8:05
  • 1
    $\begingroup$ The answer to the bonus is not that allowing numbers up to (say) 600 would permit a much shorter path between the start and finish points. You need to go up to 1576 before the path gets shorter. I think the shortest path with no upper limit goes as high as 2176. $\endgroup$ – Gareth McCaughan Jul 22 '16 at 9:35
8
$\begingroup$

A favourite

position is the $69$

Books catch fire, somewhere around

$451$ Fahrenheit

Hint check

$451\times69=31,119$
$451+69=520$

My brute forcer, below, shows that

The 37 move path:

[69, 138, 276, 166, 100, 50, 25, 41, 82, 136, 68, 34, 56, 28, 14, 7, 11, 22, 44, 88, 176, 106, 64, 32, 16, 26, 52, 86, 43, 71, 142, 236, 118, 196, 326, 163, 271, 451]
is the only path we may successfully take
(without revisiting numbers on which we already stepped).

With a maximum of greater than $575$, such as $600$

We can start to take a second route by deviating at $22$ to take an alternative path to $52$ via $576$:

[69, 138, 276, 166, 100, 50, 25, 41, 82, 136, 68, 34, 56, 28, 14, 7, 11, 22, 36, 72, 144, 288, 576, 346, 208, 104, 52, 86, 43, 71, 142, 236, 118, 196, 326, 163, 271, 451]

The very simple Python code I wrote:

def iterNextNs(curN, minN=1, maxN=560):
    if curN % 2 == 0:
        v = curN // 2
        if v >= minN:
            yield v
    v = 2 * curN
    if v <= maxN:
        yield v
    m1 = curN - 1
    v = 3 * m1
    if v % 5 == 0:
        v = v // 5 + 1
        if v >= minN:
            yield v
    v = 5 * m1
    if v % 3 == 0:
        v = v // 3 + 1
        if v <= maxN:
            yield v

def routes(visited=[69], toN=451, minN=1, maxN=560):
    for nextN in iterNextNs(visited[-1], minN, maxN):
        if nextN == toN:
            yield visited + [toN]
        elif nextN not in visited:
            for route in routes(visited + [nextN], toN, minN, maxN):
                yield route
$\endgroup$
  • 1
    $\begingroup$ Now, is there a simple way to show this without such an attack... $\endgroup$ – Jonathan Allan Jul 22 '16 at 10:02
  • $\begingroup$ Correct, including the bonus. Up to 575, each component of the maze is a tree. 576 creates the first cycle. Unfortunately, the path overlaps the cycle, so the puzzle fails to have a unique answer. Moreover, the path includes exactly half of the cycle, so even requiring a shortest route still fails to yield a unique answer. $\endgroup$ – Rosie F Jul 22 '16 at 10:03
  • $\begingroup$ Although if we make the maximum $2176$ we can take a $21$ step route: [69, 138, 276, 166, 100, 50, 25, 41, 82, 136, 272, 544, 1088, 2176, 1306, 784, 392, 196, 326, 163, 271, 451] $\endgroup$ – Jonathan Allan Jul 22 '16 at 10:25
  • 1
    $\begingroup$ But if I'd chosen a different set of numbers, I'd have chosen different endpoints, e.g. 78 & 257 for {1,...,1576}. $\endgroup$ – Rosie F Jul 22 '16 at 10:36
  • 1
    $\begingroup$ Oooo, I've never tried a $78$ :p $\endgroup$ – Jonathan Allan Jul 22 '16 at 10:39
3
$\begingroup$

I believe the shortest route between

69 (I don't think I need to explain) and 451 (Ray Bradbury's Fahrenheit 451)

is

37 moves

using this route:

69 138 276 166 100 50 25 41 82 136 68 34 56 28 14 7 11 22 44 88 176 106 64 32 16 26 52 86 43 71 142 236 118 196 326 163 271 451.

I got this result from writing java code to implement a naiive breadth-first search.

import java.util.*;
import java.text.*;
import java.math.*; 

public class bfs {

    public static void main(String[] args) {
        //processing
        Cell[] board = new Cell[561];

        for (int i = 1; i <= 560; i++){
            board[i] = new Cell(i);
            if (i*2 <= 560) {board[i].addAdj(i*2);}
            if (i%2 == 0) {board[i].addAdj(i/2);}
            if ((i-1)%5 == 0) {board[i].addAdj((i/5*3)+1);}
            if ((i-1)%3 == 0 && (i/3*5)+1 <= 560) {board[i].addAdj(i/3*5+1);}
        }

        //bfs
        Queue<Cell> q = new LinkedList<Cell>();
        board[69].setVisited(true);
        q.add(board[69]);
        while (!q.isEmpty()){
            Cell curr = q.remove();
            for (Integer e : curr.getAdjs()) {
                if (board[e].getVisited() == false) {
                    board[e].setVisited(true);
                    board[e].setLevel(curr.getLevel()+1);
                    board[e].setParent(curr.getLabel());
                    q.add(board[e]);}
            }
        }

        int result = board[451].getLevel();
        if (result == 0) {result = -1;}
        //output
        System.out.println(result);
        System.out.print("451 ");
        Cell parent = board[451];
        while (parent.getLabel() != 69) {
            parent = board[parent.getParent()];
            System.out.print(parent.getLabel() + " ");

        }
    }
}   


class Cell {
    private int label;
    private int level;
    private boolean visited;
    private ArrayList<Integer> adjacents = new ArrayList<Integer>();
    private int parent;

    public Cell(int i){
        label = i;
        level = 0;
        visited = false;
        adjacents = new ArrayList<Integer>();
        parent = 0;
    }

    public int getLabel() {return label;}
    public int getLevel() {return level;}
    public void setLevel(int i) {level = i;}
    public boolean getVisited() {return visited;}
    public void setVisited(boolean b) {visited = b;}
    public ArrayList<Integer> getAdjs() {return adjacents;}
    public void addAdj(int i) {
        adjacents.add(i);
    }
    public int getParent(){return parent;}
    public void setParent(int i) {parent = i;}
}
$\endgroup$
  • $\begingroup$ It would be very interesting to see, if one can find the solution by deduction logic rather than brute force testing it (with or without computer help.) BTW, how many "alternatives" did you code explore before finding your solution? $\endgroup$ – BmyGuest Jul 22 '16 at 9:18
  • $\begingroup$ For what it's worth, my program agrees with yours :-). $\endgroup$ – Gareth McCaughan Jul 22 '16 at 9:18
  • $\begingroup$ @Glorfindel thank you for whatever magic you did to the formatting! $\endgroup$ – yuzuki Jul 22 '16 at 9:27
  • $\begingroup$ @BmyGuest I have no idea. My code should simply extend and explore all paths when it reaches any reachable cell. Only at the end do I trace the 'parent' (the first cell to reach 451) back to the source. $\endgroup$ – yuzuki Jul 22 '16 at 9:27
  • 2
    $\begingroup$ This particular puzzle seems unlikely to be much fun by hand. I mean, you could certainly do it -- 560 isn't a terribly large number, after all -- but I don't think there's much scope for cleverness to improve on brute force. $\endgroup$ – Gareth McCaughan Jul 22 '16 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.