Challenge "Fastest in the West" ¶
By: admin on June 12, 2018, 1:24 p.m.
Buying a train ticket via credit card should not be a problem — actually. Can you solve the subset-sum problem to get your train?
By: ExAstris on June 13, 2018, 3:04 a.m.
I understand (I think) how to get c from N. After finding c, since n/10=8, we get 8 bits.
What I don't understand is how (which system/method) is the credit card number (CC#) 22****65 encrypted to get c?
I read again about the knapsack problem, which I knew, and the subset-sum problem, which I didn't know, but I still don't see how the CC# is encrypted to yield c.
Any hints on the method ?
Thanks in advance!
By: AnLeRo on June 14, 2018, 8:27 p.m.
I'll try to describe the problem: you are given an array with 80 values and you are looking for the 8 values that sum up to c. Each value is at a certain position in the array and the concatenation of the 8 positions is the credit card number.
I hope this helps,
By: ExAstris on June 21, 2018, 2:07 a.m.
I have not solved it, so don't take my word for it!
N has 80 numbers, you must find 8 numbers out of the 80 that will sum up to c. The concatenation of the positions of these 8 numbers ( I am assuming they are all 2-digit numbers) will provide the 16-digit credit card number (AnReLo explained this). However, I don't know how to find the correct ORDER of these 8 numbers.
Short example (those would be nice in the challenges' PDF):
Suppose n = 4 (the vector/array N contains 4 integers),
N=[1, 2, 4, 8], and c = 7. The only solution is
c = N + N + N = 7. The positions are 00, 01, 02. So a 6-digit card number would be 000102. 010002, or 020001, could be a solution if the order didn't matter.
Hopefully, this is a little clearer.