Programming
The mystery of the silver bullet › Forums › The Intelligence Room › Programming
Tagged: python madness
 This topic has 27 replies, 11 voices, and was last updated 6 days, 11 hours ago by Astralica.

AuthorPosts

26th October 2024 at 7:47 pm #98024ByteInBitsParticipant
*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: ?
26th October 2024 at 9:54 pm #98032ByteInBitsParticipant@Astralica, You are very good!
You missed giving how many sets there are ðŸ˜‰28th October 2024 at 10:03 am #98089upsidedownParticipantIn 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!
28th October 2024 at 10:05 am #98096AspiringPenguinParticipantSolution 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]
30th October 2024 at 11:10 am #98115RickOSheaParticipantI 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, halfcrown, 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/4d30th October 2024 at 11:14 am #98025AstralicaParticipantSince 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.]
30th October 2024 at 11:15 am #98031_madness_ParticipantHere 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
30th October 2024 at 11:15 am #96956AstralicaParticipantX = 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 500050000 withrange(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 inbuilt filter function:filter(lambda x: ...)
. Lambda simply creates an anonymous function for this purpose.
Finally, we print out the first (and only) number usingprint(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 = 1707r12Naturally, I also decided to write a oneliner for this:
print(list(divmod(29031, v) for v in (4, 5, 7, 11, 17)))
30th October 2024 at 4:09 pm #98121robbParticipant@_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.
30th October 2024 at 4:09 pm #98122ByteInBitsParticipant@_madness_ post #98031
They certainly don’t ðŸ˜‰
MD5 = 4EBDCAD9DDA2CA2ED7CD3830ACED90D3(did not want to give it away)
2nd November 2024 at 12:37 pm #98126ByteInBitsParticipantOh 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
2nd November 2024 at 12:37 pm #98027upsidedownParticipantRe @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]])
2nd November 2024 at 12:37 pm #98131AstralicaParticipant@_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!2nd November 2024 at 12:38 pm #98132upsidedownParticipantRe: #98031
Interesting challenge.
md5("upsidedown"  $answer) = 42e009483103cf28ef15821579a9cdd3
2nd November 2024 at 12:38 pm #98133upsidedownParticipantMy 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 bep âˆˆ { 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 numberp % (n  1)!
. We can therefore just map the symbols into{ 0, ..., n  2 }
and reuse the samefirst
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

AuthorPosts
 You must be logged in to reply to this topic.