#!/usr/local/bin/bc -l

### Digits-Happy.BC - Tracking the chain of numbers which leads to happiness

max_array_ = 4^8-1
bijective = 0

# Generalised happy number determination
#  returns 1 if x is happy in the given base
#   when raising digits to the given power
#  The original happy numbers are determined using
#   base ten and squaring of digits, i.e. is_happy(A,2,x)
define is_happy(base,pow,x) {
  auto os,t,i,tape[],tapetop,b;
  os=scale;scale=0
  base/=1;pow/=1;x/=1
  if(base<2)base=ibase
  if(pow <1)pow=2
  if(x<0)x=-x
  if(x==0){scale=os;return 0}
  tapetop=-1;bijective=(b=!!bijective)
  while(1){
    for(t=0;x;x/=base)t+=((x-b)%base+b)^pow
    if(t==1){scale=os;return 1}
    # Search backwards for previous occurrence of t (which is more
    #   likely to be near end of tape since chains lead to loops)
    for(i=tapetop;i>0;i--)if(tape[i]==t){scale=os;return 0}
    if(tapetop++>max_array_){
      print "is_happy: can't calculate happiness; chain too long\n"
      scale=os;return 0
    }
    tape[tapetop]=x=t
  }
}

# Print the chain of iterations of x until a loop or 1
define happy_print(base,pow,x) {
  auto os,t,i,tape[],tapetop,b;
  os=scale;scale=0
  base/=1;pow/=1;x/=1
  if(base<2)base=ibase
  if(pow <1)pow=2
  if(x<0)x=-x
  if(x==0){scale=os;return 0}
  tapetop=-1;bijective=(b=!!bijective)
  while(1){
    for(t=0;x;x/=base)t+=((x-b)%base+b)^pow
    if(t==1){scale=os;return 1}
    # Search backwards for previous occurrence of t (which is more
    #   likely to be near end of tape since chains lead to loops)
    for(i=tapetop;i>0;i--)if(tape[i]==t){scale=os;"looping ";return t}
    if(tapetop++>max_array_){
      print "happy_print: can't calculate happiness; chain too long\n"
      scale=os;return 0
    }
    tape[tapetop]=x=t;t
  }
}

# Return 1 for happy numbers or the smallest number in the loop
# that the iteration becomes trapped within.
define happy_root(base,pow,x) {
  auto os,t,i,tape[],tapetop,b;
  os=scale;scale=0
  base/=1;pow/=1;x/=1
  if(base<2)base=ibase
  if(pow <1)pow=2
  if(x<0)x=-x
  if(x==0){scale=os;return 0}
  tapetop=-1;bijective=(b=!!bijective)
  while(1){
    for(t=0;x;x/=base)t+=((x-b)%base+b)^pow
    if(t==1){scale=os;return 1}
    # Search backwards for previous occurrence of t (which is more
    #   likely to be near end of tape since chains lead to loops)
    for(i=tapetop;i>0;i--)if(tape[i]==t){
      #go back the other way looking for the lowest value
      while(++i<=tapetop)if(tape[i]<t)t=tape[i]
      scale=os;return t
    }
    if(tapetop++>max_array_){
      print "happy_root: can't calculate happiness; chain too long\n"
      scale=os;return 0
    }
    tape[tapetop]=x=t
  }
}

# For unhappy numbers, returns the size of the loop the iterations
# become trapped within. e.g. 4 -> 16 -> ... -> 20 -> 4 is a loop of 8
define happy_loopsize(base,pow,x) {
  auto os,t,i,tape[],tapetop,b;
  os=scale;scale=0
  base/=1;pow/=1;x/=1
  if(base<2)base=ibase
  if(pow <1)pow=2
  if(x<0)x=-x
  if(x==0){scale=os;return 1}
  tapetop=-1;bijective=(b=!!bijective)
  while(1){
    for(t=0;x;x/=base)t+=((x-b)%base+b)^pow
    if(t==1){scale=os;return 0}
    # Search backwards for previous occurrence of t (which is more
    #   likely to be near end of tape since chains lead to loops)
    for(i=tapetop;i>0;i--)if(tape[i]==t){ scale=os;return tapetop-i+1 }
    if(tapetop++>max_array_){
      print "happy_loopsize: can't calculate happiness; chain too long\n"
      scale=os;return 0
    }
    tape[tapetop]=x=t
  }
}

# Find how many iterations are required to reach 1 = happiness
define happy_chainlength(base,pow,x) {
  auto os,t,i,c,tape[],tapetop,b;
  os=scale;scale=0
  base/=1;pow/=1;x/=1
  if(base<2)base=ibase
  if(pow <1)pow=2
  if(x<0)x=-x
  if(x==0){scale=os;return 0}
  tapetop=-1;bijective=(b=!!bijective)
  while(1){
    .=c++
    for(t=0;x;x/=base)t+=((x-b)%base+b)^pow
    if(t==1){scale=os;return c}
    # Search backwards for previous occurrence of t (which is more
    #   likely to be near end of tape since chains lead to loops)
    for(i=tapetop;i>0;i--)if(tape[i]==t){ scale=os;return 2-c }# infinity
    if(tapetop++>max_array_){
      print "happy_chainlength: can't calculate happiness; chain too long\n"
      scale=os;return -c
    }
    tape[tapetop]=x=t
  }
}

# All of the above rolled into one. Negative values suggest error condition.
# Global variables are set with the same names as the above functions
# with the exception of global variable happy_print, which should be
# set to non-zero if emulation of the happy_print() function is required
define is_happy_sg(base,pow,x) {
  auto os,t,i,c,tape[],tapetop,b;
  os=scale;scale=0
  base/=1;pow/=1;x/=1
  if(base<2)base=ibase
  if(pow <1)pow=2
  if(x<0)x=-x
  if(x==0){
    happy_root        = 0
    happy_loopsize    = 1
    happy_chainlength = 0
    scale=os;return 0
  }
  tapetop=-1;bijective=(b=!!bijective)
  while(1){
    .=c++
    for(t=0;x;x/=base)t+=((x-b)%base+b)^pow;if(happy_print)t
    if(t==1){
      happy_root        = 1
      happy_loopsize    = 0
      happy_chainlength = c
      scale=os;return 1
    }
    # Search backwards for previous occurrence of t (which is more
    #   likely to be near end of tape since chains lead to loops)
    for(i=tapetop;i>0;i--)if(tape[i]==t){
      happy_loopsize    = tapetop-i+1
      happy_chainlength = 2-c # Infinite
      #go back the other way looking for the lowest value
      while(++i<=tapetop)if(tape[i]<t)t=tape[i]
      happy_root        = t
      scale=os;return 0
    }
    if(tapetop++>max_array_){
      happy_root        = -1 # Error: Unknown
      happy_loopsize    = -1 # Error: Unknown
      happy_chainlength = -c
      print "is_happy_sg: can't calculate happiness; chain too long\n"
      scale=os;return 0 # not happy
    }
    tape[tapetop]=x=t
  }
}