Skip to main content
Code Golf

Return to Answer

deleted 6 characters in body
Source Link
Nick Kennedy
Nick Kennedy
  • 21.2k
  • 3
  • 17
  • 43

Jelly, 216 201199 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢñ4ñ3ñ1Ɗ=¥Ƈñ1‘$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;1aL$,¬ȧ"Tɗʋ/;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

Jelly, 216 201 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;1aL$,¬ȧ"Tɗʋ/;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

Jelly, 216 199 bytes

ñ4ñ3ñ1Ɗ=¥Ƈñ1‘$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;1aL$,¬ȧ"Tɗʋ/;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

deleted 16 characters in body
Source Link
Nick Kennedy
Nick Kennedy
  • 21.2k
  • 3
  • 17
  • 43

Jelly, 216 206201 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;@©;L‘$aL$Ɗ;1aL$,¬ȧ"Tɗɗ¬ȧ"Tɗʋ/2ịḢç4ç3ç1=®ẈḢ¤ƊƇ,¹Ƈ$Ʋ;ç1‘$Ṫ;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;F¥¹¹4ƭ€ɼƲ®0;ç1$>¦;¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿Ɗ$T€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLHƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

Jelly, 216 206 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;@©;L‘$aL$Ɗ,¬ȧ"Tɗɗ/2ịḢç4ç3ç1=®ẈḢ¤ƊƇ,¹Ƈ$Ʋ;ç1‘$Ṫ}Ḣ}¦;F¥¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿Ɗ$T€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

Jelly, 216 201 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;1aL$,¬ȧ"Tɗʋ/;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

deleted 6 characters in body
Source Link
Nick Kennedy
Nick Kennedy
  • 21.2k
  • 3
  • 17
  • 43

Jelly, 216 208206 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
ŒṪ§Ḃ$Ƈṭ+Ø.FJṁ×⁸Z,UN;$¤fɗ¥€$’Uæ.L‘ṪṬȧ€Ɗ€S$ṖŻż"ḊƲ€Z,@F0€$ȯ"\ṫ¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;@©;L‘$aL$Ɗ,¬ȧ"Tɗɗ/2ịḢç4ç3ç1=®ẈḢ¤ƊƇ,¹Ƈ$Ʋ;ç1‘$Ṫ}Ḣ}¦;F¥¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿Ɗ$T€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 5028 seconds total on TIO.

Jelly, 216 208 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
ŒṪ§Ḃ$Ƈṭ+Ø.,UN;$¤fɗ¥€$’Uæ.L‘ṪṬȧ€Ɗ€S,@F0€$ȯ"\ṫ-;@©;L‘$aL$Ɗ,¬ȧ"Tɗɗ/2ịḢç4ç3ç1=®ẈḢ¤ƊƇ,¹Ƈ$Ʋ;ç1‘$Ṫ}Ḣ}¦;F¥¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿Ɗ$T€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 50 seconds total on TIO.

Jelly, 216 206 bytes

ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;@©;L‘$aL$Ɗ,¬ȧ"Tɗɗ/2ịḢç4ç3ç1=®ẈḢ¤ƊƇ,¹Ƈ$Ʋ;ç1‘$Ṫ}Ḣ}¦;F¥¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿Ɗ$T€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

deleted 25 characters in body; added 1 character in body
Source Link
Nick Kennedy
Nick Kennedy
  • 21.2k
  • 3
  • 17
  • 43
added 28 characters in body
Source Link
Nick Kennedy
Nick Kennedy
  • 21.2k
  • 3
  • 17
  • 43
deleted 4 characters in body
Source Link
Nick Kennedy
Nick Kennedy
  • 21.2k
  • 3
  • 17
  • 43
Source Link
Nick Kennedy
Nick Kennedy
  • 21.2k
  • 3
  • 17
  • 43