[ rss / options / help ]
post ]
[ b / iq / g / zoo ] [ e / news / lab ] [ v / nom / pol / eco / emo / 101 / shed ]
[ art / A / beat / boo / com / fat / job / lit / map / mph / poof / £$€¥ / spo / uhu / uni / x / y ] [ * | sfw | o ]
logo
technology

Return ]

Posting mode: Reply
Reply ]
Subject   (reply to 26310)
Message
File  []
close
proofs.png
263102631026310
>> No. 26310 Anonymous
4th February 2018
Sunday 12:29 am
26310 https://www.codewars.com/kata/regular-expression-for-binary-numbers-divisib
Managed to do this challenge. The way the code works is to make a table of equations describing the FSM to match the numbers, and then algebraically reduces it down to a single term. The regexes it produces are longer than they need to be but they work. Simple solution but took a lot of thinking to get there.

Here it is in action for n = 5:

0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 4(0) 4 = 2(0) | 4(1) 0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 4(1*0) 4 = 2(0) 0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 2(01*0) 0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 2(01*0) 0 = 0(0) | 2(1) 1 = 0(1) | 1(10) | 2(01*00) 2 = 1((0|11)) | 2(01*01) 0 = 0(0) | 2((01*01)*1) 1 = 0(1) | 2((01*01)*01*00) 2 = 1((10)*(0|11)) 0 = 0(0) | 1((10)*(0|11)(01*01)*1) 1 = 0(1) | 1((10)*(0|11)(01*01)*01*00) 0 = 0(0) | 1(((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1) 1 = 0(1) 0 = 0((0|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)) regex: ^(0|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)+$


Code here: https://pastebin.com/ys9MeW5T
Expand all images.
>> No. 26311 Anonymous
4th February 2018
Sunday 12:31 am
26311 spacer
Correct link: https://www.codewars.com/kata/regular-expression-for-binary-numbers-divisible-by-n/
>> No. 26312 Anonymous
4th February 2018
Sunday 1:04 am
26312 spacer
>>26310
Oh I love that very much.

Return ]
whiteline

Delete Post []
Password