I've taken 1 course in Java and 1 in C++ and now I'm tinkering with Python (love it so far). My module I'm currently working on is designed to solve a certain puzzle. To understand the code you'll need to understand the puzzle:

There is an upside down triangle with n amount of numbers on the top row. For example, if n were 3 the triangle would look like this:

_ _ _
_ _
_

There are a total of 6 spaces in this example. The puzzle is to find all the possible solutions so that the difference between any 2 numbers above 1 number is equal to the number below. Below is an example of one particular solution. In this example, we can use the numbers 1 - 6 since there are 6 spaces. Note that we can say "3 - 2 = 1" and also "2 - 3 = 1" for this puzzle (just take the absolute value of the difference):

6 2 5
4 3
1

This is my solution. My code attempts to find all possible solutions, but I have hit a roadblock. I can't remember my Grade 12 statistics anymore and am having trouble testing all the possible combinations of the puzzle. I'm getting confused as to how to do this. For example, I understand that in this puzzle order matters, so I would say "6 choose 6" which is "6!" or 720 different combinations. I don't know how to systematically rotate through all of them. I'll post my code below. Any help is greatly appreciated.

"""Currently this module contains functions which solve
the upside down triangle puzzle thing."""


def triangle(toprow):
    """This function solves all possible answers for the
    funny upside down triangle puzzle thing from calculus."""

    print("You entered a puzzle with " + str(toprow) + " spaces on the top row.\n")

    # Find the total number of numbers to be used in the puzzle

    total = toprow

    for i in range(0, toprow):
        total = total + i

    # State how many possibilities there are for the puzzle

    if (toprow > 17):
        print("There are A LOT of possibilities. Hopefully the program doesn't crash...\n")
    elif (toprow > 4):
        print("There are " + "%e" % npr(total) + " possibilities to test.\n")
    else:
        print("There are " + str(npr(total)) + " possibilities to test.\n")

    # Apply the initial numbers to the triangle

    tri = []
    line = []

    count = total

    for k in range(0, toprow):
        line = []
        for l in range(0, (toprow - k)):
            line.append(count)
            count = count - 1
        tri.append(line)

    print("The initial triangle is: " + str(tri) + "\n")

    # The array tri is correct up to here
    # Ex. triangle(3) gives tri = [[6, 5, 4], [3, 2], [1]]

    # Do all the possible arrangements of the numbers. Ugh.
    # Currently this is not working. I need help here!

    sols = []
    
    for m in range(0, toprow):
        for n in range(0, (toprow - m)):
            for o in range(m, toprow):
                for p in range(n, (toprow - o)):
                    print("Testing triangle " + str(tri) + "...")
                    if (test(tri)):
                        sols.append(tri)
                        print("The triangle " + str(tri) + " is a solution.")
                    temp = tri[o][n]
                    if (o == (toprow - 1)):
                        tri[o][n] = tri[m][n]
                        tri[m][n] = temp
                    elif (n == (toprow - o - 1)):
                        tri[o][n] = tri[(o + 1)][0]
                        tri[(o + 1)][0] = temp
                    else:
                        tri[o][n] = tri[o][(n + 1)]
                        tri[o][(n + 1)] = temp
    return sols


def test(arr):
    """This complimentary function tests the array to see
    if it is a solution."""

    count = len(arr) - 1

    # Test if the difference between two tops is equal to
    # their corresponding bottom (directly below the pair)

    for i in range(count):
        for j in range(count - i):
            if (((arr[i][j] - arr[i][(j + 1)]) != arr[(i + 1)][j]) and ((arr[i][(j + 1)] - arr[i][j]) != arr[(i + 1)][j])):
                return 0

    return 1


def npr(n):
    """This function determines how many possible arrangements
    of the numbers there are (nPr from Math 12 statistics)."""

    # Do n factorial (there is a math module function but ya)

    for i in range(1, n):
        n = n * i

    return n


def triprint(arr):
    """This function prints the triangle."""

    count = len(arr)
    
    # Print the numbers

    for i in range(0, count):
        print(str(arr[i]))

Recommended Answers

All 3 Replies

You can use itertools.permutations to rotate over all the numbers

import itertools
for p in itertools.permutations(range(1, 5)):
    print(p)
(1, 2, 3, 4)
(1, 2, 4, 3)
(1, 3, 2, 4)
(1, 3, 4, 2)
(1, 4, 2, 3)
(1, 4, 3, 2)
(2, 1, 3, 4)
(2, 1, 4, 3)
(2, 3, 1, 4)
(2, 3, 4, 1)
(2, 4, 1, 3)
(2, 4, 3, 1)
(3, 1, 2, 4)
(3, 1, 4, 2)
(3, 2, 1, 4)
(3, 2, 4, 1)
(3, 4, 1, 2)
(3, 4, 2, 1)
(4, 1, 2, 3)
(4, 1, 3, 2)
(4, 2, 1, 3)
(4, 2, 3, 1)
(4, 3, 1, 2)
(4, 3, 2, 1)

Beware that the number of permutations is very very large: factorial(n) for n being the number of items permuted. The number of permutations to handle a triangle with 4 in the top row is 3,628,800 (10 factorial) and for 5 in the top row, its 1,307,674,368,000.

You might be better served to try to discover a pattern that you can exploit.

Just for fun, I wrote my own version of your exhaustive search, using Gribouillis' suggestion. I found:

  • for 2 in the top row: 4 (of 6) wins (about .04 seconds)
  • for 3 in the top row: 8 (of 720) wins (about .05 seconds)
  • for 4 in the top row: 8 (of 3,628,800) wins (about 30 seconds)
  • for 5 in the top row: ... would finish in about 125 days... if the time were linear in the number of permutations, which I really doubt. At 14.5 minutes, I killed it with no hits yet found.

I'll list code if you ask, but hint: I created three functions (and a main() to drive them): def layout(anArray): # chops up the flat array into an array of arrays in triangle format def display(anArray): # calls layout, then pretty-prints the result def check(anArray) : # calls layout, then from the top calculates the next lower row of diffs and returns False if it doesn't match the actual next lower row. If all rows match, returns True
Sample output:
% psum.py 2
1 3
2

2 3
1

3 1
2

3 2
1

4 of 6

Thanks so much for your help. Python is amazing; itertools worked perfectly. And thanks for the explanation/testing griswolf, it really helped.

I successfully got a working version of the program. It takes around the same time as griswolf's results. Perhaps in the future I will attempt to optimize the code so it can actually calculate problems other than n = 1, 2, 3, or 4. =D

I'll attach my new code.

"""This module contains functions which solve the upside down
triangle problem from Calculus class."""

from itertools import permutations


def brute(toprow):
    """This function solves the upside down triangle problem
    via brute force (inefficient)."""

    print("You entered a puzzle with " + str(toprow) + " spaces on the top row.\n")

    # Find the total number of numbers to be used in the puzzle
    total = toprow
    for i in range(0, toprow):
        total = total + i

    # State how many possibilities there are for the puzzle
    if (toprow > 17):
        print("There are A LOT of possibilities. Hopefully the program doesn't crash...\n")
    elif (toprow > 4):
        print("There are " + "%e" % npr(total) + " possibilities to test.\n")
    else:
        print("There are " + str(npr(total)) + " possibilities to test.\n")

    # Perform the brute force attack
    sols = []
    for j in permutations(range(1, (total + 1))):
        if(test(j, toprow)):
            print("\nSolution #" + str(len(sols) + 1))
            display(j, toprow)
            a = input("Press enter to continue...")
            sols.append(j)

    # Return all the answers!
    print("\n\nThere are " + str(len(sols)) + " solutions to this triangle.")
    return sols


def npr(n):
    """This function determines how many possible arrangements
    of the numbers there are (nPr from Math 12 statistics)."""

    # Do n factorial (there is a math module function but ya)
    for i in range(1, n):
        n = n * i
    return n


def test(arr, toprow):
    """This complimentary function tests the array to see
    if it is a solution."""
    
    # Test if the difference between two tops is equal to
    # their corresponding bottom (directly below the pair)
    step = toprow
    i = -step
    for k in range(0, (toprow - 1)):
        i = i + step
        for j in range(0, (step - 1)):
            if (abs(arr[(i + j + k)] - arr[(i + j + k + 1)]) != arr[(i + j + k + step)]):
                return 0
        step = step - 1
        
    return 1


def display(arr, toprow):
    """This function displays the upside down triangle real
    fancy like (formatted well)."""

    count = 0
    print("")
    for i in range(0, toprow):
        for j in range(0, i):
            print(" ", end = '')
        for k in range(count, (count + toprow)):
            print(str(arr[k]), end=" ")
        print("")
        count = count + toprow
        toprow = toprow - 1
    print("")
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.