Challenge Accepted!

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

33 Replies - 6069 Views - Last Post: 07 November 2015 - 05:45 PM

#1 astonecipher  Icon User is offline

  • Too busy for this
  • member icon

Reputation: 2340
  • View blog
  • Posts: 9,388
  • Joined: 03-December 12

Challenge Accepted!

Post icon  Posted 13 October 2015 - 01:51 PM

This challenge can be in whatever language you feel comfortable using, however, being as this is the PHP section, it is preferred that you use PHP.

Challenge

Numbers may or may not have holes.

Find the most efficient way to count the number of holes for any given set of numbers.
Examples:
Input Output
90214 = 3 holes
11237 = 0 holes
88001 = 6 holes

For sake of member involvement, I would like member levels Expert and above to wait a few days on posting their code.

When responding to this topic with your code, surround the code tags with the SPOILER tag. It is the same as the code tags

[ spoiler ]
// your code goes here
[ / spoiler ]

It will end up looking like this when done properly:

Spoiler


Is This A Good Question/Topic? 4
  • +

Replies To: Challenge Accepted!

#2 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 456
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Challenge Accepted!

Posted 13 October 2015 - 05:35 PM

I just want to mention that depending on your font - 0 - (zero) can have one or two "holes", and the two-holes version is probably way more widely used among our kin. :P

This post has been edited by Xupicor: 13 October 2015 - 05:36 PM

Was This Post Helpful? 2
  • +
  • -

#3 astonecipher  Icon User is offline

  • Too busy for this
  • member icon

Reputation: 2340
  • View blog
  • Posts: 9,388
  • Joined: 03-December 12

Re: Challenge Accepted!

Posted 13 October 2015 - 06:18 PM

Okay, to remedy that situation when code is posted it should show whether you are expecting 0 to be a single value or double.

I completely forgot that editors like vim show it as two.
Was This Post Helpful? 0
  • +
  • -

#4 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3717
  • View blog
  • Posts: 13,491
  • Joined: 08-August 08

Re: Challenge Accepted!

Posted 14 October 2015 - 05:05 AM

I thought this might be harder in C++ because PHP has associative arrays. After doing it in C++ it occurs to me that PHP might be a little more difficult because you'd need to initialize the number of holes for all ten digits. Maybe I'll do it in PHP later, but below is my C++ version. It's using one hole for zero.
Spoiler

Was This Post Helpful? 1
  • +
  • -

#5 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3717
  • View blog
  • Posts: 13,491
  • Joined: 08-August 08

Re: Challenge Accepted!

Posted 14 October 2015 - 06:06 AM

Doh! I was being stupid. An associative array or map isn't required!
Spoiler

Was This Post Helpful? 0
  • +
  • -

#6 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 456
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Challenge Accepted!

Posted 14 October 2015 - 06:44 AM

Aaaalso, 4 may or may not have a hole, also depending on font. : P (Pedant alert, pedant alert! ...my written 4s never have a hole though.)

So, I was trying to think about something clever, but not there yet. I mean, sure, working solution is trivial, but "interesting" solution is what I seek. : P Notice that "interesting" might not necessarily mean "faster" here, though ideally I'd like both.

Maybe a bit spoilery details follow, so peek at your own peril:
Spoiler

Was This Post Helpful? 0
  • +
  • -

#7 astonecipher  Icon User is offline

  • Too busy for this
  • member icon

Reputation: 2340
  • View blog
  • Posts: 9,388
  • Joined: 03-December 12

Re: Challenge Accepted!

Posted 14 October 2015 - 07:02 AM

I'll throw what I came up with after I get done turning in this rental car. I was hoping for non "badged" members to take a crack, as I didn't think it was too complicated.
Was This Post Helpful? 0
  • +
  • -

#8 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3717
  • View blog
  • Posts: 13,491
  • Joined: 08-August 08

Re: Challenge Accepted!

Posted 14 October 2015 - 07:12 AM

I don't see how you could do it without a lookup or something else that clearly defines the number of holes in a digit. The number of holes depends entirely on the font, so it's possible to design a font where each digit has that number of holes. Zero through nine could look something like this: {*, o, oo, ooo,88,oo8o, 888, o888,8888,o8888}. Granted, it might be harder to read than a sentence written in Zapf Dinbats, but it would work!

View Postastonecipher, on 14 October 2015 - 10:02 AM, said:

I was hoping for non "badged" members to take a crack, as I didn't think it was too complicated.

Well, you had us fooled into thinking there was something we weren't getting.
;)
Was This Post Helpful? 1
  • +
  • -

#9 astonecipher  Icon User is offline

  • Too busy for this
  • member icon

Reputation: 2340
  • View blog
  • Posts: 9,388
  • Joined: 03-December 12

Re: Challenge Accepted!

Posted 14 October 2015 - 09:07 AM

Here is what I came up with,

Spoiler

Was This Post Helpful? 0
  • +
  • -

#10 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 456
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Challenge Accepted!

Posted 14 October 2015 - 09:42 AM

Quote

The number of holes depends entirely on the font, so it's possible to design a font where each digit has that number of holes.

...I was still thinking about arabic numerals though. ; )

Hm, so I can't find any particularly clever solution...

Quote

Well, you had us fooled into thinking there was something we weren't getting.
What? I refuse to believe that!
Posted Image


Sigh.

Performance testing some implementations (just results, very mild spoilers):
Spoiler


The challenge would probably be more of a challenge if we had to constrain ourselves to, say, not using relational (< > <= >=) or equality (== !=) operators, and not using a lookup array.

This post has been edited by Xupicor: 14 October 2015 - 09:46 AM

Was This Post Helpful? 0
  • +
  • -

#11 elsaba68  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 14-November 08

Re: Challenge Accepted!

Posted 14 October 2015 - 10:00 AM

declare
x number;
y number;
n varchar2(6);
res varchar2(6);
counter number:=0;
begin
n:='888458';
x:=1;
y:=length(n);
loop 
select substr(n,x,1) into res  from dual;
x:=x+1;
if res in(0,4,6,9)  then
dbms_output.put_line(res);
counter:=counter+1;
end if;
if res=8 then
dbms_output.put_line(res);
counter:=counter+2;
end if;
exit when x=7;
end loop;
dbms_output.put_line('holes = ' || counter);
end;


Was This Post Helpful? 0
  • +
  • -

#12 Atli  Icon User is offline

  • Enhance Your Calm
  • member icon

Reputation: 4238
  • View blog
  • Posts: 7,216
  • Joined: 08-June 10

Re: Challenge Accepted!

Posted 14 October 2015 - 10:01 AM

Because I can't help but make everything uber re-usable...
Spoiler


I wonder if there is a way to use some sort of OCR technique to count these holes...
Was This Post Helpful? 0
  • +
  • -

#13 astonecipher  Icon User is offline

  • Too busy for this
  • member icon

Reputation: 2340
  • View blog
  • Posts: 9,388
  • Joined: 03-December 12

Re: Challenge Accepted!

Posted 14 October 2015 - 10:05 AM

Atli, I was thinking the same thing! Take a number convert it to an image. Read the image and magically count the holes in the image.
Was This Post Helpful? 0
  • +
  • -

#14 jon.kiparsky  Icon User is offline

  • Chinga la migra
  • member icon


Reputation: 10714
  • View blog
  • Posts: 18,348
  • Joined: 19-March 11

Re: Challenge Accepted!

Posted 14 October 2015 - 10:15 AM

View PostXupicor, on 14 October 2015 - 11:42 AM, said:

...I was still thinking about arabic numerals though. ; )


Well in that case, it looks like Eastern Arabic and Persian-Arabic both have holes in 5 and 9 - one each - and no other digits.
Was This Post Helpful? 1
  • +
  • -

#15 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 456
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Challenge Accepted!

Posted 14 October 2015 - 10:56 AM

...Indo-Arabic then. Good catch though. :P

@Atli - heh, OCR huh? That gives me some ideas.

Well, if each character would be a bitmap, say 1 bit color depth (or more but one particular color to be "traversable background", or even make it a threshold...), then we could just check if there's any pixel on a particular bitmap that can't draw a path to its edges. So one could define "a digit" to be whatever shape in that bitmap and one could always check if it has holes, how many and how big, by, say, flooding stuff. That might actually make a nice tutorial concept approaching A*, breadth/depth-first, etc.

Or, if you define a digit to be a shape consisting of, say, points on a 2d plane and lines between them, one could also check if there are "inaccessible" parts, though I think that might get a tad more complicated. ;)
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3