Tags: misc ppc algorithms
Rating:
# Too Much
Here is the Challenge Description
```
I found a program that generates the flag of this challenge, but the implementation of one of its functions is not available. This function seems simple, but I am confused because of the large number of numbers! Can you help me find the flag before the competition is over?!
```
```python
def func(x):
# Returns the number of distinct pairs (y, z) from the numbers in the file "numbers.txt" whose y != z and (y + z) == x
# Note that two pairs (y, z) and (z, y) are considered the same and are counted only once
def get_flag(res):
flag = []
for i in range(len(res)):
flag.append(chr(func(res[i])))
flag = ''.join(flag)
return flag
if __name__ == "__main__":
res = [751741232, 519127658, 583555720, 3491231752, 3333111256, 481365731, 982100628, 1001121327, 3520999746,
915725624, 3218509573, 3621224627, 3270950626, 3321456817, 3091205444, 999888800, 475855017, 448213157,
3222412857, 820711846, 3710211491, 3119823672, 3333211607, 812955676, 971211391, 3210953872, 289789909,
781213400, 578265122, 910021887, 653886578, 3712776506, 229812345, 582319118, 1111276998, 1151016390,
700123328, 1074521304, 3210438183, 817210125, 501231350, 753244584, 3240911853, 415234677, 469125436,
592610671, 612980665, 291821367, 344199617, 1011100412, 681623864, 897219249, 3132267885, 565913000,
301203203, 3100544737, 432812663, 1012813485, 510928797, 671553831, 3216409218, 3191288433, 698777123,
3512778698, 810476845, 3102989588, 3621432709, 812321695, 526486561, 378912454, 3316207359, 623111580,
344209171, 537454826, 691277475, 2634678623, 1112182335, 792111856, 762989676, 666210267, 871278369,
581009345, 391231132, 921732469, 717217468, 3101412929, 3101217354, 831912337, 532666530, 701012510,
601365919, 492699680, 2843119525]
print("The flag is", get_flag(res))
```
# Solution
No need to check every 2 pairs. here are the required steps for better and faster solution
1. For every `x` read whole numbers, if they are greater than `x` ignore them.
2. Subtract whole numbers from x and keep the results in a new list.
3. Intersect the new list with the old list to see which results are same
4. because we have redundant numbers, Caculate `size of the new list / 2` and thats the answer
```python
def intersection(lst1, lst2):
lst3 = [value for value in lst1 if value in lst2]
return lst3
def func(x):
# Returns the number of distinct pairs (y, z) from the numbers in the file "numbers.txt" whose y != z and (y + z) == x
# Note that two pairs (y, z) and (z, y) are considered the same and are counted only once
numbers = open('numbers.txt', 'r').readlines()
numbers = set(numbers)
results = []
for num in numbers:
num = int(num.rstrip("\n"))
if x < num:
continue
tmp = x - num
results.append(str(tmp)+"\n")
new_list = intersection(results, numbers)
print(f"{len(new_list)//2} : {chr(len(new_list)//2)}")
return(len(new_list)//2)
def get_flag(res):
flag = []
for i in range(len(res)):
flag.append(chr(func(res[i])))
flag = ''.join(flag)
return flag
if __name__ == "__main__":
res = [751741232, 519127658, 583555720, 3491231752, 3333111256, 481365731, 982100628, 1001121327, 3520999746,
915725624, 3218509573, 3621224627, 3270950626, 3321456817, 3091205444, 999888800, 475855017, 448213157,
3222412857, 820711846, 3710211491, 3119823672, 3333211607, 812955676, 971211391, 3210953872, 289789909,
781213400, 578265122, 910021887, 653886578, 3712776506, 229812345, 582319118, 1111276998, 1151016390,
700123328, 1074521304, 3210438183, 817210125, 501231350, 753244584, 3240911853, 415234677, 469125436,
592610671, 612980665, 291821367, 344199617, 1011100412, 681623864, 897219249, 3132267885, 565913000,
301203203, 3100544737, 432812663, 1012813485, 510928797, 671553831, 3216409218, 3191288433, 698777123,
3512778698, 810476845, 3102989588, 3621432709, 812321695, 526486561, 378912454, 3316207359, 623111580,
344209171, 537454826, 691277475, 2634678623, 1112182335, 792111856, 762989676, 666210267, 871278369,
581009345, 391231132, 921732469, 717217468, 3101412929, 3101217354, 831912337, 532666530, 701012510,
601365919, 492699680, 2843119525]
print("The flag is", get_flag(res))
```
And here is the result after less than a minute which is fast enough for this numbers
```
The flag is TMUCTF{r4nd0m_fl46_f0r_fun!_SzC!$JvnbrRh6kc*1@L!4vMueH1k0xKPJem@vh6Y2&Sb2CJzwjnTfU6wVZyePOK3}
```
[solution code](https://github.com/KooroshRZ/CTF-Writeups/blob/main/TMU2021/Misc/TooMuch/solve.py)
> KouroshRZ for **AbyssalCruelty**
