Programming

[ByteInBits]

*CORRECTION* TO QUESTION #3

\\ ===================== PROGRAM OUTPUT ======================
\\\     1)      0(1p) 0(2p) 0(5p) 0(10p) 0(20p) 0(50p) 1(100p)
\\      2)      0(1p) 0(2p) 0(5p) 0(10p) 0(20p) 2(50p) 0(100p)
\\      3)      0(1p) 0(2p) 0(5p) 0(10p) 5(20p) 0(50p) 0(100p)
\\      4)      0(1p) 0(2p) 0(5p) 1(10p) 2(20p) 1(50p) 0(100p)
\\      5)      0(1p) 0(2p) 0(5p) 2(10p) 4(20p) 0(50p) 0(100p)
\\      ?)     94(1p) 3(2p) 0(5p) 0(10p) 0(20p) 0(50p) 0(100p)
\\      ?)     95(1p) 0(2p) 1(5p) 0(10p) 0(20p) 0(50p) 0(100p)
\\      ?)     96(1p) 2(2p) 0(5p) 0(10p) 0(20p) 0(50p) 0(100p)
\\      ?)     98(1p) 1(2p) 0(5p) 0(10p) 0(20p) 0(50p) 0(100p)
\\      ?)    100(1p) 0(2p) 0(5p) 0(10p) 0(20p) 0(50p) 0(100p)

\\ The number of possible ways (sets) is: ?

[ByteInBits]

@Astralica, You are very good!
You missed giving how many sets there are 😉

[upsidedown]

In fact, here’s an improvement to my previous answer which runs in linear time and constant space.

def ways(target):
    # ways[amount][coin] = number of ways of making amount using only coins with value <= coin
    coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000]
    length = 1 + max(coins)
    ways = [{c: c == coins[0] for c in coins} for _ in range(2 * length)]
    offset = 0

    for amount in range(target + 1):
        if amount - max(coins) - offset >= length:
            offset += length
            ways[:length] = ways[length:]
            ways[length:] = [{c: c == coins[0] for c in coins} for _ in range(length)]
        for prev, coin in zip(coins, coins[1:]):
            ways[amount - offset][coin] = ways[amount - offset][prev]
            if amount >= coin:
                ways[amount - offset][coin] += ways[amount - coin - offset][coin]
    return ways[target - offset][coins[-1]]

It appears that there are 21114405534221677368358438421551668808393848059500 ways of making change for £99,999.99!

[AspiringPenguin]

Solution to Q2

def get_factors(number):
    factors = []
    for i in range(1, number+1):
        if number % i == 0:
            factors.append(i)
    return factors

primes = []
for i in range(2, 10000):
    if len(get_factors(i)) == 2:
        primes.append(i)

for i in range(1111, 9999):
    #Factors
    if len(get_factors(i)) != 60:
        continue
    #Primes
    for j in range(len(primes) - 42):
        if i == sum(primes[j:j+42]):
            print(i, primes[j:j+42])

Output: 5040 [23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229]

[RickOShea]

I have set one of Babbage’s confounded contraptions to the task and, as yet, it has only provided a partial solution to the problem at hand. Calculations have been performed including the following coins of the realm: crown, half-crown, florin, shilling, sixpence, thre’pence, penny, ha’penny and farthing. Calculations have proceeded accompanied by the sounding of bells at all unholy hours as the device arrived at each partial solution.

For brevity, I have limited the number of ha’pennies and farthings to have a total value of one penny, or less. Other than that, no consideration has been given to what may be considered legal tender. I would suggest consulting with Sir John Herschel, in his role as Master of the Mint, on that matter. The full solution, including all combinations of ha’pennies and farthings has proved, due to the multiplicity of solutions involved, unattainable in an acceptable time and with the limited cranking resource available. However, I provide sample of the output from the device so far. I’d be most willing to build an improved engine specific to the task in hand and provide a full solution for a modest investment on your part.

Unfortunately I am unable to provide details of the engine due to the complexity of its construction.

I remain your humble servant Rick OShea.

1: 4 x 5/- + 0 x 2/6 + 0 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 0 x 1d + 0 x 1/2d + 0 x 1/4d
2: 3 x 5/- + 2 x 2/6 + 0 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 0 x 1d + 0 x 1/2d + 0 x 1/4d
3: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 1 x 6d + 0 x 3d + 0 x 1d + 0 x 1/2d + 0 x 1/4d
4: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 0 x 6d + 2 x 3d + 0 x 1d + 0 x 1/2d + 0 x 1/4d
5: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 0 x 6d + 1 x 3d + 3 x 1d + 0 x 1/2d + 0 x 1/4d
6: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 0 x 6d + 1 x 3d + 2 x 1d + 2 x 1/2d + 0 x 1/4d
7: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 0 x 6d + 1 x 3d + 2 x 1d + 1 x 1/2d + 2 x 1/4d
8: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 0 x 6d + 1 x 3d + 2 x 1d + 0 x 1/2d + 4 x 1/4d
9: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 0 x 6d + 1 x 3d + 1 x 1d + 2 x 1/2d + 4 x 1/4d
10: 3 x 5/- + 1 x 2/6 + 1 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 6 x 1d + 0 x 1/2d + 0 x 1/4d

…

575450: 0 x 5/- + 0 x 2/6 + 0 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 240 x 1d + 0 x 1/2d + 0 x 1/4d
575451: 0 x 5/- + 0 x 2/6 + 0 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 239 x 1d + 2 x 1/2d + 0 x 1/4d
575452: 0 x 5/- + 0 x 2/6 + 0 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 239 x 1d + 1 x 1/2d + 2 x 1/4d
575453: 0 x 5/- + 0 x 2/6 + 0 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 239 x 1d + 0 x 1/2d + 4 x 1/4d
575454: 0 x 5/- + 0 x 2/6 + 0 x 2/- + 0 x 1/- + 0 x 6d + 0 x 3d + 238 x 1d + 2 x 1/2d + 4 x 1/4d

[Astralica]

Since I know Harry will withhold publishing my solutions:

Here is my claim to have solved both questions 2 and 3. @ByteInBits

If you’re struggling with 3, my advice is that it’s easier than you think…

[P.S. Harry, please could you publish my solution to question 1? It looks like it’s over.]

[_madness_]

Here is a programming task that will take some cleverness. The straightforward approach will not be possible.

Background:

One of the challenge ciphers this week involves permutations. A permutation is a reordering of some set. For example, all of the permutations of the digits 1, 2, 3 are
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
Notice that I listed them in a sort of numerical order: 123, 132, 213, 231, 312, 321. There are 3! = 6 of them. If I were to ask you what is the fourth permutation of 1, 2, 3, you should answer “2, 3, 1”. OK, got it?

This part isn’t background anymore; this is the task:

Consider permutations of the alphabet. There are 26! = a big number of them. Arrange them in alphabetical order. Tell me what is the
390304790967593360819076481st permutation of the alphabet? There is a secret message there for you.

Ha ha ha h a ha ha ha a a a aha h ah ah h aha ha ha ha ha h a

[Astralica]

X = 29031

Here’s a python solution; I challenged myself to write it all in one line. (I don’t usually write unreadable code like this.)
print(next(filter(lambda x: all(x % (4, 5, 7, 11, 17)[i] == (3, 1, 2, 2, 12)[i] for i in range(5)), range(5000, 50000))))

I’ll break it down step by step.
First, I generate a list of numbers from 5000-50000 with range(5000, 50000).
Next, we check each number in turn. I check the remainder division of the number with each divisor we care about, and check it against the expected result.
That’s this section: all(x % (4, 5, 7, 11, 17)[i] == (3, 1, 2, 2, 12)[i] for i in range(5)). It uses list comprehension for efficiency.
We filter out each number from the list by using the in-built filter function: filter(lambda x: ...). Lambda simply creates an anonymous function for this purpose.
Finally, we print out the first (and only) number using print(next(...)). It is important to use the next keyword rather than indexing (e.g. list[0]), as we have created a filter object that isn’t subscriptable.

Manually checking the result:
29031 / 4 = 7257r3
29031 / 5 = 5806r1
29031 / 7 = 4147r2
29031 / 11 = 2639r2
29031 / 17 = 1707r12

Naturally, I also decided to write a one-liner for this:
print(list(divmod(29031, v) for v in (4, 5, 7, 11, 17)))

[robb]

@_madness_, nice challenge. Much? Maybe not at all, unless they worked with Father Christmas! And no programming required, I just used PARI for the calculations.

[ByteInBits]

@_madness_ post #98031

They certainly don’t 😉
MD5 = 4EBDCAD9DDA2CA2ED7CD3830ACED90D3

(did not want to give it away)

[ByteInBits]

Oh dear, why do I notice something wrong after posting?
I mistyped a V, for C (the key next to it), within the alphabet.

Here is the new MD5 F09C437C737F2B836B1EC48A5056148E

[upsidedown]

Re @ByteInBits Question #3

Here’s a Python solution, which outputs 4563.
It iterates over target amount, rather than actual sets of coins, so there’s no first/last sets.

target = 100
current = 0
coins = [ 1, 2, 5, 10, 20, 50, 100 ]
# ways[amount][coin] = number of ways of making amount using only coins with value <= coin
ways = [{c: 0 for c in coins} for amount in range(target + 1)]

while current != target:
    current += 1
    ways[current][1] = 1
    for prev, coin in zip(coins, filter(lambda c: c > 1, coins)):
        for count in range((current // coin) + 1):
            ways[current][coin] += max(1, ways[current - count * coin][prev])
print(ways[target][coins[-1]])

[Astralica]

@_madness_

Looks a lot like last year’s Q3 in the Olympiad, without the restriction of having the letter values sum to anything.
I’ve already done that one, so I’ll leave it for the others!

[upsidedown]

Re: #98031

Interesting challenge.

md5("upsidedown" || $answer) = 42e009483103cf28ef15821579a9cdd3

[upsidedown]

My solution to: #98031

The first thing I noticed is that the first symbol is easy to work out. In madness’ example, we have:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

… so the first digit just increases sequentially. The gap between increments of the first digit is always the same, and equals the number of permutations of the remaining digits (n - 1)!.

Let’s normalise permutation symbols to be s ∈ { 0, ..., n - 1 }; and permutation numbers to be p ∈ { 0, ..., n! - 1 }. We can then write an expression for the first symbol as:

first p n = int(p / n!)

Now we know the first symbol, we’re effectively left with the same problem, but with n - 1 symbols from the set { 0, ..., n - 1 } - { the first symbol } and a permutation sequence number p % (n - 1)!. We can therefore just map the symbols into { 0, ..., n - 2 } and reuse the same first function. Python:

def permutation(p, n):
    permutation = []
    symbols = list(range(n))

    while len(permutation) < n:
        f = factorial(n - len(permutation) - 1)
        symbol = symbols[p // f]
        symbols.remove(symbol)
        permutation.append(symbol)
        p %= f

    return permutation

[Author]

Posts