[🐉 Challenge ] The Code Festival Combinations

Question

Teams of coders are coming to a CODE FESTIVAL:

Each team stays united, of course (unless in some of BONUS 1 solutions)
A big final event is organised : a code battle between 2 guilds.
You have been assigned to build those guilds.
Each team is given a letter, according to the number of coders in it:
"a" is a coder who came alone.
"b" is a team of two
...
"z" is a big team of 26 coders.

"z" will be the max team size allowed.
When the registrations are closed, you receive the list of teams :
a string of letters. Like "adlskeajb" this one would be representing 8 teams, with respectively:
1, 4, 12, 19, 11, 5, 1, 10, 2
coders in each team. You guessed it, the letter position in alphabet gives the number
of coders in the team.

And your TASK is:

To organise the 2 guilds. The conditions : to get the smaller possible difference of size between the 2 guilds. Equal sizes is optimal. If you get two or more solutions, you'll prefer the one with the smallest difference of number of teams for each side. If there still are more than one respecting this condition, they are equivalent. Nothing is organised if only one team. The code has to work for a string of two letters and more.

-- read next Instructions in comments --

Answer 1

Not a one liner but stronger non exponential algo. works for ''venezuelanbeavercheesetartinewithchampagnehoneyandcaviartoastsandcandlesonthetable'
https://code.sololearn.com/c4pCY795CaQn/?ref=app

Answer 2

I've no idea why my name appears in the output but anyway thank you for the awesome challenge @Cpasgrave! 😄

Answer 3

Bookmark

Answer 4

lol. seems you guys have fun here. Very interesting challenge. I have mine in python here although it is not optimized by algo so it cant work out long string...
but it is quite clear and readable. And it prints out all possible combinations...
https://code.sololearn.com/cdQJBxhSn79Y/#py

Answer 5

The output will come this way:
thankstozephyrkoo
-> (123) aehrttyz / hkknooops (124)

🍒BONUS 1:
After the right distribution's chosen, you'll have to split one team to balance the guilds when needed. Show the result before and after the split. And show the modification separately. Final difference has to be 0 or 1.

🍀 BONUS 2 (optimisation):
For each language, you can challenge whoever wrote another code with the same language. The winner will be the challenger who designed a code able to find a right solution (using SL code playground interpreter) with the longest (random-like, not "aaaaaaaa" or so) string input. Share your inputs, and show your best results to challenge the other coders !

🐉 BONUS 3: Hardcore version !
Same situation, but you're asked to build the biggest number of balanced guilds. You must check the distributions, with 2 to n-1 guilds where n is the total number of teams.
Your task is to find the solutions with the smallest ratio :
(biggest guild size - smallest guild size)/(smallest guild size)
And if you have equal ratios for many solutions, you'll prefer the solution with a bigger number of guilds.

TEST CASES :

ab
-> (1) a / b (2)

gg
-> (7) g / g (7)

codefestival
-> (61) acdlsv / eefiot (60)

testcase
-> (46) aett / cess (46)

thankstozephyrkoo
-> (123) aehrttyz/ hkknooops (124)

aaaaaaz
-> (26) z / aaaaaa (6)
>team z splits to: p+j
>(16) p / aaaaaaj (16)

crazy
-> (43) ry / acz (30)
>team y splits to: s+f
>(37) rs / aczf (36)

what
-> (24) aw / ht (28)
>team t splits to: r+b
> (26) awb / hr (26)

venezuelanbeavercheese
-> (111) aabceeesvvz /eeeeehlnnru (112)

Enjoy coding it ! and don't forget to comment your codes :)

Answer 6

one liner
https://code.sololearn.com/crFDxfmivKXA/?ref=app

Answer 7

@VcC

Very impressive !
I'll definitely take some time to walk through your codes slowly till I understand them. Thank you for sharing !
And good choice for this : 'venezuelanbeavercheesetartinewithchampagnehoneyandcaviartoastsandcandlesonthetable'. Is it your max limit ?
Could you explain with little more details the strategy you're using in the second code for more beginner ears ?
And do you have then an idea for the multi-guilds version ?
My version of the code is here :
https://code.sololearn.com/c03CZm4o3YcO/#py
don't hesitate to give your comments about it :

Well done ! And so quick ... It seems like you're writing oneliners at breakfast :)

Answer 8

Haha thanks. Look at the wikipedia link provided for details on the algo. It can do much longer - complexity is O(Sxn) where S=sum=~26/2×n. If max loops is m=1000000 in sololearn you can probably do stg like (m/13)^1/2~277. The exponential algo is O(2^n) so with the same max loop n max~20 (2^20~1000000)

Answer 9

still works (need to relaunch a few times) with 'venezuelanbeavercheesetartinewithchampagnehoneyandcaviartoastsandcandlesonthetableandwhynotalittlebitofabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzeellentesqueinterdumnequeelementummaximusegestasisvolutpatsuscipitlacusegetvolutpatedefficiturexetimperdiettinciduntyoooololotrplololotrololo'
https://code.sololearn.com/c19OcqRv00XS/?ref=app

Answer 10

@VcC
Well, I just made something a little silly, but funny :
I added a pre-sorting code to yours, and I could use it on a 3880 characters string. Because I observed there nearly always is a balanced solution even with relatively short strings, then after a certain level, adding new letters is only creating pairs of similar letters, and you can just separate thos pairs to guild 1 and guild 2 respectively. And then use the algoritghm only on the remaining letters.

https://code.sololearn.com/cVEafX0K7A1f/#py

Do you have an idea for multi-guilds ?

Answer 11

@cpasgrave Bravo. Good proof that picking thr good algorithm>picking the good implementation>picking the good language.

Answer 12

@Zephyr
I placed your name there because I got the idea for this challende when answering yours, the alphabetical balance ! I mean no kind of link between you and venezuelan beavers !

Answer 13

@Lindsay Linjie Chen
We indeed have fun here : ), glad you joined us !
Nice job, it's interesting to see all the possible balances, thanks for that !
There still is some challenge pending ... Well the longest word is already quite advanced, but no solution has been given for multi-guilds solution.