Weekly Challenge 361
Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, GitHub Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.
Task 1: Zeckendorf Representation
Task
You are given a positive integer (<= 100).
Write a script to return Zeckendorf Representation of the given integer. Every positive integer can be uniquely represented as sum of non-consecutive Fibonacci numbers.
My solution
My original solution was to use a recursive function to calculate the numbers. This attempt is recorded in ch-1-recursive.py. However, I realized when looking at larger numbers, this was not required. There is a reason this is the first task and not the second :)
My solution starts with a function called generate_fibonacci which generates a list of Fibonacci numbers that are less than or equal to the target number. This is stored in a list called seq.
def generate_fibonacci(number: int) -> list[int]:
seq = [0, 1]
while seq[-1] <= number:
seq.append(seq[-2] + seq[-1])
return seq[:-1]
I create an a variable called remaining which is set to the input number, and an empty list called result which has the numbers that make up the solution.
Next I have a loop that runs until a solution is found, or it the seq list is empty (which should never happen). For each iteration, I take the last value from the list and assign it to a variable called value. If this is larger than remaining, the loop starts again with no further action.
I subtract value from remaining, and append value to the result list. If remaining is zero, the solution is found, and is returned. If the is still a remainder, I remove another value from the seq list (as we cannot use consecutive numbers), and the loop starts again.
def zeckendorf_representation(number: int) -> list[int] | None:
if number < 1:
raise ValueError("The number must be a positive integer")
seq = generate_fibonacci(number)
remaining = number
result = []
while seq:
value = seq.pop()
if value <= remaining:
remaining -= value
result.append(value)
if remaining == 0:
return result
seq.pop()
return None
Examples
$ ./ch-1.py 4
[3, 1]
$ ./ch-1.py 12
[8, 3, 1]
$ ./ch-1.py 20
[13, 5, 2]
$ ./ch-1.py 96
[89, 5, 2]
$ ./ch-1.py 100
[89, 8, 3]
Bonus
I'm not sure why there is a restriction on numbers less than 100. Even calculating the Zeckendorf Representation of a Googol (10100) takes less than 0.2 seconds.
$ time ./ch-1.py 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
[9216845717656874712980450562726202415567360565980794777111390850331644813674856981646960226192287360, 513637207677450246125760857023446893186481668075116373246321641937144993869266524849692790595738232, 196191955446197556957565929345772792668594307949581132632670453793550007197467505024573547039776939, 46314638123912707463692067318029823029991796402327083329291014906539951751195524576517845992591769, 17690617586682990180447203622188161240682337031027142006892310369574875779255058929007841461590953, 6757214636136263077649543548534660692055214690754342691385916202184675586569652210505678392181090, 1595161992684664972646689501703019021088600608282570556855039728226373625661856805487290962276456, 609297663643530892791951979990217206693894175329255046444641219473596270869815908465388209600595, 232730998245927705729166438267632598993081917705194582478883930194415186947590919908873666525329, 88895331094252224395547334812680590285351577786328700992010571109649289972956851261232789975392, 33954995036828967457475566170409171862972815653791520497147783134532682971279633874824703400847, 1892247019390521442608211077147886839616506438992322504018876947992022613217501281456451614651, 446698926797525733283994464723773897373051547730509482206718754667074636645528022516256487945, 170623807298553611905880623235491323624375649830112453507358412671675285005069415562415412537, 65172495098135102433647404982700073500075401759827878315356483347951218369680224170989749666, 24893677995851695395061591712608896875850555449371181438711037372178370103971256950553836461, 5876600217011727891986851402355662620898026272799849437157779835010586219504163589210317027, 2244661544603472032436332649584708114319787957314032873538930901437280496774780497748874337, 125090700579089545268174422433569433531336921195894847055310250098200676237081739043824861, 6971065820139782390806954219541689244276624212074373456653600330331675492690805039973161, 2662710205480735617346452022100755074809023407208374441801919604845563638678145849451440, 91708675472160090711036102616287632089318911882123915231537729562617689923506638302133, 35029596967131343602213497450232647402139968983372205851566400021802909132390757909314, 745648276861993189984204820755333242001144560869101973859680384188513887852280667477, 9809463517264670023038788649658295091956272699959366635620342487725314342549664567, 3746881652193013001948452031301618270087167924331813432662649918207032018665867029, 1431181439314368982806567444246559718305231073036073662367607266895781713447936520, 546662665750093946471250301438060884828525294776407554440171882480313121677942531, 129049549878268233256883381302815012467835672190109552534355121389997818506160385, 49292541820623609906583302538007088755326533087070104115801862234837985426429697, 7191684930184179482016276395611672639105248126232175323349533708710427892956421, 2746979206949941983182302875628764119171817307595766156998135811615145905740557, 648473825618649048121038413079524682351409714485519861708388359345126257210057, 58472848379039952684853851736901133239741266891456844557261755914039063645794, 22334640661774067356412331900038009953045351020683823507202893507476314037053, 1244666864935793005828156005589143096022236302705537193166716344690085611761, 475420437734698220747368027166749382927701417016557193662268716376935476241, 181594448268301656413948075911105052760867948344134387820089804440720816962, 16374361185569570355515148989381228747223756609038926650176124155306760699, 6254449428820551641549772190170184190608177514674331726439961915653414425, 1476475227036382503281437027911536541406625644706194668152438732346449273, 133133688169362819419341682354326791750874517270785300499298099495818696, 50852543833066829834000968538942350270948615962802847667687312219838755, 19423943329837670082661223262500259061971330617623242503763837163697569, 7419286156446180413982701248558426914965375890066879843604199271253952, 1751455877444438095408940282208383549115781784912085789506677971125378, 157928677948851033162880158208040021697730983590298819190379481318411, 60323387178125067141700354899227346590944200352359771993651057202793, 23041483585524168262220906489642018075101617466780496790573690289968, 8801063578447437644962364569698707634360652047981718378070013667111, 3361707149818144672666187219454104827980338677164658343636350711365, 1284057871006996373036197088663606849580363983512256652839038466984, 490466463202844446442404046536715720760753273372111614880764689587, 44225333398004061429732838340729878012027363723832270745251370289, 16892574194241670428824570378554538679120491007541580961500624834, 6452389184720949856740872794933738025334109298792472139250504213, 137347080577163115432025771710279131845700275212767467264610201, 32423247527351544763402471792982538876233052554697128188128597, 12384578529797304192493293627316781267732493780359086838016392, 690168906931029935139391829792095612517948949963798093315456, 38461794961234640015759308940939757590587318989278841661816, 14691098406862188148944207245954912110548093601382197697835, 5611500259351924431073312796924978741056961814867751431689, 2143402371193585144275731144820024112622791843221056597232, 119447720249892581203851665820676436622934188700177088360, 45624969256769882625644229676772632057353264935332782291, 6656593304481317393598839952151746590023553382130993248, 370959230771131880927453318055001997489772178180790104, 87571595343018854458033386304178158174356588264390370, 33449372971981195681356806732944396691005381570580873, 712011255569818855923257924200496343807632829750245, 271964099255182923543922814194423915162591622175362, 24522987531716273545293036474970821924473060471519, 3577855662560905981638959513147239988861837901112, 199387062373213542599493807777207997205533596336, 76159080909572301618801306271765994056795952743, 6867260041627791953052057353082063289320596021, 619220451666590135228675387863297874269396512, 236521166007575960984144537828161815236311727, 90343046356137747723758225621187571439538669, 21327100234463183349497947550385773274930109, 5034645418285014325766435419644478339818233, 173402521172797813159685037284371942044301, 25299086886458645685589389182743678652930, 9663391306290450775010025392525829059713, 1409869790947669143312035591975596518914, 538522340430300790495419781092981030533, 205697230343233228174223751303346572685, 18547707689471986212190138521399707760, 7084593923980518516849609894969925639, 244006547798191185585064349218729154, 93202207781383214849429075266681969, 35600075545958458963222876581316753, 13598018856492162040239554477268290, 5193981023518027157495786850488117, 1983924214061919432247806074196061, 757791618667731139247631372100066, 178890334785183168257455287891792, 16130531424904581415797907386349, 3807901929474025356630904134051, 555565404224292694404015791808, 131151201344081895336534324866, 659034621587630041982498215, 251728825683549488150424261, 96151855463018422468774568, 14028366653498915298923761, 3311648143516982017180081, 781774079430987230203437, 298611126818977066918552, 70492524767089125814114, 16641027750620563662096, 2427893228399975082453, 573147844013817084101, 12200160415121876738, 1100087778366101931, 259695496911122585, 99194853094755497, 37889062373143906, 14472334024676221, 3416454622906707, 806515533049393, 308061521170129, 117669030460994, 2504730781961, 365435296162, 139583862445, 4807526976, 701408733, 165580141, 63245986, 14930352, 121393, 4181, 987, 233, 55, 3]
real 0m0.017s
user 0m0.011s
sys 0m0.006s
Task 2: Celebrity list
Task
You are given a binary matrix (m × n).
Write a script to find the celebrity, return -1 when none found. A celebrity is someone, everyone knows and knows nobody.
My solution
For input from the command line, I take a JSON string, and convert it to a list of lists of integers (arrays in Perl). The first thing I do is check that the matrix is valid (each row is the same length). Even though the task suggests that m and n could be different values, it makes no sense if it is not square, so I check this as well.
I then have a loop with the index called row_idx and row as the row from the matrix. If this row has any 1 (meaning they know someone), I skip to the next row.
I then check that all other people know this person (column row_idx is 1) or is the person themselves (row_idx == col_idx). If they are, I return the current row_idx value.
If the list is exhausted, I return -1.
def find_celebrity(matrix: list[list[int]]) -> int:
row_length = len(matrix[0])
for row in matrix:
if len(row) != row_length:
raise ValueError("All rows must have the same length")
for row_idx, row in enumerate(matrix):
if sum(row):
continue
is_celebrity = all(
col_idx == row_idx or matrix[col_idx][row_idx]
for col_idx in range(row_length)
)
if is_celebrity:
return row_idx
return -1
Examples
$ ./ch-2.py "[[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0]]"
-1
$ ./ch-2.py "[[0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]"
0
$ ./ch-2.py "[[0, 1, 0, 1, 0, 1], [1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 0]]"
3
$ ./ch-2.py "[[0, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 0], [0, 0, 0, 0]]"
-1
$ ./ch-2.py "[[0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0]]"
-1
$ ./ch-2.py "[[0, 1, 0, 1, 0, 1], [1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 0]]"
3
Top comments (0)